Tutorials › Stochastic Processes › One Complete Baum-Welch Iteration by Hand

Home  /  Tutorials  /  Hidden Markov Models

Hidden Markov Models · Tutorial 953 of 994

One Complete Baum-Welch Iteration by Hand

Follow one categorical HMM sequence from the E-step through the M-step, with exact posterior calculations and checks on every updated parameter matrix.

Advanced 12 min read

What You'll Learn

  • Set up a categorical hidden Markov model and check its probability matrices.
  • Compute forward and backward quantities for a short observation sequence.
  • Convert smoothed state and transition probabilities into expected counts.
  • Update initial, transition, and emission probabilities from those counts.
  • Check count marginals and identify when a parameter row cannot be updated.
  • Avoid confusing posterior transition probabilities with updated transition probabilities.

From Posterior Probabilities to Updated Parameters

Baum-Welch training alternates between inferring hidden states under the current model and updating the model using those inferences. One complete iteration is therefore a concrete sequence of calculations: evaluate the current model, find posterior probabilities for hidden states and transitions, add those probabilities as fractional counts, and normalize the counts to obtain new parameters. The counts need not be integers; they are expectations over the possible hidden paths.

Consider a hidden Markov model on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Its hidden process \((X_t)_{t\ge1}\) is a discrete-time Markov chain with finite state space \(S=\{1,\ldots,K\}\), initial distribution \(\pi\) as a row vector, and transition matrix \(A=(a_{ij})\), where \(a_{ij}=\mathbb{P}(X_{t+1}=j\mid X_t=i)\). The observed process \((Y_t)_{t\ge1}\) takes values in a finite alphabet \(\mathcal{Y}\). Given the hidden states, observations are conditionally independent, and \(\mathbb{P}(Y_t=y\mid X_t=i)=b_i(y)\). Write \(B=(b_i(y))\) for the emission probabilities. Each row of \(A\) and each row of \(B\) sums to \(1\). We observe one sequence \(y_{1:T}=(y_1,\ldots,y_T)\) with positive probability under the current parameters.

Definition: The E-step calculates posterior state probabilities \(\gamma_t(i)=\mathbb{P}(X_t=i\mid Y_{1:T}=y_{1:T})\) and posterior transition probabilities \(\xi_t(i,j)=\mathbb{P}(X_t=i,X_{t+1}=j\mid Y_{1:T}=y_{1:T})\). Their sums give expected state and transition counts. The M-step chooses initial, transition, and emission probabilities that maximize the expected complete-data log likelihood formed from those counts.

These conditional probabilities are well-defined because the observed sequence has positive probability. For computing them, define the forward quantity \(\alpha_t(i)=\mathbb{P}(Y_{1:t}=y_{1:t},X_t=i)\) and the backward quantity \(\beta_t(i)=\mathbb{P}(Y_{t+1:T}=y_{t+1:T}\mid X_t=i)\). The backward quantity at \(t=T\) is \(1\): there are no later observations to account for. The observation sequence likelihood is \(L=\sum_i\alpha_T(i)\).

The forward and backward recursions, and the posterior formulas used in the E-step, are:

$$ \begin{aligned} \alpha_1(i)&=\pi_i b_i(y_1),& \alpha_{t+1}(j)&=b_j(y_{t+1})\sum_i\alpha_t(i)a_{ij},\\ \beta_T(i)&=1,& \beta_t(i)&=\sum_j a_{ij}b_j(y_{t+1})\beta_{t+1}(j),\\ \gamma_t(i)&=\frac{\alpha_t(i)\beta_t(i)}{L},& \xi_t(i,j)&=\frac{\alpha_t(i)a_{ij}b_j(y_{t+1})\beta_{t+1}(j)}{L}. \end{aligned} $$

Why the posterior formulas work. The probability of the observed prefix and \(X_t=i\), multiplied by the conditional probability of all later observations given \(X_t=i\), is \(\alpha_t(i)\beta_t(i)\). Summing this product over \(i\) gives the probability \(L\) of the full observation sequence, so division by \(L\) gives \(\gamma_t(i)\). For a transition from \(i\) to \(j\), the corresponding joint probability is the prefix probability \(\alpha_t(i)\), times the transition probability \(a_{ij}\), times the probability \(b_j(y_{t+1})\) of the next observation, times the remaining likelihood \(\beta_{t+1}(j)\). Division by \(L\) gives \(\xi_t(i,j)\). These decompositions follow from the Markov property and the conditional independence of observations given the hidden states.

