基于统计的分词方法有：N-gram、隐马尔可夫（Hidden Markov Model ，HMM）、最大熵模型（Maximum Entropy Model, ME）和条件随机场（Conditional Random Fields，CRF）等，一般用的比较多的是HMM和CRF，比如简单又好用的jieba就是字符串匹配+HMM 的分词方法，HanLP等有用到CRF。一般来说CRF分词效果要好于HMM，本文主要介绍HMM分词。

  HMM由俄国数学家A.A.马尔可夫于1907年提出，主要用于描述随机生成过程， HMM在语音识别、信息科学、NLP等诸多领域有着极其广泛的应用。在NLP领域更多的是用来处理分词、词性标注、实体识别等序列标注问题，HMM属于生成式模型，原理在这里不打算细讲了，李航的《统计学习方法》和周志华的西瓜书都讲得很详细了，网上也是随便一搜一大堆的街货。

HMM基本问题

HMM有三个基本问题：

• 概率计算问题。给定模型 $\lambda=(A,B,\pi)$ 和观测序列 $O=(o_1,o_2,…,o_T)$ ，计算在模型 $\lambda$ 下观测序列 $O$ 出现的概率 $P(O|\lambda)$ 。也就是模型、参数、结果已知，求出现该结果的概率。
• 学习问题。 已知观测序列 $O=(o_1,o_2,…,o_T)$ , 估计模型 $\lambda=(A,B,\pi)$ 的参数，使得在该模型下观测序列概率 $P(O|\lambda)$ 最大，即用极大似然估计的方法估计参数。即模型已知，参数未知
• 预测问题。 也称为解码问题，已知模型 $\lambda=(A,B,\pi)$ 和观测序列 $O=(o_1,o_2,…,o_T)$ ，求对给定观测序列条件概率 $P(I|O)$ 最大的状态序列 $I=(i_1,i_2,…,i_T)$ ，即给定观测序列，求最有可能的对应状态序列。

中文分词属于第三个问题，也就是给定一个待分词句子/文本，找出最有可能的隐藏状态序列。

基于HMM的中文分词

假如现在要对这样一句话分词：“我们都是追梦人”，嗯，很简单，幼儿园水平，不假思索就分出来了，结果是：我们/都/是/追梦人 。如果使用BMES分别表示词首位、词中间位置、词末尾位置、单字词，那么：我们/都/是/追梦人 可以表示为：BE/S/S/BME。这里分词的语句被称为观测序列，“BE/S/S/BME”为隐藏状态序列。我们人工分词的话，一般是从左（句首）往右（句尾）浏览要分词的文本，根据场景以及语句的通顺程度将句子逐一切分，有时遇到易混淆的地方还会前后追溯，如“我们都是追梦人” 就可能会误分为：我们/都/是/追梦/人，HMM在分词时不会考虑这么多，其假设:

• 1、当前时刻t的状态只依赖于其前一时刻的状态，与其他时刻状态及观测无关，也与时刻t无关。也称为齐次马尔可夫性假设；
• 2、任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关。也称为观测独立性假设
  这两个假设条件只是为了简化计算，不是必须的。对于假设1，如果当前时刻t的状态与前2个时刻的状态有关的话就是二阶马尔可夫，与前3个时刻的状态有关的话就是三阶马尔可夫，以此类推。
  

上图，箭头指向代表依赖关系，如 $A \rightarrow B$ 表示 $B$ 依赖于 $A$ ，但 $A$事件发生与 $B$ 无关，无箭头指向的事件代表不相关，如观测“我”和观测“们”无关。
由t时刻到t+1时刻的状态可能性称为状态概率，各种状态之间可能性组成状态概率矩阵。

状态转移概率矩阵：

状态到观测的可能性称为发射概率，不同状态到不同观测的可能性组成的矩阵称为发射概率矩阵。

发射概率矩阵：

初始概率，组成初始概率矩阵。

初始状态: $\pi$

为了方便计算，上面矩阵的概率都转成了对数。这里有两个问题，第一是，发射矩阵、状态转移矩阵、初始概率矩阵怎么计算出来的；第二是：如何找出最有可能的隐藏状态序列。

概率矩阵计算

矩阵的计算很简单，直接根据语料库统计出来就好了。
初始概率矩阵：

