DSP HW3

Author: B04705003 林子雋

Notation

In the following section,

$W$ denotes a random variable of a word, while

$q$ denotes a state.
Moverover,

$W_{1:t}$ means a tuple of

$(W_1,...,W_t)$. If you have ever write python or matlab, you would be familar to this notation.
For example,

$W_1$ denotes the first word and

$W_1=q_1$ means the first word is

$q_1$ this word(ex.

$q_1=\text{speech}$,

$q_2=\text{hello}$…)

Bigram Derivation of Viterbi

To derive bigram part of Viterbi algorithm, define:

$${\delta }_t(q_i)=\underset{W_{1:t-1}}{max}P(W_1,...,W_{t-1},W_t=q_i)$$
where:

$${\delta }_t(q_i)=\underset{W_{1:t-1}}{max}P(q_i|W_{t-1})P(W_{1:t-1})=\underset{q_j}{max}P(q_i|q_j){\delta }_{t-1}(q_j)$$

For

$t=1$, initialize first timestep like:

$${\delta }_1(q_i)=P(W_1=q_i)$$

Trigram Derivation of Viterbi

To derive trigram, define:

$${\delta }_t(q_i,q_j)=\underset{W_{1:t-2}}{max}P(W_1,...,W_{t-1}=q_j,W_t=q_i)$$

Then, by same method, we can get:

$$\begin{array}{rl}{\delta }_t(q_i,q_j)& =\underset{W_{1:t-2}}{max}P(q_i|q_j,W_{t-2})P(W_1,...,W_{t-2},W_{t-1}=q_j)\text{ (by conditional probability decomposition)}\\ & =\underset{q_k}{max}\underset{W_{1:t-3}}{max}P(q_i|q_j,q_k)P(W_1,...,W_{t-3},W_{t-2}=q_k,W_{t-1}=q_j)\text{ (maximize one variable first)}\\ & =\underset{q_k}{max}P(q_i|q_j,q_k)\underset{W_{1:t-3}}{max}P(W_1,...,W_{t-3},W_{t-2}=q_k,W_{t-1}=q_j)\text{ (take the independent term out)}\\ & =\underset{q_k}{max}P(q_i|q_j,q_k){\delta }_{t-1}(q_j,q_k)\end{array}$$

For

$t=1$ and

$t=2$, initialize first timestep like:

$$\begin{gathered} {\delta }_1(q_i,q_j)=P(W_1=q_i) \\ {\delta }_2(q_i,q_j)=\underset{q_k}{max}P(q_i|q_j){\delta }_1(q_j,q_k) \end{gathered}$$