Result (count identities): For \(t<T\), \(\sum_j\xi_t(i,j)=\gamma_t(i)\) and \(\sum_i\xi_t(i,j)=\gamma_{t+1}(j)\). Thus the expected number of transitions out of state \(i\) is \(\sum_{t=1}^{T-1}\gamma_t(i)\), and the expected number of transitions from \(i\) to \(j\) is \(\sum_{t=1}^{T-1}\xi_t(i,j)\).

Proof. Summing the numerator defining \(\xi_t(i,j)\) over \(j\) gives \(\alpha_t(i)\sum_j a_{ij}b_j(y_{t+1})\beta_{t+1}(j)=\alpha_t(i)\beta_t(i)\), by the backward recursion. Dividing by \(L\) gives \(\gamma_t(i)\). Summing instead over \(i\), the numerator becomes \(b_j(y_{t+1})\beta_{t+1}(j)\sum_i\alpha_t(i)a_{ij}=\alpha_{t+1}(j)\beta_{t+1}(j)\), by the forward recursion. Dividing by \(L\) gives \(\gamma_{t+1}(j)\). Summing these one-time probabilities over the relevant times gives the stated expected counts. \(\square\)

For the M-step, let \(C_{ij}=\sum_{t=1}^{T-1}\xi_t(i,j)\) be the expected transition count and let \(D_i(y)=\sum_{t=1}^{T}\gamma_t(i)\mathbf{1}_{\{y_t=y\}}\) be the expected count of symbol \(y\) emitted from state \(i\). Here \(\mathbf{1}_{\{y_t=y\}}\) is \(1\) when \(y_t=y\), and \(0\) otherwise. The updates, when their denominators are positive, are:

$$ \pi_i^{\mathrm{new}}=\gamma_1(i),\qquad a_{ij}^{\mathrm{new}}=\frac{C_{ij}}{\sum_k C_{ik}},\qquad b_i^{\mathrm{new}}(y)=\frac{D_i(y)}{\sum_{z\in\mathcal{Y}}D_i(z)}. $$

The transition denominator is the expected number of departures from state \(i\), over times \(1,\ldots,T-1\). The emission denominator is the expected number of visits to state \(i\), over times \(1,\ldots,T\). These differ at the endpoint, so using the emission count total as a transition denominator would be an error.

Why normalization is the M-step. For any row of probabilities \((q_r)\) with nonnegative expected counts \((c_r)\) and positive total \(C=\sum_r c_r\), its contribution to the expected log likelihood is \(\sum_r c_r\log q_r\). Set \(p_r=c_r/C\). For any probability row \(q\), the inequality \(\log x\le x-1\), applied to \(q_r/p_r\) where \(p_r>0\), gives \(\sum_{r:p_r>0}p_r\log(q_r/p_r)\le \sum_{r:p_r>0}q_r-1\le0\). Therefore \(\sum_r c_r\log q_r\le\sum_r c_r\log p_r\). The normalized counts maximize the row contribution. If \(C=0\), that contribution is zero for every probability row, so the data do not determine an update for that row. The same argument applies to the initial distribution, whose expected counts are \(\gamma_1(i)\) and sum to \(1\).

Worked E-Step and M-Step

Worked Example: One Complete Iteration on Three Observations

Use two hidden states, \(S=\{1,2\}\), and symbols \(\mathcal{Y}=\{a,b\}\). Start with \(\pi=(\tfrac12,\tfrac12)\), transition matrix and emission matrix

$$ A=\begin{bmatrix}\tfrac34&\tfrac14\\[2pt]\tfrac14&\tfrac34\end{bmatrix}, \qquad B=\begin{bmatrix}\tfrac34&\tfrac14\\[2pt]\tfrac14&\tfrac34\end{bmatrix}, \qquad (y_1,y_2,y_3)=(a,b,a). $$

