Hidden Markov Models

A Markov chain observed only through noisy signals, and the three computations that make it usable. The model and its likelihood as a sum over every path of hidden states; the moments and autocorrelation it implies; the forward algorithm, which computes the likelihood in time proportional to the length of the series times the square of the number of states, and the backward algorithm, with the posterior probabilities of each hidden state; Viterbi decoding, proved optimal as dynamic programming; scaling and logarithms against underflow; and Baum–Welch fitting, whose updates are derived as an EM algorithm. On Iowa's weekly deaths, 2014 to 2019, a two-state Poisson model finds a high and a low season, fits far better than a Poisson or negative binomial model, and its decoded high weeks fall in winter, with longer decoded seasons in later years that are consistent with a trend the model does not include; simulations from the fitted model measure decoding accuracy, parameter recovery and local maxima. Worked problems on a three-week forward and Viterbi computation in exact fractions, a decoded path that cannot occur, and the autocorrelation the model implies.

Iowa recorded between 465 and 734 deaths from all causes in each of the 313 weeks from January 2014 to December 2019. The counts rise every winter and fall every summer, and they vary far more than a Poisson count with the same mean would: their variance is 3.84 times their mean. One explanation is that the state's weeks are of two kinds, a high season and a low season, that no record marks which kind each week was, and that the kind of week persists, so that a high week is usually followed by another. Can a model built on that explanation find the seasons from the counts alone, and does it describe the series better than a single distribution with extra variance? It does both, within limits. Without being told the calendar, a two-state model puts 91 of the 104 weeks of December to March in its high season, and its log-likelihood exceeds that of a negative binomial model by 59.37; but it appears also to fold a six-year rise in deaths into its seasons, and it cannot represent a cycle of fixed length.

A hidden Markov model is a Markov chain whose states are not observed. At each time the chain is in some hidden state, and what is observed is a random signal whose distribution depends on that state alone. Here the hidden state is the season of the week, the chain says how seasons follow one another, and the signal is the week's count of deaths, a Poisson count with a rate that depends on the season. Three computations make such a model usable, and Rabiner (1989) organized the subject around them: the likelihood of the observations, the most probable sequence of hidden states, and the fitting of the parameters. This article derives all three.

Here is the route. First the model, its likelihood as a sum over every possible sequence of hidden states, and what it implies for the mean, variance and autocorrelation of the counts. Then the forward algorithm, which computes the likelihood without the sum's exponential cost, and the backward algorithm, which gives the probability of each hidden state given all the data. Then Viterbi decoding, the most probable sequence of states, proved optimal as dynamic programming. Then scaling, without which none of this runs on a real series. Then Baum–Welch fitting, derived as an EM algorithm. Finally the Iowa series, and simulations from the fitted model that measure what can be recovered. The article assumes Markov Chains and Stationary Distributions and The EM Algorithm, which proves that each iteration of the fitting cannot lower the likelihood.

The model

The hidden states are $Z_1, Z_2, \ldots, Z_T$, each in $\{1, \ldots, K\}$. They form a Markov chain with initial distribution $\mu$ (a row vector, $\mu_k = P(Z_1 = k)$) and transition matrix $P = (p_{jk})$, as in Markov Chains and Stationary Distributions; there the letter $\pi$ is reserved for a stationary distribution, and so it is here. Rabiner (1989) writes $\pi$ for the initial distribution, $A$ for the transition matrix and $b_j$ for the emission distributions; we keep the unit's letters. The observations are $Y_1, \ldots, Y_T$. Given the whole sequence of hidden states, the observations are independent, and $Y_t$ has the emission distribution $f_k$ of the current state $k = Z_t$: a probability mass function for counts, a density for measurements. For the Iowa series the emissions are Poisson, $f_k(y) = e^{-\lambda_k}\lambda_k^y/y!$, with a rate $\lambda_k$ for each season. The parameters are collected as $\theta = (\mu, P, \lambda_1, \ldots, \lambda_K)$. (In The EM Algorithm the observed data are $\mathbf{x}$ and the missing data $\mathbf{z}$; here the observed series is $\mathbf{y} = (y_1, \ldots, y_T)$, keeping $X$ for the chains of the unit, and the missing data are the hidden states $\mathbf{z} = (z_1, \ldots, z_T)$.)

These two assumptions give the joint probability of a sequence of hidden states and a sequence of observations as one product:

$$p(\mathbf{z}, \mathbf{y}) = \mu_{z_1}f_{z_1}(y_1)\prod_{t=2}^{T}p_{z_{t-1}z_t}\,f_{z_t}(y_t). \qquad (1)$$

The first factor chooses the first state and its observation. Each later factor moves the chain one step and emits one observation. The likelihood is the probability of the observations alone, the sum of (1) over every sequence of hidden states:

$$L(\theta) = p(\mathbf{y}) = \sum_{z_1 = 1}^K\cdots\sum_{z_T = 1}^K p(\mathbf{z}, \mathbf{y}). \qquad (2)$$

That sum has $K^T$ terms. For two seasons and 313 weeks it is $2^{313}$, a number with 95 digits: about $10^{94}$ paths. Rabiner (1989, §III.A) makes the same point with five states and 100 observations, where direct evaluation would take on the order of $2 \cdot 100 \cdot 5^{100} \approx 10^{72}$ computations. Nobody could add them one by one. The forward algorithm below adds them in a way that costs, for two states, about $K^2 = 4$ multiplications and $K(K - 1) = 2$ additions per week, plus two multiplications by the emission probabilities.

The observations are not a Markov chain. The hidden states are, but the counts are not: the distribution of $Y_{t+1}$ given the past counts depends on all of them, because each past count carries information about the current hidden state. This is what lets the model describe dependence on the whole past using few parameters. The forward algorithm makes the dependence exact: it computes, week by week, the distribution of the hidden state given every count so far.

What the model implies for the counts

Before fitting anything, what kind of series does a two-state Poisson model produce? Here is the idea. Given the hidden states, a count is Poisson, so its variance equals its mean. Averaging over the hidden states adds the variation of the rate between seasons. Two counts at different times are independent given the states, so their covariance comes entirely from the covariance of their rates, which is the covariance of the hidden chain at two times.

