# Q6b · HMM components and estimates Subject: Natural Language Processing Exam: TEE Reader: https://deep-learning-study-room.vercel.app/nlp/#tee/papers/legacy-r25/q6b Canonical: https://deep-learning-study-room.vercel.app/read/nlp/tee/papers/legacy-r25--q6b/ Previous examination · complete worked answers **Question. Explain HMM components, the number of possible tag sequences and limitations. Construct transition and emission tables for the supplied Alice/Bob/They/The-cat tagged corpus.** [10 marks] ### Answer **A Hidden Markov Model (HMM)** is a probabilistic sequence model in which the underlying state sequence is unobserved, while each state emits an observed item. For POS tagging, words are observed and their grammatical tags are hidden. The task is to infer a suitable tag sequence from the words. Hidden: Noun → Hidden: Verb → Hidden: Noun Observed: birds → Observed: eat → Observed: seeds Horizontal state-to-state links are **transitions**. The relation from each hidden state to its observed word is an **emission**. A transition P(V|N) asks how often a verb tag follows a noun tag. An emission P(eat|V) asks how often the observed word eat appears among verb-tagged tokens. | Component | Notation | Meaning | | --- | --- | --- | | State set | S={N,V,…} | Possible hidden tags. | | Observation vocabulary | O={birds,eat,seeds,…} | Visible word tokens. | | Initial distribution | πⱼ=P(t₁=j) | Probability of starting in tag j. | | Transition matrix | aᵢⱼ=P(tₖ=j|tₖ₋₁=i) | Probability of next tag j after i. | | Emission matrix | bⱼ(w)=P(w|tag j) | Probability that state j emits word w. | Two basic assumptions are used: the current hidden state depends only on the previous hidden state, and the current observation depends only on the current hidden state. A standard first-order HMM therefore does not explicitly condition an emitted word on the whole sentence. $$ P(t_{1:T},w_{1:T})=\pi_{t_1}b_{t_1}(w_1)\prod_{k=2}^{T}a_{t_{k-1},t_k}b_{t_k}(w_k) $$ Read the formula as **start × first emission × transition × emission × transition × emission…**. There are T emission factors and T−1 transitions, plus one initial factor. If the question supplies an explicit end-state probability, multiply that too. Do not invent an end factor when the model has none. **Three different questions.** (1) Scoring a specified tag path uses the joint product above. (2) Finding the probability of the observed words sums scores over all possible tag paths. (3) Finding the best tag path maximizes the path score, typically using Viterbi. A joint path score is not a normalized posterior P(tags|words). **Yaad rakho:** Transition = tag se agla tag. Emission = tag se visible word. 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^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^T $$ Every independent position contributes a factor of three choices. #### Solution ##### Step 1. Write one factor per position $$ M=3\times3\times3\times3 $$ ##### Step 2. Multiply $$ 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^T $$ The length is the exponent, not a multiplier. #### Solution ##### Step 1. Substitute $$ M=2^5 $$ ##### Step 2. Evaluate $$ 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^3 $$ Adding one position multiplies the possibilities by the number of tag choices. #### Solution ##### Step 1. Two words $$ 45^2=2025 $$ ##### Step 2. Three words $$ 45^3=2025\times45=91125 $$ ##### Step 3. Compare $$ 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. ### Exact corpus calculation ### Given | Sentence | Given tags | | --- | --- | | Alice will eat cookies | N M V N | | Bob can drink tea | N M V N | | They will watch movies | Pronoun M V N | | The cat is sleeping | Det N V V | ### To find Emission and transition tables ### Formula: which one and why $$ P(w\mid t)=\frac{c(t,w)}{c(t)} $$ $$ P(t_j\mid t_i)=\frac{c(t_i,t_j)}{\sum_kc(t_i,t_k)} $$ The second formula is the declared no-END convention. Reset at sentence boundaries; never create a transition from the last word of one training sentence to the first of the next. ### Step 1. Count emissions | Tag | Total occurrences | Alice | will | eat | cookies | Bob | can | drink | tea | They | watch | movies | The | cat | is | sleeping | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | N | 6 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | | M | 3 | 0 | 2 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | V | 5 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | | Pronoun | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | | Det | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | ### Step 2. Divide each emission by its tag count | Tag | Alice | will | eat | cookies | Bob | can | drink | tea | They | watch | movies | The | cat | is | sleeping | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | N | 1/6 | 0 | 0 | 1/6 | 1/6 | 0 | 0 | 1/6 | 0 | 0 | 1/6 | 0 | 1/6 | 0 | 0 | | M | 0 | 2/3 | 0 | 0 | 0 | 1/3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | V | 0 | 0 | 1/5 | 0 | 0 | 0 | 1/5 | 0 | 0 | 1/5 | 0 | 0 | 0 | 1/5 | 1/5 | | Pronoun | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | | Det | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | ### Step 3. Count transitions inside each sentence | From | Outgoing transitions | Sentence-final count | N | M | V | Pronoun | Det | | --- | --- | --- | --- | --- | --- | --- | --- | | N | 3 | 3 | 0 | 2 | 1 | 0 | 0 | | M | 3 | 0 | 0 | 0 | 3 | 0 | 0 | | V | 4 | 1 | 3 | 0 | 1 | 0 | 0 | | Pronoun | 1 | 0 | 0 | 1 | 0 | 0 | 0 | | Det | 1 | 0 | 1 | 0 | 0 | 0 | 0 | ### Step 4. Convert to a transition table | From / to | N | M | V | Pronoun | Det | | --- | --- | --- | --- | --- | --- | | N | 0 | 2/3 | 1/3 | 0 | 0 | | M | 0 | 0 | 1 | 0 | 0 | | V | 3/4 | 0 | 1/4 | 0 | 0 | | Pronoun | 0 | 1 | 0 | 0 | 0 | | Det | 1 | 0 | 0 | 0 | 0 | Here sentence-final tags are excluded from the no-END outgoing denominator. If END is explicitly modeled, divide all tag→tag and tag→END counts by the total tag count instead; the row then includes END. Do not mix denominators. ### Final answer The two displayed probability tables are the estimated HMM. Zero means unobserved without smoothing, not logically impossible. For T tokens and K possible tags per token, exhaustive assignments number K^T before constraints; the paper does not supply a single test length for a specific numerical total. HMM assumptions limit long-range context, first-order transitions and emission independence; sparsity and unknown words require smoothing or other handling. The supplied tag is for is and sleeping is V, so both count as V even though finer linguistic tagsets distinguish auxiliaries/participles.