Viterbi decoding

Skill positionModule 2 of 3 · Topic 2 of 4

2.2 Viterbi decoding

—Lab score— / 100Total XP—Streak—

The single most likely story

The forward algorithm adds up all hidden paths to say how likely the data are. Often we want something else: the one best story, the single sequence of states that explains the data with the highest probability. Viterbi decoding finds it. The idea is the forward algorithm with one change: instead of summing over the previous states, take the best one. Keep a score $\delta_t(j)$ , the probability of the best path that ends in state $j$ on day $t$ , and remember which previous state gave it, the back-pointer.

\delta_1(j)=\pi_jB_j(o_1),\qquad \delta_t(j)=\Big[\max_i\delta_{t-1}(i)A_{ij}\Big]B_j(o_t),\qquad \psi_t(j)=\arg\max_i\delta_{t-1}(i)A_{ij}

(1)

After the last day, pick the state with the largest $\delta_T$ and walk back through the pointers $\psi$ to read off the whole path. Two practical points. First, work with logs: products of many probabilities shrink to nearly zero, but logs turn them into sums, and since the log is increasing the best path is the same. Second, the best path is not the same as picking the most likely state on each day separately. The path can be forced by what comes later, as the example shows.

Small, Large, Large againDay 1:

\delta_1=(0.54,\ 0.12)

. Day 2 (large): Calm comes best from Calm,

0.54\cdot0.9\cdot0.1=0.0486

. Stormy comes best from Stormy,

0.12\cdot0.8\cdot0.7=0.0672

, not from Calm (

0.54\cdot0.1\cdot0.7=0.0378

). Day 3: Stormy comes from Stormy,

0.0672\cdot0.8\cdot0.7=0.0376

, and Calm only

0.0044

. The best path is Stormy, Stormy, Stormy with probability

0.0376

. Yet day one alone looked calm with probability

0.82

. The later large moves pull the whole story toward Stormy. This path is

1.78

