CSDN博客：皮乾东
知乎：Htrying
微博：Htring的微博
微信公众号：自然语言处理爱好者（ID：NLP_lover）
文章来自：《数学之美》

Viterbi-Algorithm算法

维特比算法是一个特殊但应用最广的动态规划算法。利用动态规划，可以解决任何一个图中的最短路径问题。而维特比算法是针对一个特殊的图-篱笆网了（Lattice）的有向图最短路径问题而提出来的。它之所以重要，是因为凡是使用隐马尔科夫模型描述的问题都可以用它解码，包括当前的数字通信、语音识别、机器翻译、拼音转汉字、分词等。

背景

假定用户（盲打时）输入的拼音时$<![CDATA[y_1,y_2,...,y_N]]>$，对应的汉字是$<![CDATA[x_1,x_2,...,x_N]]>$（虽然真正的输入法产品都是以词作为输入单位的，为了便于说明问题及简单起见，以字为单位来解释维特比算法），那么根据当前介绍的工具：

$<![CDATA[x_1,x_2,...,x_N=Argmathop{Max}limits_{x in X}P(x_1,x_2,...,x_N|y_1,y_2,...,y_N)=Argmathop{Max}limits_{x in X}prod_{i=1}^NP(y_i|x_i)P(x_i|x_{i-1})]]>$ (1)

输入的可见序列为$<![CDATA[y_1,y_2,...,y_N]]>$,而产生他们的隐含序列是$<![CDATA[x_1,x_2,...,x_N]]>$。可以用下图描述这样一个过程：

这是一个相对简单的隐马尔科夫链，没用状态跳跃，也没有自环。$<![CDATA[P(x_i|x_{i-1})]]>$是状态之间的转移概率，$<![CDATA[P(y_i|x_i)]]>$是每个状态的产生概率。现在，这个马尔科夫链的每个状态的输出是固定，但是每个状态的值可以变化。比如输出读音”zhong”的字可以是”中”、”种“等多个字。我们不妨抽象一点，用符号$<![CDATA[x_{ij}]]>$表示状态$<![CDATA[x_i]]>$的第$<![CDATA[j]]>$个可能的值。如果把每个状态按照不同的值展开，就得到下面这个篱笆网络(Lattice):

在上图中，每个状态有3个或4个值，当然时间中它们可以有任意个值。

那么从第一个状态到最后一个状态的任何一条路径（Path）都可能产生我们观察到的输出序列Y。当然这些路径的可能性不一样，而我们要做的就是找到最可能的这条路径，并不是很难。但麻烦的是这样的路径组合数非常多，会让序列状态数的增长呈指数式增长。汉语中每个无声调的拼音对应13个左右的国标汉字，假定句子长为10个字，那么这个组合数为$<![CDATA[13^{10}sim 5times10^{14}]]>$这个计算量就相当的大了。因此，需要一个最好能和状态数目成正比的算法，而这个算法在1967年首次提出，即维特比算法。

主要内容

维特比算法基础

1.如果概率最大的路径P（或者说是最短路径）经过某个点，比如下图中的$<![CDATA[x_{22}]]>$，那么这条路径上从起始点S到 版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/meiqi0538/article/details/80960128
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。