Marginalized Probabilities and Counts of HMM

Forward Algorithm,Backward AlgorithmのDP変数,\(f_i(t), b_i(t)\)を用いて,周辺確率や周辺化カウントを計算できる.

States and Outputs

出力列が \(x_{1…T}=x_1\ldots x_T\)であるとき,時刻 \(t\) の状態が \(s_i\) である確率は,
\[
\begin{eqnarray}
P(h_t=s_i|x_{1…T}) &=& \frac{P(x_{1…T},h_t=s_i)}{P(x_{1…T})}\\
&=& \frac{P(x_{1…t},h_t=s_i)P(x_{t+1…T}|h_t=s_i)}{P(x_{1…T})}\\
&=& \frac{f_i(t)b_i(t)}{\sum_j f_j(T)}.
\end{eqnarray}
\tag{hmm.M.1}\label{eq:hmm_state_prob_esitimate}
\]

このとき,状態が \(s_i\) が記号 \(c\) を出力した回数の期待値 \(\hat{E_i(c)}\) は,上の確率を \(x_t=c\) である \(t\) についてだけ和をとれば求まる.
\[
\begin{eqnarray}
\hat{E_i(c)} &=& E[s_i \mbox{ emits } c |x_{1…T}]\\
&=& \sum_{t|x_t=c} P(h_t=s_i|x_{1…T})\\
&=& \frac{\sum_{t|x_t=c}f_i(t)b_i(t)}{\sum_j f_j(T)}.
\end{eqnarray}
\tag{hmm.M.2}\label{eq:hmm_emission_count_esitimate}
\]

Transitions

出力列が \(x_{1…T}=x_1\ldots x_T\)であるとき,時刻 \(t\) から時刻 \(t+1\) で状態 \(s_i\) から状態 \(s_j\) に遷移した確率は,
\[
\begin{eqnarray}
P(h_t=s_i,h_{t+1}=s_j|x_{1…T}) &=& \frac{P(x_{1…T},h_t=s_i,h_{t+1}=s_j)}{P(x_{1…T})}\\
&=& \frac{P(x_{1…t},h_t=s_i)P(x_{t+1…T},h_{t+1}=s_j|h_t=s_i)}{P(x_{1…T})}\\
&=& \frac{f_i(t)a_{i,j}e_j(x_{t+1})b_j(t+1)}{\sum_j f_j(T)}.
\end{eqnarray}
\tag{hmm.M.3}\label{eq:hmm_transition_prob_esitimate}
\]
このとき,状態 \(s_i\) から状態 \(s_j\) に遷移した回数の期待値 \(\hat{A_{i,j}}\) は,上の確率を以下のように \(t\) について合計すれば求まる.
\[
\begin{eqnarray}
\hat{A_{i,j}} &=& E[s_i \rightarrow s_j|x_{1…T}]\\
&=& \sum_{t=1}^{T-1} P(h_t=s_i,h_{t+1}=s_j|x_{1…T})\\
&=& \frac{\sum_{t=1}^{T-1} f_i(t)a_{i,j}e_j(x_{t+1})b_j(t+1)}{\sum_j f_j(T)}.
\end{eqnarray}
\tag{hmm.M.4}\label{eq:hmm_transition_count_esitimate}
\]