Theorem 1 (moments of a stationary two-state Poisson model). Let the hidden chain have two states with $p_{12} = a$ and $p_{21} = b$, $0 < a + b < 2$, and start in its stationary distribution $\pi = \big(\frac{b}{a+b}, \frac{a}{a+b}\big)$. Let the emissions be Poisson with rates $\lambda_1$ and $\lambda_2$, and write $\Delta = \lambda_2 - \lambda_1$ and $\lambda = 1 - a - b$. Then for every $t$ and every $h \ge 1$,

$$E[Y_t] = \pi_1\lambda_1 + \pi_2\lambda_2, \qquad \operatorname{Var}(Y_t) = E[Y_t] + \Delta^2\pi_1\pi_2, \qquad \operatorname{Cov}(Y_t, Y_{t+h}) = \Delta^2\pi_1\pi_2\,\lambda^h.$$

Proof. Write $\Lambda_t = \lambda_{Z_t}$, the rate of the hidden state at time $t$. Given all the hidden states, $Y_t$ is Poisson with mean and variance $\Lambda_t$, and $Y_t$ and $Y_{t+h}$ are independent. The laws of total expectation, variance and covariance (Conditional Expectation and the Laws of Total Expectation and Variance) give $E[Y_t] = E[\Lambda_t]$, $\operatorname{Var}(Y_t) = E[\Lambda_t] + \operatorname{Var}(\Lambda_t)$ and $\operatorname{Cov}(Y_t, Y_{t+h}) = 0 + \operatorname{Cov}(\Lambda_t, \Lambda_{t+h})$. The chain is stationary, so $Z_t$ has distribution $\pi$ and $E[\Lambda_t] = \pi_1\lambda_1 + \pi_2\lambda_2$. Write $\Lambda_t = \lambda_1 + \Delta\,\mathbf{1}\{Z_t = 2\}$. Then $\operatorname{Var}(\Lambda_t) = \Delta^2\pi_2(1 - \pi_2) = \Delta^2\pi_1\pi_2$, and

$$\operatorname{Cov}(\Lambda_t, \Lambda_{t+h}) = \Delta^2\big[P(Z_t = 2, Z_{t+h} = 2) - \pi_2^2\big] = \Delta^2\pi_2\big[p_{22}^{(h)} - \pi_2\big].$$

Markov Chains and Stationary Distributions (Problem 3 of its worked problems) proves that $P^h = \mathbf{1}\pi + \frac{\lambda^h}{a+b}\begin{pmatrix} a & -a \\ -b & b\end{pmatrix}$, so $p_{22}^{(h)} - \pi_2 = \lambda^h\frac{b}{a+b} = \lambda^h\pi_1$. $\square$

Three consequences matter for Iowa. The variance exceeds the mean by $\Delta^2\pi_1\pi_2$, so the model is overdispersed, as the counts are. The autocorrelation $\rho(h) = \operatorname{Cov}(Y_t, Y_{t+h})/\operatorname{Var}(Y_t)$ is a constant times $\lambda^h$: it decays geometrically, at the rate of the hidden chain's second eigenvalue. And if $\Delta \ne 0$ and $\lambda > 0$, as for persistent seasons, it is positive at every lag. At an even lag such as 26 weeks, $\lambda^h \ge 0$ whatever $\lambda$, so no model of this form, persistent or not, produces the negative autocorrelation that a regular annual cycle has half a year apart. The Iowa section measures both consequences.

The forward algorithm

How can a sum of $K^T$ terms be computed in about $TK^2$ operations? Here is the idea. The terms share most of their factors. Group the paths by the state they occupy at time $t$: all paths that are in state $k$ at time $t$ continue in the same way, whatever they did before. So it is enough to carry forward, for each state, the total probability of the observations so far together with that state.

Define the forward variable

$$\alpha_t(k) = P(Y_1 = y_1, \ldots, Y_t = y_t,\ Z_t = k),$$

the probability of the first $t$ observations and of being in state $k$ at time $t$. (For densities read "joint density" for "probability" throughout; every step below is the same.)

Theorem 2 (forward algorithm). $\alpha_1(k) = \mu_kf_k(y_1)$, and for $t = 1, \ldots, T - 1$,

$$\alpha_{t+1}(k) = \Big[\sum_{j=1}^K\alpha_t(j)\,p_{jk}\Big]f_k(y_{t+1}). \qquad (3)$$

The likelihood is $L(\theta) = \sum_{k=1}^K\alpha_T(k)$. Computing it this way takes about $K$ multiplications for each new state and $K^2$ for each $t$, in all of the order of $TK^2$ operations.

Proof. By (1) summed over the states after time $t$ (each later factor is a probability distribution over the next state and observation, which sums to 1 over them), $P(y_1, \ldots, y_t, z_1, \ldots, z_t) = \mu_{z_1}f_{z_1}(y_1)\prod_{s=2}^tp_{z_{s-1}z_s}f_{z_s}(y_s)$. So $\alpha_t(k)$ is the sum of this product over $z_1, \ldots, z_{t-1}$ with $z_t = k$. For $t = 1$ there is nothing to sum, which is the first formula. For $t + 1$, the product for $z_1, \ldots, z_t, z_{t+1} = k$ is the product for $z_1, \ldots, z_t$ times $p_{z_tk}f_k(y_{t+1})$. Summing first over $z_1, \ldots, z_{t-1}$ with $z_t = j$ fixed gives $\alpha_t(j)p_{jk}f_k(y_{t+1})$, and then summing over $j$ gives (3). At $t = T$, summing $\alpha_T(k)$ over $k$ removes the last condition, which is (2). Each step computes $K$ values, each a sum of $K$ products, so $T$ steps cost of the order of $TK^2$. $\square$

These are equations (18) to (21) of Rabiner (1989), who cites papers of Baum and his coauthors for it. In matrix form (3) is $\alpha_{t+1} = (\alpha_tP)\,\mathrm{diag}(f(y_{t+1}))$: one step of the chain, as in Markov Chains and Stationary Distributions, followed by weighting each state by how well it explains the new observation. Dividing $\alpha_t$ by its sum gives the filtered distribution $P(Z_t = k \mid y_1, \ldots, y_t)$, the best current guess of the state from the data so far.

