From Hidden Paths to an EM Objective
In a hidden Markov model, the observed sequence does not reveal the states that generated it. Directly maximizing the observation likelihood can therefore be difficult: that likelihood sums over every possible hidden path. The expectation–maximization (EM) approach uses the current parameter to assign posterior probabilities to those paths, then averages their complete-data log likelihoods. For HMMs, this procedure is called the Baum–Welch algorithm.
Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, and let \(X_1,\ldots,X_T\) be a Markov chain with finite state space \(S=\{1,\ldots,K\}\). The observed sequence is \(Y_1,\ldots,Y_T\). The initial distribution is the row vector \(\pi=(\pi_i)\), and the transition matrix \(A=(a_{ij})\) is row-stochastic: \(a_{ij}\ge 0\) and \(\sum_{j\in S}a_{ij}=1\) for each \(i\). Conditional on the hidden states, observations are independent, with observation likelihood \(b_i(y_t)\) in state \(i\). For discrete observations, \(b_i\) is a probability mass function; for continuous observations, it is a density with respect to a specified dominating measure.
Write \(\theta\) for all model parameters, including \(\pi\), \(A\), and the emission parameters. A hidden path is \(z=(z_1,\ldots,z_T)\in S^T\). The complete data consist of the observations and this path. The factorization below follows from the Markov property and conditional independence of the observations.
Proof. The chain rule gives \(p_\theta(z)=\pi_{z_1}\prod_{t=2}^{T}a_{z_{t-1}z_t}\), since the conditional distribution of \(X_t\), given the preceding states, depends only on \(X_{t-1}\). Conditional independence gives \(p_\theta(y\mid z)=\prod_{t=1}^{T}b_{z_t}(y_t)\). Multiplying \(p_\theta(z)\) by \(p_\theta(y\mid z)\) gives the stated joint likelihood. Summing the joint likelihood over the finite set \(S^T\) gives the marginal likelihood. \(\square\)
When the current parameter is \(\theta^{(r)}\), the E-step uses the posterior distribution on hidden paths. For discrete observations, this is ordinary conditioning when the observed sequence has positive probability. For continuous observations, conditioning on an exact sequence requires a chosen version of the conditional distribution: at the data in question, assume \(0<p_{\theta^{(r)}}(y)<\infty\) and that the joint densities \(p_{\theta^{(r)}}(y,z)\) are finite. The ratio below then specifies that pointwise version.
Because the path space is finite, the posterior probabilities sum to one: \(\sum_z q_r(z)=\sum_z p_{\theta^{(r)}}(y,z)/p_{\theta^{(r)}}(y)=1\). Expanding the logarithm of the complete-data likelihood shows what is being averaged:
Thus \(Q\) is a posterior-weighted average of the initial-state, transition, and emission log-likelihood terms. It is not the log likelihood of a single “representative” path. The posterior is computed at the current parameter, while the log joint likelihood inside the average is evaluated at the candidate parameter. Forward–backward calculations provide the relevant posterior information without listing every path when \(T\) is large; here the path sum makes the definition transparent.
Why the Posterior-Weighted Objective Appears
The following identity gives a precise connection between the observed-data likelihood and an average over paths. For probability distributions \(q\) and \(r\) on a finite set, their Kullback–Leibler divergence is \(D(q\|r)=\sum_{z:q(z)>0}q(z)\log(q(z)/r(z))\), provided \(r(z)>0\) wherever \(q(z)>0\).
Proof. On the support of \(q\), the posterior is \(p_\theta(z\mid y)=p_\theta(y,z)/p_\theta(y)\), which is positive by the support assumption. Hence $$ D\!\left(q\,\middle\|\,p_\theta(\,\cdot\mid y)\right) =\sum_{z:q(z)>0}q(z)\log q(z)-\sum_z q(z)\log p_\theta(y,z)+\sum_zq(z)\log p_\theta(y). $$ Since \(\sum_zq(z)=1\), the last sum is \(\log p_\theta(y)\). Rearranging proves the identity. \(\square\)
For the E-step, \(q=q_r\) is the posterior under \(\theta^{(r)}\). The entropy term \(-\sum_z q_r(z)\log q_r(z)\) is then fixed while comparing candidate parameters. This explains why the EM M-step maximizes the expected complete-data log likelihood \(Q\). The identity itself does not prescribe how to solve that maximization, and it does not require choosing a single hidden path.
Worked Examples
Worked Example: A Singleton Observation Alphabet
Take two hidden states, \(T=2\), initial distribution \(\pi=(\tfrac12,\tfrac12)\), and transition matrix $$ A=\begin{bmatrix}\tfrac34&\tfrac14\\[2pt]\tfrac14&\tfrac34\end{bmatrix}. $$ The observation alphabet contains just one symbol, which has probability \(1\) in either state. Find the posterior path probabilities, then evaluate \(Q\) at a candidate parameter with \(\pi'=(\tfrac23,\tfrac13)\) and $$ A'=\begin{bmatrix}\tfrac12&\tfrac12\\[2pt]\tfrac14&\tfrac34\end{bmatrix}. $$
Both rows of \(A\) sum to \(\tfrac34+\tfrac14=1\) and \(\tfrac14+\tfrac34=1\). Both rows of \(A'\) sum to \(\tfrac12+\tfrac12=1\) and \(\tfrac14+\tfrac34=1\). The initial distributions sum to \(1\), and the sole emission probability is \(1\) in each state, so the model is normalized.
There are four paths. Their joint probabilities at the current parameter are \(p( y,11)=\tfrac12\cdot\tfrac34=\tfrac38\), \(p( y,12)=\tfrac12\cdot\tfrac14=\tfrac18\), \(p( y,21)=\tfrac12\cdot\tfrac14=\tfrac18\), and \(p( y,22)=\tfrac12\cdot\tfrac34=\tfrac38\). Their sum is \(\tfrac38+\tfrac18+\tfrac18+\tfrac38=1\). Thus the marginal likelihood is \(1\), and the posterior path probabilities are \(\tfrac38,\tfrac18,\tfrac18,\tfrac38\), respectively.
At the candidate parameter, the complete-data likelihoods for paths \(11,12,21,22\) are \(\tfrac23\cdot\tfrac12=\tfrac13\), \(\tfrac23\cdot\tfrac12=\tfrac13\), \(\tfrac13\cdot\tfrac14=\tfrac1{12}\), and \(\tfrac13\cdot\tfrac34=\tfrac14\). Therefore $$ Q(\theta'\mid\theta^{(r)}) =\tfrac12\log\tfrac13+\tfrac18\log\tfrac1{12}+\tfrac38\log\tfrac14. $$
Check: The four candidate likelihoods sum to \(\tfrac13+\tfrac13+\tfrac1{12}+\tfrac14=1\), as expected for the singleton observation. The posterior weights also sum to \(\tfrac38+\tfrac18+\tfrac18+\tfrac38=1\). The displayed \(Q\) uses the current posterior weights, not the candidate model’s path probabilities.
Worked Example: A Single Informative Observation
There are two states and one binary observation, \(x\) or \(w\). At the current parameter, \(\pi=(\tfrac23,\tfrac13)\), \(b_1(x)=\tfrac34\), and \(b_2(x)=\tfrac14\). The complementary probabilities are \(b_1(w)=\tfrac14\) and \(b_2(w)=\tfrac34\). Given observation \(x\), find the posterior state probabilities and evaluate \(Q\) at the candidate with \(\pi'=(\tfrac12,\tfrac12)\), \(b'_1(x)=\tfrac23\), \(b'_2(x)=\tfrac13\), and complementary probabilities \(b'_1(w)=\tfrac13\), \(b'_2(w)=\tfrac23\).
The current emission probabilities sum to \(1\) in each state: \(\tfrac34+\tfrac14=1\) and \(\tfrac14+\tfrac34=1\). The candidate emission probabilities also sum to \(1\): \(\tfrac23+\tfrac13=1\) in state 1 and \(\tfrac13+\tfrac23=1\) in state 2. The current joint likelihoods for \(x\) and states 1 and 2 are \(\tfrac23\cdot\tfrac34=\tfrac12\) and \(\tfrac13\cdot\tfrac14=\tfrac1{12}\). Thus \(p(x)=\tfrac12+\tfrac1{12}=\tfrac7{12}\), and the posterior probabilities are \((\tfrac12)/(\tfrac7{12})=\tfrac67\) and \((\tfrac1{12})/(\tfrac7{12})=\tfrac17\).
Under the candidate, the complete-data likelihoods for \((x,1)\) and \((x,2)\) are \(\tfrac12\cdot\tfrac23=\tfrac13\) and \(\tfrac12\cdot\tfrac13=\tfrac16\). Therefore $$ Q(\theta'\mid\theta^{(r)}) =\tfrac67\log\tfrac13+\tfrac17\log\tfrac16 =\log\tfrac12+\tfrac67\log\tfrac23+\tfrac17\log\tfrac13. $$
Check: The candidate observation likelihood is \(\tfrac13+\tfrac16=\tfrac12\). The posterior probabilities at the current parameter sum to \(\tfrac67+\tfrac17=1\); they are not the candidate probabilities \((\tfrac23,\tfrac13)\).
Worked Example: Two Observations and Four Hidden Paths
Use two states, initial distribution \((\tfrac12,\tfrac12)\), and transition matrix with diagonal entries \(\tfrac34\) and off-diagonal entries \(\tfrac14\). The observation alphabet is \(x,w\), with current probabilities \(b_1(x)=\tfrac34\), \(b_1(w)=\tfrac14\), \(b_2(x)=\tfrac14\), and \(b_2(w)=\tfrac34\). For observations \(y=(x,x)\), find the posterior path probabilities and evaluate the objective at a candidate with initial distribution \((\tfrac12,\tfrac12)\), transition diagonal entries \(\tfrac23\), off-diagonal entries \(\tfrac13\), and emissions \(b'_1(x)=\tfrac23\), \(b'_2(x)=\tfrac13\).
The current transition rows each sum to \(\tfrac34+\tfrac14=1\); the candidate rows each sum to \(\tfrac23+\tfrac13=1\). In both models, the two emission probabilities in each state sum to \(1\): the current sums are \(\tfrac34+\tfrac14\) and \(\tfrac14+\tfrac34\); the candidate complements are \(\tfrac13\) and \(\tfrac23\).
At the current parameter, the four joint likelihoods are \(p(y,11)=\tfrac12\cdot\tfrac34\cdot\tfrac34\cdot\tfrac34=\tfrac{27}{128}\), \(p(y,12)=\tfrac12\cdot\tfrac14\cdot\tfrac34\cdot\tfrac14=\tfrac3{128}\), \(p(y,21)=\tfrac12\cdot\tfrac14\cdot\tfrac14\cdot\tfrac34=\tfrac3{128}\), and \(p(y,22)=\tfrac12\cdot\tfrac34\cdot\tfrac14\cdot\tfrac14=\tfrac3{128}\). Their sum is \(\tfrac{36}{128}=\tfrac9{32}\). Dividing each by \(\tfrac9{32}=\tfrac{36}{128}\) gives posterior probabilities \(\tfrac34,\tfrac1{12},\tfrac1{12},\tfrac1{12}\).
At the candidate parameter, the four complete-data likelihoods are \(\tfrac12(\tfrac23)^3=\tfrac4{27}\) for path \(11\), and \(\tfrac12\cdot\tfrac13\cdot\tfrac23\cdot\tfrac13=\tfrac1{27}\) for each of paths \(12,21,22\). Hence $$ Q(\theta'\mid\theta^{(r)}) =\tfrac34\log\tfrac4{27}+\tfrac14\log\tfrac1{27}. $$
Check: The candidate joint likelihoods sum to \(\tfrac4{27}+\tfrac1{27}+\tfrac1{27}+\tfrac1{27}=\tfrac7{27}\). The current posterior probabilities sum to \(\tfrac34+\tfrac1{12}+\tfrac1{12}+\tfrac1{12}=1\). Both checks use the four path values just computed.
What the E-Step Does—and Does Not Do
The examples show the essential division of roles. The current parameter determines how plausible each hidden path is after seeing the data. Those posterior probabilities remain fixed while the M-step compares candidate parameters through their complete-data log likelihoods. The computation can be summarized as follows.
Write the initial, transition, and emission factors for a path and check that the probability distributions are normalized.
For each path, divide its current joint likelihood by the current observation likelihood, requiring a finite, strictly positive denominator.
Weight each candidate complete-data log likelihood by the current posterior path probability to obtain \(Q(\theta\mid\theta^{(r)})\).
The M-step maximizes this objective over the allowed parameter space; the form of the resulting parameter updates depends on the emission model and constraints.
Common pitfall: replacing an average of logs by a log of an average. In the two-observation example, the correct objective at the candidate is \(\tfrac34\log\tfrac4{27}+\tfrac14\log\tfrac1{27}\). A tempting but incorrect calculation is \(\log\bigl(\tfrac34\cdot\tfrac4{27}+\tfrac14\cdot\tfrac1{27}\bigr)=\log\tfrac{13}{108}\). That expression takes the logarithm after averaging likelihoods; it is not the posterior expectation of the log likelihood. The definition of \(Q\) requires averaging the logarithms, with the posterior weights calculated at the current parameter.
A second error is to replace the posterior distribution on paths by the single most probable path. In the same example, path \(11\) has posterior probability \(\tfrac34\), but the other three paths together have probability \(\tfrac14\); their contributions to \(Q\) are not zero. Viterbi decoding asks for a most probable path, whereas the E-step averages over all paths with positive posterior probability. The two calculations answer different questions.
For continuous observations, likelihoods in these formulas are densities. The ratio defining \(q_r(z)\) is appropriate at the observed sequence only when the chosen density values are finite and the marginal density is strictly positive there. This condition avoids an undefined ratio such as \(\infty/\infty\). For discrete observations, the analogous condition is that the observed sequence has positive probability. If a candidate parameter creates zero joint likelihood on a path that the E-step assigns positive probability, its log contribution is \(-\infty\), so support restrictions matter in optimization.
Check Your Understanding
For each question, distinguish the current posterior over paths from the candidate complete-data likelihood.
- Why must the posterior path probabilities sum to \(1\), and what denominator is used to normalize them?
- For continuous observations, state the finiteness and positivity conditions needed for the pointwise posterior ratio.
- In a two-state, one-observation HMM, explain why the complete-data log likelihood contains an initial-state term and an emission term but no transition term.
- Explain in words why the most probable hidden path does not generally suffice to compute \(Q(\theta\mid\theta^{(r)})\).
- What happens to \(Q\) if a candidate parameter assigns zero joint likelihood to a path that has positive current posterior probability?