# Viterbi assignment Solution¶

## Part One¶

Complete Viterbi Table (including last column):

```
end 0.0000 0.0000 0.0000 0.0000
H 0.0000 0.3200 0.0448 0.0125
C 0.0000 0.0200 0.0480 0.0029
start 1.0000 0.0000 0.0000 0.0000
t= 0 1 2 3
```

The table shows that , since:

```
max { path-prob2(1,2), path-prob2(2,2) } = max { 0.0480 * .4 * .4, 0.0448 * .7 * .4 } = .0125
```

The state visited at on the best path to state 2 (H) at is state 2.

Note

Add a backtrace link (dashed line) to the backtrace figure going from H at time to H at time .

The table shows that = .0029, since:

```
max { path-prob2(1,1), path-prob2(2,1) } = max { 0.0480 * .6 * .1 , 0.0448 * .3 *.1 } = .0029
```

The state visited at on the best path to state 1 (C) at is state 1.

Note

Add a backtrace link (dashed line) to the backtrace figure going from C at time to C at time .

So the best path overall ends at H at (0.125 > .0029), and that was reached on a path that visited H at t=2. Looking at our back trace diagram to complete the best path, we see that the best way to reach H at also goes through H, so we conclude the best path is:

```
start H H H
```

## Part Two¶

Explaining the tables will require referring to them by numerical indices. Rows come first, then columns. Rows correspond to states, columns to input observations. So the state (row) indices are s = 0, t = 1, h =2 , e =3. The observation (column) indices are times of observations, so at t=0 we are observing nothing, at t=1 T, at t=2, H, at t=3 T, and T=4, end. The viterbi value at cell [1,2] is 0.02560; that means the path probability of the best path that reach state 1 (t) at time 2 is 0.02560.

Viterbi Table:

```
s 1.00000 0.00000 0.00000 0.00000 0.00000
t 0.00000 0.32000 0.02560 0.02765 0.00000
h 0.00000 0.06000 0.08640 0.00432 0.00000
e 0.00000 0.00000 0.00000 0.00000 0.00829
T H T end
```

Backtrace Table:

```
s -1 -1 -1 -1 -1
t -1 0 1 2 -1
h -1 0 1 2 -1
e -1 -1 -1 -1 1
T H T end
```

Backtrace table interpretation: A positive value in cell i,t is the index of the next-to-last state on the best path that ends at cell i at time t. For example, the 2 at cell 1,3 [state 1 (= state t), time t=3, ] means the best path arriving at state t at time t=3 went through state 2 (= h) at time t=2. The two 0’s in the t = 1 column mean that the best paths to states 1 and 2 at time t = 1 both went through state 0 (= start state “s”) at t = 0. A negative value in the backtrace table in cell i, t indicates no path at time t-1 could be extended to a path ending in state i at time t with a positive Viterbi value. Since no path can arrive at “s” at any time, the entire top row has negative values. Since there are no paths at time t = -1 to extend, the entire t=0 column has negative values.

We assume the last state visited is e, so we start with a best path that ends:

```
e
```

We construct our best path working backward from there. At time t = 4, state = e (cell [3,4] in the backtrace table), our backtrace value is 1 (=state t). So our best path now ends:

```
t e
```

We continue constructing th ebacktrace backward until we have the complete best path:

```
s t h t e
```

Here are the Viterbi calculations:

```
V1(1) = max(0.80000 * 1.00000 * 0.40000,0.80000 * 0.00000 * 0.40000,0.80000 * 0.00000 * 0.40000,0.80000 * 0.00000 * 0.00000)
V1(1) = max(0.32000,0.00000,0.00000,0.00000)
V1(1) = 0.32
V1(2) = max(0.10000 * 1.00000 * 0.60000,0.10000 * 0.00000 * 0.30000,0.10000 * 0.00000 * 0.50000,0.10000 * 0.00000 * 0.00000)
V1(2) = max(0.06000,0.00000,0.00000,0.00000)
V1(2) = 0.06
V2(1) = max(0.20000 * 0.00000 * 0.40000,0.20000 * 0.32000 * 0.40000,0.20000 * 0.06000 * 0.40000,0.20000 * 0.00000 * 0.00000)
V2(1) = max(0.00000,0.02560,0.00480,0.00000)
V2(1) = 0.0256
V2(2) = max(0.90000 * 0.00000 * 0.60000,0.90000 * 0.32000 * 0.30000,0.90000 * 0.06000 * 0.50000,0.90000 * 0.00000 * 0.00000)
V2(2) = max(0.00000,0.08640,0.02700,0.00000)
V2(2) = 0.0864
V3(1) = max(0.80000 * 0.00000 * 0.40000,0.80000 * 0.02560 * 0.40000,0.80000 * 0.08640 * 0.40000,0.80000 * 0.00000 * 0.00000)
V3(1) = max(0.00000,0.00819,0.02765,0.00000)
V3(1) = 0.027648
V3(2) = max(0.10000 * 0.00000 * 0.60000,0.10000 * 0.02560 * 0.30000,0.10000 * 0.08640 * 0.50000,0.10000 * 0.00000 * 0.00000)
V3(2) = max(0.00000,0.00077,0.00432,0.00000)
V3(2) = 0.00432
V4(3) = max(1.00000 * 0.00000 * 0.00000,1.00000 * 0.02765 * 0.30000,1.00000 * 0.00432 * 0.10000,1.00000 * 0.00000 * 0.00000)
V4(3) = max(0.00000,0.00830,0.00043,0.00000)
V4(3) = 0.008295
```