M-Step Updates for Categorical HMMs

From Posterior Counts to Parameter Updates

In a categorical hidden Markov model, each parameter is a probability vector: the initial-state distribution, one transition row for each hidden state, and one emission distribution for each hidden state. The M-step updates these vectors using the expected numbers of times the corresponding events occurred under the current model. The calculation is simple once the counts are assembled, but two details matter: counts from different sequences must be pooled before normalization, and a row with zero expected count does not have a uniquely determined update.

Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space supporting \(R\) independent observed sequences \(Y_r=(Y_{r,1},\ldots,Y_{r,T_r})\), where \(T_r\ge1\). The hidden state process for sequence \(r\) is \((X_{r,t})_{1\le t\le T_r}\), with state space \(S=\{1,\ldots,K\}\), and each observation takes values in \(\{1,\ldots,M\}\). The model parameters are an initial row distribution \(\pi\), a row-stochastic transition matrix \(A=(a_{ij})\), and categorical emission probabilities \(b_{i\ell}\). Thus \(\sum_i\pi_i=1\), \(\sum_j a_{ij}=1\) for every \(i\), and \(\sum_{\ell=1}^M b_{i\ell}=1\) for every \(i\). Conditional on the hidden states, the observations are independent, with \(\mathbb{P}(Y_{r,t}=\ell\mid X_{r,t}=i)=b_{i\ell}\).

Fix the current parameter value, denoted by a superscript “old.” Assume every observed sequence has positive probability under that model, so conditioning on the observed data is defined. Write \(\gamma_{r,t}(i)=\mathbb{P}_{\mathrm{old}}(X_{r,t}=i\mid Y_r)\) and, for \(t<T_r\), \(\xi_{r,t}(i,j)=\mathbb{P}_{\mathrm{old}}(X_{r,t}=i,X_{r,t+1}=j\mid Y_r)\). These are posterior probabilities; in particular, \(\sum_i\gamma_{r,t}(i)=1\) and \(\sum_{i,j}\xi_{r,t}(i,j)=1\).

Every sequence contributes one initial state, so \(\sum_i C_i^{(0)}=R\). For each state \(i\), the transition row total \(\sum_j C_{ij}^{(A)}\) is its expected number of departures, while the emission row total \(\sum_\ell C_{i\ell}^{(B)}\) is its expected number of visits across all observed times. Those totals need not agree: departures exclude the last time point in each sequence.

Why the M-Step Separates

For a hidden path and its observations, the parts of the complete-data log likelihood that depend on the parameters are \(\log\pi_{X_{r,1}}+\sum_{t<T_r}\log a_{X_{r,t},X_{r,t+1}}+\sum_{t\le T_r}\log b_{X_{r,t},Y_{r,t}}\). The M-step maximizes the conditional expectation of this expression, with the posterior distribution of the hidden paths held fixed at its old-model value. This expected log likelihood is often called the \(Q\)-function.

Proof. For one complete hidden path, the initial-state log term is \(\sum_i\mathbf{1}_{\{X_{r,1}=i\}}\log\pi_i\). Taking its conditional expectation given \(Y_r\) replaces the indicator by \(\gamma_{r,1}(i)\). For a transition at time \(t\), the corresponding indicator is \(\mathbf{1}_{\{X_{r,t}=i,X_{r,t+1}=j\}}\), whose conditional expectation is \(\xi_{r,t}(i,j)\). For an emission symbol \(\ell\), the indicator is \(\mathbf{1}_{\{X_{r,t}=i\}}\mathbf{1}_{\{Y_{r,t}=\ell\}}\). The observation is fixed when conditioning, so its conditional expectation is \(\gamma_{r,t}(i)\mathbf{1}_{\{Y_{r,t}=\ell\}}\). Summing these expectations over sequences and times gives exactly the three count sums in the displayed formula. Linearity of conditional expectation justifies adding the terms, and terms not involving the new parameters do not affect maximization. \(\square\)

Because the initial vector, each transition row, and each emission row have separate simplex constraints, this objective can be maximized one probability vector at a time. The needed optimization fact also explains the zero-count case.

Proof. If \(C=0\), nonnegativity implies \(c_j=0\) for every \(j\), so \(L\) is zero for every probability vector. Now suppose \(C>0\), and set \(p_j=c_j/C\). A vector \(\theta\) with \(\theta_j=0\) for some \(p_j>0\) has \(L(\theta)=-\infty\), so it cannot maximize the objective because \(\theta=p\) has finite objective. For any other \(\theta\), let \(J=\{j:p_j>0\}\) and \(s=\sum_{j\in J}\theta_j\). Then \(0<s\le1\). For \(j\in J\), set \(q_j=\theta_j/s\); these \(q_j\) sum to one. The inequality \(\log x\le x-1\) for \(x>0\) gives $$ \sum_{j\in J}p_j\log\frac{q_j}{p_j} \le \sum_{j\in J}p_j\left(\frac{q_j}{p_j}-1\right) =\sum_{j\in J}q_j-1=0. $$ Consequently, $$ \frac{L(\theta)}{C} =\log s+\sum_{j\in J}p_j\log q_j \le \sum_{j\in J}p_j\log p_j+\log s \le \sum_{j\in J}p_j\log p_j. $$ The last expression is \(L(p)/C\). Equality requires \(s=1\) and equality in \(\log x\le x-1\) for every \(j\in J\), which requires \(q_j=p_j\). Thus \(\theta_j=p_j\) on \(J\), and \(s=1\) forces \(\theta_j=0\) off \(J\). This proves both maximality and uniqueness when \(C>0\). \(\square\)

Applying the theorem separately to the terms of \(Q\) yields the updates. An initial distribution always has a positive total count when \(R\ge1\). A transition or emission row can have total count zero, in which case the objective does not depend on that row and any probability vector is a valid maximizer.

Worked Updates

Interpretation and Common Pitfalls

These updates are maximum-likelihood updates for the expected complete-data objective with the old-model posterior held fixed. They do not replace posterior inference: the counts must first be computed under the old model. Nor do they say that every fitted row is uniquely determined. If a state has zero expected departures, its transition row has no contribution to the objective; if it has zero expected visits, its emission row has no contribution. A numerical implementation should test the denominator before dividing.

Common mistake. Dividing a transition row by the total count over the entire matrix rather than by that row's total violates the row-stochastic constraint. For the first row in the all-components example, this wrong calculation would give \((3/8,1/8)\), because the whole transition matrix has total count \(3+1+1+3=8\). The row then sums to \(3/8+1/8=1/2\), not \(1\). The correct denominator is the first-row total \(3+1=4\), giving \((3/4,1/4)\). Normalize each probability vector by its own count total.

The same principle applies to emissions: divide \(C_{i\ell}^{(B)}\) by the total emission count for state \(i\), not by the total number of observations or by a different state's count. The M-step is therefore a collection of categorical maximum-likelihood problems, linked only through the posterior expected counts that were computed beforehand.