前面一篇博客讲到了中文分词的机械分词算法，这种算法实现相对比较简单，但是分词效果还是有待商榷。比如下面这样一句话：产量三年中将增长两倍。按照机械分词的算法，它可能会被分成这样一种形式：产量
| 三年 | 中将 | 增长 | 两倍。
机械分词将‘中将’分成了一个词，的确‘中将’在词典中是有这么一个词，但在这句话中将它们划分成一个词显然是不合理的，于是一种新的方法就被提出来了
- 基于隐马尔科夫模型的维特比算法。
关于这个问题，google前研究员吴军（现在好像去腾讯了）有一篇博客（数学之美系列 -
统计语言模型）对此进行了很好的概述，建议大家在阅读这篇博客前先看看他的那篇文章。
就像文献[1]中所说的，自然语言处理中的很大一类问题可以直接或间接的看成是对应问题，例如音到字转换就是给音串找到对应的字串，字到音的转化则是给字串找对应的音串，甚至翻译问题也是对应问题：给定一种语言的一个字串（句子），找到另一种语言中对应的字串（句子）。同样，中文分词也可以看成这样一种问题，给定一个字串（句子），找到对应的词串（分词）。
用公式表示，给定的子串（句子）用Y表示就是
其中
表示一个单字。
我们所求的分词X表示为：
其中
表示一个单词（每个单词由一个或多个单字组成）
我们的目标很简单，就是希望找到最可能的X，使得其后验概率P（X|Y）最大。也就是说我们需要找到一种最可能的分词方法，使得在这个句子存在的前提条件下，该分词结果出现的概率最大。根据贝叶斯公式有：
那么为了最大化P（X|Y），经过变化就变成了下面的形式
接下来的问题就是分词的模型是什么？答案就是马尔科夫模型。一个句子中某个分词的出现不是独立出现的，而是和它前面的n个单词有关联的，这就是n阶马尔科夫模型。我们先考虑最简单的情况，一阶马尔科夫模型（实践证明，一阶模型是一个很有效的模型），也就是说某个分词的出现只和它紧邻的前面的一个分词有关，而与之前的分词无关。同时分词相对于字串的条件概率又是独立分布的（独立输出假设）。那么就有：
看到这里就会有同学举手了？“这不是典型的隐马尔科夫模型嘛”的确，回答正确。这的确是一个隐马尔科夫模型，X（分词）就是隐变量，Y（字串）就是观测变量。隐马尔科夫模型以及维特比算法在很多资料或教材中都有涉及，文献[2][3]都对它有很好的阐述，本文也就不再赘述。这里着重阐述一下维特比算法如何对应到中文分词。举个例子，假若有这么一个句子：ABCDEF。其中A,B,C,...F分别对应一个个单字。我们来考虑如何对其分词。我们知道，维特比算法实际上是动态规划算法中的一种，它实际上是在求一个最佳路径的问题。如果机械得将其对应到隐马尔科夫模型，那么就有如下：
图1
所有可能的分词（这些可能的分词通过前面提到的trie字典树得到）组成了隐变量，分词对应在句子中的字串就是观测变量。隐变量是一个马尔科夫模型，隐变量相对于观测变量的概率是独立分布的。
S1,S2,..S6就是观测变量，表示的是分词所对应的字串，S1+S2+...+S6=ABCDEF。
T1,T2,...,T6表示的就是分词的阶段，T1表示第一次分词的阶段，T2表示第二次分词阶段等等。可以想象一下，分词是按照时间顺序从前往后开始分词的，所有我们用Tn对分词过程进行区分。
椭圆代表的就是隐藏变量。椭圆之间的连线表示的是条件概率。把它对应到一个标准的HMM模型中去，那么就有
π向量。隐藏变量的初始化向量，对于这个例子就有
π[A, AB, ABC, B, BC,...., E, EF, F ]=[r1, r2, r3, r4, ..., rn]
rn代表对应单词出现的概率
状态转移矩阵A,就是各个分词之间的关系概率
A AB ABC B BC ... E EF F
A 0 0 0 a1 a2 0 0 0
AB 0 0 0 0 0
ABC
B
BC
...
E
EF
S1 S2 S3 S4 S5 ... E
A 1 1 1 1 1 1
AB 1 1 1 1 1 1
ABC
B
BC
...
E
EF
针对分词问题，其实仔细观察上面的公式3，你会发现,
的值要么是100%，要么为0,举个例子P(S1|A)=100%，为什么呢，因为A作为第一个分词，那么一定会有A这个字串出现在句子的第一部分。同理P(S1|AB),P(S1|ABC)都是100%。那么P(S1|B)呢，它等于0，为什么呢？B作为第一个分词的话，不可能形成ABCDEF这样一个句子。基于这个特点，你会发现中文分词的混淆矩阵是一个大部分为0的稀疏矩阵，有些分词在某些特定的分词阶段就可以舍掉不必考虑。于是该马尔科夫模型可以简化成如图2
图2
至于剩下的就是标准的维特比算法了，教科书中都有明确的讲解，这里就不在啰嗦。具体可以参考文献[3]的一系列文章。维特比算法的关键就是求局部最优路径。每一步的局部最优路径都只和前面一步的最优路径有关。
总结下图2基于维特比的分词方法就是：
第一步：利用Trie字典树，构造一个类似图1的graph。构造方法很简单，先生成T1，T1就是以A开头的可能出现的分词，再生成T2，T2就是以B开头的可能的分词，直到T6，以F开头的分词。
第二步：针对每一步Ti，计算这一步中的每一个可能分词的最佳路径
表示分词Wi在Tn时与之前所得到得分词组成的联合概率中最佳的那个概率，也就是说目前阶段所对应字串对应的最可能的分词，这也是当前阶段最可能的分词所组成的最佳路径。表示在最佳路径上的前向词，是转移概率，表示混淆概率，始终为100%，当你从T1进行到T6最后一步时，你就可以得到最后的结果，也就是所有最佳分词路径。
二阶马尔科模型
如果我们假设某一分词跟前面两个分词有关，就构成二阶马尔科夫分词模型。本质上二阶马尔科夫模型的维特比算法和一阶马尔科夫模型算法是一致的，只不过每个节点都有两个前向节点.二阶马尔科夫模型有
一个二阶马尔科夫模型由以下几个参数来代表
1 转移矩阵 A1={a[ij] = p(w[j] | w[i])}
2 转移矩阵 A2={a[ijk]=P(w[k] | w[i], w[j] )}
3 混淆矩阵 B1 ={b[i] = P(O[i] | w[i]) }
4 混淆矩阵 B2 = {b[ij] = p(O[j] | w[i], w[j])}
5 初始向量 π = {w[1],...w[N]}
w代表分词，是隐变量，o是分词的字串，是观察变量。方括号[
]代表下标。也许有人会在意，为什么转移矩阵和混淆矩阵有2个？其实很简单，A1，B1是在马尔科夫链的第一步起作用，在初始状态，只有一个概率，只能用一阶转移矩阵来求联合概率。回到维特比算法，它与一阶马尔科夫模型的区别仅在于第二步。
表示最佳路径，也就是目前阶段字串所对应的分词最大的联合概率，转移向量，j,k两个分词表示的是前一步最佳路径上的前2个词，混淆概率，混淆概率也是一个条件概率，由该路径上当前分词和前一个分词决定，实际上是100%.
所以本质上二阶与一阶差别并不大，算法本质上一样。只不过转移矩阵，混淆矩阵相对一阶比较大
独立分布模型
我们再多想一下，如果中文分词不是马尔科夫模型，而是独立分布模型，也就是说当前分词与之前的分词是独立分布的。这种模型其实在有些特定的应用环境下也是有意义的，比如说用户输入论文的关键词，而且忘记输入分割符，那么系统应该能够纠错并给出正确的分词，在在这种情况下，这个模型也就有意义了。
这种情况实际上是马尔科夫模型的一种特例，只不过转移概率被独立分布的联合概率取代而已。因此上述的方法针对独立模型全部有效。
总结一下，隐马尔科夫模型和独立分布模型是一种特殊的图。这些模型的不同之处在于，他们的图根据分词的位置，可以划分成不同的阶段。因此一些通用图算法不能解决的问题，比如最长路径问题，在HMM模型中往往能够得以解决。
参考文献：
[1]统计语言模型和汉语音字转换的一些新结论
[2]http://www.comp./roger/HiddenMarkovModels/html_dev/viterbi_algorithm/s3_pg3.html
[3]http://www./hmm-learn-best-practices-five-forward-algorithm-5
[4]基于二阶隐马尔科夫模型的文本信息抽取
