Natural Language Processing · TEE · about

Forward HMM: sum paths and normalize posteriors

Optional extensions — after the TEE questions

Additional explanation; no corresponding question in the two supplied TEE papers. No exam marks are implied.

Optional extension. Forward totals and tag-path posteriors are optional HMM extensions here. Both supplied TEE papers ask emission and transition matrices, then the joint probability of a given tag sequence. Complete the actual solved papers first.

The forward algorithm finds the total probability of observations when the hidden path is unknown. Its cell αₜ(j) is the joint probability of the observed prefix o₁…oₜ and ending in hidden state j, summed over every earlier hidden path. It stores two totals per time step in the two-state example; it does not choose one winning predecessor.

LaTeX: \alpha_1(j)=\pi_jb_j(o_1)

LaTeX: \alpha_t(j)=b_j(o_t)\sum_i\alpha_{t-1}(i)a_{ij}

LaTeX: P(O)=\sum_j\alpha_T(j).

πⱼ is the first-state probability; aᵢⱼ is transition i→j; bⱼ(oₜ) is the probability that state j emits the current observation. Multiply each earlier total by its transition, add all incoming alternatives, then multiply by the current emission. With explicit END transitions, terminate using Σⱼ αT(j)aⱼ,END instead. Do not invent END factors in a fixed-length model that has none.

Question. Use the HMM tables below to compute P(1,3,1) with the forward algorithm. Compare with the Viterbi path H,H,C whose joint score is 0.00672, then obtain that path’s posterior. [Authored worked example]

Answer

Given

Use H,C state order and the tables shown. Three observations are 1,3,1. There is no END state.

Quantity	H	C
Initial π	0.8	0.2
From H → next state	0.7	0.3
From C → next state	0.4	0.6

State	Emit 1	Emit 2	Emit 3
H	0.2	0.4	0.4
C	0.5	0.4	0.1

To find

Every forward cell, total observation probability, and P(H,H,C | 1,3,1).

Formula and why it applies

LaTeX: \alpha_t(j)=b_j(o_t)\sum_i\alpha_{t-1}(i)a_{ij}

All hidden paths are mutually exclusive alternatives, so their scores must be added. Viterbi’s maximum answers a different question.

Solution

Step 1. Initialize observation 1

LaTeX: \alpha_1(H)=0.8(0.2)=0.16,\qquad\alpha_1(C)=0.2(0.5)=0.10.

Step 2. Sum incoming paths to H at observation 3

LaTeX: \alpha_2(H)=[0.16(0.7)+0.10(0.4)](0.4)

LaTeX: =[0.112+0.040](0.4)=0.0608.

Step 3. Sum incoming paths to C at observation 3

LaTeX: \alpha_2(C)=[0.16(0.3)+0.10(0.6)](0.1)

LaTeX: =[0.048+0.060](0.1)=0.0108.

Step 4. Calculate final H at observation 1

LaTeX: \alpha_3(H)=[0.0608(0.7)+0.0108(0.4)](0.2)

LaTeX: =[0.04256+0.00432](0.2)=0.009376.

Step 5. Calculate final C at observation 1

LaTeX: \alpha_3(C)=[0.0608(0.3)+0.0108(0.6)](0.5)

LaTeX: =[0.01824+0.00648](0.5)=0.01236.

Step 6. Add the final-state alternatives

LaTeX: P(1,3,1)=0.009376+0.01236=0.021736.

Step 7. Read the table as a trace

State / time	1: observe 1	2: observe 3	3: observe 1
H	0.16	0.0608	0.009376
C	0.10	0.0108	0.01236
Column total	0.26	0.0716	0.021736

For each new cell, draw arrows from both cells in the previous column. Along each arrow multiply by its transition; add the two contributions and multiply by the destination’s emission.

Step 8. Normalize the specified best path

LaTeX: P(H,H,C\mid1,3,1)=\frac{0.00672}{0.021736}=\frac{840}{2717}\approx0.309164.

The best single path has only part of the total mass. The remaining paths account for the rest.

Final answer. P(observations)=0.021736. Viterbi selects H,H,C with joint score 0.00672; its posterior is about 0.309164, not 0.00672.

Question. With the same explicitly listed HMM, find the probability of observations 3,1 by forward calculation and by enumerating all four hidden paths. [Authored worked example]

Answer

Given

π=(0.8,0.2); transition rows H=(0.7,0.3), C=(0.4,0.6); emissions H=(0.2,0.4,0.4), C=(0.5,0.4,0.1) for labels 1,2,3; no END factor.

To find

P(3,1), and an independent path-sum check.

Formula and why it applies

Forward reuses prefix totals. Exhaustive enumeration is practical for this two-position example and must give the same total.

Solution

Step 1. Initialize observation 3

LaTeX: \alpha_1(H)=0.8(0.4)=0.32,\quad\alpha_1(C)=0.2(0.1)=0.02.

Step 2. Calculate the second H cell

LaTeX: \alpha_2(H)=[0.32(0.7)+0.02(0.4)](0.2)=0.0464.

Step 3. Calculate the second C cell

LaTeX: \alpha_2(C)=[0.32(0.3)+0.02(0.6)](0.5)=0.054.

Step 4. Sum final cells

LaTeX: P(3,1)=0.0464+0.054=0.1004.

Step 5. Enumerate each complete path

Path	Full multiplication	Joint score
HH	0.8 × 0.4 × 0.7 × 0.2	0.0448
HC	0.8 × 0.4 × 0.3 × 0.5	0.048
CH	0.2 × 0.1 × 0.4 × 0.2	0.0016
CC	0.2 × 0.1 × 0.6 × 0.5	0.006

LaTeX: 0.0448+0.048+0.0016+0.006=0.1004.

Final answer. Both methods give 0.1004. The largest single-path score is 0.048, which is smaller than the sum.

For K states and T observations, both dense forward and Viterbi recurrences take O(TK²) work. Forward needs only the preceding column for the probability total. Viterbi also stores backpointers to recover the path. Very long sequences need scaling or log-sum-exp for forward; ordinary logarithms alone do not turn a sum into a maximum.

Yaad rakho: Viterbi = best raasta. Forward = saare raaston ka total. This is a supporting HMM extension, not an assertion that a separate forward-algorithm question appeared in the supplied papers.

This worked lesson was added after the video plan. No matching video has been generated or reviewed.