中文分词之HMM模型详解

文章转载自: http://yanyiwu.com/work/2014/04/07/hmm-segment-xiangjie.html

HMM(Hidden Markov Model): 隐式马尔科夫模型。

HMM模型可以应用在很多领域，所以它的模型参数描述一般都比较抽象，以下篇幅针对HMM的模型参数介绍直接使用它在中文分词中的实际含义来讲：

HMM的典型介绍就是这个模型是一个五元组:

  • StatusSet: 状态值集合
  • ObservedSet: 观察值集合
  • TransProbMatrix: 转移概率矩阵
  • EmitProbMatrix: 发射概率矩阵
  • InitStatus: 初始状态分布

HMM模型可以用来解决三种问题：

  1. 参数(StatusSet, TransProbMatrix, EmitRobMatrix, InitStatus)已知的情况下，求解观察值序列。(Forward-backward算法)
  2. 参数(ObservedSet, TransProbMatrix, EmitRobMatrix, InitStatus)已知的情况下，求解状态值序列。(viterbi算法)
  3. 参数(ObservedSet)已知的情况下，求解(TransProbMatrix, EmitRobMatrix, InitStatus)。(Baum-Welch算法)

其中，第三种问题最玄乎也最不常用，第二种问题最常用，【中文分词】，【语音识别】, 【新词发现】， 【词性标注】 都有它的一席之地。所以本文主要介绍第二种问题，即【viterbi算法求解状态值序列】的方法。

五元组参数在中文分词中的具体含义

接下来我们讲实的，不讲虚的，针对中文分词应用，直接给五元组参数赋予具体含义：

StatusSet & ObservedSet

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

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

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

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

输出的状态序列为

BEBEBMEBEBMEBES

根据这个状态序列我们可以进行切词:

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

所以切词结果如下:

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

同时我们可以注意到：

B后面只可能接(M or E)，不可能接(B or S)。而M后面也只可能接(M or E)，不可能接(B, S)。

没错，就是这么简单，现在输入输出都明确了，下文讲讲输入和输出之间的具体过程，里面究竟发生了什么不可告人的秘密，请看下文：

上文只介绍了五元组中的两元【StatusSet, ObservedSet】，下文介绍剩下的三元【InitStatus, TransProbMatrix, EmitProbMatrix】。

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

InitStatus

初始状态概率分布是最好理解的，可以示例如下：

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

示例数值是对概率值取对数之后的结果(可以让概率相乘的计算变成对数相加)，其中-3.14e+100作为负无穷，也就是对应的概率值是0。下同。

也就是句子的第一个字属于{B,E,M,S}这四种状态的概率，如上可以看出，E和M的概率都是0，这和实际相符合，开头的第一个字只可能是词语的首字(B)，或者是单字成词(S)。

TransProbMatrix

转移概率是马尔科夫链很重要的一个知识点，大学里面学过概率论的人都知道，马尔科夫链最大的特点就是当前T=i时刻的状态Status(i)，只和T=i时刻之前的n个状态有关。也就是:

{Status(i-1), Status(i-2), Status(i-3), ... Status(i - n)}

更进一步的说，HMM模型有三个基本假设(具体哪三个请看文末备注)作为模型的前提，其中有个【有限历史性假设】，也就是马尔科夫链的n=1。即Status(i)只和Status(i-1)相关，这个假设能大大简化问题。

回过头看TransProbMatrix，其实就是一个4x4(4就是状态值集合的大小)的二维矩阵，示例如下：

矩阵的横坐标和纵坐标顺序是BEMS x BEMS。(数值是概率求对数后的值，别忘了。)

-3.14e+100 -0.510825623765990 -0.916290731874155 -3.14e+100
-0.5897149736854513 -3.14e+100 -3.14e+100 -0.8085250474669937
-3.14e+100 -0.33344856811948514 -1.2603623820268226 -3.14e+100
-0.7211965654669841 -3.14e+100 -3.14e+100 -0.6658631448798212

比如TransProbMatrix[0][0]代表的含义就是从状态B转移到状态B的概率，由

TransProbMatrix[0][0] = -3.14e+100

可知，这个转移概率是0，这符合常理。由状态各自的含义可知，状态B的下一个状态只可能是ME，不可能是BS，所以不可能的转移对应的概率都是0，也就是对数值负无穷，在此记为-3.14e+100。

