AI: The forward algorithm

Keep a belief about a hidden state up to date as observations arrive.

What to build

A program that filters a hidden Markov model and prints the belief after every observation.

Requirements

  • The prior is the distribution one step before the first observation. Each observation: predict with the transition model, multiply by P(observation | state), normalize.
  • Print day T (OBS): followed by STATE P pairs (four decimal places) for each observation.

Input

Line 1: states. Line 2: observation symbols. Then n transition rows, then n sensor rows (one probability per symbol), then the prior, then the observations.

Output

One line per observation.

Constraints

At most 10 states, 10 symbols and 100 observations.

Example

Input:

Rain Dry
U N
0.7 0.3
0.3 0.7
0.9 0.1
0.2 0.8
0.5 0.5
U U

Output:

day 1 (U): Rain 0.8182 Dry 0.1818
day 2 (U): Rain 0.8834 Dry 0.1166

Why it works

Predicting accounts for how the state may have changed, and multiplying by the sensor model weighs each state by how well it explains what was seen.

Examples

Example 1 · Input
Rain Dry
U N
0.7 0.3
0.3 0.7
0.9 0.1
0.2 0.8
0.5 0.5
U U
Expected output
day 1 (U): Rain 0.8182 Dry 0.1818
day 2 (U): Rain 0.8834 Dry 0.1166
Example 2 · Input
Rain Dry
U N
0.7 0.3
0.3 0.7
0.9 0.1
0.2 0.8
0.5 0.5
N
Expected output
day 1 (N): Rain 0.1111 Dry 0.8889

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

For each observation: predict with the transition rows, multiply by the sensor probability of that observation, then divide by the total.

Hint 2

Start from the prior, which describes the state before the first observation's day.

Solution

Show one correct solution (try it yourself first)
states = input().split()
symbols = input().split()
n = len(states)
T = [list(map(float, input().split())) for _ in range(n)]
E = [dict(zip(symbols, map(float, input().split()))) for _ in range(n)]
belief = list(map(float, input().split()))
for t, obs in enumerate(input().split(), start=1):
    predicted = [sum(belief[r] * T[r][s] for r in range(n)) for s in range(n)]
    weights = [predicted[s] * E[s][obs] for s in range(n)]
    total = sum(weights)
    belief = [w / total for w in weights]
    print(f"day {t} ({obs}): " + " ".join(f"{s} {b:.4f}" for s, b in zip(states, belief)))

Lesson: Hidden Markov models →