Each transition row sums to \(\tfrac34+\tfrac14=1\) and \(\tfrac14+\tfrac34=1\); each emission row has the same sum, so both matrices are valid. We calculate the forward quantities first. At time \(1\), \(\alpha_1=(\tfrac12\cdot\tfrac34,\tfrac12\cdot\tfrac14)=(\tfrac38,\tfrac18)\). Before applying the time-2 emission probabilities, the predicted state weights are \((\tfrac38\cdot\tfrac34+\tfrac18\cdot\tfrac14,\tfrac38\cdot\tfrac14+\tfrac18\cdot\tfrac34)=(\tfrac5{16},\tfrac3{16})\). Since \(y_2=b\), this gives \(\alpha_2=(\tfrac5{16}\cdot\tfrac14,\tfrac3{16}\cdot\tfrac34)=(\tfrac5{64},\tfrac9{64})\). Before the time-3 emission, the predicted weights are \((\tfrac5{64}\cdot\tfrac34+\tfrac9{64}\cdot\tfrac14,\tfrac5{64}\cdot\tfrac14+\tfrac9{64}\cdot\tfrac34)=(\tfrac3{32},\tfrac18)\). Applying the probabilities of \(a\) gives \(\alpha_3=(\tfrac9{128},\tfrac4{128})\), so \(L=\tfrac9{128}+\tfrac4{128}=\tfrac{13}{128}>0\).

For the backward quantities, \(\beta_3=(1,1)\). At time \(2\), the next symbol is \(a\), so \(\beta_2=(\tfrac34\cdot\tfrac34+\tfrac14\cdot\tfrac14,\tfrac14\cdot\tfrac34+\tfrac34\cdot\tfrac14)=(\tfrac58,\tfrac38)\). At time \(1\), the next symbol is \(b\), giving \(\beta_1=(\tfrac34\cdot\tfrac14\cdot\tfrac58+\tfrac14\cdot\tfrac34\cdot\tfrac38,\tfrac14\cdot\tfrac14\cdot\tfrac58+\tfrac34\cdot\tfrac34\cdot\tfrac38)=(\tfrac3{16},\tfrac14)\).

Multiply \(\alpha_t(i)\beta_t(i)\) and divide by \(L=\tfrac{13}{128}\). The state posterior probabilities are \(\gamma_1=(\tfrac9{13},\tfrac4{13})\), \(\gamma_2=(\tfrac{25}{52},\tfrac{27}{52})\), and \(\gamma_3=(\tfrac9{13},\tfrac4{13})\). Each vector sums to \(1\): for time \(2\), \(\tfrac{25}{52}+\tfrac{27}{52}=1\); at times \(1\) and \(3\), \(\tfrac9{13}+\tfrac4{13}=1\).

For the transition from time \(1\) to time \(2\), substituting in the formula for \(\xi_1(i,j)\) gives

$$ \xi_1= \begin{bmatrix} \tfrac{45}{104}&\tfrac{27}{104}\\[2pt] \tfrac{5}{104}&\tfrac{27}{104} \end{bmatrix}. $$

For example, its \((1,1)\) numerator is \(\tfrac38\cdot\tfrac34\cdot\tfrac14\cdot\tfrac58=\tfrac{45}{1024}\); dividing by \(\tfrac{13}{128}\) gives \(\tfrac{45}{104}\). The other numerators, in row order, are \(\tfrac{27}{1024},\tfrac5{1024},\tfrac{27}{1024}\), giving the displayed entries. For the transition from time \(2\) to time \(3\), the four numerators are \(\tfrac{45}{1024},\tfrac5{1024},\tfrac{27}{1024},\tfrac{27}{1024}\), so

$$ \xi_2= \begin{bmatrix} \tfrac{45}{104}&\tfrac{5}{104}\\[2pt] \tfrac{27}{104}&\tfrac{27}{104} \end{bmatrix}. $$

Both transition-posterior matrices sum to \(1\). Their row sums are \((\tfrac9{13},\tfrac4{13})\) for \(\xi_1\) and \((\tfrac{25}{52},\tfrac{27}{52})\) for \(\xi_2\), matching the state posteriors at the source times. Their column sums are \((\tfrac{25}{52},\tfrac{27}{52})\) and \((\tfrac9{13},\tfrac4{13})\), matching the state posteriors at the destination times.

