# Forward HMM: sum paths and normalize posteriors

Subject: Natural Language Processing

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/nlp/#tee/about/optional-extensions/forward-probability

Canonical: https://deep-learning-study-room.vercel.app/read/nlp/tee/about/optional-extensions--forward-probability/

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.



$$
\alpha_1(j)=\pi_jb_j(o_1)
$$





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





$$
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 | Operation | Output |
| --- | --- | --- |
| Given one hidden path and the words | Multiply its start, transitions and emissions | P(path, observations) |
| Find the best hidden path | Viterbi: maximum, with backpointers | Best path and its joint score |
| Find observation probability | Forward: sum incoming paths | P(observations) |
| Find a specified path posterior | Divide its joint score by P(observations) | P(path | observations) |

**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



$$
\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



$$
\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



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





$$
=[0.112+0.040](0.4)=0.0608.
$$



##### Step 3. Sum incoming paths to C at observation 3



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





$$
=[0.048+0.060](0.1)=0.0108.
$$



##### Step 4. Calculate final H at observation 1



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





$$
=[0.04256+0.00432](0.2)=0.009376.
$$



##### Step 5. Calculate final C at observation 1



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





$$
=[0.01824+0.00648](0.5)=0.01236.
$$



##### Step 6. Add the final-state alternatives



$$
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



$$
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



$$
\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



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



##### Step 3. Calculate the second C cell



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



##### Step 4. Sum final cells



$$
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 |



$$
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.