📊 Classic MLID: hmm-evaluation

HMM Forward Algorithm (Evaluation)

Q: Write the forward recursion $\alpha_t(j) = [\sum_i \alpha_{t-1}(i)a_{ij}]b_j(o_t)$ with its initialization $\alpha_1(j)$ and termination $P(O \mid \lambda)$?

【HMM Forward Algorithm (Evaluation) 核心考点 1】Write the forward recursion $\alpha_t(j) = [\sum_i \alpha_{t-1}(i)a_{ij}]b_j(o_t)$ with its initialization $\alpha_1(j)$ and termination $P(O \mid \lambda)$?。技术解析：Definition: The evaluation problem asks for the observation probability P(O \mid \lambda) given HMM parameters \lambda = (A, B, \pi) and an observation sequence O = o_1 o_2 \dots o_T. Summing over state sequences requires N^T paths, which is intractable; the forward algorithm def... 完整推导与工程落地见：https://talentme.airsota.com/resources/tech/roadmap/mindmap/ML/card/hmm-evaluation

Q: Why is naive computation of $P(O \mid \lambda)$ exponential in $O(N^T)$, and how does the forward algorithm reduce it to $O(N^2T)$?

【HMM Forward Algorithm (Evaluation) 核心考点 2】Why is naive computation of $P(O \mid \lambda)$ exponential in $O(N^T)$, and how does the forward algorithm reduce it to $O(N^2T)$?。技术解析：Definition: The evaluation problem asks for the observation probability P(O \mid \lambda) given HMM parameters \lambda = (A, B, \pi) and an observation sequence O = o_1 o_2 \dots o_T. Summing over state sequences requires N^T paths, which is intractable; the forward algorithm def... 完整推导与工程落地见：https://talentme.airsota.com/resources/tech/roadmap/mindmap/ML/card/hmm-evaluation

Q: How do the forward algorithm and Viterbi differ (sum vs max, and what each outputs)?

【HMM Forward Algorithm (Evaluation) 核心考点 3】How do the forward algorithm and Viterbi differ (sum vs max, and what each outputs)?。技术解析：Definition: The evaluation problem asks for the observation probability P(O \mid \lambda) given HMM parameters \lambda = (A, B, \pi) and an observation sequence O = o_1 o_2 \dots o_T. Summing over state sequences requires N^T paths, which is intractable; the forward algorithm def... 完整推导与工程落地见：https://talentme.airsota.com/resources/tech/roadmap/mindmap/ML/card/hmm-evaluation

Q: What is the probabilistic meaning of $\alpha_t(j)$, and how does it combine with the backward variable $\beta_t(j)$ to give $P(q_t = j \mid O, \lambda)$?

【HMM Forward Algorithm (Evaluation) 核心考点 4】What is the probabilistic meaning of $\alpha_t(j)$, and how does it combine with the backward variable $\beta_t(j)$ to give $P(q_t = j \mid O, \lambda)$?。技术解析：Definition: The evaluation problem asks for the observation probability P(O \mid \lambda) given HMM parameters \lambda = (A, B, \pi) and an observation sequence O = o_1 o_2 \dots o_T. Summing over state sequences requires N^T paths, which is intractable; the forward algorithm def... 完整推导与工程落地见：https://talentme.airsota.com/resources/tech/roadmap/mindmap/ML/card/hmm-evaluation

Q: Compute $P(O \mid \lambda)$ by hand for a concrete HMM (e.g. $N=2$, $T=3$), showing each forward step?

【HMM Forward Algorithm (Evaluation) 核心考点 5】Compute $P(O \mid \lambda)$ by hand for a concrete HMM (e.g. $N=2$, $T=3$), showing each forward step?。技术解析：Definition: The evaluation problem asks for the observation probability P(O \mid \lambda) given HMM parameters \lambda = (A, B, \pi) and an observation sequence O = o_1 o_2 \dots o_T. Summing over state sequences requires N^T paths, which is intractable; the forward algorithm def... 完整推导与工程落地见：https://talentme.airsota.com/resources/tech/roadmap/mindmap/ML/card/hmm-evaluation

HMM 前向算法 (评估)

🎯Core Definition

The evaluation problem asks for the observation probability

P(O \mid \lambda)

given HMM parameters

\lambda = (A, B, \pi)

and an observation sequence

O = o_1 o_2 \dots o_T

. Summing over state sequences requires

N^T

paths, which is intractable; the forward algorithm defines forward variables

\alpha_t(j) = P(o_1 \dots o_t, q_t = j \mid \lambda)

— the joint probability of being in state

j

at time

t

after emitting

o_1 \dots o_t

— and recurses

📌Overview

\alpha_t(j) = \Bigl[\sum_{i} \alpha_{t-1}(i)\, a_{ij}\Bigr] b_j(o_t),

📌Overview

initialized with

\alpha_1(j) = \pi_j b_j(o_1)

and terminating at

P(O \mid \lambda) = \sum_j \alpha_T(j)

. Each step sums

N

transitions for each of

N

states, reducing the cost from

O(N^T)

path enumeration to

O(N^2 T)

💡Use Cases

scoring sequences in speech recognition and bio-sequence analysis, and as the E-step machinery of Baum-Welch; interviews often ask for the forward-variable definition and how forward differs from Viterbi (sum vs max).

⚡Key Problems Solved

direct summation over hidden states is exponential, and the forward algorithm caches subproblems to make likelihood computation polynomial; the cost is an

O(N^2)

transition sum per step and

O(NT)

storage (rollable to

O(N)

🎯5 High-Frequency Exam Points

Write the forward recursion

\alpha_t(j) = [\sum_i \alpha_{t-1}(i)a_{ij}]b_j(o_t)

with its initialization

\alpha_1(j)

and termination

P(O \mid \lambda)

Why is naive computation of

P(O \mid \lambda)

exponential in

O(N^T)

, and how does the forward algorithm reduce it to

O(N^2T)

How do the forward algorithm and Viterbi differ (sum vs max, and what each outputs)?

What is the probabilistic meaning of

\alpha_t(j)

, and how does it combine with the backward variable

\beta_t(j)

to give

P(q_t = j \mid O, \lambda)

Compute

P(O \mid \lambda)

by hand for a concrete HMM (e.g.

N=2

T=3

), showing each forward step?

📖 In-depth Guide:📄 probabilistic-models →

Updated 2026-08-12

🎯

Test Your Knowledge: Practice Questions for "HMM Forward Algorithm (Evaluation)"

Single choice pitfall questions with instant feedback and mistake tracking.

🚀 Start Card Practice ➔

← Previous CardNaive Bayes Next Card →Viterbi Decoding

🔗 More Classic ML Knowledge Cards

AdaBoost Derivation Bagging & Random Forest Baum-Welch (HMM EM)GBDT Negative Gradient