Natural Language Processing · M2 · formulas

Why exhaustive search grows exponentially

HMM & decoding

Formulas explained through full worked examples

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.