Tutorials › Stochastic Processes › Handling Missing Observations in HMM Inference and Training

Home  /  Tutorials  /  Hidden Markov Models

Hidden Markov Models · Tutorial 956 of 994

Handling Missing Observations in HMM Inference and Training

Treat a missing emission as an uninformative observation, then use forward-backward probabilities to calculate the likelihood and the expected counts used in categorical HMM training.

Advanced 14 min read

What You'll Learn

  • Represent an unobserved categorical emission by a likelihood factor of one.
  • Derive forward and backward recursions when the observation pattern has gaps.
  • Compute smoothed state probabilities and adjacent-state transition posteriors.
  • Separate transition expected counts from emission counts at observed times.
  • Apply categorical Baum-Welch updates, including rows with no expected counts.
  • Recognize why deleting a missing time point can give the wrong likelihood.

Missing Emissions Do Not Remove Hidden States

In a hidden Markov model, an observation at a time point provides information about the hidden state through its emission probability. If that observation is missing, it provides no such information. The hidden state at that time still exists, however, and the chain still makes its transition to the next time point. This distinction determines how to compute both the observed-data likelihood and the expected counts used in categorical-emission training.

Work on a probability space \((\Omega,\mathcal F,\mathbb P)\). Let \((Z_t)_{1\le t\le T}\) be a hidden Markov chain on a finite state space \(S\), with initial distribution \(\pi\) and row-stochastic transition matrix \(A=(a_{ij})\). Conditional on the hidden states, observations are independent; in state \(i\), an observed category \(y\) has probability \(b_i(y)\), where the finite observation alphabet is \(\mathcal C\). Each row of the emission probabilities sums to one. At time \(t\), either a category \(y_t\in\mathcal C\) is observed or the observation is missing. Assume the missingness pattern is fixed by design or is independent of the hidden path and HMM parameters, so its probability contributes no parameter-dependent factor to the likelihood.

Definition: For a missing observation, define its emission likelihood factor to be \(b_i(*)=1\) for every state \(i\). This is the sum of the probabilities of all possible categories, \(\sum_{y\in\mathcal C}b_i(y)=1\); the symbol \(*\) is not an additional category in the emission distribution.

Write \(g_t(i)=b_i(y_t)\) if \(y_t\) is observed and \(g_t(i)=1\) if it is missing. The forward message \(\alpha_t(i)\) is the joint probability of the observations through time \(t\) and \(Z_t=i\), with missing times contributing no observed category. The backward message \(\beta_t(i)\) is the likelihood of the observations after time \(t\), conditional on \(Z_t=i\).

Theorem (Forward-backward recursions with missing observations): Under the HMM assumptions above, \(\alpha_1(i)=\pi_i g_1(i)\), \(\alpha_t(j)=g_t(j)\sum_{i\in S}\alpha_{t-1}(i)a_{ij}\) for \(t\ge2\), and the observed-data likelihood is \(L=\sum_{i\in S}\alpha_T(i)\). Also, \(\beta_T(i)=1\) and \(\beta_t(i)=\sum_{j\in S}a_{ij}g_{t+1}(j)\beta_{t+1}(j)\). When \(L>0\), the smoothed state probabilities and adjacent-state transition probabilities are \(\gamma_t(i)=\mathbb P(Z_t=i\mid\text{observed data})=\alpha_t(i)\beta_t(i)/L\) and \(\xi_t(i,j)=\mathbb P(Z_t=i,Z_{t+1}=j\mid\text{observed data})=\alpha_t(i)a_{ij}g_{t+1}(j)\beta_{t+1}(j)/L\).

