HMM-维特比算法

HMM回顾

最终的公式可以解释主要分为两个部分：

• P(xi|yi)，发射概率，字面意思是从一个词性中发射/生成出某一个单词的概率
• P(yi|yi-1)，转移概率，表示从一个词性转移到下一个词性的概率
  这两个概率都可以通过标注文档中统计得出

隐马科夫链解法：维特比算法（Viterbi）

维特比算法其思想就是动态规划，下面以HMM进行词性标注讲解维特比算法。

上图中，我们需要对 “natural language processing ( nlp )” 这句话进行词性标注。最终目标是找到下图所示的最优可能路径。

求解顺序：

1. 在natural这个词中（第一列），我们要保留所有可能的词性，因为每个词性后边都可能出现最优路径，这里需要求的概率是P(“natural”|词性)，这个是可以根据我们输入的训练集（文档）统计得出。
2. 在第二列中，我们需要求解发射概率和转移概率。例如JJ，我们可以分别求出JJ->NN，JJ->JJ，JJ->VB，JJ->LRB，JJ->RRB的转移概率以及P(“language”|词性)的发射概率，发射概率*转移概率值最大的路径即为JJ的最优路径，同理我们可以对所有的词性都求出的一个最优路径。大概样子就变成了如下图所示（示意图，嘻嘻）
   

注：我们在这里求解发射概率与转移概率的乘积时，为了避免精度损失，通常会对其取对数
3. 重复第二步，则最终结果如下图所示（示意图，嘻嘻）
*
其实最终利用维特比算法得到了“词性”（量词）条路径，从中选出概率最大路径即可