Understanding Hidden Markov Models for Sequence Labelling

Many real-world datasets are ordered rather than independent. A sentence is a sequence of words, a weather log is a sequence of observations, and a stream of website events unfolds over time. When the goal is to assign a label to every item in that sequence, the surrounding context often matters as much as the item itself. This task is known as sequence labelling. Learn more about A Guide To The Counting Sort Algorithm For Linear Time Sorting.

Hidden Markov Models, or HMMs, provide a practical mathematical framework for this problem. They represent unobserved states, visible observations, transitions between states, and the probabilities connecting them. Although newer neural models are common, HMMs remain valuable because they are interpretable, efficient on modest datasets, and excellent for learning the foundations of probabilistic modelling.

The basic idea behind an HMM

An HMM assumes that a sequence is produced by a chain of hidden states. We can observe the outputs of the chain, but not the states directly. For part-of-speech tagging, the words are observations and labels such as noun, verb, or adjective are hidden states. For speech recognition, an audio signal is observed while phonemes or words form the hidden sequence.

Two probability distributions define the basic model. The transition probability describes how likely one hidden state is to follow another:

[ P(y_t \mid y_{t-1}) ]

The emission probability describes how likely an observation is given a hidden state:

[ P(x_t \mid y_t) ]

Here, (y_t) is the hidden label at position (t), and (x_t) is the observed item. An HMM also includes an initial-state probability, which estimates how likely each label is at the beginning of a sequence.

The model makes a simplifying conditional independence assumption. The current hidden state depends only on the previous hidden state, and the current observation depends only on the current hidden state. This is called the first-order Markov assumption. Natural language does not perfectly follow it, but the assumption makes inference computationally manageable.

HMMs for sequence labelling

Suppose a sentence contains the words “The kookaburra sings”. A part-of-speech tagger might assign the labels determiner, noun, and verb. The word “sings” is more likely to be a verb than a noun, but its context strengthens that decision. A sequence model can recognise that a determiner commonly precedes a noun and that a noun commonly precedes a verb.

The task is to find the most probable hidden label sequence:

[ \hat{y}{1:T} = \arg\max{y_{1:T}} P(y_{1:T} \mid x_{1:T}) ]

Using Bayes’ rule and ignoring the constant denominator, this becomes:

[ \hat{y}{1:T} = \arg\max{y_{1:T}} P(y_1) \prod_{t=2}^{T} P(y_t \mid y_{t-1}) \prod_{t=1}^{T} P(x_t \mid y_t) ]

The first product rewards plausible label transitions, while the second rewards labels that explain the observed words. The best answer is therefore a balance between local evidence and sequence structure.

This approach is useful for named entity recognition, where each token may receive labels such as person, organisation, location, or outside an entity. It can also support shallow parsing, biological sequence analysis, optical character recognition, and log-event classification. An Australian application might label references to places such as “Sydney”, “Perth”, or “Great Barrier Reef” in news and tourism text.

Training transition and emission probabilities

A supervised HMM is trained from sequences where the correct labels are already known. The transition probability is estimated by counting adjacent label pairs. If a noun is followed by a verb 80 times and by an adjective 20 times, the corresponding estimates can be calculated from those counts.

The emission probability is estimated by counting how often a label produces a particular observation. If the word “run” appears as a verb in 30 labelled examples and as a noun in 10, the model will favour the verb interpretation, while still retaining uncertainty. Maximum likelihood estimates commonly use formulas such as:

[ P(y_t \mid y_{t-1}) = \frac{\text{count}(y_{t-1},y_t)} {\text{count}(y_{t-1})} ]

[ P(x_t \mid y_t) = \frac{\text{count}(y_t,x_t)} {\text{count}(y_t)} ]

Raw counts create a serious problem when a valid transition or word has never appeared in the training set. A zero probability can make an entire candidate sequence impossible. Smoothing addresses this by assigning a small probability to unseen events. Add-one smoothing is easy to understand, though add-(k) smoothing or more specialised language-modelling methods may work better in practice.

Unknown words need separate treatment. A tagger can use features such as capitalisation, suffixes, prefixes, digits, hyphens, or word shape. This matters in Australian datasets containing unfamiliar suburb names, local company names, Indigenous place names, and rapidly changing vocabulary from social media or job advertisements.

