HMM(隐马尔科夫)用于中文分词

 

一、理解隐马尔科夫

1.1 举例理解

来源:< http://www.cnblogs.com/skyme/p/4651331.html >
假设我手里有三个不同的骰子。第一个骰子是我们平常见的骰子(称这个骰子为D6),6个面,每个面(1,2,3,4,5,6)出现的概率是1/6。第二个骰子是个四面体(称这个骰子为D4),每个面(1,2,3,4)出现的概率是1/4。第三个骰子有八个面(称这个骰子为D8),每个面(1,2,3,4,5,6,7,8)出现的概率是1/8。

image.png

当我们无法观测到时使用哪个骰子投掷,仅仅能看到投掷的结果的时候。例如我们得到一个序列值:1 6 3 5 2 7 3 5 2 4。
它其实包含了:1、隐含的状态,选择了哪个骰子;2、可见状态,使用该骰子投出数值。如下:

image.png

而假设,每个状态间转移的概率(选择骰子的概率)是固定的(即为不因观测值的数值而改变)。可以得到状态转移矩阵。

image.png

那么我们得到观测值序列(1 6 3 5 2 7 3 5 2 4)出现概率的计算公式:

image.png

举前3个观测值(1 6 3)的例子,计算如下:

image.png

以上计算中,假设选择3个骰子的概率是相同的,都是1/3。

1.2 例子抽象

通过以上例子可以抽象一下,上面的例子中:

3种不同情况的骰子,即为:状态值集合(StatusSet)
所有可能出现的结果值(1、2、3、4、5、6、7、8):观察值集合(ObservedSet)
选择不同骰子之间的概率:转移概率矩阵(TransProbMatrix ),状态间转移的概率
在拿到某个骰子,投出某个观测值的概率:发射概率矩阵(EmitProbMatrix )-即:拿到D6这个骰子,投出6的概率是1/6。
最初一次的状态:初始状态概率分布(InitStatus )

所以,很容易得到,计算概率的方法就是,初始状态概率分布(InitStatus )、发射概率矩阵(EmitProbMatrix )、转移概率矩阵(TransProbMatrix )的乘积。
当某个状态序列的概率值最大,则该状态序列即为,出现该观测值的情况下,最可能出现的状态序列。

二、中文分词

该篇文章讲了怎么使用隐马尔科夫链作分词,原理使用上面的作为理解。下文中提到的SBME4个状态可以类比为上文提到的3个骰子。中文文字即为上文提到的投出的数字。

来源:< http://blog.csdn.net/taoyanqi8932/article/details/75312822 >

2.1 模型

HMM的典型模型是一个五元组:
StatusSet: 状态值集合
ObservedSet: 观察值集合
TransProbMatrix: 转移概率矩阵
EmitProbMatrix: 发射概率矩阵
InitStatus: 初始状态分布

2.2 基本假设

HMM模型的三个基本假设如下:
有限历史性假设:
P(Status[i]|Status[i-1],Status[i-2],… Status[1]) = P(Status[i]|Status[i-1])
齐次性假设(状态和当前时刻无关):
P(Status[i]|Status[i-1]) = P(Status[j]|Status[j-1])
观察值独立性假设(观察值只取决于当前状态值):
P(Observed[i]|Status[i],Status[i-1],…,Status[1]) = P(Observed[i]|Status[i])

2.3 五元组

2.3.1 状态值集合(StatusSet)

为(B, M, E, S): {B:begin, M:middle, E:end, S:single}。分别代表每个状态代表的是该字在词语中的位置,B代表该字是词语中的起始字,M代表是词语中的中间字,E代表是词语中的结束字,S则代表是单字成词。
如:

给你一个隐马尔科夫链的例子。
可以标注为:
给/S 你/S 一个/BE 隐马尔科夫链/BMMMME 的/S 例子/BE 。/S
2.3.2 观察值集合(ObservedSet)

为就是所有汉字(东南西北你我他…),甚至包括标点符号所组成的集合。
状态值也就是我们要求的值,在HMM模型中文分词中,我们的输入是一个句子(也就是观察值序列),输出是这个句子中每个字的状态值。

2.3.3 初始状态概率分布(InitStatus )

如:

B  -0.26268660809250016
E  -3.14e+100
M  -3.14e+100
S  -1.4652633398537678

数值是对概率值取【对数】之后的结果(可以让概率【相乘】的计算变成对数【相加】)。其中-3.14e+100作为负无穷,也就是对应的概率值是0。
也就是句子的第一个字属于{B,E,M,S}这四种状态的概率。

2.3.4 转移概率矩阵(TransProbMatrix )

【有限历史性假设】

转移概率是马尔科夫链。Status(i)只和Status(i-1)相关,这个假设能大大简化问题。所以,它其实就是一个4×4(4就是状态值集合的大小)的二维矩阵。矩阵的横坐标和纵坐标顺序是BEMS x BEMS。(数值是概率求对数后的值)

2.3.5 发射概率矩阵(EmitProbMatrix )