Add the two transition matrices to obtain \(C\). Entry by entry, \(C=\begin{bmatrix}\tfrac{90}{104}&\tfrac{32}{104}\\[2pt]\tfrac{32}{104}&\tfrac{54}{104}\end{bmatrix}=\begin{bmatrix}\tfrac{45}{52}&\tfrac4{13}\\[2pt]\tfrac4{13}&\tfrac{27}{52}\end{bmatrix}\). The first transition row total is \(\tfrac{45}{52}+\tfrac4{13}=\tfrac{61}{52}\); the second is \(\tfrac4{13}+\tfrac{27}{52}=\tfrac{43}{52}\). Normalizing each row gives the updated transition matrix

$$ A^{\mathrm{new}}= \begin{bmatrix} \tfrac{45}{61}&\tfrac{16}{61}\\[2pt] \tfrac{16}{43}&\tfrac{27}{43} \end{bmatrix}. $$

The first row sums to \(\tfrac{45+16}{61}=1\), and the second sums to \(\tfrac{16+27}{43}=1\). For emissions, symbol \(a\) occurs at times \(1\) and \(3\), and \(b\) occurs at time \(2\). State \(1\)'s expected counts are \(D_1(a)=\tfrac9{13}+\tfrac9{13}=\tfrac{72}{52}\) and \(D_1(b)=\tfrac{25}{52}\), for a total of \(\tfrac{97}{52}\). State \(2\)'s counts are \(D_2(a)=\tfrac4{13}+\tfrac4{13}=\tfrac{32}{52}\) and \(D_2(b)=\tfrac{27}{52}\), for a total of \(\tfrac{59}{52}\). Thus

$$ B^{\mathrm{new}}= \begin{bmatrix} \tfrac{72}{97}&\tfrac{25}{97}\\[2pt] \tfrac{32}{59}&\tfrac{27}{59} \end{bmatrix}, \qquad \pi^{\mathrm{new}}=(\tfrac9{13},\tfrac4{13}). $$

Check the emission rows: \(\tfrac{72+25}{97}=1\) and \(\tfrac{32+27}{59}=1\); the updated initial probabilities sum to \(\tfrac9{13}+\tfrac4{13}=1\). This completes one iteration, using the original parameters for the entire E-step and only then forming the new parameters.

Worked Example: One Observation and No Transition Update

Let \(\pi=(\tfrac23,\tfrac13)\), \(A=\begin{bmatrix}\tfrac12&\tfrac12\\[2pt]\tfrac13&\tfrac23\end{bmatrix}\), and \(B=\begin{bmatrix}\tfrac12&\tfrac12\\[2pt]\tfrac14&\tfrac34\end{bmatrix}\), with the single observation \(y_1=a\). The transition rows sum to \(\tfrac12+\tfrac12=1\) and \(\tfrac13+\tfrac23=1\); the emission rows sum to \(\tfrac12+\tfrac12=1\) and \(\tfrac14+\tfrac34=1\). The likelihood is \(L=\tfrac23\cdot\tfrac12+\tfrac13\cdot\tfrac14=\tfrac13+\tfrac1{12}=\tfrac5{12}\). Therefore \(\gamma_1(1)=(\tfrac13)/(\tfrac5{12})=\tfrac45\) and \(\gamma_1(2)=(\tfrac1{12})/(\tfrac5{12})=\tfrac15\). The new initial distribution is \((\tfrac45,\tfrac15)\). Each state has only an observed \(a\) count, so the updated emission rows are \((1,0)\) and \((1,0)\). There are no consecutive observation times, hence every transition count total is zero. The transition rows cannot be estimated from this sequence: the M-step objective contains no transition terms, and any valid transition matrix maximizes it. This example shows why a zero denominator is not permission to divide; it means the data provide no update for that row.

Worked Example: Checking a Two-Time Transition Update

