This video delves into the probability calculation problem within Hidden Markov Models (HMMs), a core topic following an introductory overview. It introduces two fundamental dynamic programming algorithms, the Forward Algorithm and the Backward Algorithm, designed to efficiently compute the probability of an observed sequence given an HMM. The Forward Algorithm is explained in detail, outlining its initialization, recursive steps, and termination condition, and is thoroughly illustrated with a practical "boxes and balls" example. The Backward Algorithm is then presented as a complementary approach, also utilizing recursion but processing the sequence in reverse. The video emphasizes how both algorithms drastically reduce computational complexity compared to direct enumeration of all possible hidden state sequences.
Summarizing HMM Probability Calculation: Forward and Backward Algorithms
0:00 Introduction to HMM Probability Calculation: The video continues the discussion on Hidden Markov Models (HMMs), focusing on the problem of calculating the probability of a given observation sequence (O) under a specific HMM model (Lambda).
0:31 Inefficiency of Direct Calculation: Directly computing P(O|Lambda) by summing the probabilities of all possible hidden state sequences is shown to be computationally infeasible due to its extremely high time complexity.
2:11 Introduction to the Forward Algorithm: The Forward Algorithm is introduced as an efficient, recursive method to solve the HMM probability calculation problem.
2:18 Definition of Forward Probability (Alpha): The forward probability, denoted as α_t(i), is defined as the joint probability of observing the partial sequence O₁ to O_t and the HMM being in a specific hidden state q_i at time t, given the model.
Initialization (Step 1): Calculate the initial forward probabilities for the first observation: α₁(i) = π_i * b_i(O₁), where π_i is the initial probability of state i, and b_i(O₁) is the emission probability of O₁ from state i.
Recursion (Step 2): Iteratively calculate α_t(i) for subsequent time steps by summing the products of previous forward probabilities (α_{t-1}(j)), transition probabilities (a_ji) from state j to state i, and the emission probability (b_i(O_t)) of the current observation O_t from state i. This process efficiently accounts for all paths leading to state i at time t.
Termination (Step 3): The total probability P(O|Lambda) is obtained by summing all forward probabilities α_T(i) at the final time step T.
5:28 Forward Algorithm Example (Boxes and Balls): A practical example involving three boxes (hidden states) and two types of balls (red/white observations) is used to illustrate the step-by-step application of the Forward Algorithm for an observation sequence "red, white, red".
9:41 Introduction to the Backward Algorithm: The Backward Algorithm is presented as another dynamic programming technique, analogous to the Forward Algorithm but computing probabilities by moving backward in time from the end of the observation sequence.
10:06 Definition of Backward Probability (Beta): The backward probability, denoted as β_t(i), is defined as the probability of observing the partial sequence O_{t+1} to O_T, given that the HMM is in state q_i at time t.
Initialization (Step 1): Unlike the Forward Algorithm, β_T(i) is conventionally set to 1 for all states i at the final time T.
Recursion (Step 2): β_t(i) is calculated by summing over all possible next states j, considering the transition probability (a_ij) from state i to state j, the emission probability (b_j(O_{t+1})) of the next observation O_{t+1} from state j, and the backward probability (β_{t+1}(j)) of state j at time t+1.
Termination (Step 3): The total probability P(O|Lambda) is calculated by summing the products of initial state probabilities (π_i), the emission probability of the first observation (b_i(O₁)), and the backward probability of state i at time 1 (β₁(i)).
12:18 Core Principle of Efficiency: Both algorithms significantly reduce computational complexity by leveraging the Markov property and dynamic programming, reusing previously calculated probabilities in a recursive manner.
13:01 Unified Probability Formula: A combined expression for P(O|Lambda) using both forward (alpha) and backward (beta) probabilities is provided, demonstrating their interrelation.