Given an stochastic model \( P(v,h|\theta) \), where \( v \) is ‘Visible’ data, \( h \) is ‘Hidden’ data, \( \theta \) is parameter(s).

General EM algorithm consists of two steps, E (expectation) step and M (Maximization) step.

E step: Calculate the following ‘Q function’
\[ Q(\theta|\theta^{(t)})
= E_{\theta^{(t)}}[\log P(v,h|\theta)]
= \sum_t P(h|v, \theta^{(t)}) \log P(v,h|\theta) \]

M step: Calculate new parameter(s) \( \theta^{(t+1)} \) that maximize the ‘Q function’
\[ \theta^{(t+1)} = argmax_{\theta} Q(\theta|\theta^{(t)}) \]

On an HMM, the joint probability of the output sequence (‘Visible’ data) \( x \) and the hidden state sequence (‘Hidden’ data) \( \pi \) is written as
\[ P(x, \pi | \theta ) = a_{0,\pi_1} \prod_{i} e_{\pi_i}(x_i) a_{\pi_i, \pi_{i+1}}
=\prod_k \prod_{\ell} (a_{k\ell}^{A_{k\ell}(\pi)})
\prod_k \prod_b (e_k(b)^{E_k(b,\pi)})
\]
using ‘real’ parameters \( \theta = (\{a_{k\ell}\}, \{e_k(b)\}) \) and the ‘real counts’ on the ‘real state transitions’ \( \pi \) of emissions \( E_k(b,\pi) \) and that of transitions \( A_{k\ell}(\pi) \).

E step of HMM

The Q function of the HMM is calculated as
\[ \begin{align}
Q(\theta|\theta^{(t)}) &= \sum_\pi P(\pi|x, \theta^{(t)})
\left(
\sum_k \sum_{\ell} A_{k\ell}(\pi) \log{a_{k\ell}}
+\sum_k \sum_b E_k(b,\pi) \log{e_k(b)}
\right) \\
&= \sum_k \sum_{\ell} A_{k\ell} \log{a_{k\ell}}
+ \sum_k \sum_b E_k(b) \log{e_k(b)}
\end{align} \]

by using the values obtained from forward-backward algorithm,
\[
A_{k\ell}^{(t)} = E_{\theta^{(t)}}[A_{k\ell}(\pi)]
= \sum_\pi P(\pi|x,\theta^{(t)}) A_{k\ell}(\pi) \\
E_k(b)^{(t)} = E_{\theta^{(t)}}[E_k(b,\pi)]
= \sum_\pi P(\pi|x,\theta^{(t)}) E_k(b,\pi)
\]

M step of HMM

Under the constraint \( \sum_\ell a_{k\ell} = 1 \) and \( \sum_b e_k(b) = 1 \), \( Q(\theta|\theta^{(t)}) \) is maximized by setting
\[
\theta^{(t+1)} = (\{a_{k\ell}\}^{(t+1)}, \{e_k(b)\}^{(t+1)})
= ( \{ \frac{A_{k\ell}^{(t)}}{\sum_j A_{kj}^{(t)}} \},
\{ \frac{e_k(b)^{(t)}}{\sum_a e_k(a)^{(t)}} \} )
\]