Why Baum-Welch Does Not Decrease Likelihood

Why an Exact Update Has a Likelihood Guarantee

Baum-Welch repeatedly estimates hidden-state probabilities under the current model and uses those estimates to update its parameters. The likelihood is not usually maximized directly at each iteration. Instead, the update maximizes an expected complete-data log likelihood, where the expectation is taken over hidden paths given the observed sequence. The key fact is that this objective is a lower bound on the observed-data log likelihood, and the bound is tight at the current parameters. Raising that bound therefore cannot lower the likelihood.

Consider a categorical hidden Markov model on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, with finite state space $S=\{1,\ldots,K\}$ and discrete observation times $t=1,\ldots,T$. The hidden states are $X_1,\ldots,X_T$, and the observed sequence $y=(y_1,\ldots,y_T)$ is fixed. Write $\pi_i=\mathbb{P}(X_1=i)$, $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)$. The rows of $A=(a_{ij})$ and the categorical emission distributions $b_i$ sum to one; $\pi$ also sums to one. A parameter collection is denoted $\theta=(\pi,A,B)$.

p_\theta(y,z) =\pi_{z_1}b_{z_1}(y_1)\prod_{t=2}^{T}a_{z_{t-1}z_t}b_{z_t}(y_t), \qquad p_\theta(y)=\sum_{z\in S^T}p_\theta(y,z).

Here $z=(z_1,\ldots,z_T)$ ranges over all hidden paths, $p_\theta(y,z)$ is the joint probability of the observations and path, and $p_\theta(y)$ is the observed-data likelihood. Assume the current likelihood $p_\theta(y)$ is positive, so the posterior path probabilities are defined. Write $q_\theta(z)=p_\theta(y,z)/p_\theta(y)$. The exact E-step computes this posterior, usually through forward-backward messages.

Definition: For a probability distribution $q$ on hidden paths, define the EM objective $Q(\theta'\mid\theta)=\sum_z q_\theta(z)\log p_{\theta'}(y,z)$. The exact Baum-Welch M-step chooses a feasible $\theta'$ that maximizes this objective, or at least does not decrease it, with the current $\theta$ among the feasible choices. The objective is finite for the selected update. A parameter with zero posterior expected count contributes no log term to $Q$; its corresponding distribution row may be left unchanged.

The Lower-Bound Identity

The precise relationship between the objective and the observed likelihood is an identity, not just an inequality. For distributions $q$ and $r$ on a finite set, their Kullback-Leibler divergence is $D(q\Vert r)=\sum_{z:q(z)>0}q(z)\log(q(z)/r(z))$, with value $+\infty$ if $r(z)=0$ for some $z$ with $q(z)>0$. It is nonnegative and equals zero exactly when $q=r$. The identity below applies when $p_{\theta'}(y)>0$ and $p_{\theta'}(y,z)>0$ wherever $q_\theta(z)>0$.

