← Back to Classic ML Mind Map
📊 Classic MLID: viterbi

Viterbi Decoding

HMM 维特比解码
🎯Core Definition
The decoding problem asks for the most probable hidden state sequence q∗=arg⁡max⁡qP(q∣O,λ)q^* = \arg\max_q P(q \mid O, \lambda) given λ=(A,B,π)\lambda = (A, B, \pi) and observations OO. Viterbi maintains the DP quantity δt(j)\delta_t(j) — the maximum probability over all paths that end in state jj at time tt after emitting o1…oto_1 \dots o_t — via
📌Overview
δt(j)=max⁡i[δt−1(i) aij] bj(ot),\delta_t(j) = \max_i[\delta_{t-1}(i)\, a_{ij}]\, b_j(o_t),
📌Overview
with a backpointer table ψt(j)=arg⁡max⁡iδt−1(i)aij\psi_t(j) = \arg\max_i \delta_{t-1}(i) a_{ij} storing the optimal predecessor; initialized by δ1(j)=πjbj(o1)\delta_1(j) = \pi_j b_j(o_1), it terminates with P∗=max⁡jδT(j)P^* = \max_j \delta_T(j) and then walks the ψ\psi table backward (backtracking) to recover the full best sequence. Complexity is O(N2T)O(N^2 T), the same order as the forward algorithm.
💡Use Cases
part-of-speech tagging, named-entity recognition, best-path search in speech and handwriting recognition; interviews often contrast Viterbi with the forward algorithm and with greedy/beam search.
⚡Key Problems Solved
enumerating NTN^T paths is intractable; like forward, Viterbi caches subproblems but replaces summation with max and keeps predecessors to reconstruct the trajectory, guaranteeing a globally optimal path rather than greedy step-wise optima; the cost is O(N2)O(N^2) comparisons per step and retaining the full ψ\psi table for backtracking (it cannot be rolled over like evaluation).
🎯Core Interview Exam Points
Fundamentals · Production Scenarios · Deep Dive
Core Def
Explain the core definition, underlying mechanism/math, and key principles of Viterbi Decoding.
Use Cases
In production engineering, what are the primary use cases for Viterbi Decoding and what core pain points does it solve?
🔥 High-Frequency Deep-Dive Questions
1
Write the Viterbi recursion δt(j)=max⁡i[δt−1(i)aij]bj(ot)\delta_t(j) = \max_i[\delta_{t-1}(i)a_{ij}]b_j(o_t) and the backtracking procedure; what is the complexity?
2
How do Viterbi and the forward algorithm differ (sum vs max, their outputs, and why Viterbi needs the backpointer table ψ\psi)?
3
Why does Viterbi guarantee a global optimum, unlike greedy per-position choice or beam search?
4
Work through a concrete example (e.g. N=2N=2, T=3T=3) by hand, deriving the best path and explaining backtracking.
5
How is Viterbi used in CRF/MEMM inference (the same decoding DP with different score functions)?
📖 In-depth Guide:📄 probabilistic-models →
Updated 2026-08-12
🎯
Verify Mastery: Practice Exam Questions for "Viterbi Decoding"
Take pitfall multiple-choice questions with derivation options; mistakes are automatically logged.
🚀 Start Card Practice ➔
← Previous CardHMM Forward Algorithm (Evaluation)Next Card →Baum-Welch (HMM EM)

🔗 More Classic ML Knowledge Cards

引用出处: TalentMe 450+ 工业级 AI 架构考点知识库 (Tech Vault) · 遵循 CC-BY-4.0 知识共享协议
URL: https://talentme.airsota.com/resources/tech/roadmap/mindmap/ML/card/viterbi
中文速览与面试要点

HMM 维特比解码 (Viterbi Decoding)

定义: 解码问题是给定 = (A, B, ) 与观测 O,求最可能的隐藏状态序列 q^* = _q P(q O, )。维特比算法用动态规划维护 _t(j) — 到时刻 t 处于状态 j 且输出前 t 个观测的所有路径中的最大概率,递推 _t(j) = _i[ _t-1(i)\, a_ij]\, b_j(o_t) 同时用前驱表 _t(j) = _i _t-1(i) a_ij 记录最优路径中 t−1 时刻的状态;初值 _1(j) = _j b_j(o_1),终止取 P^* = _j _T(j),再从 _T 沿表回溯(backtracking)得到整条最优状态序列。复杂度 O(N^2 T),与前向算法同阶。 使用场景: 词性标注、命名实体识别、语音与手写识别中的最优路径搜索;面试常考维特比与前向算法对比、与贪心/束搜索的区别。 解决的问题: 穷举 N^T 条路径不可行;维特比与前向算法同样用 DP 缓存,但把“求和”换成“取 max”并保存前驱以重建轨迹,保证全局最优而非贪心逐点最优;代价是每步 O(N^2) 比较,且必须保留完整 表用于回溯(不能像评估那样滚动丢弃)。

核心要点

  • 写出维特比递推 _t(j) = _i[ _t-1(i)a_ij]b_j(o_t) 及回溯过程,复杂度是多少?
  • 维特比与前向算法的区别?(求和 vs 取 max、各自输出什么、为什么需要前驱表 )
  • 为什么维特比能保证全局最优?与贪心逐点选择、束搜索有何不同?
  • 给定具体例子(如 N=2、T=3),手推最优状态路径并说明回溯如何工作?
  • 维特比与 CRF/MEMM 推理有何联系(推断阶段共用同一 DP,只是势函数不同)?