The backward algorithm and the posterior probability of each state

The forward variable uses the data up to time $t$. Which state was the chain in at time $t$, given all the data, including later observations? A week in early November with a moderate count looks different once we know that the following weeks were high. Here is the idea. The joint probability (1) splits at time $t$ into a factor for the past and a factor for the future, which meet only through $z_t$. The forward variable sums the past factor; a backward variable sums the future factor; their product, normalized, is the posterior.

Define the backward variable

$$\beta_t(j) = P(Y_{t+1} = y_{t+1}, \ldots, Y_T = y_T \mid Z_t = j),$$

with $\beta_T(j) = 1$, the posterior state probability $\gamma_t(k) = P(Z_t = k \mid \mathbf{y})$ and the posterior transition probability $\xi_t(j, k) = P(Z_t = j, Z_{t+1} = k \mid \mathbf{y})$.

Theorem 3 (backward algorithm and posteriors). For $t = T - 1, \ldots, 1$,

$$\beta_t(j) = \sum_{k=1}^K p_{jk}\,f_k(y_{t+1})\,\beta_{t+1}(k). \qquad (4)$$

For every $t$, $\alpha_t(k)\beta_t(k) = P(\mathbf{y}, Z_t = k)$, so $\sum_k\alpha_t(k)\beta_t(k) = L(\theta)$ at every $t$, and

$$\gamma_t(k) = \frac{\alpha_t(k)\beta_t(k)}{L(\theta)}, \qquad \xi_t(j, k) = \frac{\alpha_t(j)\,p_{jk}\,f_k(y_{t+1})\,\beta_{t+1}(k)}{L(\theta)}. \qquad (5)$$

Proof. Given $Z_t = j$, the future of the chain is a chain started at $j$ (Markov Chains and Stationary Distributions, Lemma 6, or directly from (1)), and the future observations depend on the future states only. So $\beta_t(j)$ is the sum over $z_{t+1}, \ldots, z_T$ of $\prod_{s=t+1}^{T}p_{z_{s-1}z_s}f_{z_s}(y_s)$ with $z_t = j$. Fix $z_{t+1} = k$: the first factor is $p_{jk}f_k(y_{t+1})$, and the sum of the rest over $z_{t+2}, \ldots, z_T$ is $\beta_{t+1}(k)$. Summing over $k$ gives (4). For the product, (1) with $z_t = k$ fixed is the product of the factors up to time $t$ and the factors after it. Summing over the earlier states gives $\alpha_t(k)$ times the later factors; summing over the later states then gives $\alpha_t(k)\beta_t(k) = P(\mathbf{y}, Z_t = k)$. Summing over $k$ gives $P(\mathbf{y}) = L(\theta)$, and dividing by it gives $\gamma_t$. For $\xi_t$, fix both $z_t = j$ and $z_{t+1} = k$: (1) splits into the factors up to $t$, the middle factor $p_{jk}f_k(y_{t+1})$, and the factors after $t + 1$, whose sums are $\alpha_t(j)$ and $\beta_{t+1}(k)$. $\square$

These are Rabiner's (1989) equations (23) to (27) and (37). Computing $\alpha$ forward and $\beta$ backward once each gives every $\gamma_t$ and $\xi_t$, again in time of the order of $TK^2$; the combination is called the forward–backward algorithm. Summing (5) over $k$ gives $\sum_k\xi_t(j, k) = \gamma_t(j)$, Rabiner's equation (38).

Viterbi decoding

The posteriors $\gamma_t$ say which state is most probable at each time separately. Is the sequence of those states the most probable sequence? Not necessarily, and it need not even be a possible sequence: when the chain cannot move from one state to another, the most probable state at time $t$ and at time $t + 1$ can be such a pair (Problem 3 below constructs one). Rabiner (1989, §III.B) gives this as the reason to look for the single best sequence instead, the one that maximizes $P(\mathbf{z} \mid \mathbf{y})$, or equivalently $p(\mathbf{z}, \mathbf{y})$, since the two differ by the factor $L(\theta)$ that does not depend on $\mathbf{z}$. He cites Viterbi (1967) and Forney (1973) for the algorithm.

Here is the idea. The best path that ends in state $k$ at time $t + 1$ must reach $k$ from some state $j$ at time $t$, and the part of it up to time $t$ must be the best path ending in $j$: if a better one existed, swapping it in would improve the whole path, because the factors after time $t$ depend on the earlier states only through $j$. So it is enough to carry forward, for each state, the probability of the best path ending there and the state it came from. This is the forward algorithm with each sum replaced by a maximum.

Define $\delta_t(k) = \max_{z_1, \ldots, z_{t-1}}P(z_1, \ldots, z_{t-1}, Z_t = k, y_1, \ldots, y_t)$, the largest joint probability of a path ending in $k$ at time $t$ with the first $t$ observations, and the back-pointer $\psi_{t+1}(k)$, a state $j$ that attains the maximum in (6).

Theorem 4 (Viterbi algorithm). $\delta_1(k) = \mu_kf_k(y_1)$, and

$$\delta_{t+1}(k) = \Big[\max_j\delta_t(j)\,p_{jk}\Big]f_k(y_{t+1}), \qquad \psi_{t+1}(k) \in \arg\max_j\delta_t(j)\,p_{jk}. \qquad (6)$$

Let $z_T^* \in \arg\max_k\delta_T(k)$ and, for $t = T - 1, \ldots, 1$, $z_t^* = \psi_{t+1}(z_{t+1}^*)$. Then $\mathbf{z}^* = (z_1^*, \ldots, z_T^*)$ maximizes $p(\mathbf{z}, \mathbf{y})$ over all sequences of hidden states, and $\max_{\mathbf{z}}p(\mathbf{z}, \mathbf{y}) = \max_k\delta_T(k)$.

