Baum–Welch algorithm

Definition

Consider a hidden Markov model with hidden states $\set{1, \dots, N}$ and observation symbols $\set{1, \dots, M}$. Its parameter $\theta = (\pi, A, B)$ consists of an initial distribution $\pi_i$, a transition matrix $a_{ij}$ and emission probabilities $b_i(k)$. Let $y_1, \dots, y_T$ with $T \ge 2$ be an observed sequence.

For the current $\theta$, the forward and backward variables are $$\alpha_t(i) = P_\theta(Y_1 = y_1, \dots, Y_t = y_t, X_t = i), \qquad \beta_t(i) = P_\theta(Y_{t+1} = y_{t+1}, \dots, Y_T = y_T \mid X_t = i),$$ computed by $\alpha_1(i) = \pi_i b_i(y_1)$, $\alpha_{t+1}(j) = \sum_i \alpha_t(i) a_{ij} b_j(y_{t+1})$, $\beta_T(i) = 1$ and $\beta_t(i) = \sum_j a_{ij} b_j(y_{t+1}) \beta_{t+1}(j)$. With $L = \sum_i \alpha_T(i)$, set $$\gamma_t(i) = \frac{\alpha_t(i) \beta_t(i)}{L}, \qquad \xi_t(i, j) = \frac{\alpha_t(i) a_{ij} b_j(y_{t+1}) \beta_{t+1}(j)}{L}.$$ The Baum–Welch algorithm repeats the following update until the likelihood $L$ stops changing: $$\pi_i \leftarrow \gamma_1(i), \qquad a_{ij} \leftarrow \frac{\sum_{t=1}^{T-1} \xi_t(i, j)}{\sum_{t=1}^{T-1} \gamma_t(i)}, \qquad b_i(k) \leftarrow \frac{\sum_{t \,:\, y_t = k} \gamma_t(i)}{\sum_{t=1}^{T} \gamma_t(i)}.$$