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{align}
\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{align}

For $t=1$ and $t=2$, initialize first timestep like:
$$ \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}) $$