Selecting the Number of Hidden States by Prediction

Why State Count Is a Predictive Choice

A hidden Markov model with more states can represent more patterns in a sequence, but added flexibility can also fit accidental features of the training data. The number of states is therefore not chosen by asking only which model achieves the largest likelihood on the data used to fit it. For a prediction-focused comparison, fit each candidate model on training sequences, then evaluate how well it assigns probability to separate held-out sequences.

Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space. In a candidate model with \(K\) hidden states, the hidden process \((X_t)_{t\ge1}\) has state space \(S=\{1,\ldots,K\}\) and discrete time \(t=1,\ldots,T\). The observations \((Y_t)_{t\ge1}\) take values in an alphabet \(\mathcal{A}\). The initial hidden-state distribution is the row vector \(\pi\); the transition matrix is \(P=(p_{ij})\), with nonnegative entries and each row summing to \(1\). In state \(i\), an observation \(y\) has probability \(b_i(y)\), where \(\sum_{y\in\mathcal{A}}b_i(y)=1\). Given the hidden states, observations are conditionally independent, with \(Y_t\) distributed according to \(b_{X_t}\).

Each likelihood sums over all possible hidden-state paths; it does not select one path and score only that path. The forward recursion is a convenient way to do this calculation. Define \(\alpha_t(i)=\mathbb{P}_\theta(Y_1=y_1,\ldots,Y_t=y_t,X_t=i)\). Then

Proof. At \(t=1\), the event \(X_1=i\) has probability \(\pi_i\), and, conditional on that state, \(Y_1=y_1\) has probability \(b_i(y_1)\). Multiplication gives the stated \(\alpha_1(i)\). For \(t\ge2\), the event counted by \(\alpha_t(j)\) can be partitioned into the disjoint possibilities \(X_{t-1}=i\), for \(i=1,\ldots,K\). For each such possibility, the joint probability of the observations through time \(t-1\) and the transition to \(j\) is \(\alpha_{t-1}(i)p_{ij}\). The probability of the new observation given \(X_t=j\) is \(b_j(y_t)\). Summing over \(i\) and multiplying by this emission probability gives the recursion. Finally, the events \(X_T=i\) partition the sample event \(Y_{1:T}=y_{1:T}\), so summing \(\alpha_T(i)\) over \(i\) gives its probability. \(\square\)

Split at the Prediction Unit

If the goal is to predict a new independent sequence, split the data by whole sequences before fitting the candidate models. Fit each state-count candidate using the training sequences only, and evaluate its sequence likelihood on the held-out sequences. When multiple sequences come from the same person, household, or other sampling unit, the split should generally keep that unit together if the target is prediction for a new unit. Otherwise, information specific to a unit can appear on both sides of the split.

The split should match the intended prediction task. For forecasting later observations from a sequence whose earlier observations are already available, a chronological split can be appropriate: the earlier prefix supplies the prediction context, and the later segment is scored. That is a different task from predicting a wholly new sequence. Randomly scattering observations from the same trajectory between training and held-out data does not evaluate either task cleanly.

For candidate state counts \(K\) in a specified set, let \(\widehat{\theta}_K\) denote the parameter fitted using training data. A prediction-based choice is

This criterion compares the probabilities assigned to the same held-out sequences. A larger score means a larger likelihood for those sequences under the fitted candidate; it does not establish that the model is true or that it will win on every future sample. If several state counts tie, preferring the smaller one is a transparent parsimony rule, not a consequence of the likelihood calculation.

Predictive Fit and Training Fit Are Different

The training log likelihood measures how well a fitted model accounts for data used in fitting. Its value is useful for diagnosing optimization and comparing models under appropriate conditions, but it is not an independent assessment of prediction. The distinction can be stated precisely for nested model classes.

Proof. Every parameter \(\theta\in\Theta_1\) also belongs to \(\Theta_2\), so \(L(\theta;D)\le\sup_{\vartheta\in\Theta_2}L(\vartheta;D)\) for every \(\theta\in\Theta_1\). Taking the supremum of the left side over \(\Theta_1\) preserves the inequality and proves the likelihood statement. If maxima exist, both suprema are attained. Likelihoods are nonnegative, and the logarithm is increasing on positive numbers; taking logs therefore preserves the ordering when the maxima are positive. If a maximum likelihood is zero, its log score is \(-\infty\), and the same ordering holds in the extended real numbers. \(\square\)

This result applies only when one parameter class really contains the other. A model with more hidden states is not automatically a nested enlargement for every choice of emission and transition restrictions. Even when nesting holds, the proposition concerns training likelihood only; it says nothing about held-out likelihood. Flexible models can assign larger likelihood to the data they were fitted on without assigning larger probability to new sequences.

Choose the Score That Matches the Goal

The pooled held-out log likelihood gives each observation its contribution to the joint sequence likelihood. Dividing by the total number of observations reports an average log score per observation, without changing the ranking when all candidates are evaluated on the same sequences. If the scientific target instead weights each independent sequence equally, one may report an average of within-sequence log scores, with an explicit decision about whether to divide each sequence's score by its length. These summaries answer different questions when lengths vary; state the chosen summary before comparing candidates.

Common Pitfalls and a Practical Comparison

A common error is to treat the initial hidden-state mixture as if one state were selected once and then held fixed for the entire sequence. In the identical-row example, that mistaken calculation gives \(L(111)=\tfrac12(\tfrac9{10})^3+\tfrac12(\tfrac1{10})^3=\tfrac{730}{2000}=\tfrac{73}{200}\). It is wrong because the transition matrix redraws the state at every step, rather than preserving the initial state. The correct calculation is \((\tfrac12\cdot\tfrac9{10}+\tfrac12\cdot\tfrac1{10})^3=(\tfrac12)^3=\tfrac18\). Always use the transition probabilities at each time, or apply the forward recursion, when summing over paths.

For a defensible state-count comparison, keep the held-out sequences fixed across candidates, fit parameters without using those sequences, compute each sequence likelihood with the full HMM likelihood rather than a decoded path, and report the score definition and length handling. The in-sample likelihood may rise with model flexibility, especially for nested classes, while held-out scores can favor a smaller candidate. A validation comparison is itself noisy, particularly with few independent sequences; the selected state count is evidence about predictive performance under the chosen split and scoring rule, not a universal property of the data.