W9.L4. Hidden Markov Model - Viterbi Decoding

| Viterbi Decoding

The most probable assignment to a single latent variable $z_t$, given the whole observed sequence X

특정 시간 t 의 Latent factor 가 특정 k cluster 에 속할 확률

Recursive formation

 

$$
\begin{align*}
P(z_{t}^{k}=1, X) &= \alpha_{t}^{k} \cdot \beta_{t}^{k} \\
&= (b_{k, x_t} \cdot \sum_{i} \alpha_{t-1}^{i} \cdot a_{i, k}) \cdot (\sum_{i} \alpha_{k, i} \cdot b_{i, x_{t}} \cdot \beta_{t+1}^{i})
\end{align*}
$$

 

모든 X 가 Given 인 상황에서

특정 Assignment 확률을 Maximization 하는 형태로 Assign 해보자!

확률을 최대화 하는 $k$ 가 $k^{*}$!

 

$$k_{t}^{*} = argmax_k\ P(z_{t}^{k}=1 \mid X) = argmax_k\ P(z_{t}^{k}=1, X) = argmax_k \ \alpha_{t}^{k} \cdot \beta_{t}^{k}$$

 

 

이제 Single Latent $z_{t}^{k}$ 가 아닌 Whole sequence $Z$ 를 계산해보자!

 

The most probable sequence of latent states until $t-1$ and fixing the state $k$ at time $t$

 

$$
\begin{align*}
V_{t}^{k}&=max_{z_1, ..., z_{t-1}}P(x_1, ..., x_{t-1}, z_1, ..., z_{t-1}, x_t, z_{t}^{k}=1) \\
&= max_{z_1, ..., z_{t-1}}P(x_t, z_{t}^{k}=1 \mid x_1, ..., x_{t-1}, z_1, ..., z_{t-1}) \cdot P(x_1, ..., x_{t-1}, z_1, ..., z_{t-1}) \\
&= max_{z_1, ..., z_{t-1}} P(x_t, z_{t}^{k}=1 \mid z_{t-1}) \cdot P(x_1, ..., x_{t-2}, z_1, ..., z_{t-2}, x_{t-1}, z_{t-1}) \\
&= max_{z_{t-1}}P(x_t, z_{t}^{k}=1 \mid z_{t-1}) \cdot max_{z_1, ..., z_{t-2}} P(x_1, ..., x_{t-2}, z_1, ..., z_{t-2}, x_{t-1}, z_{t-1}) \\
&= max_{i\in z_{t-1}}P(x_t, z_{t}^{k}=1 \mid z_{t-1}^{i}=1) \cdot V_{t-1}^{i} \\
&= max_{i\in z_{t-1}}P(x_t \mid z_{t}^{k}=1) \cdot P(z_{t}^{k}=1 \mid z_{t-1}^{i}=1) \cdot V_{t-1}^{i} \\
&= P(x_t \mid z_{t}^{k}=1) \cdot max_{i\in z_{t-1}} P(z_{t}^{k}=1 \mid z_{t-1}^{i}=1) \cdot V_{t-1}^{i} \\
&= b_{k, idx(x_t)} \cdot max_{i \in z_{t-1}} a_{i, k} \cdot V_{t-1}^{i} \\
\end{align*}
$$

 

Recursive formation ... Solve using DP ...

 

 

| Viterbi Decoding Algorithm

Need to know $V_{t}^{k}$

 

Initialize

$V_{1}^{k} = b_{k, x_1} \cdot \pi_{k}$

 

Iterate until time T

$V_{t}^{k} = b_{k, idx(x_t)} \cdot max_{i \in z_{t-1}} a_{i, k} \cdot V_{t-1}^{i}$
$trace_{t}^{k} = argmax_{i \in z_{t-1}} a_{i, k} \cdot V_{t-1}^{i}$

 

Return
$P(X, Z^{*}) = max_{k} V_{T}^{k}$
$z_{T}^{*} = argmax_{k} \ V_{T}^{k}$
$z_{t-1}^{*} = trace_{t}^{z_{t}^{*}}$

 

Very frequent underflow problems ... → Log calculation

 

 

 

 

 

Reference
문일철 교수님 강의 
https://www.youtube.com/watch?v=mnUcZbT5E28&list=PLbhbGI_ppZISMV4tAWHlytBqNq1-lb8bz&index=60