HMM算法用于分词

一、HMM的典型模型五元组

状态集、观测集、初始状态分布、状态转移矩阵、发射矩阵。

1、状态集

(B, M, E, S)，B代表该字是词语中的起始字，M代表是词语中的中间字，E代表是词语中的结束字，S则代表是单字成词。

2、观测集

就是所有汉字(东南西北你我他…)，甚至包括标点符号所组成的集合。

在HMM模型中文分词中，输入是一个句子(也就是观察序列)，输出是这个句子中每个字的状态值，即状态序列。

3、初始状态分布

每一句话第一个字符的对应状态概率。

在训练阶段参数估计中得到。

如：{'B': -0.48164247830489765,'M': -3.14e+100, 'E': -3.14e+100, 'S': -0.96172723110752845}

可以看到第一个字符的初始状态只能是‘B’和‘S’。

4、转移概率矩阵

状态集STATES={‘B’,‘M’,‘E’,‘S’}之间的转移概率。

在中文分词中状态转移矩阵是一个4*4的矩阵，在训练阶段参数估计中得到。1、统计训练数据中状态转移的频数确定矩阵；2、频数矩阵除以对应每一行状态的统计数得到频率；3、对频率取对数。

如：

{'B': {'B': -3.14e+100, 'M':-1.9594399657636383, 'E': -0.15191340104766693, 'S': -3.14e+100},

'M': {'B': -3.14e+100, 'M':-1.0983633205740504, 'E': -0.40558961540346977, 'S': -3.14e+100},

'E': {'B':-0.78182902092047468, 'M': -3.14e+100, 'E': -3.14e+100, 'S':-0.62312924475978682},

'S': {'B': -0.74289298827998818,'M': -3.14e+100, 'E': -3.14e+100, 'S': -0.81330579119502522}}

可以看到对应状态‘B’后面只能接‘M’和‘E’；状态‘M’后面只能接‘M’和‘E’；状态‘E’后面只能接‘B’和‘S’；状态‘S’后面只能接‘B’和‘S’。

5、发射概率矩阵

每一个字符对应状态集STATES={‘B’,‘M’,‘E’,‘S’}中每一个状态的概率。

通过对训练集每个字符对应状态的频数统计得到。

二、 Viterbi算法

Viterbi算法用在测试阶段对输入文本序列进行标注，输入是观测序列，输出是状态序列，需要借助三个模型参数，分别是初始化矩阵、状态转移矩阵、发射概率矩阵。

被标注的文本是：小明硕士毕业于中国科学院计算所

1、变量定义

二维数组 weight[4][15]——4是状态数(0:B,1:E,2:M,3:S)，15是输入句子的字数。比如 weight[0][2] 代表观测值“硕”字被标注为状态值B的概率。

二维数组 path[4][15]——4是状态数(0:B,1:E,2:M,3:S)，15是输入句子的字数。比如 path[0][2] 代表 weight[0][2]取到最大值时，前一个字的状态，比如 path[0][2] = 1, 则代表 weight[0][2]取到最大时，前一个字(也就是“明”)的状态是E。记录前一个字的状态是为了使用viterbi算法计算完整个 weight 之后，能对输入句子从右向左地回溯回来，找出对应的状态序列。

2、变量初始化

weight[0][0]，weight[1][0]，weight[2][0]，weight[3][0]要被初始化，分别代表第0个词“小”被标注为B、E、M、S的概率。根据初始状态分布和发射概率矩阵求解。

初始状态分布

B:-0.26268660809250016

E:-3.14e+100

M:-3.14e+100

S:-1.4652633398537678

发射概率矩阵可以得出

Status(B) -> Observed(小) : -5.79545

Status(E) -> Observed(小) : -7.36797

Status(M) -> Observed(小) : -5.09518

Status(S) -> Observed(小) : -6.2475

所以可以初始化 weight[i][0] 的值如下：

weight[0][0] = -0.26268660809250016 + -5.79545 = -6.05814

weight[1][0] = -3.14e+100 + -7.36797 = -3.14e+100

weight[2][0] = -3.14e+100 + -5.09518 = -3.14e+100

weight[3][0] = -1.4652633398537678 + -6.2475 = -7.71276

注意上式计算的时候是相加而不是相乘，因为之前取过对数的原因。

3、变量求解

Viterbi算法变量求解

tmp=weight[k][i-1] + _transProb[k][j] + _emitProb[j][sentence[i]];

后一个字的标注取{B,E,M,S}的概率weight与前一个字的标注取{B,E,M,S}的概率weight有关。后一个字的weight要根据前一个字的weight去推断。

4、确定边界条件和路径回溯

对于每个句子，最后一个字的状态只可能是 E 或者 S，不可能是 M 或者 B。

所以在本文的例子中只需要比较 weight[1][14] 和 weight[3][14] 的大小即可，即最后一个字标注为E和S的概率谁大。

在本例中weight[1][14] < weight[3][14]，即 S > E，也就是说第14字(最后一个字)的标注是S。path[3][14]的取值代表第14个字标注为S(3)时，前一个字(第13个字)的标注。所以回溯的起点就是path[3][14]。

回溯的路径是:

SEBEMBEBEMBEBEB

倒序一下就是:

BE/BE/BME/BE/BME/BE/S

所以切词结果就是:

小明/硕士/毕业于/中国/科学院/计算/所

三、代码实现

1、语料信息

首先，需要一个完整的语料信息，该语料库需要：

1）覆盖范围广。

理论上需要覆盖你所有可能会被分词的文字，否则发射矩阵为出现极端情况，无法分词。

2）需要文本标注正确。

如一些专有名词，"太平洋保险"等等，需要被分为一个词，因为他是一个公司名称，而不应该被分为"太平洋/保险"。

提取该语料库，可能需要人工干预。

将分词的结果进行标注，按照上文提到的信息，打上SBME的标注（方便起见，这里直接用jieba分词的结果）：

标注数据

2、计算初始状态概率分布

ME是不会出现在句首，即将其概率设置为0，在矩阵中为：-3.14e+100（取了log值）。

计算初始状态概率分布伪代码

3、计算转移概率矩阵

其中有一些是不可能转移的信息，如：B->S，E->M等等，将这些情况的概率的log值设置为-3.14e+100。其他的按照词前后的状态序列统计，统计前后之间的关系，这里已知假设，当前状态仅与前一状态有关，与更前面的状态无关。所以，思路：

内容按照/拆分->取出状态序列->分拆为2元组->统计前一状态出现后一状态的概率

4、计算发射概率矩阵

内容按照/拆分->取出状态：观测的key：value->统计某状态下，某观测出现的次数，即为概率值。某状态下，所有观测出现的概率和为1。（拿到一个盒子，所有球出现的概率和为1）

5、使用Viterbi算法

HMM+Viterbi实现中文分词，代码见HMM中文分词