The Learning Library
Contents

Module 01 — The Model and the Three Problems

Part I · Foundations & the Inference Engine · Status: Draft v0.1 Scope: HMM definition plus evaluation, decoding, and learning · Prerequisites: 00

Overview

An HMM has hidden states, visible observations, a start distribution, a transition matrix, and an emission matrix. You choose matrices that describe how weather persists and how weather produces activities. The model then scores any observation sequence you hand it.

Three canonical problems organize everything you will ever do with an HMM. You evaluate how likely a sequence is, decode the most likely hidden path, and learn the matrices from data. This module defines all three and works the first two by hand.

You will reuse one shared toy problem across all Part I modules. Memorizing its numbers now pays off in every later module.

How It Works

The hidden state evolves as a Markov chain: tomorrow’s weather depends only on today’s weather. Each day’s activity depends only on that day’s weather. Those two independence assumptions are the entire model, and every algorithm here exploits them.

How to read this: observations sit at the bottom, hidden states at the top, and arrows show which variables directly influence which.

flowchart TD
    S1[Day 1 weather hidden] --> S2[Day 2 weather hidden]
    S1 --> O1[Day 1 activity seen]
    S2 --> O2[Day 2 activity seen]
    START[Start distribution] --> S1
    TRANS[Transition matrix] --> S2
    EMIT[Emission matrix] --> O1
    EMIT --> O2

THE SHARED TOY PROBLEM used by all Part I modules is fixed here. States are Rainy and Sunny. Observations are Walk, Shop, and Clean. The start distribution gives Rainy 0.6 and Sunny 0.4.

From state To Rainy To Sunny
Rainy 0.7 0.3
Sunny 0.4 0.6
State Walk Shop Clean
Rainy 0.1 0.4 0.5
Sunny 0.6 0.3 0.1

You run every hand calculation in this module on the 2-day sequence Walk then Clean. Later modules reuse these exact matrices, so verify them once and trust them afterward.

Problem 1: Evaluation With the Forward Algorithm

Evaluation asks how likely the observation sequence is under your matrices. You sweep forward in time, maintaining one running score per state. Each running score accumulates every path that could have led there.

The recurrence in words: today’s score for a state equals its emission probability times the sum over yesterday’s states of yesterday’s score times the transition probability. In code with named variables this reads directly.

import numpy as np

# Shared toy matrices: rows are Rainy then Sunny.
start_prob = np.array([0.6, 0.4])
trans_mat = np.array([[0.7, 0.3], [0.4, 0.6]])
# Columns are Walk, Shop, Clean.
emit_mat = np.array([[0.1, 0.4, 0.5], [0.6, 0.3, 0.1]])
obs_walk, obs_clean = 0, 2  # column indices

# Day 1: start probability times emission of Walk.
fwd_day1 = start_prob * emit_mat[:, obs_walk]
# Day 2: transition-weighted sum times emission of Clean.
fwd_day2 = (fwd_day1 @ trans_mat) * emit_mat[:, obs_clean]
print("day1:", fwd_day1, "sum:", fwd_day1.sum())
print("day2:", fwd_day2, "total:", fwd_day2.sum())

The worked arithmetic confirms the code. Day 1 gives Rainy 0.6 times 0.1 = 0.06 and Sunny 0.4 times 0.6 = 0.24, summing to 0.30. Day 2 gives Rainy as (0.06 times 0.7 plus 0.24 times 0.4) times 0.5 = 0.069, and Sunny as (0.06 times 0.3 plus 0.24 times 0.6) times 0.1 = 0.0162.

The total likelihood is 0.069 plus 0.0162 = 0.0852. That number means your toy weather model assigns about an 8.5 percent chance to seeing Walk then Clean. You will reproduce it from scratch in Module 02.

Problem 2: Decoding With Viterbi

Decoding asks for the single most likely hidden path, not the total over all paths. You sweep forward like before, but you take a maximum over predecessor states instead of a sum. You also record which predecessor won at each step so you can trace the path back.

The recurrence in words: today’s best-path score for a state equals its emission probability times the best over yesterday’s states of yesterday’s best score times the transition probability. The code differs from the forward pass in exactly one operation.

import numpy as np

start_prob = np.array([0.6, 0.4])
trans_mat = np.array([[0.7, 0.3], [0.4, 0.6]])
emit_mat = np.array([[0.1, 0.4, 0.5], [0.6, 0.3, 0.1]])
obs_walk, obs_clean = 0, 2