Proof. For any hidden path \(z_{1:T}\), its joint probability with the observed data, up to the parameter-free missingness mechanism, is \(\pi_{z_1}g_1(z_1)\prod_{t=2}^T a_{z_{t-1}z_t}g_t(z_t)\). For \(t=1\), summing this expression over paths of length one ending at \(i\) gives \(\alpha_1(i)=\pi_i g_1(i)\). Suppose the forward message sums the path weights through \(t-1\), grouped by the state at \(t-1\). To extend a path ending at \(i\) to state \(j\), multiply its weight by \(a_{ij}g_t(j)\); summing over \(i\) gives the stated recursion. Summing over the final state sums the weight of every path exactly once, so \(L=\sum_i\alpha_T(i)\). For the backward recursion, conditional on \(Z_t=i\), the next state is \(j\) with probability \(a_{ij}\), the observation factor at \(t+1\) is \(g_{t+1}(j)\), and the remaining likelihood is \(\beta_{t+1}(j)\); summing over \(j\) gives the formula, with terminal value one because no observations follow \(T\). Finally, the total joint weight of paths with \(Z_t=i\) is \(\alpha_t(i)\beta_t(i)\). The total weight with \(Z_t=i,Z_{t+1}=j\) is \(\alpha_t(i)a_{ij}g_{t+1}(j)\beta_{t+1}(j)\). Dividing each by the positive total weight \(L\) gives the two conditional probabilities. \(\square\)

At a missing time \(t\), the factor \(g_t(i)=1\) leaves the state’s forward prediction unchanged. It does not make \(\gamma_t(i)\) undefined or eliminate the transitions into and out of that time. In particular, the transition posterior \(\xi_t\) uses the emission factor at time \(t+1\), not at time \(t\). This indexing matters when one endpoint of a transition is missing.

Worked Example: A Missing Final Observation

Consider two states \(S=\{1,2\}\), with initial distribution \(\pi=(\tfrac12,\tfrac12)\), and transition matrix \(A=\begin{bmatrix}\tfrac34&\tfrac14\\[2pt]\tfrac14&\tfrac34\end{bmatrix}\). Each row sums to \(\tfrac34+\tfrac14=1\) or \(\tfrac14+\tfrac34=1\). The alphabet is \(\{A,B\}\), with emission rows \((\tfrac34,\tfrac14)\) in state 1 and \((\tfrac14,\tfrac34)\) in state 2; each row sums to one. Observe category \(A\) at time 1 and no observation at time 2.

The initial forward values are \(\alpha_1(1)=\tfrac12\cdot\tfrac34=\tfrac38\) and \(\alpha_1(2)=\tfrac12\cdot\tfrac14=\tfrac18\). Since time 2 is missing, \(g_2(1)=g_2(2)=1\), and

$$ \alpha_2(1)=\tfrac38\cdot\tfrac34+\tfrac18\cdot\tfrac14=\tfrac{10}{32}=\tfrac5{16}, \qquad \alpha_2(2)=\tfrac38\cdot\tfrac14+\tfrac18\cdot\tfrac34=\tfrac6{32}=\tfrac3{16}. $$

Thus \(L=\tfrac5{16}+\tfrac3{16}=\tfrac12\), the probability of the observed category \(A\) at time 1. The check is that the probabilities at time 2 sum to the same likelihood: \(\tfrac5{16}+\tfrac3{16}=\tfrac12\). The missing final observation adds no information and no likelihood penalty.

Expected Counts for Categorical Training

For a single sequence, define the expected transition count from \(i\) to \(j\) by \(N_{ij}=\sum_{t=1}^{T-1}\xi_t(i,j)\). Define the expected emission count for category \(y\) in state \(i\) by \(C_i(y)=\sum_{t:\,y_t\text{ observed}}\gamma_t(i)\mathbf 1_{\{y_t=y\}}\). The emission sum includes observed times only; a missing time contributes no category count. By contrast, every adjacent pair of hidden states contributes a transition posterior, including transitions into and out of missing times.

Theorem (Expected counts and categorical M-step): If \(L>0\), \(N_{ij}\) and \(C_i(y)\) are the conditional expectations of the corresponding complete-data transition and emission indicators given the observations. Maximizing the expected complete-data log likelihood over each transition row and emission row gives \(a_{ij}^{\mathrm{new}}=N_{ij}/\sum_k N_{ik}\) when \(\sum_kN_{ik}>0\), and \(b_i^{\mathrm{new}}(y)=C_i(y)/\sum_{v\in\mathcal C}C_i(v)\) when the emission denominator is positive. If a denominator is zero, that row contributes no parameter-dependent term to the expected complete-data log likelihood, so any probability row maximizes it.