Theorem (EM lower-bound identity): Under those positivity conditions, $$ \log p_{\theta'}(y) =Q(\theta'\mid\theta)+H(q_\theta) +D\!\left(q_\theta\middle\Vert q_{\theta'}\right), $$ where $H(q_\theta)=-\sum_z q_\theta(z)\log q_\theta(z)$. In particular, $Q(\theta'\mid\theta)+H(q_\theta)$ is a lower bound on $\log p_{\theta'}(y)$. At $\theta'=\theta$, the bound is an equality.

Proof. For every path with $q_\theta(z)>0$, the definition of the new posterior gives $\log p_{\theta'}(y,z)=\log p_{\theta'}(y)+\log q_{\theta'}(z)$. Multiply by $q_\theta(z)$ and sum over those paths. Since the probabilities $q_\theta(z)$ sum to one, this yields $Q(\theta'\mid\theta)=\log p_{\theta'}(y)+\sum_z q_\theta(z)\log q_{\theta'}(z)$. Rearranging and using the definitions of entropy and divergence gives the displayed identity. Nonnegativity of the divergence follows from $\log x\le x-1$: when $q(z)>0$, apply it to $x=r(z)/q(z)$, multiply by $q(z)$, and sum to get $-D(q\Vert r)\le\sum_{q(z)>0}r(z)-1\le0$. Equality requires $r(z)=q(z)$ on the support of $q$ and no probability mass for $r$ outside that support, hence $r=q$. At $\theta'=\theta$, $q_{\theta'}=q_\theta$, so the divergence is zero. $\square$

The lower bound is tight at the current parameter because its posterior is precisely the distribution used to form the bound. The same identity also shows what can happen after an update: the new posterior may differ from the old one, leaving a nonnegative divergence gap between the bound and the new log likelihood.

Expected Counts and the Monotonicity Result

For a categorical HMM, the posterior expected counts are $\gamma_t(i)=\mathbb{P}_\theta(X_t=i\mid y)$ and, for $t<T$, $\xi_t(i,j)=\mathbb{P}_\theta(X_t=i,X_{t+1}=j\mid y)$. These are the smoothed state and transition probabilities computed by forward-backward inference. Expanding the complete-data log probability and taking its posterior expectation gives

Q(\theta'\mid\theta) =\sum_i\gamma_1(i)\log\pi'_i +\sum_{t=1}^{T-1}\sum_{i,j}\xi_t(i,j)\log a'_{ij} +\sum_{t=1}^{T}\sum_i\sum_v \gamma_t(i)\mathbf{1}_{\{y_t=v\}}\log b'_i(v).

Each group of terms is a weighted categorical log likelihood. For example, the transition update uses counts $C_{ij}=\sum_{t=1}^{T-1}\xi_t(i,j)$, then sets $a'_{ij}=C_{ij}/\sum_j C_{ij}$ when the denominator is positive. The initial distribution uses counts $\gamma_1(i)$, and an emission row uses counts $\sum_t\gamma_t(i)\mathbf{1}_{\{y_t=v\}}$. If a row has zero total count, retaining its old values is a valid maximizing choice.

To see why normalization maximizes a row, let $c_j\ge0$ be its counts, $C=\sum_jc_j>0$, and $r_j$ a candidate probability row. Put $s_j=c_j/C$. If $r_j=0$ for any $c_j>0$, its objective is $-\infty$. Otherwise, $\sum_jc_j\log r_j=C\sum_{j:s_j>0}s_j\log r_j$, which equals $C\sum_js_j\log s_j-CD(s\Vert r)$. The divergence is nonnegative, so the objective is maximized at $r=s$. If $C=0$, every row gives objective zero. This justifies the normalized expected-count updates, including the zero-count case.

Theorem (Likelihood monotonicity for an exact update): Suppose $p_\theta(y)>0$, the exact E-step uses $q_\theta$, and the M-step returns a feasible $\theta'$ with finite $Q(\theta'\mid\theta)\ge Q(\theta\mid\theta)$ and $p_{\theta'}(y)>0$. Then $p_{\theta'}(y)\ge p_\theta(y)$. Equality holds exactly when both $Q(\theta'\mid\theta)=Q(\theta\mid\theta)$ and $q_{\theta'}=q_\theta$.

Proof. Apply the lower-bound identity at $\theta'$ and at $\theta$. At $\theta$, the posterior-divergence term is zero. Subtracting the two identities gives $$ \log p_{\theta'}(y)-\log p_\theta(y) =Q(\theta'\mid\theta)-Q(\theta\mid\theta) +D(q_\theta\Vert q_{\theta'}). $$ The first term on the right is nonnegative by the M-step condition, and the second is nonnegative by the divergence result. Thus the log likelihood cannot decrease. Since both likelihoods are positive and logarithm is strictly increasing, the likelihood cannot decrease either. Their difference is zero exactly when both nonnegative terms are zero. The first vanishes exactly when the objective is unchanged; the second vanishes exactly when the posterior path distributions agree. $\square$

Equality is therefore more restrictive than simply having an M-step tie: the posterior over paths must also remain unchanged. Conversely, the likelihood can increase even if the posterior changes, because the objective gain may outweigh the new divergence gap.

Worked Example: Updating the Initial Distribution

Take $T=1$, $S=\{1,2\}$, and one observed symbol $a$. Let $\pi=(\tfrac12,\tfrac12)$, $b_1(a)=\tfrac45$, and $b_2(a)=\tfrac15$. The complementary emission probabilities are $b_1(\text{other})=\tfrac15$ and $b_2(\text{other})=\tfrac45$, so both emission rows sum to $1$; the initial distribution also sums to $1$.

The likelihood is $\tfrac12\cdot\tfrac45+\tfrac12\cdot\tfrac15=\tfrac12$. The posterior state probabilities are $(\tfrac12\cdot\tfrac45)/\tfrac12=\tfrac45$ and $(\tfrac12\cdot\tfrac15)/\tfrac12=\tfrac15$. The exact initial-distribution update is therefore $\pi'=(\tfrac45,\tfrac15)$. Its likelihood is $\tfrac45\cdot\tfrac45+\tfrac15\cdot\tfrac15=\tfrac{17}{25}$, which exceeds $\tfrac12$, since $\tfrac{17}{25}-\tfrac12=\tfrac{9}{50}>0$.

Check: The updated row sums to $\tfrac45+\tfrac15=1$, and substituting it into the likelihood gives $\tfrac{16}{25}+\tfrac{1}{25}=\tfrac{17}{25}$. The posterior has changed, so equality does not hold.

Worked Example: Updating Categorical Emissions

Let $T=1$, $\pi=(\tfrac13,\tfrac23)$, and observe $a$ from the alphabet $\{a,b\}$. Suppose $b_1(a)=\tfrac12$, $b_1(b)=\tfrac12$, $b_2(a)=\tfrac14$, and $b_2(b)=\tfrac34$. Each emission row sums to $1$, and the initial distribution sums to $1$.