【观察值独立性假设】
P(Observed[i], Status[j]) = P(Status[j]) * P(Observed[i]|Status[j])
其中,P(Observed[i]|Status[j])这个值就是从EmitProbMatrix中获取。

2.4 使用Viterbi算法

这五元的关系是通过一个叫Viterbi的算法串接起来,ObservedSet序列值是Viterbi的输入,而StatusSet序列值是Viterbi的输出,输入和输出之间Viterbi算法还需要借助三个模型参数,分别是InitStatus, TransProbMatrix, EmitProbMatrix。

定义变量
二维数组 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[4][15] 之后,能对输入句子从右向左地回溯回来,找出对应的状态序列。

B:-0.26268660809250016
E:-3.14e+100
M:-3.14e+100
S:-1.4652633398537678

且由EmitProbMatrix可以得出

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

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

//遍历句子,下标i从1开始是因为刚才初始化的时候已经对0初始化结束了
for(size_t i = 1; i < 15; i++)
{
    // 遍历可能的状态
    for(size_t j = 0; j < 4; j++) 
    {
        weight[j][i] = MIN_DOUBLE;
        path[j][i] = -1;
        //遍历前一个字可能的状态
        for(size_t k = 0; k < 4; k++)
        {
            double tmp = weight[k][i-1] + _transProb[k][j] + _emitProb[j][sentence[i]];
            if(tmp > weight[j][i]) // 找出最大的weight[j][i]值
            {
                weight[j][i] = tmp;
                path[j][i] = k;
            }
        }
    }
}

确定边界条件和路径回溯
边界条件如下:
对于每个句子,最后一个字的状态只可能是 E 或者 S,不可能是 M 或者 B。
所以在本文的例子中我们只需要比较 weight[1(E)][14] 和 weight[3(S)][14] 的大小即可。

在本例中:
weight[1][14] = -102.492;
weight[3][14] = -101.632;
所以 S > E,也就是对于路径回溯的起点是 path[3][14]。

回溯的路径是:
SEBEMBEBEMBEBEB
倒序一下就是:
BE/BE/BME/BE/BME/BE/S
所以切词结果就是:
小明/硕士/毕业于/中国/科学院/计算/所

三、练习与实例

这里可以通过理解上文提到的所有,进行分词。
给出我的github练习源码:https://github.com/longgb246/pythonstudy/blob/master/longgb/Algorithm/TextMining/NLP/HMM/HMM.py
以及数据:https://github.com/longgb246/pythonstudy/tree/master/longgb/Algorithm/TextMining/Data

3.1 预料信息

首先,需要一个完整的预料信息,该预料库需要特征:
1、覆盖范围广,理论上需要覆盖你所有可能会被分词的文字,否则发射矩阵为出现极端情况,无法分词。
2、需要文本标注正确,如一些专有名词,”太平洋保险”等等,需要被分为一个词,因为他是一个公司名称,而不应该被分为”太平洋/保险”。
提取该语料库,可能需要人工干预。
将分词的结果进行标注,按照上文提到的信息,打上SBME的标注:

image.png

我这里的练习为了方便,直接使用jieba分词的结果,仅仅作为练习。

3.2 计算初始状态概率分布(InitStatus )

初始状态即为第一次选择的状态的概率。
这里选择的是语料库中,每个句子的第一个字的状态,统计该状态的频率,计算出该状态的概率。当然,为了确保不会出现一些问题,默认,ME是不会出现在句首,即将其概率设置为0,在矩阵中为:-3.14e+100(取了log值,方便转化为加法计算)。
伪代码:

content = f.readlines()
content_str = ''.join(content)            # 1、将换行拼接在一起。
content_list = content.split(split_list)   # 2、按照断句拆分。split_list为。!?等断句的符号
initStatus.append(firstStatus(content_list))    # 将每一句话的第一个字的状态记录下来,语料库中,观测与状态按照/划分开。
statusCount(initStatus)                   # 统计出现状态的概率

3.3 计算转移概率矩阵(TransProbMatrix )

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

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

3.4 计算发射概率矩阵(EmitProbMatrix )

回想一下上面举的例子,发射概率矩阵是在某状态下,出现某个观测值的概率,所以有,在某状态下,所有该状态下观测值的概率之和为1【该处理解对于计算发射矩阵很重要,即,当矩阵的列为SBEM,行为观测值时候,某一行的概率和为1,而不是某一列的概率和为1。根据隐马尔科夫链的计算公式,不理解的看看本文第一部分】。
所以,统计方法:

内容按照/拆分 -> 取出状态:观测的key:value -> 统计某状态下,某观测出现的次数,即为概率值 

3.5 使用Viterbi算法

第二部分给出了,Viterbi算法的方法,可以根据初始状态概率分布(InitStatus )、转移概率矩阵(TransProbMatrix )、发射概率矩阵(EmitProbMatrix )以及观测值,得出一个最有可能的状态序列。按照该状态序列,将文本划分出来即可。

Leave a Reply

Your email address will not be published. Required fields are marked *