Proof. The complete-data transition log likelihood contains \(\sum_{t=1}^{T-1}\log a_{Z_tZ_{t+1}}\). Its conditional expectation given the observations is \(\sum_{i,j}N_{ij}\log a_{ij}\), because \(\xi_t(i,j)\) is the conditional probability of the indicator of the transition \(i\to j\). The complete-data emission log likelihood is \(\sum_{t:\,y_t\text{ observed}}\log b_{Z_t}(y_t)\); its conditional expectation is \(\sum_{i,y}C_i(y)\log b_i(y)\), by the definition of \(\gamma_t(i)\). For a transition row with total \(n_i=\sum_jN_{ij}>0\), put \(q_j=N_{ij}/n_i\). For any candidate probability row \(r\), the row contribution is \(n_i\sum_{j:q_j>0}q_j\log r_j\). Since \(\log x\le x-1\) for \(x>0\), if any \(r_j=0\) with \(q_j>0\) the contribution is negative infinity; otherwise \(\sum_{j:q_j>0}q_j\log(r_j/q_j)\le\sum_{j:q_j>0}q_j(r_j/q_j-1)=\sum_{j:q_j>0}r_j-1\le0\). So the contribution is at most \(n_i\sum_jq_j\log q_j\), attained by \(r_j=q_j\), which proves the transition update. Applying the same argument to the emission row with \(q_y=C_i(y)/\sum_v C_i(v)\) proves its update. If the relevant total is zero, every count in that row is zero and its contribution is zero for every probability row. \(\square\)

Worked Example: Forward-Backward Counts With a Missing Middle Observation

Use \(S=\{1,2\}\), \(\pi=(\tfrac12,\tfrac12)\), and \(A=\begin{bmatrix}\tfrac34&\tfrac14\\[2pt]\tfrac14&\tfrac34\end{bmatrix}\). Both transition rows sum to one. Let the emission rows for categories \(A,B\) be \((\tfrac34,\tfrac14)\) and \((\tfrac14,\tfrac34)\); each sums to one. The observed sequence is \(A,*,B\), with the middle observation missing.

The first forward vector is \((\tfrac38,\tfrac18)\). At the missing time it becomes \((\tfrac5{16},\tfrac3{16})\), as the transition calculation in the previous example shows. Predicting the state at time 3 gives \((\tfrac9{32},\tfrac7{32})\); multiplying by the \(B\) emission probabilities gives \(\alpha_3=(\tfrac9{128},\tfrac{21}{128})\). Hence \(L=\tfrac{30}{128}=\tfrac{15}{64}\).

The backward values are \(\beta_3=(1,1)\), then \(\beta_2=(\tfrac38,\tfrac58)\), because the next observation is \(B\). One more step gives \(\beta_1=(\tfrac7{16},\tfrac9{16})\). Dividing \(\alpha_t(i)\beta_t(i)\) by \(L=\tfrac{15}{64}\) yields \(\gamma_1=(\tfrac7{10},\tfrac3{10})\), \(\gamma_2=(\tfrac12,\tfrac12)\), and \(\gamma_3=(\tfrac3{10},\tfrac7{10})\). Each vector sums to one.

For the transition from time 1 to 2, the four \(\xi_1(i,j)\) values, in row order, are \(\tfrac9{20},\tfrac14,\tfrac1{20},\tfrac14\). For example, \(\xi_1(1,1)=(\tfrac38)(\tfrac34)(\tfrac38)/(\tfrac{15}{64})=\tfrac9{20}\); the other entries follow by the same substitution into the proved formula. For the transition from time 2 to 3, they are \(\tfrac14,\tfrac14,\tfrac1{20},\tfrac9{20}\). Each matrix sums to one. The first matrix has row sums \((\tfrac7{10},\tfrac3{10})=\gamma_1\) and column sums \((\tfrac12,\tfrac12)=\gamma_2\); the second has row sums \(\gamma_2\) and column sums \(\gamma_3\).

