From Smoothed Probabilities to Expected Counts
In the E-step of the Baum-Welch procedure, the hidden states are not observed, so their complete-data counts are not known. Forward-backward inference supplies posterior probabilities for the hidden states and for adjacent pairs of states. Summing those probabilities gives the expected counts: how often the sequence starts in each state, makes each transition, and emits each categorical symbol from each state. These are posterior expectations, not counts along a single guessed path.
Consider a hidden Markov model on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with hidden states \(X_1,\ldots,X_T\) in the finite state space \(S=\{1,\ldots,K\}\) and observations \(Y_1,\ldots,Y_T\) in the categorical alphabet \(\{1,\ldots,V\}\). The initial distribution is the row vector \(\pi\); the transition matrix is \(A=(a_{ij})\), where \(a_{ij}=\mathbb{P}(X_{t+1}=j\mid X_t=i)\); and \(b_i(v)=\mathbb{P}(Y_t=v\mid X_t=i)\) is the emission probability for symbol \(v\) in state \(i\). Each row of \(A\) sums to \(1\), and \(\sum_{v=1}^V b_i(v)=1\) for every state \(i\). We condition on a fixed observed sequence \(y_{1:T}=(y_1,\ldots,y_T)\) whose probability is positive.
Here \(\mathbf{1}_{\{E\}}\) is \(1\) when event \(E\) occurs and \(0\) otherwise. The E-step conditions the random counts on the observations. The key calculation is that the conditional expectation of an indicator is the conditional probability of its event.
Proof. Fix \(i,j,v\). The event \(I_i=1\) is exactly \(\{X_1=i\}\), so the conditional expectation of \(I_i\) is its conditional probability, \(\gamma_1(i)\). By linearity of conditional expectation, the conditional expectation of \(N_{ij}\) is the sum over \(t\) of the conditional expectations of \(\mathbf{1}_{\{X_t=i,X_{t+1}=j\}}\). Each such expectation is \(\xi_t(i,j)\). In \(C_{iv}\), the observation is fixed at \(y_t\), so the summand is zero if \(y_t\ne v\), and otherwise it is \(\mathbf{1}_{\{X_t=i\}}\). Its conditional expectation is therefore \(\gamma_t(i)\mathbf{1}_{\{y_t=v\}}\). Summing proves the three count formulas, including the empty sum when \(T=1\). For the first marginal identity, the disjoint events \(\{X_t=i,X_{t+1}=j\}\), as \(j\) ranges over \(S\), have union \(\{X_t=i\}\). Taking their conditional probabilities gives \(\sum_j\xi_t(i,j)=\gamma_t(i)\). For the second, the same events, now summed over \(i\), partition \(\{X_{t+1}=j\}\), giving \(\sum_i\xi_t(i,j)=\gamma_{t+1}(j)\). All probabilities are conditioned on the same positive-probability observation event, so these conditional probabilities are defined. \(\square\)
These identities explain the connection to forward-backward inference. If \(\alpha_t(i)=\mathbb{P}(Y_{1:t}=y_{1:t},X_t=i)\), \(\beta_t(i)=\mathbb{P}(Y_{t+1:T}=y_{t+1:T}\mid X_t=i)\), and \(L=\mathbb{P}(Y_{1:T}=y_{1:T})>0\), then the forward-backward factorization gives $$ \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}. $$
In computation, first obtain \(\gamma_t\) and \(\xi_t\) from the forward-backward messages, then sum over time as in the theorem. The row sums of \(\xi_t\) must match \(\gamma_t\), and its column sums must match \(\gamma_{t+1}\). These are useful checks on indexing and arithmetic.
Worked Example: One Observation and No Transitions
Let \(S=\{1,2\}\), with initial distribution \(\pi=(\tfrac23,\tfrac13)\), and observe the single symbol \(x\). State 1 emits \(x\) with probability \(\tfrac34\) and \(y\) with probability \(\tfrac14\); state 2 emits each symbol with probability \(\tfrac12\). For completeness, take the transition matrix \(A=\begin{bmatrix}\tfrac12&\tfrac12\\\tfrac12&\tfrac12\end{bmatrix}\). Its first row sums to \(\tfrac12+\tfrac12=1\), and its second row sums to \(\tfrac12+\tfrac12=1\). The emission rows also sum to \(1\): \(\tfrac34+\tfrac14=1\) and \(\tfrac12+\tfrac12=1\).
The joint probabilities of the observation and each initial state are \(\mathbb{P}(X_1=1,Y_1=x)=\tfrac23\cdot\tfrac34=\tfrac12\) and \(\mathbb{P}(X_1=2,Y_1=x)=\tfrac13\cdot\tfrac12=\tfrac16\). Thus \(L=\mathbb{P}(Y_1=x)=\tfrac12+\tfrac16=\tfrac23\), and $$ \gamma_1(1)=\frac{\tfrac12}{\tfrac23}=\tfrac34,\qquad \gamma_1(2)=\frac{\tfrac16}{\tfrac23}=\tfrac14. $$
The expected initial-state counts are \((\tfrac34,\tfrac14)\). The expected emission counts for \(x\) are \((\tfrac34,\tfrac14)\), and for \(y\) they are \((0,0)\), because the only observation is \(x\). Their total is \(1\), as required for one observation. Since \(T=1\), there are no adjacent time points and every expected transition count is zero.
Worked Example: Expected Counts for a Three-Observation Sequence
Take two states, initial distribution \((\tfrac12,\tfrac12)\), transition matrix $$ A=\begin{bmatrix}\tfrac23&\tfrac13\\[2pt]\tfrac13&\tfrac23\end{bmatrix}, $$ and categorical emissions \(b_1(a)=\tfrac34,\ b_1(b)=\tfrac14,\ b_2(a)=\tfrac14,\ b_2(b)=\tfrac34\). Each transition row sums to \(1\), since \(\tfrac23+\tfrac13=1\) and \(\tfrac13+\tfrac23=1\). Each emission row sums to \(1\), since \(\tfrac34+\tfrac14=1\) for state 1 and \(\tfrac14+\tfrac34=1\) for state 2. For observations \(a,b,a\), compute the smoothed probabilities and all three expected-count arrays.
The forward quantities are \(\alpha_1=(\tfrac38,\tfrac18)\). At time 2, $$ \alpha_2(1)=\left(\tfrac38\cdot\tfrac23+\tfrac18\cdot\tfrac13\right)\tfrac14 =\left(\tfrac14+\tfrac1{24}\right)\tfrac14=\tfrac7{96}, $$ $$ \alpha_2(2)=\left(\tfrac38\cdot\tfrac13+\tfrac18\cdot\tfrac23\right)\tfrac34 =\left(\tfrac18+\tfrac1{12}\right)\tfrac34=\tfrac{15}{96}. $$ At time 3, $$ \alpha_3(1)=\left(\tfrac7{96}\cdot\tfrac23+\tfrac{15}{96}\cdot\tfrac13\right)\tfrac34 =\left(\tfrac{14}{288}+\tfrac{15}{288}\right)\tfrac34=\tfrac{87}{1152}, $$ $$ \alpha_3(2)=\left(\tfrac7{96}\cdot\tfrac13+\tfrac{15}{96}\cdot\tfrac23\right)\tfrac14 =\left(\tfrac7{288}+\tfrac{30}{288}\right)\tfrac14=\tfrac{37}{1152}. $$ Therefore \(L=\tfrac{87}{1152}+\tfrac{37}{1152}=\tfrac{124}{1152}\), which is positive.
The backward quantities are \(\beta_3=(1,1)\), \(\beta_2=(\tfrac7{12},\tfrac5{12})\), and \(\beta_1=(\tfrac{29}{144},\tfrac{37}{144})\). For example, \(\beta_2(1)=\tfrac23\cdot\tfrac34+\tfrac13\cdot\tfrac14=\tfrac7{12}\), while \(\beta_1(1)=\tfrac23\cdot\tfrac14\cdot\tfrac7{12}+\tfrac13\cdot\tfrac34\cdot\tfrac5{12}=\tfrac{29}{144}\); the other entries follow from the same backward sum. Applying the forward-backward formulas gives $$ \gamma_1=\left(\tfrac{87}{124},\tfrac{37}{124}\right),\qquad \gamma_2=\left(\tfrac{49}{124},\tfrac{75}{124}\right),\qquad \gamma_3=\left(\tfrac{87}{124},\tfrac{37}{124}\right). $$ For instance, the unnormalized weights at time 2 are \(\tfrac7{96}\cdot\tfrac7{12}=\tfrac{49}{1152}\) and \(\tfrac{15}{96}\cdot\tfrac5{12}=\tfrac{75}{1152}\); dividing by \(L=\tfrac{124}{1152}\) gives \(\gamma_2\).
For the first adjacent pair, the four unnormalized \(\xi_1(i,j)\) numerators, with common denominator \(1152\), are \(42,45,7,30\). For example, the \((1,2)\) numerator is obtained from \(\tfrac38\cdot\tfrac13\cdot\tfrac34\cdot\tfrac5{12}=\tfrac{45}{1152}\). Dividing each entry by \(L=\tfrac{124}{1152}\) gives $$ \xi_1=\frac1{124}\begin{bmatrix}42&45\\7&30\end{bmatrix}. $$ For the second pair, using \(\alpha_2\), the emission probabilities for \(a\), and \(\beta_3=(1,1)\), the unnormalized numerators with denominator \(1152\) are \(42,7,45,30\). For example, the \((2,2)\) numerator is \(\tfrac{15}{96}\cdot\tfrac23\cdot\tfrac14=\tfrac{30}{1152}\). Hence $$ \xi_2=\frac1{124}\begin{bmatrix}42&7\\45&30\end{bmatrix}. $$
Check the marginals: the row sums of \(\xi_1\) are \((\tfrac{87}{124},\tfrac{37}{124})=\gamma_1\), and its column sums are \((\tfrac{49}{124},\tfrac{75}{124})=\gamma_2\). The row sums of \(\xi_2\) are \(\gamma_2\), and its column sums are \(\gamma_3\). Each \(\gamma_t\) sums to \(1\).
The expected initial-state counts are \((\tfrac{87}{124},\tfrac{37}{124})\). Summing the two adjacent-pair matrices gives the transition counts: $$ \left(\mathbb{E}[N_{ij}\mid y_{1:3}]\right)_{i,j} =\xi_1+\xi_2 =\frac1{124}\begin{bmatrix}84&52\\52&60\end{bmatrix}. $$ Their total is \(\tfrac{84+52+52+60}{124}=2\), the number of transitions in a length-three sequence. For emissions, the observations are \(a,b,a\). State 1 has expected count \(\tfrac{87}{124}+\tfrac{87}{124}=\tfrac{174}{124}\) for \(a\) and \(\tfrac{49}{124}\) for \(b\). State 2 has expected count \(\tfrac{37}{124}+\tfrac{37}{124}=\tfrac{74}{124}\) for \(a\) and \(\tfrac{75}{124}\) for \(b\). The total expected count for \(a\) is \(\tfrac{174+74}{124}=2\), and for \(b\) it is \(\tfrac{49+75}{124}=1\), matching the observed sequence.
Expected Counts Are Not Counts Along One Path
A posterior expected count averages over every hidden path, weighted by its posterior probability. It is generally fractional. In contrast, the Viterbi path is a single joint maximum-probability path, and choosing the most probable state separately at each time is pointwise posterior decoding. Neither procedure, by itself, computes the expected counts.
Worked Example: A Most-Probable State Sequence Is Not the E-Step
Use two states with initial distribution \((\tfrac12,\tfrac12)\), transition matrix \(A=\begin{bmatrix}\tfrac34&\tfrac14\\\tfrac14&\tfrac34\end{bmatrix}\), and emissions \(b_1(x)=\tfrac34,\ b_1(y)=\tfrac14,\ b_2(x)=\tfrac14,\ b_2(y)=\tfrac34\). The transition rows each sum to \(\tfrac34+\tfrac14=1\), and both emission rows also sum to \(1\). Observe \(x,x\).
The four hidden-path joint probabilities, including the observations, are $$ \begin{aligned} \mathbb{P}(1,1,x,x)&=\tfrac12\cdot\tfrac34\cdot\tfrac34\cdot\tfrac34=\tfrac{27}{128},\\ \mathbb{P}(1,2,x,x)&=\tfrac12\cdot\tfrac34\cdot\tfrac14\cdot\tfrac14=\tfrac3{128},\\ \mathbb{P}(2,1,x,x)&=\tfrac12\cdot\tfrac14\cdot\tfrac14\cdot\tfrac34=\tfrac3{128},\\ \mathbb{P}(2,2,x,x)&=\tfrac12\cdot\tfrac14\cdot\tfrac34\cdot\tfrac14=\tfrac3{128}. \end{aligned} $$ Their sum is \(L=\tfrac{36}{128}=\tfrac9{32}\). Dividing by \(L\), the path posterior probabilities are \(\tfrac34,\tfrac1{12},\tfrac1{12},\tfrac1{12}\), in the displayed order. Thus the unique most probable path is \((1,1)\), while the smoothed state probabilities at each time are \((\tfrac56,\tfrac16)\).
The expected transition-count matrix is the adjacent-pair posterior matrix $$ \begin{bmatrix}\tfrac34&\tfrac1{12}\\[2pt]\tfrac1{12}&\tfrac1{12}\end{bmatrix}, $$ whose entries sum to \(1\), the single transition in the sequence. Counting transitions along the most probable path instead gives one \(1\to1\) transition and zero of each other type. The expected emission counts are \(\tfrac56+\tfrac56=\tfrac53\) occurrences of \(x\) from state 1 and \(\tfrac16+\tfrac16=\tfrac13\) from state 2; both states have zero counts for \(y\). These fractional counts incorporate uncertainty over paths that a single decoded path discards.
Checks, Common Mistakes, and Use
For a sequence of length \(T\), the initial-state expected counts sum to \(1\), the transition expected counts sum to \(T-1\), and the categorical-emission expected counts sum to \(T\). The sum of the emission counts for a particular symbol \(v\) is the number of times \(v\) appears in the observed sequence. These follow directly from the indicator definitions: each sequence has exactly one initial state, one transition at each of the \(T-1\) adjacent pairs, and one emitted symbol at each of the \(T\) times.
Common mistake. In the length-three example, the largest entries of \(\gamma_1,\gamma_2,\gamma_3\) correspond respectively to states \(1,2,1\): the time-2 probabilities are \((\tfrac{49}{124},\tfrac{75}{124})\), so state 2 has the larger posterior probability there. The pointwise most-probable sequence is therefore \(1,2,1\), which has one \(1\to2\) transition and one \(2\to1\) transition—not two \(1\to1\) transitions. Even that corrected path count is not the E-step transition count: the posterior expected counts are \(\tfrac{84}{124}\) for \(1\to1\), \(\tfrac{52}{124}\) for \(1\to2\), \(\tfrac{52}{124}\) for \(2\to1\), and \(\tfrac{60}{124}\) for \(2\to2\).
Another frequent error is to use \(\gamma_t(i)\gamma_{t+1}(j)\) as if it were \(\xi_t(i,j)\). The two state probabilities are not generally conditionally independent given all the observations; the transition posterior must account for the transition probability and the observation sequence. The marginal checks on \(\xi_t\) are necessary consistency checks, but they do not justify replacing \(\xi_t\) by a product of \(\gamma\)'s.
Once these expected counts are computed, they provide the state and transition totals, and the state-by-symbol totals, used in the HMM E-step. The calculations here stop at those expected counts: converting them into updated parameter estimates is a separate maximization step.
Check Your Understanding
For each question, use the definitions of \(\gamma_t\), \(\xi_t\), and the complete-data counts.
- Why does the sum of all expected transition counts equal \(T-1\), including when some transition probabilities are zero?
- For \(T=1\), which expected count arrays can be nonzero, and what must their totals be?
- What two marginal identities should \(\xi_t\) satisfy, and which smoothed distributions do they recover?
- In the \(x,x\) example, compare the posterior expected transition counts with the counts along the unique most probable path.
- For a fixed symbol \(v\), how can the total expected emission count for \(v\) be checked directly from the observed sequence?