如何通俗地讲解 viterbi 算法?

关注者
1,226
被浏览
759,192

49 个回答

这篇回答你绝对看得懂!如下图,假如你从S和E之间找一条最短的路径,除了遍历完所有路径,还有什么更好的方法?

viterbi维特比算法解决的是篱笆型的图的最短路径问题,图的节点按列组织,每列的节点数量可以不一样,每一列的节点只能和相邻列的节点相连,不能跨列相连,节点之间有着不同的距离,距离的值就不在图上一一标注出来了,大家自行脑补

答案:viterbi (维特比)算法。

过程非常简单:

为了找出S到E之间的最短路径,我们先从S开始从左到右一列一列地来看。

首先起点是S,从S到A列的路径有三种可能:S-A1、S-A2、S-A3,如下图:



我们不能武断地说S-A1、S-A2、S-A3中的哪一段必定是全局最短路径中的一部分,目前为止任何一段都有可能是全局最短路径的备选项。

我们继续往右看,到了B列。按B列的B1、B2、B3逐个分析。

先看B1:



如上图,经过B1的所有路径只有3条:

S-A1-B1

S-A2-B1

S-A3-B1

以上这三条路径,各节点距离加起来对比一下,我们就可以知道其中哪一条是最短的。假设S-A3-B1是最短的,那么我们就知道了经过B1的所有路径当中S-A3-B1是最短的,其它两条路径路径S-A1-B1和S-A2-B1都比S-A3-B1长,绝对不是目标答案,可以大胆地删掉了。删掉了不可能是答案的路径,就是viterbi算法(维特比算法)的重点,因为后面我们再也不用考虑这些被删掉的路径了。现在经过B1的所有路径只剩一条路径了,如下图:



接下来,我们继续看B2:



同理,如上图,经过B2的路径有3条:

S-A1-B2

S-A2-B2

S-A3-B2

这三条路径中,各节点距离加起来对比一下,我们肯定也可以知道其中哪一条是最短的,假设S-A1-B2是最短的,那么我们就知道了经过B2的所有路径当中S-A1-B2是最短的,其它两条路径路径S-A2-B2和S-A3-B1也可以删掉了。经过B2所有路径只剩一条,如下图:




接下来我们继续看B3:



同理,如上图,经过B3的路径也有3条:

S-A1-B3

S-A2-B3

S-A3-B3

这三条路径中我们也肯定可以算出其中哪一条是最短的,假设S-A2-B3是最短的,那么我们就知道了经过B3的所有路径当中S-A2-B3是最短的,其它两条路径路径S-A1-B3和S-A3-B3也可以删掉了。经过B3的所有路径只剩一条,如下图:



现在对于B列的所有节点我们都过了一遍,B列的每个节点我们都删除了一些不可能是答案的路径,看看我们剩下哪些备选的最短路径,如下图:



上图是我们删掉了其它不可能是最短路径的情况,留下了三个有可能是最短的路径:S-A3-B1、S-A1-B2、S-A2-B3。现在我们将这三条备选的路径放在一起汇总到下图:



S-A3-B1、S-A1-B2、S-A2-B3都有可能是全局的最短路径的备选路径,我们还没有足够的信息判断哪一条一定是全局最短路径的子路径。

如果我们你认为没毛病就继续往下看C列,如果不理解,回头再看一遍,前面的步骤决定你是否能看懂viterbi算法(维特比算法)。

接下来讲到C列了,类似上面说的B列,我们从C1、C2、C3一个个节点分析。

经过C1节点的路径有:

S-A3-B1-C1、

S-A1-B2-C1、

S-A2-B3-C1



和B列的做法一样,从这三条路径中找到最短的那条(假定是S-A3-B1-C1),其它两条路径同样道理可以删掉了。那么经过C1的所有路径只剩一条,如下图:




同理,我们可以找到经过C2和C3节点的最短路径,汇总一下:



到达C列时最终也只剩3条备选的最短路径,我们仍然没有足够信息断定哪条才是全局最短。

最后,我们继续看E节点,才能得出最后的结论。

到E的路径也只有3种可能性:



E点已经是终点了,我们稍微对比一下这三条路径的总长度就能知道哪条是最短路径了。



在效率方面相对于粗暴地遍历所有路径,viterbi 维特比算法到达每一列的时候都会删除不符合最短路径要求的路径,大大降低时间复杂度。

viterbi算法果然很简单吧!

看没看懂都去左下角点个赞吧!

尝试用高中概率知识去理解一下 Veterbi 算法。内容绝对粗浅,100% 抄袭,欢迎指正。用一个别人家的栗子来说一下。

1.题目背景:

从前有个村儿,村里的人的身体情况只有两种可能:健康或者发烧。
假设这个村儿的人没有体温计或者百度这种神奇东西,他唯一判断他身体情况的途径就是到村头我的偶像金正月的小诊所询问。
月儿通过询问村民的感觉,判断她的病情,再假设村民只会回答正常、头晕或冷。
有一天村里奥巴驴就去月儿那去询问了。
第一天她告诉月儿她感觉正常。
第二天她告诉月儿感觉有点冷。
第三天她告诉月儿感觉有点头晕。
那么问题来了,月儿如何根据阿驴的描述的情况,推断出这三天中阿驴的一个身体状态呢?
为此月儿上百度搜 google ,一番狂搜,发现维特比算法正好能解决这个问题。月儿乐了。


2.已知情况:

隐含的身体状态 = { 健康 , 发烧 }

可观察的感觉状态 = { 正常 , 冷 , 头晕 }

月儿预判的阿驴身体状态的概率分布 = { 健康:0.6 , 发烧: 0.4 }

月儿认为的阿驴身体健康状态的转换概率分布 = {
健康->健康: 0.7 ,
健康->发烧: 0.3 ,
发烧->健康:0.4 ,
发烧->发烧: 0.6
}

月儿认为的在相应健康状况条件下,阿驴的感觉的概率分布 = {
健康,正常:0.5 ,冷 :0.4 ,头晕: 0.1 ;
发烧,正常:0.1 ,冷 :0.3 ,头晕: 0.6
}
阿驴连续三天的身体感觉依次是: 正常、冷、头晕 。


3.题目:

已知如上,求:阿驴这三天的身体健康状态变化的过程是怎么样的?


4.过程:

根据 Viterbi 理论,后一天的状态会依赖前一天的状态和当前的可观察的状态。那么只要根据第一天的正常状态依次推算找出到达第三天头晕状态的最大的概率,就可以知道这三天的身体变化情况。
传不了图片,悲剧了。。。
1.初始情况:
  • P(健康) = 0.6,P(发烧)=0.4。

2.求第一天的身体情况:
计算在阿驴感觉正常的情况下最可能的身体状态。

  • P(今天健康) = P(正常|健康)*P(健康|初始情况) = 0.5 * 0.6 = 0.3
  • P(今天发烧) = P(正常|发烧)*P(发烧|初始情况) = 0.1 * 0.4 = 0.04

那么就可以认为第一天最可能的身体状态是:健康。
3.求第二天的身体状况:
计算在阿驴感觉冷的情况下最可能的身体状态。
那么第二天有四种情况,由于第一天的发烧或者健康转换到第二天的发烧或者健康。

  • P(前一天发烧,今天发烧) = P(前一天发烧)*P(发烧->发烧)*P(冷|发烧) = 0.04 * 0.6 * 0.3 = 0.0072
  • P(前一天发烧,今天健康) = P(前一天发烧)*P(发烧->健康)*P(冷|健康) = 0.04 * 0.4 * 0.4 = 0.0064
  • P(前一天健康,今天健康) = P(前一天健康)*P(健康->健康)*P(冷|健康) = 0.3 * 0.7 * 0.4 = 0.084
  • P(前一天健康,今天发烧) = P(前一天健康)*P(健康->发烧)*P(冷|发烧) = 0.3 * 0.3 *.03 = 0.027

那么可以认为,第二天最可能的状态是:健康。
4.求第三天的身体状态:
计算在阿驴感觉头晕的情况下最可能的身体状态。

  • P(前一天发烧,今天发烧) = P(前一天发烧)*P(发烧->发烧)*P(头晕|发烧) = 0.027 * 0.6 * 0.6 = 0.00972
  • P(前一天发烧,今天健康) = P(前一天发烧)*P(发烧->健康)*P(头晕|健康) = 0.027 * 0.4 * 0.1 = 0.00108
  • P(前一天健康,今天健康) = P(前一天健康)*P(健康->健康)*P(头晕|健康) = 0.084 * 0.7 * 0.1 = 0.00588
  • P(前一天健康,今天发烧) = P(前一天健康)*P(健康->发烧)*P(头晕|发烧) = 0.084 * 0.3 *0.6 = 0.01512

那么可以认为:第三天最可能的状态是发烧。

5.结论

根据如上计算。这样月儿断定,阿驴这三天身体变化的序列是:健康->健康->发烧。


维基百科的这个例子的动态图:File:Viterbi animated demo.gif


这个算法大概就是通过已知的可以观察到的序列,和一些已知的状态转换之间的概率情况,通过综合状态之间的转移概率和前一个状态的情况计算出概率最大的状态转换路径,从而推断出隐含状态的序列的情况。