Proof. Write $g_t(z_1, \ldots, z_t) = \mu_{z_1}f_{z_1}(y_1)\prod_{s=2}^tp_{z_{s-1}z_s}f_{z_s}(y_s)$, so $g_T = p(\mathbf{z}, \mathbf{y})$ by (1), and $\delta_t(k)$ is the maximum of $g_t$ over paths ending in $k$ (the joint probability in its definition is $g_t$, by the proof of Theorem 2). The recursion: $g_{t+1}(z_1, \ldots, z_t, k) = g_t(z_1, \ldots, z_t)\,p_{z_tk}f_k(y_{t+1})$, and all factors are nonnegative. Maximize first over $z_1, \ldots, z_{t-1}$ with $z_t = j$ fixed: the maximum is $\delta_t(j)p_{jk}f_k(y_{t+1})$, because multiplying by the nonnegative constant $p_{jk}f_k(y_{t+1})$ preserves the maximizer. Then maximize over $j$, which gives (6).

Optimality of the backtracked path: the claim is that $g_t(z_1^*, \ldots, z_t^*) = \delta_t(z_t^*)$ for every $t$, that is, the backtracked path up to $t$ is a best path ending in $z_t^*$. We prove it by induction upward in $t$. At $t = 1$ both sides are $\mu_{z_1^*}f_{z_1^*}(y_1)$. Suppose $g_t(z_1^*, \ldots, z_t^*) = \delta_t(z_t^*)$ for some $t$, where $z_t^* = \psi_{t+1}(z_{t+1}^*)$. Then

$$g_{t+1}(z_1^*, \ldots, z_{t+1}^*) = \delta_t(z_t^*)\,p_{z_t^*z_{t+1}^*}\,f_{z_{t+1}^*}(y_{t+1}) = \Big[\max_j\delta_t(j)\,p_{jz_{t+1}^*}\Big]f_{z_{t+1}^*}(y_{t+1}) = \delta_{t+1}(z_{t+1}^*),$$

using the choice of the back-pointer and (6). So $g_T(\mathbf{z}^*) = \delta_T(z_T^*) = \max_k\delta_T(k)$, which is the largest value of $g_T$ over all paths, since every path ends in some state $k$ and is then bounded by $\delta_T(k)$. $\square$

These are equations (30) to (35) of Rabiner (1989). The cost is the same as the forward algorithm's, plus $T$ steps of backtracking and the storage of $TK$ back-pointers. The two kinds of decoding answer different questions. The sequence of $\arg\max_k\gamma_t(k)$ maximizes the expected number of correctly decoded times: for any decoded sequence $\hat z_1, \ldots, \hat z_T$, that expected number given $\mathbf{y}$ is $\sum_tP(Z_t = \hat z_t \mid \mathbf{y}) = \sum_t\gamma_t(\hat z_t)$, which is largest when each term is. The Viterbi path maximizes the probability that the whole sequence is right. On Iowa the two differ in 1 week of 313.

Underflow, scaling and logarithms

Every forward variable is a product of $t$ probabilities, and a count's Poisson probability is small: for Iowa, the likelihood of the fitted two-state model is about $10^{-689}$. The smallest positive normalized number in double-precision arithmetic is about $10^{-308}$, and the smallest of all, counting the denormalized numbers, about $10^{-323}$. Run as written, the forward algorithm for Iowa returns exactly zero for every state from week 146 on, and every later quantity is meaningless. Rabiner (1989, §V.A) gives the remedy: rescale the forward variables, here at every step (he notes that scaling need not be applied at every time, only whenever necessary).

Theorem 5 (scaling). Let $\hat\alpha_1(k) = \alpha_1(k)/c_1$ with $c_1 = \sum_k\alpha_1(k)$, and for $t \ge 1$ let

$$\tilde\alpha_{t+1}(k) = \Big[\sum_j\hat\alpha_t(j)\,p_{jk}\Big]f_k(y_{t+1}), \qquad c_{t+1} = \sum_k\tilde\alpha_{t+1}(k), \qquad \hat\alpha_{t+1} = \tilde\alpha_{t+1}/c_{t+1}.$$

Then $\hat\alpha_t(k) = \alpha_t(k)/(c_1\cdots c_t) = P(Z_t = k \mid y_1, \ldots, y_t)$, $c_t = P(Y_t = y_t \mid y_1, \ldots, y_{t-1})$ (for $t = 1$, $c_1 = P(Y_1 = y_1)$), and

$$L(\theta) = \prod_{t=1}^Tc_t, \qquad \ln L(\theta) = \sum_{t=1}^T\ln c_t.$$

With backward variables scaled by the same factors, $\hat\beta_T = 1$ and $\hat\beta_t(j) = \sum_kp_{jk}f_k(y_{t+1})\hat\beta_{t+1}(k)/c_{t+1}$, one has $\hat\beta_t = \beta_t/(c_{t+1}\cdots c_T)$ and $\gamma_t(k) = \hat\alpha_t(k)\hat\beta_t(k)$.

Proof. By induction, $\hat\alpha_t = \alpha_t/(c_1\cdots c_t)$: it holds at $t = 1$, and if it holds at $t$, then (3) is linear in $\alpha_t$, so $\tilde\alpha_{t+1} = \alpha_{t+1}/(c_1\cdots c_t)$, and dividing by $c_{t+1}$ gives the claim. Each $\hat\alpha_t$ sums to 1 by construction, so $c_1\cdots c_t = \sum_k\alpha_t(k) = P(y_1, \ldots, y_t)$ and $\hat\alpha_t(k) = P(y_1, \ldots, y_t, Z_t = k)/P(y_1, \ldots, y_t)$, the filtered probability. The ratio of consecutive products is $c_t = P(y_1, \ldots, y_t)/P(y_1, \ldots, y_{t-1})$, the predictive probability; at $t = T$ the product is $L(\theta)$. For the backward variables the same induction, downward from $T$ with (4), gives $\hat\beta_t = \beta_t/(c_{t+1}\cdots c_T)$. Then $\hat\alpha_t(k)\hat\beta_t(k) = \alpha_t(k)\beta_t(k)/(c_1\cdots c_T) = \alpha_t(k)\beta_t(k)/L(\theta) = \gamma_t(k)$ by Theorem 3. $\square$