times more likely than Calm, Stormy, Stormy (

0.0212

Viterbi replaces the sum of the forward algorithm by a maximum and keeps back-pointers.
The best path can differ from the most likely state of each day taken separately.
Use logs: sums of logs avoid underflow and keep the same best path.

Lab · what's graded

A Viterbi score on day two15 pts
The best path's probability15 pts
The log of the best path10 pts
Against another path10 pts
The first state of the best path15 pts
The steps of Viterbi10 pts
Match the vocabulary10 pts
Why use logs15 pts

0/ 8 answered

1Numeric answer15 ptsNot answered

With $\delta_1=(0.54,\ 0.12)$ and a large move on day 2, what is $\delta_2(S)=\max(0.54\cdot0.1,\ 0.12\cdot0.8)\cdot0.7$ ? Give four decimals.

d =

accepted: ± 0.0003

2Numeric answer15 ptsNot answered

With $\delta_2=(0.0486,\ 0.0672)$ and a large move on day 3, what is $\delta_3(S)=\max(0.0486\cdot0.1,\ 0.0672\cdot0.8)\cdot0.7$ , the probability of the best path? Give four decimals.

d =

accepted: ± 0.0003

3Numeric answer10 ptsNot answered

What is the natural log of the best path's probability $0.0376$ ? Give two decimals.

l =

accepted: ± 0.02

4Numeric answer10 ptsNot answered

How many times more likely is the best path (probability $0.0376$ ) than the path Calm, Stormy, Stormy (probability $0.0212$ )? Give two decimals.

r =

accepted: ± 0.02

5Choice15 ptsNot answered

Day one shows a small move, which makes Calm 82% likely on its own. What is the first state of the best path for Small, Large, Large?

6Order the steps10 ptsNot answered

Put the steps of Viterbi decoding in order.

Drag to reorder, or focus an item, press Space to lift it, the arrow keys to move it and Space to drop it.

1After the last day, pick the state with the largest score
2Start with delta equal to start probability times the first emission
3Walk back through the pointers to read the path
4For each day and state, keep the best predecessor and remember it

7Match10 ptsNot answered

Match each term with its meaning.

Pick the partner of each item on the left.

\delta_t(j)

\psi_t(j)

Forward algorithm

Viterbi algorithm

8Explain in words15 ptsNot answered

In one or two sentences, explain why Viterbi decoding is usually written with logs of the probabilities and why that does not change the best path.

Graded on:Products of many probabilities shrink to nearly zero and underflowLogs turn products into sums and the log is increasing, so the best path is the same0 / 400 characters

Math modeKeyboard or LaTeX inputTask 1 of 8 · Ctrl ⏎ to check

Viterbi decoding

Skill positionModule 2 of 3 · Topic 2 of 4

2.2 Viterbi decoding

—Lab score— / 100Total XP—Streak—

The single most likely story

\delta_1(j)=\pi_jB_j(o_1),\qquad \delta_t(j)=\Big[\max_i\delta_{t-1}(i)A_{ij}\Big]B_j(o_t),\qquad \psi_t(j)=\arg\max_i\delta_{t-1}(i)A_{ij}

(1)

Small, Large, Large againDay 1:

\delta_1=(0.54,\ 0.12)

. Day 2 (large): Calm comes best from Calm,

0.54\cdot0.9\cdot0.1=0.0486

. Stormy comes best from Stormy,

0.12\cdot0.8\cdot0.7=0.0672

, not from Calm (

0.54\cdot0.1\cdot0.7=0.0378

). Day 3: Stormy comes from Stormy,

0.0672\cdot0.8\cdot0.7=0.0376

, and Calm only

0.0044

. The best path is Stormy, Stormy, Stormy with probability

0.0376

. Yet day one alone looked calm with probability

0.82

. The later large moves pull the whole story toward Stormy. This path is

1.78

times more likely than Calm, Stormy, Stormy (

0.0212

Viterbi replaces the sum of the forward algorithm by a maximum and keeps back-pointers.
The best path can differ from the most likely state of each day taken separately.
Use logs: sums of logs avoid underflow and keep the same best path.

Lab · what's graded

A Viterbi score on day two15 pts
The best path's probability15 pts
The log of the best path10 pts
Against another path10 pts
The first state of the best path15 pts
The steps of Viterbi10 pts
Match the vocabulary10 pts
Why use logs15 pts

0/ 8 answered

1Numeric answer15 ptsNot answered

With $\delta_1=(0.54,\ 0.12)$ and a large move on day 2, what is $\delta_2(S)=\max(0.54\cdot0.1,\ 0.12\cdot0.8)\cdot0.7$ ? Give four decimals.

d =

accepted: ± 0.0003

2Numeric answer15 ptsNot answered

With $\delta_2=(0.0486,\ 0.0672)$ and a large move on day 3, what is $\delta_3(S)=\max(0.0486\cdot0.1,\ 0.0672\cdot0.8)\cdot0.7$ , the probability of the best path? Give four decimals.

d =

accepted: ± 0.0003

3Numeric answer10 ptsNot answered

What is the natural log of the best path's probability $0.0376$ ? Give two decimals.

l =

accepted: ± 0.02

4Numeric answer10 ptsNot answered

How many times more likely is the best path (probability $0.0376$ ) than the path Calm, Stormy, Stormy (probability $0.0212$ )? Give two decimals.

r =

accepted: ± 0.02

5Choice15 ptsNot answered

Day one shows a small move, which makes Calm 82% likely on its own. What is the first state of the best path for Small, Large, Large?

6Order the steps10 ptsNot answered

Put the steps of Viterbi decoding in order.

Drag to reorder, or focus an item, press Space to lift it, the arrow keys to move it and Space to drop it.

1After the last day, pick the state with the largest score
2Start with delta equal to start probability times the first emission
3Walk back through the pointers to read the path
4For each day and state, keep the best predecessor and remember it

7Match10 ptsNot answered

Match each term with its meaning.

Pick the partner of each item on the left.

\delta_t(j)

\psi_t(j)

Forward algorithm

Viterbi algorithm

8Explain in words15 ptsNot answered

In one or two sentences, explain why Viterbi decoding is usually written with logs of the probabilities and why that does not change the best path.

Graded on:Products of many probabilities shrink to nearly zero and underflowLogs turn products into sums and the log is increasing, so the best path is the same0 / 400 characters

Math modeKeyboard or LaTeX inputTask 1 of 8 · Ctrl ⏎ to check

Viterbi decoding

The single most likely story

Lab · what's graded

Log in to run your code.

Viterbi decoding

The single most likely story

Lab · what's graded

Log in to run your code.