维特比算法是什么？用动态规划找出最可能的隐藏状态序列

维特比算法（Viterbi Algorithm）是一种动态规划算法，用来在一串观测数据背后，找出最有可能的那一串隐藏状态。它由美国电气工程师、高通公司联合创始人安德鲁·维特比在 1967 年提出，最初是为了对通信中的卷积码进行译码，后来被广泛地用于语音识别、自然语言处理、生物信息学等众多领域。

它要解决的问题

以隐马尔可夫模型为例：假设一位朋友每天告诉你他做了什么，散步、购物或者打扫房间，而你想推测他那里每天的天气是晴还是雨。你知道各种天气之间相互转换的概率，也知道每种天气下他做各种事情的概率。现在给你他一周的活动记录，问：这一周最可能的天气序列是什么？最直接的方法是列出所有可能的天气序列，逐一计算每个序列的概率，选出最大的那一个。但如果有 2 种天气、7 天，就有 2 的 7 次方等于 128 种可能；如果有 10 种状态、100 天，可能的序列数量就是 10 的 100 次方，这是一个天文数字，根本无法逐一计算。

动态规划的思路

维特比算法的关键在于一个观察：如果到达某一天某个状态的最优路径经过了前一天的某个状态，那么这条路径的前半段，一定也是到达前一天那个状态的最优路径。因此，不需要记住所有可能的路径，只需要在每一天、对于每一个状态，记住到达它的那条概率最大的路径就够了。

具体的步骤是：第一步，初始化：对于第一天的每一个可能状态，计算它的概率，等于这个状态的初始概率乘以在这个状态下观测到第一天活动的概率。第二步，递推：对于之后的每一天和每一个状态，考察前一天的所有状态，计算“前一天到达那个状态的最大概率，乘以从那个状态转移到当前状态的概率”，从中选出最大的，再乘以在当前状态下观测到今天活动的概率，就得到了今天到达这个状态的最大概率。同时记下是前一天的哪个状态带来了这个最大值，作为回溯的指针。第三步，终止和回溯：到了最后一天，选出概率最大的那个状态，再沿着记录下来的指针一步步往回走，就得到了整个最优的状态序列。

这样，计算量只与序列的长度乘以状态数的平方成正比，从指数级降到了多项式级。在实际计算中，为了避免许多个很小的概率连乘导致数值下溢，通常对概率取对数，把乘法变成加法。

与前向算法的区别

维特比算法与隐马尔可夫模型中的前向算法非常相似，两者都按时间逐步递推。区别在于：前向算法在每一步把来自前一天所有状态的概率加起来，计算的是观测序列出现的总概率；而维特比算法在每一步取最大值，寻找的是单条最优的路径。

广泛的应用

通信：维特比算法最初用于卷积码的译码，从受到噪声干扰的接收信号中，恢复出最可能被发送的原始数据，被广泛地应用于卫星通信、深空探测，以及早期的数字移动通信等。语音识别：在基于隐马尔可夫模型的语音识别系统中，用维特比算法找出与一段语音最匹配的音素和词的序列。自然语言处理：在词性标注、中文分词、命名实体识别中，找出最可能的标签序列；在条件随机场模型中，也使用同样的思路进行解码。生物信息学：在基因序列分析中识别基因的位置，以及进行序列比对。此外，在大语言模型生成文本时使用的束搜索，可以看作维特比思想的一种近似：由于语言模型的状态空间极其庞大，不可能保留每个状态的最优路径，束搜索只保留当前得分最高的若干条候选路径。