个人笔记

1 维特比算法概述

维特比算法（Viterbi algorithm）是一种寻找最短路径的动态规划算法。可以用于寻找最有可能产生观测事件序列的维特比路径——隐含状态序列，适应于多步骤每步多选择模型的最优选择问题，比如HMM。

2 维特比算法核心

维特比算法是针对暴力枚举法的优化

假设有一个长度为$l$的序列，其中$l$对应总天数

其中第$i$天的隐含状态可能情况有$n$种，第$i+1$天的隐含状态可能情况有$m$种

第$i$天的最大概率为$P_i=argma{x}_k(P_{ik},k=1,...,n)$，其中$P_{ik}$表示第$i$天隐含状态$k$的最大概率，而第$i+1$天的最大概率$P_{i+1,j}=argma{x}_j(P_{i+1,j},j=1,...,m)$，，其中$P_{i+1,k}$表示第$i+1$天隐含状态$k$的最大概率，则 $$P_{i+1,j}=argma{x}_k(P_{i,k}\times T_{k,j},k=1,...,n,j=1,...,m)$$

其中$T_{kj}$表示隐含状态从$k$到$j$的转移概率

通过这种方式，第$i+1$天的最大概率就不用再从头开始了，而是基于第$i$天的结果继续计算，减少了计算成本。

将乘法转为加法，最大概率转为最短距离，此时这就是一个最短距离问题了。

3 维特比算法示例

承接1_study/algorithm/概率图类模型/隐马尔可夫模型 HMM:

现在有个病人连续三天来看医生，第一天正常，第二天发寒，第三天头晕

那么这个病人最近这三天每一天的状态到底是健康还是发烧呢？

将连续三天，每天两种状态表述为下图的形式，由左到右的每一条完整路径都是一个维特比路径，每一条维特比路径都对应着一种状态的可能组合，比如{健康，生病，健康} 或 {生病，生病，生病}

已知初始状态及其概率为{健康0.6，发烧0.4}

当第一天的健康状况为正常时:

• 第一天健康状态概率为$0.6\times 0.5=0.3$
• 第一天发烧状态概率为$0.4\times 0.1=0.04$

当第二天的健康状况为发寒时:

假设第一天是健康状态：

• 第二天继续保持健康状态并且发寒的概率为$0.3\ast 0.7\ast 0.4=0.084$
• 第二天健康转为发烧状态并且发寒的概率为$0.3\ast 0.3\ast 0.3=0.027$

假设第一天是发烧状态：

• 第二天继续保持发烧状态并且发寒的概率为$0.04\ast 0.6\ast 0.3=0.0072$
• 第二天发烧转为健康状态并且发寒的概率为$0.04\ast 0.4\ast 0.4=0.0064$

• 第二天健康状态最大概率为$0.084$
• 第二天发烧状态最大概率为$0.027$

当第三天的健康状况为头晕时:

假设第二天是健康状态：

• 第三天继续保持健康状态并且头晕的概率为$0.084\ast 0.7\ast 0.1=0.00588$
• 第三天健康转为发烧状态并且头晕的概率为$0.084\ast 0.3\ast 0.6=0.01512$

假设第二天是发烧状态：

• 第三天继续保持发烧状态并且头晕的概率为$0.027\ast 0.6\ast 0.6=0.00972$
• 第三天发烧转为健康状态并且头晕的概率为$0.027\ast 0.4\ast 0.1=0.00108$

注意，此时不需要再考虑第一天的可能性，这就是维特比算法的计算优势

• 第三天健康状态最大概率为$0.00588$
• 第三天发烧状态最大概率为$0.01512$

所以观察值序列为{正常，发寒，头晕}的病人最有可能的状态序列是

{健康，健康，发烧}

最后总结动图如下：

4 参考

维基百科 - 维特比算法

#Viterbi