# Day 1 best scores match the forward day 1 values.
vit_day1 = start_prob * emit_mat[:, obs_walk]
# Day 2 takes the max over predecessors, not the sum.
vit_rainy = max(vit_day1[0] * 0.7, vit_day1[1] * 0.4) * 0.5
vit_sunny = max(vit_day1[0] * 0.3, vit_day1[1] * 0.6) * 0.1
print("viterbi scores:", vit_rainy, vit_sunny)

The worked arithmetic gives Rainy as max(0.042, 0.096) times 0.5 = 0.048 with backpointer Sunny, and Sunny as max(0.018, 0.144) times 0.1 = 0.0144 with backpointer Sunny. The winning final state is Rainy at 0.048. Tracing back gives the decoded path Sunny then Rainy.

That path means the single best explanation of Walk then Clean starts sunny and turns rainy. Notice the decoded path probability 0.048 is smaller than the total likelihood 0.0852. The total counts every path while Viterbi counts only the winner, so the total must always be at least as large.

Problem 3: Learning With Baum-Welch

Learning asks for matrices that make your observed sequences likely. You start from a guess, compute state beliefs with a forward-backward pass, and update the matrices to match those beliefs. You repeat until the likelihood stops improving.

The update in words: the new transition estimate from one state to another equals the expected count of such transitions divided by the expected count of visits to the source state. In code this is one ratio of accumulated beliefs.

import numpy as np

# Expected counts come from the forward-backward pass.
expected_trans_rainy_to_sunny = 1.8
expected_visits_to_rainy = 6.0
# M-step: normalize expected counts into a probability.
updated_trans_prob = expected_trans_rainy_to_sunny / expected_visits_to_rainy
print("updated Rainy->Sunny:", updated_trans_prob)

The numeric example gives 1.8 divided by 6.0 = 0.3, which recovers the toy transition value. That means Baum-Welch re-estimates each row of your matrices by counting, where fractional expected counts replace hard counts. You implement the full loop in Module 04.

[!WARNING] Baum-Welch climbs to a local optimum, not the global one. You must restart from several initial guesses and keep the best run.

Testing Your Implementation

You verify both hand calculations with one runnable script. The snippet below recomputes the forward total and the Viterbi winner from the shared matrices and asserts the exact values derived above. You run it now and again after Module 02.

import numpy as np

start_prob = np.array([0.6, 0.4])
trans_mat = np.array([[0.7, 0.3], [0.4, 0.6]])
emit_mat = np.array([[0.1, 0.4, 0.5], [0.6, 0.3, 0.1]])

fwd_day1 = start_prob * emit_mat[:, 0]
fwd_day2 = (fwd_day1 @ trans_mat) * emit_mat[:, 2]
total_likelihood = float(fwd_day2.sum())
print("forward total:", total_likelihood)
assert abs(total_likelihood - 0.0852) < 1e-12

vit_rainy = max(fwd_day1[0] * 0.7, fwd_day1[1] * 0.4) * 0.5
vit_sunny = max(fwd_day1[0] * 0.3, fwd_day1[1] * 0.6) * 0.1
print("viterbi winner:", max(vit_rainy, vit_sunny))
assert abs(vit_rainy - 0.048) < 1e-12
assert vit_rainy > vit_sunny  # decoded path ends Rainy
print("hand calculations confirmed")

The expected output shows forward total 0.0852 and Viterbi winner 0.048. If either assertion fails, your matrices differ from the shared toy problem and you fix them before continuing.

Hands-On Project

Extend the toy to the 3-day sequence Walk, Shop, Clean by hand and then in code. Compute the forward total for all three days and the Viterbi path with backpointers. Your reproduction card records the shared matrices above, no library, and seed not applicable.

Your acceptance check has two parts. Your code’s forward total must match your hand arithmetic to six decimals. Your decoded path must end with a stated final state and probability. If hand and code disagree, your hand math is wrong more often than your code, so recheck the hand math first.

[!TIP] Build a small table with one row per day showing both state scores. You will spot max-versus-sum mistakes instantly.

Key Takeaways

  • An HMM pairs a hidden Markov chain with per-state observation distributions.
  • The forward algorithm sums over all paths to score a sequence; the toy total is 0.0852.
  • Viterbi takes the maximum instead of the sum; the toy winner is Sunny then Rainy at 0.048.
  • The total likelihood always dominates the single best-path probability.
  • Baum-Welch re-estimates matrices from expected counts and needs multiple restarts.
  • The shared Rainy and Sunny matrices anchor every later Part I module.
  • Learning finds a local optimum, so initialization discipline starts in Module 04.

References