Natural Language Processing · M2 · read

Why exhaustive search grows exponentially

Choosing the most likely tag sequence

Unit 4 page 73: Viterbi motivation, explained with small worked extensions

If each of T observed words can receive any of N tags, there are N choices at each position. Thus the total number of complete tag sequences is N multiplied by itself T times. This counts possible assignments before grammar rules or zero probabilities eliminate any.

\text{Number of tag sequences}=N^TLaTeX: \text{Number of tag sequences}=N^T

Question. A four-word sentence is tagged using three possible POS tags per word. How many complete tag sequences are possible?

Given

N=3 possible tags per position; T=4 word positions.

To find

The number of tag sequences.

Formula and why it applies

M=N^TLaTeX: M=N^T

Every independent position contributes a factor of three choices.

Solution

Step 1. Write one factor per position
M=3\times3\times3\times3LaTeX: M=3\times3\times3\times3
Step 2. Multiply
3\times3=9,\quad9\times3=27,\quad27\times3=81LaTeX: 3\times3=9,\quad9\times3=27,\quad27\times3=81
Final answer. 81 possible tag sequences.

Question. A five-word sentence has two candidate tags per word. Count its tag sequences.

Given

N=2; T=5.

To find

M.

Formula and why it applies

M=N^TLaTeX: M=N^T

The length is the exponent, not a multiplier.

Solution

Step 1. Substitute
M=2^5LaTeX: M=2^5
Step 2. Evaluate
2\times2\times2\times2\times2=32LaTeX: 2\times2\times2\times2\times2=32
Final answer. 32 possible sequences.

Question. Using 45 possible tags, compare the number of tag sequences for sentences of length 2 and 3.

Given

N=45. First T=2, then T=3.

To find

Both counts and the growth factor.

Formula and why it applies

M_2=45^2,\quad M_3=45^3LaTeX: M_2=45^2,\quad M_3=45^3

Adding one position multiplies the possibilities by the number of tag choices.

Solution

Step 1. Two words
45^2=2025LaTeX: 45^2=2025
Step 2. Three words
45^3=2025\times45=91125LaTeX: 45^3=2025\times45=91125
Step 3. Compare
91125/2025=45LaTeX: 91125/2025=45
Final answer. 2 words: 2025 paths. 3 words: 91125 paths. One additional word multiplies the count by 45.

The slides introduce Viterbi to avoid enumerating every path. It reuses the best prefix score for each ending state. For a dense first-order HMM, it needs O(TN²) recurrence work instead of enumerating NT complete paths.

Yaad rakho: Choices per word ki power = sentence length.

M2 10 Viterbi Decoding

id
nlp-m2-10-viterbi-decoding
title
M2 10 Viterbi Decoding
title_confirmed
true
topic_title
Viterbi decoding with backpointers
mode
m2
kind
focused
status
available
duration
9:34
reviewed
false
notebook_url
https://notebook.google.com/notebook/a270ef1e-c285-4d31-9db1-302090c5f8b1
youtube_url
corrected_visuals
false
upload_pending_correction
false
correction_note
related_topic_ids

    These are recorded generation statuses, not a live service check. Private YouTube and signed-in NotebookLM links require the owner's account. This export publishes existing catalog metadata, not private video files or an invented transcript.

    NLP M2 — HMM and Viterbi | Reviewed worked numericals

    id
    overview-hmm-viterbi
    title
    NLP M2 — HMM and Viterbi | Reviewed worked numericals
    title_confirmed
    true
    topic_title
    HMM Prob & Viterbi
    mode
    m2
    kind
    supplemental
    status
    available
    duration
    8:30
    reviewed
    true
    notebook_url
    https://notebook.google.com/notebook/a270ef1e-c285-4d31-9db1-302090c5f8b1
    youtube_url
    https://www.youtube.com/watch?v=RRuSfA_ZMhY
    corrected_visuals
    true
    upload_pending_correction
    false
    correction_note
    Complete HMM factors, all Viterbi candidate scores and backpointers; clarified zero emissions. Full transcript and detected slides checked; short voice corrections included.
    related_topic_ids
    • nlp-m2-08-markov-hmm-components
    • nlp-m2-09-hmm-joint-paths
    • nlp-m2-10-viterbi-decoding

    These are recorded generation statuses, not a live service check. Private YouTube and signed-in NotebookLM links require the owner's account. This export publishes existing catalog metadata, not private video files or an invented transcript.