Natural Language Processing · TEE · papers

Q6b · HMM components and estimates

2025-02-21 · re-exam · recovered AI paper

Previous examination · complete worked answers

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.

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.

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.

LaTeX: 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.

LaTeX: \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

LaTeX: M=N^T

Every independent position contributes a factor of three choices.

Solution

Step 1. Write one factor per position

LaTeX: M=3\times3\times3\times3

Step 2. Multiply

LaTeX: 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

LaTeX: M=N^T

The length is the exponent, not a multiplier.

Solution

Step 1. Substitute

LaTeX: M=2^5

Step 2. Evaluate

LaTeX: 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

LaTeX: 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

LaTeX: 45^2=2025

Step 2. Three words

LaTeX: 45^3=2025\times45=91125

Step 3. Compare

LaTeX: 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 N^T complete paths.

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

Exact corpus calculation

Given

To find

Emission and transition tables

Formula: which one and why

LaTeX: P(w\mid t)=\frac{c(t,w)}{c(t)}

LaTeX: 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

Step 2. Divide each emission by its tag count

Step 3. Count transitions inside each sentence

Step 4. Convert to a transition table

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.