Adding the two matrices gives expected transition counts \(N_{11}=\tfrac7{10}\), \(N_{12}=\tfrac12\), \(N_{21}=\tfrac1{10}\), and \(N_{22}=\tfrac7{10}\). The transition update is therefore row 1: \((\tfrac7{10},\tfrac12)/(\tfrac7{10}+\tfrac12)=(\tfrac7{12},\tfrac5{12})\); row 2: \((\tfrac1{10},\tfrac7{10})/(\tfrac1{10}+\tfrac7{10})=(\tfrac18,\tfrac78)\). For emissions, only times 1 and 3 count. The counts are \(C_1(A)=\tfrac7{10}\), \(C_1(B)=\tfrac3{10}\), \(C_2(A)=\tfrac3{10}\), and \(C_2(B)=\tfrac7{10}\), giving updated emission rows \((\tfrac7{10},\tfrac3{10})\) and \((\tfrac3{10},\tfrac7{10})\). Each updated row sums to one. The absent middle category contributes no emission count, although both transitions through its hidden state are included.

Worked Example: A Sequence With No Observed Categories

Take two states, initial distribution \((\tfrac12,\tfrac12)\), and transition matrix \(A=\begin{bmatrix}\tfrac34&\tfrac14\\[2pt]\tfrac14&\tfrac34\end{bmatrix}\), whose rows each sum to one. Consider \(T=3\) with all three observations missing. Every path has emission factor one, so \(L=1\), since summing the probabilities of all hidden paths gives one.

The state distribution remains \((\tfrac12,\tfrac12)\) at every time: multiplying it by \(A\) gives first component \(\tfrac12\cdot\tfrac34+\tfrac12\cdot\tfrac14=\tfrac12\), and second component \(\tfrac12\cdot\tfrac14+\tfrac12\cdot\tfrac34=\tfrac12\). Consequently each adjacent transition posterior is \(\tfrac12 A\), with entries \((\tfrac38,\tfrac18;\tfrac18,\tfrac38)\). Across the two transitions, the expected counts are \(N_{11}=\tfrac34\), \(N_{12}=\tfrac14\), \(N_{21}=\tfrac14\), and \(N_{22}=\tfrac34\). The row totals are one, so the transition update returns the original rows \((\tfrac34,\tfrac14)\) and \((\tfrac14,\tfrac34)\).

There are no emission counts: \(C_i(y)=0\) for every state and category. Thus each emission row is unconstrained by this sequence’s expected complete-data log likelihood and must not be computed by dividing by zero. Any probability row maximizes that term. This example checks both the likelihood boundary case and the zero-denominator rule.

Why the Missing-Time Convention Matters

A common error is to delete a missing time point and connect the observed times with only one transition. In the middle-missing example, that incorrect calculation takes \(\alpha_1=(\tfrac38,\tfrac18)\), multiplies by \(A\) just once, and applies the \(B\) emission immediately. It obtains \((\tfrac5{16})(\tfrac14)+(\tfrac3{16})(\tfrac34)=\tfrac{14}{64}=\tfrac7{32}\). The correct calculation includes the transition into time 2 and the transition from time 2 to time 3, and gives \(L=\tfrac{15}{64}\). The hidden chain advances at every time, whether or not an emission is recorded.

Similarly, treating missingness as a new observed category would incorrectly multiply by an emission probability for that symbol and would change the model. The right factor is one in every state, obtained by summing over all possible unobserved categories. If the probability of a value being missing depends on the hidden state or on unknown HMM parameters, this convention alone is not sufficient: the missingness mechanism must be included in the likelihood. Under the stated ignorable-pattern assumption, the practical rules are concise: retain every hidden time point, use a unit emission factor at missing times, include every adjacent transition in \(\xi_t\), and count emissions only where categories were observed.

Check Your Understanding

Use the forward-backward and expected-count formulas to answer these questions.

  1. Why is the likelihood factor for a missing categorical observation one, rather than an extra emission probability?
  2. If time \(t\) is missing, which transition posteriors still contribute to the expected transition counts?
  3. For the sequence \(A,*,B\) above, verify that the column sums of \(\xi_1\) equal \(\gamma_2\).
  4. What happens to a categorical emission update when a state has zero total expected observed-emission count?
  5. Give the assumption on the missingness pattern needed for the likelihood calculation in this tutorial to apply without modeling missingness explicitly.

Previous

Next

Back to Tutorials