Finding the best path with Viterbi

Trying every possible label sequence is inefficient. If there are (N) labels and (T) observations, exhaustive search requires examining roughly (N^T) paths. The Viterbi algorithm solves the same optimisation problem using dynamic programming.

For each position and possible current label, Viterbi stores the score of the best path ending there. A typical recurrence is:

[ V_t(s) = P(x_t \mid s) \max_{r} \left[V_{t-1}(r)P(s \mid r)\right] ]

In practice, probabilities are usually converted to log probabilities. Products then become sums, and very small floating-point values do not underflow:

[ \log V_t(s) = \log P(x_t \mid s) + \max_r \left[ \log V_{t-1}(r) + \log P(s \mid r) \right] ]

A backpointer records which previous state achieved the maximum. After processing the final observation, the algorithm follows these pointers backwards to reconstruct the optimal label sequence.

The time complexity is (O(TN^2)), because each of (T) positions considers every pair of previous and current states. Space complexity is (O(TN)) when the complete backpointer table is retained. If only the final score is required, rolling arrays can reduce the score storage to (O(N)). This dynamic-programming pattern is related to other algorithmic techniques discussed in the topological sort tutorial, where ordering and dependency structure also determine efficient computation.

Forward-backward inference and model evaluation

Viterbi returns one best explanation, but sometimes a system needs uncertainty. The forward algorithm calculates the total probability of observing a sequence by summing over all possible hidden paths. Its recurrence is:

[ \alpha_t(s) = P(x_t \mid s) \sum_r \alpha_{t-1}(r)P(s \mid r) ]

The backward algorithm works from the end towards the beginning. Combining forward and backward values gives the posterior probability that a particular label occurred at a particular position. This is useful when a classifier should flag ambiguous cases for review rather than making an unquestioned decision.

Forward-backward inference is also used in the Baum-Welch algorithm, an expectation-maximisation procedure for training HMMs when labels are missing. During the expectation step, the algorithm estimates likely hidden states and transitions. During the maximisation step, it updates model probabilities. This is different from supervised training, where the state sequence is supplied directly.

Evaluation should match the sequence-labelling goal. Token accuracy is intuitive but can be misleading when one label dominates. Precision, recall, and F1 score are more informative for named entities or rare categories. A complete-entity metric can be stricter: a predicted organisation is counted as correct only when its entire span and type match the reference. Training and test examples should also be separated by document or source to avoid leakage.

For scalable preprocessing, data structures such as arrays, dictionaries, and sparse matrices matter. A useful data structures collection can clarify how transition tables and dynamic-programming charts should be represented in Python or C.

Implementing an HMM in Python

A straightforward implementation can represent labels in a list and map each label to an integer index. Transition and emission probabilities then fit naturally into two-dimensional arrays. A dictionary is helpful for vocabulary lookup, while a special <UNK> token handles observations absent from training data.

The Viterbi procedure follows four stages:

1. Initialise the score for each label using the start probability and the first emission probability.
2. For every later observation, compute the best previous label for each current label.
3. Store that previous label in a backpointer matrix.
4. Select the best final label and trace the path backwards.

A production implementation should validate sequence lengths, handle empty input, and use log probabilities. It should also distinguish an unknown token from a genuinely missing observation. Small numerical details can change results when sequences are long, so stable calculations are important.

The model’s quality depends heavily on the training corpus. Text written in Australian English may contain spelling differences such as “organise” rather than “organize”, references to the Bureau of Meteorology, and local abbreviations such as “NSW” or “ACT”. A dataset built from Melbourne tram updates will have a different vocabulary from one built from Australian Securities Exchange reports or customer reviews from Woolworths. These domain differences should be reflected in training data and error analysis.

HMMs are less expressive than conditional random fields and transformer-based systems, which can use wider context and rich learned representations. Still, an HMM offers transparent probabilities, fast decoding, and a compact baseline. It is especially useful when labelled data is limited, compute resources are modest, or developers need to inspect why a particular sequence received its labels. The model also teaches the central ideas behind state estimation, dynamic programming, smoothing, and probabilistic prediction.