由上TransProbMatrix矩阵可知，对于各个状态可能转移的下一状态，且转移概率对应如下：

#B
#E:-0.510825623765990,M:-0.916290731874155
#E
#B:-0.5897149736854513,S:-0.8085250474669937
#M
#E:-0.33344856811948514,M:-1.2603623820268226
#S
#B:-0.7211965654669841,S:-0.6658631448798212

EmitProbMatrix

这里的发射概率(EmitProb)其实也是一个条件概率而已，根据HMM模型三个基本假设(哪三个请看文末备注)里的【观察值独立性假设】，观察值只取决于当前状态值，也就是:

P(Observed[i], Status[j]) = P(Status[j]) * P(Observed[i]|Status[j])

其中P(Observed[i]|Status[j])这个值就是从EmitProbMatrix中获取。

EmitProbMatrix示例如下：

#B
耀:-10.460283,涉:-8.766406,谈:-8.039065,伊:-7.682602,洞:-8.668696,...
#E
耀:-9.266706,涉:-9.096474,谈:-8.435707,伊:-10.223786,洞:-8.366213,...
#M
耀:-8.47651,涉:-10.560093,谈:-8.345223,伊:-8.021847,洞:-9.547990,....
#S
蘄:-10.005820,涉:-10.523076,唎:-15.269250,禑:-17.215160,洞:-8.369527...

虽然EmitProbMatrix也称为矩阵，这个矩阵太稀疏了，实际工程中一般是将上面四行发射转移概率存储为4个Map，详见代码HMMSegment。

到此，已经介绍完HMM模型的五元参数，假设现在手头上已经有这些参数的具体概率值，并且已经加载进来，(也就是有该模型的字典了，详见HMMDict里面的hmm_model.utf8)，那么我们只剩下Viterbi这个算法函数，这个模型就算可以开始使用了。所以接下来讲讲Viterbi算法。

HMM中文分词之Viterbi算法

输入样例:

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

Viterbi算法计算过程如下：

定义变量

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

使用InitStatus对weight二维数组进行初始化

已知InitStatus如下:

#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

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

遍历句子计算整个weight二维数组

//遍历句子，下标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;
            }
        }
    }
}

如此遍历下来，weight[4][15] 和 path[4][15] 就都计算完毕。

确定边界条件和路径回溯

边界条件如下：

对于每个句子，最后一个字的状态只可能是 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

所以切词结果就是:

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

到此，一个HMM模型中文分词算法过程就阐述完毕了。

也就是给定我们一个模型，我们对模型进行载入完毕之后，只要运行一遍Viterbi算法，就可以找出每个字对应的状态，根据状态也就可以对句子进行分词。

模型的训练问题

以上讲的前提是基于模型来进行切词，也就是假设我们手头上的HMM模型已经是被训练好了的(也就是InitStatus, TransProbMatrix, EmitProbMatrix这三个模型的关键参数都是已知的)，没有涉及到这三个参数是如何得到的。这三个参数其实也是基于已分词完毕的语料进行统计计算，计算出相应的频率和条件概率就可以算出这三个参数。具体在此就不讲了。

备注

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])
时间： 2024-10-03 20:52:57

中文分词之HMM模型详解的相关文章

Java 23种设计模型详解_java

设计模式(Design Patterns)                                   --可复用面向对象软件的基础 设计模式(Design pattern)是一套被反复使用.多数人知晓的.经过分类编目的.代码设计经验的总结.使用设计模式是为了可重用代码.让代码更容易被他人理解.保证代码可靠性. 毫无疑问,设计模式于己于他人于系统都是多赢的,设计模式使代码编制真正工程化,设计模式是软件工程的基石,如同大厦的一块块砖石一样.项目中合理的运用设计模式可以完美的解决很多问题,每

ASP.NET Core的配置（2）：配置模型详解

在上面一章我们以实例演示的方式介绍了几种读取配置的几种方式,其中涉及到三个重要的对象,它们分别是承载结构化配置信息的Configuration,提供原始配置源数据的ConfigurationProvider,以及作为"中间人"的ConfigurationBuilder.接下来我们将会对由这三个核心对象组成的配置模型进行详细介绍,不过在此之前我们有必要来认识配置信息在不同载体中所体现出来的三种结构. 目录 一.配置的三种结构 逻辑结构 原始结构 物理结构 结构转换 二.Configura

