Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Hidden Markov Models › Computing Sequence Probabilities

Michael BrenndoerferUpdated May 7, 20254 min read

Language AI HandbookAll chapters

Part 6 of 67Sequence Labeling

Chapter 40Hidden Markov Models › Computing Sequence Probabilities

Reading section 4 of 13 · Computing Sequence Probabilities · 4 minSection 4 of 13 · 4 min

Section 4 of 13 · 4 min read

Hidden Markov Models › Computing Sequence ProbabilitiesOne section · Sections in this chapter4 / 13 ↓

Sections in this chapter13

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

Given an HMM, how do we compute the probability of a particular observation sequence and state sequence? This question has two related but distinct versions. You might want to know the probability of a specific combination of words and tags: for example, how likely is the sentence "the dog runs" tagged as "DT NN VB"? Or you might want to know the probability of the observation sequence alone, summed over all possible hidden state sequences: how likely is the sentence "the dog runs" to appear at all, regardless of how it is tagged? The first question gives you the joint probability $P(O, S)$ ; the second gives you the marginal $P(O)$ . Both are important, and the joint probability decomposition is the foundation for computing either one.

The joint probability factors according to the HMM structure, exploiting the independence assumptions to decompose a complex probability into simple terms.

For an observation sequence $O = o_1, o_2, \ldots, o_n$ and state sequence $S = s_1, s_2, \ldots, s_n$ , the joint probability is:

P(O, S) = P(s_1) \cdot P(o_1 \,|\, s_1) \cdot \prod_{t=2}^{n} P(s_t \,|\, s_{t-1}) \cdot P(o_t \,|\, s_t)

where:

$P(O, S)$ : the joint probability of observing sequence $O$ while the hidden states follow sequence $S$
$P(s_1)$ : the initial probability of starting in state $s_1$ , denoted $\pi_{s_1}$
$P(o_1 \,|\, s_1)$ : the emission probability of the first observation given the first state, denoted $b_{s_1}(o_1)$
$\prod_{t=2}^{n}$ : the product over all positions from 2 to $n$
$P(s_t \,|\, s_{t-1})$ : the transition probability from state $s_{t-1}$ to state $s_t$ , denoted $a_{s_{t-1}, s_t}$
$P(o_t \,|\, s_t)$ : the emission probability of observation $o_t$ from state $s_t$ , denoted $b_{s_t}(o_t)$

The formula captures the generative story of an HMM: start in some state (with probability $\pi$ ), emit the first word (with probability $b$ ), then repeatedly transition to a new state (with probability $a$ ) and emit the next word (with probability $b$ ). This story is "generative" because you can use it to generate sentences: sample a starting tag from $\pi$ , sample a word from $b$ , sample a next tag from $a$ , sample the next word from $b$ , and so on. The HMM describes a process that could plausibly have produced the training data, and parameter estimation is the task of finding the process whose description fits that data best.

Let's compute this for a concrete example: the sentence "the dog runs" with tags "DT NN VB." We'll trace through each step of the computation, showing how the probabilities multiply together to give the joint probability of this particular word-tag pairing.

In[7]:

Code

def compute_joint_probability(observations, states, pi, A, B):
    """Compute P(observations, states) for an HMM."""
    n = len(observations)

    # Start with initial probability and first emission
    prob = pi[states[0]] * B[states[0]][observations[0]]

    # Multiply by transition and emission for each subsequent position
    for t in range(1, n):
        transition_prob = A[states[t - 1]][states[t]]
        emission_prob = B[states[t]][observations[t]]
        prob *= transition_prob * emission_prob

    return prob


# Our example sentence
observations = ["the", "dog", "runs"]
tag_sequence = ["DT", "NN", "VB"]

joint_prob = compute_joint_probability(observations, tag_sequence, pi, A, B)

Out[8]:

Console

Computing P('the dog runs', 'DT NN VB')
==================================================

1. Initial: P(DT) = 0.6
2. Emission: P('the'|DT) = 0.9
3. Transition: P(NN|DT) = 0.8
4. Emission: P('dog'|NN) = 0.45
5. Transition: P(VB|NN) = 0.6
6. Emission: P('runs'|VB) = 0.5

Joint probability: 0.6 × 0.9 × 0.8 × 0.45 × 0.6 × 0.5
                 = 0.058320

The joint probability is quite small because we're multiplying many probabilities together. For longer sequences, these products become vanishingly small, leading to numerical underflow. A 20-word sentence with probabilities around 0.1 at each step would produce a product on the order of $10^{-20}$ , which many floating-point implementations round to zero. In practice, we work in log space, converting multiplications to additions:

\log P(O, S) = \log P(s_1) + \log P(o_1 \mid s_1) + \sum_{t=2}^{n} \left[ \log P(s_t \mid s_{t-1}) + \log P(o_t \mid s_t) \right]

Since $\log$ is a monotonically increasing function, maximizing the log probability is equivalent to maximizing the probability itself. Working in log space prevents numerical underflow and is standard practice for probabilistic sequence models.