$$p(y_1=s)=\frac{count(y_1=s)}{\sum count(y_1 = s_i)}$$

发射概率矩阵：

$$p(y_{l+1}=s^{\prime}|y_l=s) = \frac{count(s \rightarrow s^{\prime})}{count(s)}$$

其中 $s$是当前时刻状态，$s^{\prime}$ 是下一时刻状态。
状态转移概率矩阵：

$$p(x_l=t|y_l=s) = \frac{count(s \rightarrow t)}{count(s)}$$

其中 $s$ 是当前时刻状态，t是当前时刻观测。

viterbi

  前面计算了初始概率矩阵、发射概率矩阵和状态转移矩阵，理论上有了这三个矩阵，就可以进行分词了，最简单直观的方法是直接按照概率公式计算，列举出所有可能的路径，然后从所有可能的路径中找到概率最大的路径，但是这样计算量很大，对于观测序列长度为T,状态为N，算法复杂度为 $N^T$，计算量太大了，并不是有效的办法。针对这种情况，可以考虑使用动态规划来求解，viterbi算法天然适用于求解HMM路径问题，其计算复杂度为 $O(T|N|^2)$。
  关于维特比算法的原理讲解可以看这篇文章小白给小白详解维特比算法（一)，通俗易懂。为了方便说明，这里以“我们都是追梦人”为例介绍viterbi算法。

对于“我”字，通过初始状态与发射概率相乘（初始状态、发射概率矩阵、状态转移矩阵沿用上面三个表格数据，这里将概率取对数后计算，也就是相加），其各隐藏状态概率为：

这里初始最优路径有4条。对于第二个字“们”，其计算方法如下（手算比较麻烦，这里偷个懒）：

其中 $B \rightarrow E, S \rightarrow S$ 这些表示 $t-1$ 时刻（我）的状态到 $t$时刻（们）的状态的路径，剩下的“都是追梦人”的计算方法也是一样。如果还不是很清楚的话，可以看下图：

因为句子结束状态只能是ES之一，两者中概率最大为-46.901，所以分词结果为：我们/都/是/追梦/人 。嗯，语料不太够。

存在问题

1、不存在语料库的字发射概率为0
由于发射概率矩阵是从训练词汇中统计的，导致出现的一种情况是，HMM对于未曾出现在语料库中的字的发射概率为0，进而导致该字后面的路径概率都为0，分词不work也就无法有效地找出最佳路径，虽然在实际计算的时候对于不存在的词往往会默认给一个最小的数。对于下面两句话：

1
2

句式1：每个月几乎都有两三条船停靠中国港口。   
句式2：每个月几乎都有6条船停靠中国港口。

句式1均为中文，句式2有一个数字（该数字不在jieba预训练的语料库中），为方便测试，可以调用jieba的纯HMM模式切词，得到的效果完全不一样。

list(jieba.finalseg.__cut('每个月几乎都有两三条船停靠中国港口。'))
#output: ['每个', '月', '几乎', '都', '有', '两三条', '船', '停靠', '中国港', '口', '。']   

list(jieba.finalseg.__cut('每个月几乎都有6条船停靠中国港口。'))
#output: ['每个', '月', '几乎', '都', '有', '6', '条', '船', '停', '靠', '中', '国', '港', '口', '。']

jieba对此问题的处理方式是先将中文提取出来，喂入HMM，对一些非中文字符如数字百分号则单独处理。
2、优化的方法就是增加语料，调整初始、发射、转移概率矩阵。这是好事也是坏事，免去了做特征的繁琐，但也没有什么可以优化的了。

总结

  HMM简单且强大，将HMM应用于中文分词，其实就是求解带切分句子最有可能隐藏状态序列，其初始状态、转移状态、发射概率矩阵都可以从训练数据中统计而来，对于句子的所有可能隐藏状态序列，穷举复杂度太高，可以使用viterbi算法求解。另外，基于HMM的中文分词方法脚本已经上传至我的github，包括生成初始概率矩阵、状态转移矩阵、发射概率矩阵的脚本，为了方便后续使用HMM训练专有领域数据，并结合jieba使用，这里生成的三个矩阵结果文件跟jieba调用文件一致。

赏

赏个铜板呗

支付宝