The scaled quantities stay between 0 and 1, and the log-likelihood is a sum of $T$ moderate logarithms. Rabiner (1989, eqs. 91 to 103) derives the same scaling, with his $c_t$ the reciprocal of ours, so that his eq. 103 reads $\log P = -\sum_t\log c_t$. The script also shifts each week's log emission probabilities by their maximum over states before exponentiating, a constant per week that cancels in $\hat\alpha$ and is added back to $\ln L$, as a precaution for rates far from the counts. For Viterbi decoding no rescaling is needed: maxima of products are maxima of sums of logarithms, so (6) is run as $\ln\delta_{t+1}(k) = \max_j[\ln\delta_t(j) + \ln p_{jk}] + \ln f_k(y_{t+1})$, as Rabiner (1989, eqs. 104 and 105) does.

Baum–Welch: fitting by EM

The parameters are unknown. How can they be estimated when the hidden states, which would make estimation easy, are not observed? If the states were known, each transition probability would be estimated by counting transitions, and each rate by the mean count in its state. The Baum–Welch algorithm replaces the unknown counts by their expected values given the data, computed by the forward–backward algorithm, re-estimates, and repeats. It is the EM algorithm of The EM Algorithm for this model. Rabiner (1989, §III.C) presents the re-estimation formulas as "essentially identical to the EM steps for this particular problem" and says that it "has been proven by Baum and his colleagues" that they lead to a model under which the observations are at least as likely, citing at that point Baum and Sell (1968) and Baker (1975).

The E step. By (1), the complete-data log-likelihood is

$$\ln p(\mathbf{z}, \mathbf{y}; \theta) = \sum_k\mathbf{1}\{z_1 = k\}\ln\mu_k + \sum_{t=1}^{T-1}\sum_{j,k}\mathbf{1}\{z_t = j, z_{t+1} = k\}\ln p_{jk} + \sum_{t=1}^T\sum_k\mathbf{1}\{z_t = k\}\ln f_k(y_t).$$

It is linear in the indicators. Their conditional expectations given $\mathbf{y}$ under the current parameters $\theta'$ are $\gamma_t(k)$ and $\xi_t(j, k)$ of Theorem 3, computed at $\theta'$. So the function that EM maximizes, $Q(\theta; \theta') = E_{\theta'}[\ln p(\mathbf{Z}, \mathbf{y}; \theta) \mid \mathbf{y}]$ in the notation of The EM Algorithm, is