Take \(\pi=(\tfrac12,\tfrac12)\), \(A=\begin{bmatrix}\tfrac34&\tfrac14\\[2pt]\tfrac14&\tfrac34\end{bmatrix}\), \(B=\begin{bmatrix}\tfrac23&\tfrac13\\[2pt]\tfrac13&\tfrac23\end{bmatrix}\), and observations \((a,b)\). The transition rows sum to \(1\), and the emission rows sum to \(\tfrac23+\tfrac13=1\) and \(\tfrac13+\tfrac23=1\). The forward vectors are \(\alpha_1=(\tfrac13,\tfrac16)\) and \(\alpha_2=(\tfrac7{72},\tfrac{10}{72})\): the predicted weights at time \(2\) are \((\tfrac7{24},\tfrac5{24})\), then the probabilities of \(b\) are \(\tfrac13\) and \(\tfrac23\). Thus \(L=\tfrac{17}{72}\). Since \(\beta_2=(1,1)\), \(\beta_1=(\tfrac34\cdot\tfrac13+\tfrac14\cdot\tfrac23,\tfrac14\cdot\tfrac13+\tfrac34\cdot\tfrac23)=(\tfrac5{12},\tfrac7{12})\). Normalization gives \(\gamma_1=(\tfrac{10}{17},\tfrac7{17})\) and \(\gamma_2=(\tfrac7{17},\tfrac{10}{17})\).

The transition numerators are \(\tfrac1{12},\tfrac1{18},\tfrac1{72},\tfrac1{12}\); dividing each by \(\tfrac{17}{72}\) gives \(\xi_1=\begin{bmatrix}\tfrac6{17}&\tfrac4{17}\\[2pt]\tfrac1{17}&\tfrac6{17}\end{bmatrix}\). Its entries sum to \(\tfrac{17}{17}=1\), its row sums are \((\tfrac{10}{17},\tfrac7{17})\), and its column sums are \((\tfrac7{17},\tfrac{10}{17})\), verifying both posterior marginals. There is one transition, so normalizing the rows of \(\xi_1\) gives \(A^{\mathrm{new}}=\begin{bmatrix}\tfrac35&\tfrac25\\[2pt]\tfrac17&\tfrac67\end{bmatrix}\). Its row sums are \(\tfrac35+\tfrac25=1\) and \(\tfrac17+\tfrac67=1\). The emission counts come from \(a\) at time \(1\) and \(b\) at time \(2\), giving \(B^{\mathrm{new}}=\begin{bmatrix}\tfrac{10}{17}&\tfrac7{17}\\[2pt]\tfrac7{17}&\tfrac{10}{17}\end{bmatrix}\). Each row sums to \(1\), and \(\pi^{\mathrm{new}}=(\tfrac{10}{17},\tfrac7{17})\) also sums to \(1\).

Checks That Prevent Common Errors

A common mistake is to calculate a transition posterior without the probability of the next observation. In the two-time example, omitting the factor \(b_j(b)\) would make the numerator for \(\xi_1(1,1)\) equal to \(\tfrac13\cdot\tfrac34=\tfrac14\); dividing by the actual likelihood \(\tfrac{17}{72}\) gives \(\tfrac{18}{17}\), which cannot be a probability. The correct numerator includes the emission factor \(\tfrac13\): \(\tfrac13\cdot\tfrac34\cdot\tfrac13=\tfrac1{12}\), and \((\tfrac1{12})/(\tfrac{17}{72})=\tfrac6{17}\). The posterior matrix then has total mass \(1\) and the required state marginals.

Also keep the E-step and M-step distinct. The values \(\xi_t(i,j)\) are posterior probabilities under the old model; they are not the updated transition probabilities. First sum them over time to obtain counts, then normalize each source-state row. Likewise, use all \(T\) time points for emission counts but only the \(T-1\) transitions for transition counts. A row with a positive count total has a normalized-count update; a row with zero total is not identified by that sequence. These checks make a hand iteration auditable without confusing it with a claim about how the likelihood changes across iterations.

Check Your Understanding

Use the definitions and checks above to work through these questions.

  1. For a sequence of length \(T\), which time indices contribute to transition counts, and which contribute to emission counts?
  2. Why must the entries of \(\xi_t\) sum to \(1\), and what do its row and column sums represent?
  3. If the expected transition counts out of one state are all zero, what can be concluded about the M-step update for that transition row?
  4. In the three-observation example, verify the first updated transition row by dividing each expected count by its row total.
  5. Explain why the emission probability of the next observation must appear in the numerator for \(\xi_t(i,j)\).

Previous

Next

Back to Tutorials