Lab 09: Forward Algorithm in HMMs

In this lab, we dive into the Forward Algorithm, a core component of probabilistic models—especially Hidden Markov Models (HMMs). The algorithm helps compute the probability of an observed sequence, given a model’s parameters. This is crucial in applications like speech recognition, bioinformatics, and NLP.

Introduction

Hidden Markov Models (HMMs) are statistical models where the system being modeled is assumed to be a Markov process with hidden states. The Forward Algorithm efficiently calculates the total probability of an observed sequence by summing over all possible hidden state sequences.

Problem Setup

Let:

• $N$: number of hidden states
• $T$: length of observation sequence
• $A$: state transition probabilities
• $B$: observation/emission probabilities
• $\pi$: initial state distribution
• $O = o_1, o_2, ..., o_T$: sequence of observations

The goal is to compute:

This is efficiently done using dynamic programming.

Algorithm Overview

Steps:

1. Initialization
   $\alpha_1(i) = \pi_i \cdot b_i(o_1)$

2. Recursion
   $\alpha*t(j) = \sum*{i=1}^{N} \alpha*{t-1}(i) \cdot a*{ij} \cdot b_j(o_t)$

3. Termination
   $P(O \mid \lambda) = \sum\_{i=1}^{N} \alpha_T(i)$

Implementation

import numpy as np
 
def forward_algorithm(A, B, pi, observations):
    N = A.shape[0]  # Number of states
    T = len(observations)  # Length of observation sequence
    alpha = np.zeros((T, N))
 
    # Initialization
    alpha[0, :] = pi * B[:, observations[0]]
 
    # Recursion
    for t in range(1, T):
        for j in range(N):
            alpha[t, j] = np.sum(alpha[t - 1] * A[:, j]) * B[j, observations[t]]
 
    # Termination
    probability = np.sum(alpha[T - 1, :])
    return probability, alpha

Example Usage

# Define model parameters
A = np.array([[0.7, 0.3],
              [0.4, 0.6]])
 
B = np.array([[0.1, 0.4, 0.5],
              [0.6, 0.3, 0.1]])
 
pi = np.array([0.6, 0.4])
 
# Observations (coded as indices)
observations = [0, 1, 2]  # e.g., observation symbols could be ['H', 'T', 'H']
 
# Run the forward algorithm
probability, alpha_matrix = forward_algorithm(A, B, pi, observations)
 
print("Probability of observing sequence:", probability)
print("Alpha matrix:\n", alpha_matrix)

Visualization

import seaborn as sns
import matplotlib.pyplot as plt
 
def visualize_alpha(alpha):
    plt.figure(figsize=(10, 4))
    sns.heatmap(alpha, annot=True, fmt=".4f", cmap="Blues")
    plt.title("Forward Probabilities (Alpha Matrix)")
    plt.xlabel("States")
    plt.ylabel("Time Step")
    plt.show()
 
visualize_alpha(alpha_matrix)

Time and Space Complexity

• $N$: Number of states
• $T$: Length of observation sequence

Applications

1. Speech Recognition: Predicting spoken words from audio input.
2. Gene Prediction: Modeling DNA sequences.
3. POS Tagging: Inferring grammatical structures from sentence tokens.
4. Time Series Analysis: Anomaly detection in sensor data.

Conclusion

The Forward Algorithm is a foundational method in probabilistic modeling for sequences. It elegantly leverages dynamic programming to solve a problem that would otherwise require exponential time. Mastering this algorithm is essential for understanding more advanced HMM tasks like training and decoding.

References

1. Rabiner, L. R.
   A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition, Proceedings of the IEEE.

2. MIT 6.864 Lecture on HMMs 

3. YouTube: HMM Tutorial Video