$$Q(\theta; \theta') = \sum_k\gamma_1(k)\ln\mu_k + \sum_{j,k}\Big[\sum_{t=1}^{T-1}\xi_t(j, k)\Big]\ln p_{jk} + \sum_k\sum_{t=1}^T\gamma_t(k)\ln f_k(y_t). \qquad (7)$$

Theorem 6 (the M step). Over initial distributions $\mu$, stochastic matrices $P$ and positive Poisson rates, (7) is maximized by

$$\mu_k = \gamma_1(k), \qquad p_{jk} = \frac{\sum_{t=1}^{T-1}\xi_t(j, k)}{\sum_{t=1}^{T-1}\gamma_t(j)}, \qquad \lambda_k = \frac{\sum_{t=1}^T\gamma_t(k)\,y_t}{\sum_{t=1}^T\gamma_t(k)}. \qquad (8)$$

Each iteration of (8) with the $\gamma$ and $\xi$ of the current parameters does not lower the likelihood.

Proof. The three groups of parameters appear in separate terms of (7), so each term can be maximized alone. The first term and, for each $j$, the part of the second with first index $j$ have the form $\sum_kc_k\ln q_k$ with nonnegative weights $c_k$ and $q$ ranging over probability vectors. Write $C = \sum_kc_k$ and $\hat q_k = c_k/C$. Then $\sum_kc_k\ln q_k - \sum_kc_k\ln\hat q_k = -C\sum_k\hat q_k\ln(\hat q_k/q_k) \le 0$, by the nonnegativity of the Kullback–Leibler divergence (Cross-Entropy and Kullback–Leibler Divergence), so $q = \hat q$ is a maximizer. For the first term $c_k = \gamma_1(k)$ with $C = 1$. For row $j$, $c_k = \sum_t\xi_t(j, k)$ with $C = \sum_t\gamma_t(j)$ by Rabiner's equation (38), $\sum_k\xi_t(j, k) = \gamma_t(j)$. For the rates, the third term is $\sum_k\sum_t\gamma_t(k)[y_t\ln\lambda_k - \lambda_k] + $ (terms free of $\lambda$), whose derivative in $\lambda_k$, $\sum_t\gamma_t(k)[y_t/\lambda_k - 1]$, is zero at the value in (8) and decreasing in $\lambda_k$, so that value is the maximum. That no iteration lowers the likelihood is Theorem 1 of The EM Algorithm, which needs only that the new parameters do not lower $Q$. $\square$

The updates are Rabiner's (1989) equations (40a) to (40c) with Poisson emissions in place of his discrete symbols: expected transitions from $j$ to $k$ over expected visits to $j$, and the expected-weight average of the counts in each state.

Proposition 1 (the fitted initial distribution sits on one state). For fixed $P$ and rates, the likelihood is $L = \sum_k\mu_kf_k(y_1)\beta_1(k)$, a linear function of $\mu$, so its maximum over initial distributions is attained at a single state: $\mu$ puts probability 1 on a state $k$ with the largest $f_k(y_1)\beta_1(k)$.

Proof. $L = \sum_k\alpha_1(k)\beta_1(k)$ by Theorem 3 at $t = 1$, and $\alpha_1(k) = \mu_kf_k(y_1)$. A linear function on the set of probability vectors is a weighted average of its values at the vertices, so it is largest at a vertex. $\square$

So the maximum likelihood estimate of $\mu$ from a single series is degenerate, and the iteration (8) moves toward it. That is no defect: one series contains one first state. When the first state is of no interest, $\mu$ can instead be fixed at the stationary distribution of $P$, at the cost of an M step without the closed form (8).

Local maxima. Theorem 6 guarantees that the likelihood never falls; it does not guarantee the largest maximum. The EM Algorithm shows where the iteration can stop. Rabiner (1989, p. 265) is blunt: "the forward-backward algorithm leads to local maxima only, and that in most problems of interest, the optimization surface is very complex and has many local maxima." The standard response, used below, is to start from many random parameter values and keep the best result.

Iowa's weekly deaths

The data are the weekly counts of deaths from all causes in Iowa from the week ending January 4, 2014, to the week ending December 28, 2019, from the National Center for Health Statistics (2021), as used by Overdispersion in Count Data and Resampling Dependent and Clustered Data. There are 313 weeks with mean 570.52 deaths, from the fewest, 465, to the most, 734. A Poisson model fits one rate to all weeks. A negative binomial model with mean 570.52 and shape 203.5 (variance $\mu + \mu^2/k$) allows extra variance but no memory. The hidden Markov models allow both. The script fits Poisson hidden Markov models with two and three states by Baum–Welch from 20 random starting values each, run until an iteration raises the log-likelihood by less than $10^{-9}$, and checks at every iteration that the log-likelihood does not fall.

Model Parameters Log-likelihood AIC BIC
Poisson 1 −1,877.08 3,756.2 3,759.9
Negative binomial 2 −1,645.65 3,295.3 3,302.8
Poisson HMM, 2 states 5 −1,586.28 3,182.6 3,201.3
Poisson HMM, 3 states 11 −1,543.10 3,108.2 3,149.4

The parameters of the two-state model are two rates, two free transition probabilities and one free initial probability; the three-state model has three rates, six transition probabilities and two initial probabilities. All 20 of 20 random starts reached the same maximum for two states, and 20 of 20 for three. The two-state model, with three more parameters than the negative binomial, raises the log-likelihood by 59.37, and both criteria of Akaike's Information Criterion, Derived and The Bayesian Information Criterion and the Laplace Approximation prefer it; both prefer three states to two. A comparison of different numbers of states is a comparison in which the smaller model is the larger one with a state removed, a boundary case for the large-sample theory behind both criteria, so we read these differences as descriptions of fit, not as tests.

The two seasons. The fitted rates are 539.1 deaths a week in the low state and 611.2 in the high state. The chain leaves the low state with probability 0.0575 a week and the high state with probability 0.0750, so a low season lasts $1/0.0575 = 17.4$ weeks on average and a high season 13.3 weeks (the number of weeks in a state is geometric, as Problem 3 of Markov Chains and Stationary Distributions notes). In the long run the high state holds a share of 0.434 of the weeks. As Proposition 1 predicts, the fitted initial distribution puts probability 1 on state 2, the high state, for the first week, January 4, 2014.

Decoded against the calendar. The Viterbi path puts 137 weeks in the high regime. Of the 104 weeks ending in December to March, 91 are high; of the weeks ending in June to August, 2 are. The high regime comes in 10 spells, of which 7 last four weeks or more, one per winter:

High spell begins Weeks
January 4, 2014 8
November 15, 2014 23
January 2, 2016 9
November 26, 2016 24
November 4, 2017 27
September 29, 2018 30
October 5, 2019 13

(The first spell begins with the data, and the last ends with them.) The other three spells are single weeks. The decoding is confident for most weeks: the largest posterior probability $\gamma_t(k)$ is below 0.9 in 28 weeks, 18 of them within two weeks of a change of state on the Viterbi path, and the Viterbi path and the sequence of most probable states differ in 1 week.

What the model misses. The long spells of the later winters, 24, 27 and 30 weeks against 23 and 9 in the second and third (the first, 8 weeks, is cut off by the start of the data), are consistent with a trend. The mean weekly count was 553.7, 563.0, 560.7, 579.4, 579.1 and 587.5 in the six years, and the high weeks per calendar year were 15, 17, 16, 27, 32 and 30. With fixed rates, a rising baseline would push weeks that would have been low in 2014 into the high regime later. The low-regime weeks themselves average 534.9, 536.3, 540.3, 534.6, 533.5 and 556.4 deaths in the six years: flat until 2019, which is what a baseline rising into the high regime would also produce, so this neither shows nor rules out the explanation. The model cannot separate a rising baseline from longer seasons. Within the decoded regimes the counts are still overdispersed: variance over mean is 1.42 in the low regime and 1.75 in the high one, against 1 for a Poisson count. The three-state model splits off a peak state with rate 657.1 (the other two rates are 535.8 and 594.9), which holds 25 weeks, all in winter; the winter of 2017 to 2018 has the most of them, 10.

The autocorrelation the model implies. Theorem 1 with the fitted values gives a stationary mean of 570.4, close to the sample mean, an implied standard deviation of 43.0 against a sample standard deviation of 46.8, and a hidden chain whose second eigenvalue is $1 - p_{12} - p_{21} = 0.867$ (from the unrounded estimates 0.05751 and 0.07504). The implied lag 1 autocorrelation is 0.60. The sample autocorrelation of the 313 weeks at lag 1 is 0.66 (the script computes it with divisor $n$, as Autocorrelation and Stationarity and Resampling Dependent and Clustered Data do). At 26 weeks the implied autocorrelation is 0.02, positive as Theorem 1 says it must be, while the sample autocorrelation at lag 26 is −0.52: half a year after a winter week comes a summer week. A two-state chain with geometric sojourns describes persistence but not a cycle of fixed length. Autocorrelation and Stationarity treats the series' autocorrelation and its annual cycle directly, and Autoregressive and Moving Average Models models what remains.

Example (a common misreading: "the model found the flu seasons"). The high state is a statistical regime: weeks whose counts are better explained by a rate near 611 than near 539. It coincides with winter because winter weeks have more deaths, and it absorbs whatever else raises the count, here probably the six-year rise in the yearly means. Nothing in the model refers to influenza, and the data contain only counts of all deaths. A claim about causes would need cause-specific counts or a model with covariates.

What can be recovered: simulations with known parameters

How much of this would the method recover if the model were true? The script simulates 313 weeks from the fitted two-state model, started in its stationary distribution, with 30 seeds. With the true parameters, Viterbi decoding gets a median 0.987 of the weeks right (interquartile range 0.981 to 0.990); decoding by the most probable state at each week, from the posterior, gets the same, 0.987 (0.981 to 0.990). Baum–Welch from 10 random starts per seed recovers the rates closely, 538.9 (538.2 to 539.9) and 611.9 (609.9 to 612.6) against 539.1 and 611.2. The switching probabilities are recovered less precisely, with median estimates 0.060 (0.040 to 0.077) and 0.072 (0.062 to 0.084) against 0.0575 and 0.0750: the model expects about 10 switches in each direction in 313 weeks, and each switching probability is estimated from those few. In all 30 seeds all 10 starts reached the same maximum.

The seasons of Iowa are far apart: their rates differ by 72.1 deaths a week, against a Poisson standard deviation within a season of about $\sqrt{570.52} = 23.9$. To see what happens when they are not, the script repeats the study with the high rate only 20 deaths above the low one and the same chain. Viterbi accuracy falls to a median 0.805 (0.765 to 0.847), and the estimated probability of leaving the low state spreads out, 0.057 (0.038 to 0.090). Local maxima appear: in 22 of the 30 seeds all 10 starts agreed, and in the others some starts stopped at a lower stationary point of the iteration, a local maximum or a flat region where it stalled, as much as 5.5 below the best log-likelihood. These are observations of these simulations, for this model and these 313 weeks.

What is proved here, what is cited, what the experiment shows

Proved here. The joint probability (1) and likelihood (2) from the model's two assumptions; the moments and autocorrelation of a stationary two-state Poisson model (Theorem 1), given the laws of total expectation, variance and covariance and the two-state $P^h$ of Markov Chains and Stationary Distributions; the forward algorithm and its cost (Theorem 2); the backward algorithm, the posterior state and transition probabilities (Theorem 3); the optimality of the Viterbi path (Theorem 4); scaling, with the filtered and predictive interpretations of the scaled quantities (Theorem 5); the M step of Baum–Welch (Theorem 6), given the nonnegativity of the Kullback–Leibler divergence; and the degeneracy of the fitted initial distribution (Proposition 1).

Cited. That no Baum–Welch iteration lowers the likelihood: Theorem 1 of The EM Algorithm, which proves it for every EM algorithm; Rabiner (1989) attributes the result for this model to "Baum and his colleagues", citing Baum and Sell (1968) and Baker (1975), which this article has not opened. The organization into three problems, the equation numbers, the scaling and logarithmic Viterbi, and the remark on local maxima, from Rabiner (1989). The Viterbi algorithm, cited to Viterbi (1967) and Forney (1973) as Rabiner cites it. The large-sample theory behind AIC and BIC, through the articles linked.

What the experiments show. The Iowa fits: log-likelihoods, criteria, the decoded seasons against the calendar, the longer decoded seasons of the later years and the yearly means that are consistent with a trend, the dispersion within the regimes, and the implied autocorrelation against the sample's. The simulations, 30 seeds of 313 weeks: decoding accuracy near 0.99 when the seasons are as far apart as Iowa's and near 0.8 when they are 20 deaths apart, recovery of rates and switching probabilities, and local maxima in the harder case. These are observations for these models and this length of series.

Worked problems

These problems were written for this article, on small exact cases and on the fitted Iowa model; the script checks each answer in exact fractions or to the digits shown.

Problem 1 (forward and backward by hand). A two-state model has states 1 (low) and 2 (high), $\mu = (\frac12, \frac12)$, $p_{11} = p_{22} = \frac34$, and two kinds of observation, "many" and "few", with $f_1(\text{many}) = \frac15$ and $f_2(\text{many}) = \frac45$. The observations are many, many, few. Find the likelihood and the posterior probability of the high state at each week.

Forward (Theorem 2): $\alpha_1 = (\frac12\cdot\frac15, \frac12\cdot\frac45) = (\frac1{10}, \frac25)$. Then $\alpha_2(1) = (\frac1{10}\cdot\frac34 + \frac25\cdot\frac14)\cdot\frac15 = \frac{7}{200}$ and $\alpha_2(2) = (\frac1{10}\cdot\frac14 + \frac25\cdot\frac34)\cdot\frac45 = \frac{13}{50}$. Then $\alpha_3(1) = (\frac{7}{200}\cdot\frac34 + \frac{13}{50}\cdot\frac14)\cdot\frac45 = 73/1000$ and $\alpha_3(2) = (\frac{7}{200}\cdot\frac14 + \frac{13}{50}\cdot\frac34)\cdot\frac15 = 163/4000$. The likelihood is $L = \frac{73}{1000} + \frac{163}{4000} = 91/800 = 0.1138$; the script confirms it by adding all eight paths of (2).

Backward (Theorem 3): $\beta_3 = (1, 1)$; $\beta_2(1) = \frac34\cdot\frac45 + \frac14\cdot\frac15 = \frac{13}{20}$ and $\beta_2(2) = \frac14\cdot\frac45 + \frac34\cdot\frac15 = \frac{7}{20}$; $\beta_1(1) = \frac34\cdot\frac15\cdot\frac{13}{20} + \frac14\cdot\frac45\cdot\frac{7}{20} = \frac{67}{400}$ and $\beta_1(2) = \frac14\cdot\frac15\cdot\frac{13}{20} + \frac34\cdot\frac45\cdot\frac{7}{20} = \frac{97}{400}$. As a check, $\sum_k\alpha_1(k)\beta_1(k) = \frac{67}{4000} + \frac{388}{4000} = \frac{455}{4000} = \frac{91}{800}$. The posteriors of the high state are $\gamma_1(2) = \frac{388/4000}{455/4000} = 0.853$, $\gamma_2(2) = \frac{(13/50)(7/20)}{91/800} = 0.800$ and $\gamma_3(2) = \frac{163/4000}{455/4000} = 0.358$. The first week alone would give the high state probability $\frac{2/5}{1/2} = 0.8$; the second "many" raises it to 0.853, through the persistence of the chain.

Problem 2 (Viterbi by hand). For the model and data of Problem 1, find the most probable sequence of hidden states and its share of the likelihood.

By (6): $\delta_1 = (\frac1{10}, \frac25)$. $\delta_2(1) = \max(\frac1{10}\cdot\frac34, \frac25\cdot\frac14)\cdot\frac15 = \frac1{10}\cdot\frac15 = \frac1{50}$ with back-pointer 2, and $\delta_2(2) = \max(\frac1{10}\cdot\frac14, \frac25\cdot\frac34)\cdot\frac45 = \frac{6}{25}$ with back-pointer 2. $\delta_3(1) = \max(\frac1{50}\cdot\frac34, \frac{6}{25}\cdot\frac14)\cdot\frac45 = \frac{6}{100}\cdot\frac45 = 6/125$ with back-pointer 2, and $\delta_3(2) = \max(\frac1{50}\cdot\frac14, \frac{6}{25}\cdot\frac34)\cdot\frac15 = \frac{9}{250}$. The larger is $\delta_3(1) = \frac{6}{125}$, and backtracking gives (high, high, low). This one path carries $\frac{6/125}{91/800} = 0.422$ of the likelihood; the other seven share the rest. Here the most probable states one week at a time from Problem 1 (high, high, low) agree with the Viterbi path.

Problem 3 (a decoded path that cannot happen). A chain has states A, B, C, with $\mu = (\frac25, \frac3{10}, \frac3{10})$, and moves A to A, B to C and C to C with probability 1. Two observations are made whose emission probabilities are the same in every state. Find the most probable state at each time and the most probable path.

The observations carry no information, so the posterior is the prior. The possible paths are (A, A), (B, C) and (C, C), with probabilities $\frac25$, $\frac3{10}$ and $\frac3{10}$. At time 1 the most probable state is A ($\frac25$). At time 2, C has probability $\frac3{10} + \frac3{10} = 0.6$ and A has $\frac25$, so the most probable state is C. The sequence (A, C) of the most probable states has probability 0, because the chain cannot move from A to C. The Viterbi path is (A, A), with probability $\frac25$. Maximizing each time separately and maximizing the whole path are different problems, as Rabiner (1989, §III.B) warns.

Problem 4 (the autocorrelation of the Iowa model). With the fitted two-state Iowa model, how strongly is a week's count correlated with the count a week later, and half a year later?

By Theorem 1, $\rho(h) = \Delta^2\pi_1\pi_2\lambda^h/(E[Y] + \Delta^2\pi_1\pi_2)$. With $\Delta = 611.2 - 539.1$, the stationary shares $0.566$ and $0.434$, and $\lambda = 0.867$: $\Delta^2\pi_1\pi_2$ is about 1,275, the variance is about $570.4 + 1{,}275$, so $\rho(1) = 0.60$ and $\rho(26) = 0.02$ (the script computes these from the unrounded estimates). Within a winter the counts are strongly correlated, through the persistence of the season. Half a year later the model has forgotten the season and predicts no correlation, while the data have a negative one, the signature of a fixed annual cycle that the hidden chain does not represent.

Summary

  • A hidden Markov model is a Markov chain of hidden states with observations independent given the states, each drawn from its state's emission distribution; its joint probability is the product (1), and its likelihood a sum over $K^T$ paths (2).
  • A stationary two-state Poisson model is overdispersed and has autocorrelation proportional to $\lambda^h$, positive at every lag when the states persist (Theorem 1).
  • The forward algorithm computes the likelihood in time of the order of $TK^2$ (Theorem 2); with the backward algorithm it gives every posterior state and transition probability (Theorem 3).
  • The Viterbi algorithm finds the most probable path by dynamic programming (Theorem 4); the sequence of individually most probable states can be impossible (Problem 3).
  • Scaling makes the computations run: $\ln L = \sum_t\ln c_t$ with $c_t$ the predictive probability of each observation (Theorem 5); Viterbi runs on logarithms.
  • Baum–Welch is EM: the M step re-estimates by expected counts (Theorem 6), the likelihood never falls, and only a local maximum is guaranteed; the fitted initial distribution sits on one state (Proposition 1).
  • On Iowa's weekly deaths, two seasons at 539.1 and 611.2 deaths a week, with mean sojourns of 17.4 and 13.3 weeks, fit far better than a Poisson or negative binomial model; 91 of the 104 weeks of December to March are decoded high; a fixed annual cycle, and apparently a trend, remain outside the model.

What we have learned

A hidden Markov model separates what persists, the hidden state, from what varies week to week, the count. Its three computations are all the same idea, splitting the sum or maximum over paths at each time because the past and future meet only through the current state. On Iowa's deaths the model finds the winters without being told the calendar, and its failures are informative: a hidden chain forgets, and a calendar does not.

What the hidden chain cannot express, a regular cycle and a trend, is the subject of the time-series articles. Autocorrelation and Stationarity defines the autocorrelation of a series in general, derives the variance of a mean under dependence and treats the annual cycle of the same Iowa counts, and Autoregressive and Moving Average Models fits linear models to what remains and forecasts with them.

References

  • Baker, J. K. (1975). The DRAGON system: An overview. IEEE Transactions on Acoustics, Speech, and Signal Processing, 23(1), 24–29. https://doi.org/10.1109/TASSP.1975.1162650 (cited as Rabiner, 1989, cites it; not opened) record
  • Baum, L. E., and Sell, G. R. (1968). Growth transformations for functions on manifolds (title as Crossref lists it; Rabiner's list gives "Growth functions for transformations on manifolds"). Pacific Journal of Mathematics, 27(2), 211–227. https://doi.org/10.2140/pjm.1968.27.211 (cited as Rabiner, 1989, cites it; not opened) record
  • Forney, G. D. (1973). The Viterbi algorithm. Proceedings of the IEEE, 61(3), 268–278. https://doi.org/10.1109/PROC.1973.9030 (cited as Rabiner, 1989, cites it) record
  • National Center for Health Statistics (2021). Weekly Counts of Deaths by State and Select Causes, 2014–2019. Centers for Disease Control and Prevention, data.cdc.gov dataset 3yf8-kanr. https://data.cdc.gov/d/3yf8-kanr record · 16 pages
  • Rabiner, L. R. (1989). A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2), 257–286. https://doi.org/10.1109/5.18626 (§III.A to §III.C, eqs. 18 to 40c; §V.A, eqs. 90 to 105) record
  • Viterbi, A. J. (1967). Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions on Information Theory, 13(2), 260–269. https://doi.org/10.1109/TIT.1967.1054010 (cited as Rabiner, 1989, cites it) record