维特比算法(Viterbi Algorithm)

维特比算法(Viterbi Algorithm)是由安德鲁·维特比提出的一种动态规划算法,用于在网格结构中寻找概率最大的状态路径,即最大后验概率的隐藏状态序列。它是隐马尔可夫模型解码问题的经典解法。

概述

许多问题可建模为随时间演进的状态序列:每个时刻有一个隐藏状态,并产生一个可观测输出,状态间存在转移概率,状态到观测存在发射概率。给定一串观测,目标是推断最可能的隐藏状态序列。直接枚举所有路径的数量随序列长度指数增长,维特比算法用动态规划把复杂度降到多项式级。

核心原理

• 定义前向量:记录在时刻 t 处于某状态、且与前面观测最匹配的路径概率。
• 递推:每个时刻的最优概率由上一时刻各状态的最优概率乘以转移概率与当前发射概率的最大值得到。
• 回溯指针:在取最大值时记录前驱状态,供最终回溯路径使用。
• 终止与回溯:序列末尾选出概率最大的状态,沿回溯指针逆推得到完整最优状态序列。
• 时间复杂度与状态数平方及序列长度成正比,远优于指数级枚举。

应用场景

维特比算法最初用于卷积码的最大似然解码,是数字通信纠错的基石。在自然语言处理中,它用于词性标注、中文分词、命名实体识别等序列标注任务的解码;在语音识别中用于从声学模型中恢复最可能的音素或词序列;在生物信息学中用于基因序列的隐状态推断。

常见问题

问:维特比算法和前向算法有什么区别?答:前向算法对所有路径概率求和,用于计算观测序列的总似然;维特比算法在递推中取最大值而非求和,目的是找出单条最优路径,两者结构相似但语义不同。

问:为什么实践中常用对数概率?答:多个小概率连乘容易造成数值下溢,取对数后乘法变为加法,既避免下溢又提升计算稳定性和效率。