CUDA C 编程指导（二）：CUDA编程模型详解

CUDA编程模型详解 本文以vectorAdd为例,通过描述C在CUDA中的使用(vectorAdd这个例子可以在CUDA sample中找到.)来介绍CUDA编程模型的主要概念.CUDA C的进一步描述可以参考<Programming Interface>. 主要内容包括: 1.Kernels(核函数) 2.Thread Hierarchy(线程结构) 3.Memory Hierarchy(存储结构) 4.Heterogeneous Programming(异构编程) 5.Compute C

Android 单线程模型详解及实例

Android 单线程模型详解及实例 我们今天将会在这篇文章中为大家详细介绍有关Android单线程模型的相关内容.希望初学者们可以通过本文介绍的内容对这一概念有一个充分的认识,并从中对这一系统有一个深刻的认识. 当第一次启动一个Android程序时,Android会自动创建一个称为"main"主线程的线程.这个主线程(也称为UI线程)很重要,因为它负责把事件分派到相应的控件,其中就包括屏幕绘图事件,它同样是用户与Andriod控件交互的线程.比如,当你在屏幕上按下一个按钮后,UI线程

使Nginx服务器支持中文URL的相关配置详解_nginx

关于中文URL已经是老话题了,到目前为止依然有很大一部分SEOer都会说不要使用中文URL,对搜索引擎不友好. 不过,那已经是以前的事了,谷歌很早就支持了中文URL,当时百度技术没有跟上,URL中会出现乱码. 在谷歌的算法中,URL包含关键字是会给页面赋予一定权重的,英文是,中文也是,朽木猜测百度之前没有给予中文URL权重,可能是因为识别的问题. 经过一些简单的测试,朽木发现中文URL中包含关键字,对百度SEO有很积极的影响. 不过需要注意的是最好使用UTF8编码,虽然百度有了"一定的识别能力&

java 安全沙箱模型详解

起到第一道安全保障作用的"双亲委派类加载模型" 双亲委派方式的类加载,指的是优先从顶层启动类加载器开始,自顶向下的方式加载类的模型(参见第一条类装载器体系结构). 这种模型的好处是,底层的类装载器装载的类无法与顶层类装载器装载的类相互调用. 哪怕是同包下的类,只要他们不属于同一类装载器,都是相互隔绝的.这对一些有安全隐患的类起到了安全隔离的作用.使它不能冒充系统类来破坏程序正常运作. 此外,不同的类装载器,也有自己的类装载范围.比如启动类装载器,它只会装在jdk/lib目录下的包/类,

Netty线程模型详解

1. 背景 1.1. Java线程模型的演进 1.1.1. 单线程 时间回到十几年前,那时主流的CPU都还是单核(除了商用高性能的小机),CPU的核心频率是机器最重要的指标之一. 在Java领域当时比较流行的是单线程编程,对于CPU密集型的应用程序而言,频繁的通过多线程进行协作和抢占时间片反而会降低性能. 1.1.2. 多线程 随着硬件性能的提升,CPU的核数越来越越多,很多服务器标配已经达到32或64核.通过多线程并发编程,可以充分利用多核CPU的处理能力,提升系统的处理效率和并发性能. 从2

.NET Core下的日志（2）：日志模型详解

NET Core的日志模型主要由三个核心对象构成,它们分别是Logger.LoggerProvider和LoggerFactory.总的来说,LoggerProvider提供一个具体的Logger对象将格式化的日志消息写入相应的目的地,但是我们在编程过程中使用的Logger对象则由LoggerFactory创建,这个Logger利用注册到LoggerFactory的LoggerProvider来提供真正具有日志写入功能的Logger,并委托后者来记录日志. 目录 一.Logger     扩展方

分布式事务（两阶段提交）模型详解

这一几天一直在回顾事务相关的知识,也准备把以前了解皮毛的知识进行一些深入总结,虽然这一些知识并没有用到,但是了解其实现原理还是很有必要的,因为知道了原理,你也能把它实现出来. 在上一节事务的编程模型里面,主要说明了三种编程模型,一般情况下,我们都接触的是单一资源的事务,也就是单独对一个数据库进行操作.如果需要跨多个资源保证事务一致性 举个例子:在ATM机取钱的时候,需要对用户的账户进行扣款处理,然后发送一条消息给消息服务器(假设消息服务器是用JMS实现的),由消息服务器异步通过短信通知用户.如果