本文主要是介绍维特比算法(Viterbi)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
维特比算法 (Viterbi algorithm) 是机器学习中应用非常广泛的动态规划算法，在求解隐马尔科夫、条件随机场的预测以及seq2seq模型概率计算等问题中均用到了该算法。实际上，维特比算法不仅是很多自然语言处理的解码算法，也是现代数字通信中使用最频繁的算法。
（1）从点S出发，对于第一个状态X1的各个节点，不妨假定有n1个，计算出S到它们的距离d(S,X1i)，其中X1i代表任意状态1的节点。因为只有一步，所以这些距离都是S到它们各自的最短距离。
（2）对于第二个状态X2的所有节点，要计算出从S到它们的最短距离。对于特点的节点X2i，从S到它的路径可以经过状态1的n1中任何一个节点X1i，对应的路径长度就是d(S,X2i) = d(S,X1i) + d(X1i,X2i)。由于j有n1种可能性，我们要一一计算，找出最小值。即：
d(S,X2i) = minI=1，n1 d(S,X1i) + d(X1i,X2i)
这样对于第二个状态的每个节点，需要n1次乘法计算。假定这个状态有n2个节
点，把S这些节点的距离都算一遍，就有O(n1·n2)次计算。
（3）接下来，类似地按照上述方法从第二个状态走到第三个状态，一直走到最后一个状态，就得到了整个网格从头到尾的最短路径。每一步计算的复杂度都和相邻两个状态Si和Si+1各自的节点数目ni，ni+1的乘积成正比，即O(ni·ni+1)
（4）假设这个隐含马尔可夫链中节点最多的状态有D个节点，也就是说整个网格的宽度为D，那么任何一步的复杂度不超过O(D2)，由于网格长度是N，所以整个维特比算法的复杂度是O(N·D2)。
分词应用：
我们有一个词典和每个词出现的概率：
词典:["经常"、"经"、“有”、“有意见”、“意见”、“分歧”、“见”、“意”、“见分歧”、“分”]
概率:[0.1、 0.05、 0.1、 0.1、 0.2、 0.2、 0.05、0.05、0.05、 0.1]
-log(x):[2.3、 3、 2.3、 2.3、 1.6、 1.6、 3、 3、 3、 2.3]
如图所示，直观地画出了各个词对应下一个词出现的转移概率，我们的目的是寻找一条最短路径（从节点1-->节点8），也就是将每条线上的权重值进行累加，使得最终的和最小。
在这里，我们定义f(8)为从第一个节点到第8个点的最短路径，同理f(7)为第一个节点到第七个节点，所以，f(8)也可以表述为f(7)+20
简单分析：从图中的1-->3，我们发现，f(1-->2-->3) > f(1-->3)，所以我们会选择从1节点到3节点的路径。
递归分析：从图中，我们可以发现，第一个节点是开始端，最短路径应为0，即minf(0)=0;在第二个节点中，只有第一个节点与之相连，所以minf(2)=3；在第三个节点中，存在两条可选的路径，可见从1-->3的路径比1-->2-->3的路径更短，所以minf(3)=2.3;在第四个节点中，只有3-->4的唯一一条路径，所以minf(4)=f(3)+2.3;依次类推.......得到如下表：
所以，我们可以寻得最短路径为1-->3-->6-->8（1经常3有意见6分歧8）
每一个最短路径的节点即为一个分词的断点，所以，分词的最后结果为：
经常|有意见|分歧
这篇关于维特比算法(Viterbi)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