The observed likelihood is $\tfrac13\cdot\tfrac12+\tfrac23\cdot\tfrac14=\tfrac13$. The posterior probabilities of states $1$ and $2$ are both $(\tfrac16)/(\tfrac13)=\tfrac12$. Thus each state has positive expected count for $a$ and zero expected count for $b$. The exact emission update sets $b'_1(a)=b'_2(a)=1$ and $b'_1(b)=b'_2(b)=0$. Both updated emission rows sum to $1$, and the new likelihood is $\tfrac13\cdot1+\tfrac23\cdot1=1$.

Check: Substitution gives a likelihood increase of $1-\tfrac13=\tfrac23$. The update is valid at the boundary of the probability simplex; the observed symbol has positive probability under both updated emission rows.

Worked Example: Updating a Transition Row

Consider a two-state HMM with observations at $t=1,2$, a known initial state $X_1=1$, and transition probabilities $A=\begin{bmatrix}\tfrac12&\tfrac12\\ \tfrac13&\tfrac23\end{bmatrix}$. Both transition rows sum to $1$. The emissions are fixed on alphabet $\{a,d,e\}$: state $1$ has probabilities $(\tfrac34,\tfrac14,0)$, and state $2$ has probabilities $(\tfrac14,\tfrac14,\tfrac12)$; each row sums to $1$. Observe $y_1=d,y_2=a$. Only the transition matrix is being estimated.

The first observation has probability $\tfrac14$ in either state. Before accounting for $y_2$, the two possible transitions from state $1$ have probabilities $\tfrac12,\tfrac12$. After multiplying by the time-2 emission probabilities, their joint weights with the observations are $\tfrac12\cdot\tfrac14\cdot\tfrac34=\tfrac{3}{32}$ for path $(1,1)$ and $\tfrac12\cdot\tfrac14\cdot\tfrac14=\tfrac{1}{32}$ for path $(1,2)$. Their sum is the old likelihood $\tfrac{4}{32}=\tfrac18$. Dividing by that likelihood gives posterior transition counts $\xi_1(1,1)=\tfrac34$, $\xi_1(1,2)=\tfrac14$. No path makes a transition out of state $2$, so that row has zero count. The exact update sets row $1$ to $(\tfrac34,\tfrac14)$ and may retain row $2$ unchanged.

Check: The updated row sums to $\tfrac34+\tfrac14=1$. The new likelihood is $\tfrac14[(\tfrac34)(\tfrac34)+(\tfrac14)(\tfrac14)]=\tfrac14(\tfrac{10}{16})=\tfrac{5}{32}$. Since $\tfrac{5}{32}>\tfrac{4}{32}$, the transition update increases the likelihood.

When Equality Holds—and a Common Mistake

An exact update can leave the likelihood unchanged when it makes no effective improvement to the objective and leaves the hidden-path posterior the same. This includes a fixed point, but equality can also arise from non-unique maximizing parameter values. For instance, a row with zero expected count does not affect $Q$ in that iteration; the update convention for that row should be chosen carefully, and the equality criterion still requires the resulting posterior to be unchanged.

The guarantee depends on the exact E-step and a nondecreasing M-step objective. An arbitrary parameter change is not covered. In the initial-distribution example, keep the emissions fixed but replace the initial distribution by $(\tfrac1{10},\tfrac9{10})$. This is a valid distribution, yet the likelihood becomes $\tfrac1{10}\cdot\tfrac45+\tfrac9{10}\cdot\tfrac15=\tfrac{13}{50}$, which is less than the old likelihood $\tfrac12=\tfrac{25}{50}$. The correction is not to claim that every parameter change is safe: the exact update uses the posterior expected counts, here $(\tfrac45,\tfrac15)$, and maximizes $Q$.

A second practical caution concerns zero probabilities. If the starting likelihood is zero, the posterior $q_\theta$ is not defined by division by $p_\theta(y)$, so this proof does not apply. If an update makes the likelihood zero, its posterior is likewise undefined. Standard exact updates from a positive-likelihood start preserve the guarantee when they have finite $Q$; implementations should handle zero-count rows explicitly rather than divide by zero or introduce zeros that invalidate the objective.

Check Your Understanding

Use the lower-bound identity and the expected-count interpretation to answer these questions.

Why is the EM lower bound tight at the current parameter $\theta$?
For an exact M-step, what two conditions must hold for the observed likelihood to remain exactly unchanged?
If an emission row has zero total posterior expected count, why is retaining its old values a valid M-step choice?
In the initial-distribution example, compute the likelihood under $(\tfrac1{10},\tfrac9{10})$ and compare it with the exact update's likelihood.
Why does a zero starting likelihood prevent the posterior-based monotonicity proof from being applied as stated?

Why Baum-Welch Does Not Decrease Likelihood

What You'll Learn