ICTCLAS层叠隐马尔科夫模型

ICTCLAS基于隐马尔科夫模型提出了层叠隐马尔科夫模型（CHMM），CHMM实际上是若干个层次的简单HMM组合，各层隐马尔科夫模型之间以以下几种方式相互关联：各层HMM之间共享一个切分词图作为公共数据结构（见下图），每一层隐马尔科夫模型都采用N-Best策略，将产生的最好的若干个结果送到此图中供更高层次的模型使用。

该CHMM由低到高依次为：原子切分，简单未登录词识别，嵌套未登录词识别，这几层中共享二元切分词图，并在每层对该数据结构进行修改，使得传递给基于类地隐马分词的参数越来越准确，最后一层为隐马词性标注。

马尔可夫链模型：

使用最广泛的描述类相关性的模型是马尔可夫链准则。如果wi1，wi2，…，wiN是一个类的序列，则马尔可夫模型假设

P(wik|wik?1,wik?2,...,wi1)?p(wik|wik?1)

它的意思是类相关性仅局限于两个连续的类，这种模型也称为一阶马尔可夫模型，以区别它的一般形式（二阶、三阶等）。换言之，已知观察值xk-1，xk-2，…，x1分别属于类wi k-1，wi k-2，…，

wi，在k阶段的观察值xk属于类wi k的概率仅依赖与在k-1阶段产生观察值xk-1的类。

p(?i)?p(wi1,wi2,...,wiN)

?p(wiN|wiN?1,...,wi1)p(wiN?1|wiN?2,...,wi1)...p(wi1)

得出

Np(?i)?p(wi1)?p(wik|wik?1)

k?2其中P（wi1）是类wi，i1∈{1,2，?，M}的先验概率。另外，两个普遍采用的假设是：（a）已知类地序列，观察值在统计上是独立的；（b）某类的概率密度函数不依赖其他类。也就是说依赖性仅仅存在于产生类地序列，而在类内，观察值服从类自己的规则。这个假设意味着

p(X|?i)?p(x1,x2,...,xN|?i)

?p(x1|?i)p(x2|?i)...p(xN|?i) ?p(x1|wi1)p(x2|wi2)...p(xN|wiN)

N ??k?1p(x|w) kik描述：已知观察值的特征向量序列X：x1,…,xN，将其分到各自的类的序列Ωi：wi 1,wi 2,…,wi N中，则下式：

NP(X|?i)P(?i)?P(wi1)P(x1|wi1)?P(wik|wik?1)P(xk|wik)

k?2

隐马尔可夫模型：

隐马尔可夫模型是在马尔可夫模型上发展而来的，马尔可夫链的状态是可以观察到的，而有

的系统中，状态的变化无法直接观察到，观察值是与每一个状态相关的行为作用的结果，由一组概率函数来描述。在序列中不同的状态被它后续的观察值访问，而这个序列又是另一个随机过程结果。这些对我们都是隐藏的，描述它的那些相关参数只能通过接收到的观察值集合来推断。为了解决我们观察的事件而不是与状态一一对应而只是通过一定的概率分布联系的问题而提出隐马尔可夫模型。HMM是一个双重随机过程，一个是具有一定状态数的马尔可夫链，这是基本的随机过程，它描述状态的转移；另一个随机过程描述状态和观察值之间

的统计对应关系，这由输出概率来定义。其中模型的状态转移过程是不可观察的，因而称之为“隐”马尔可夫模型。一个HMM可以用一个五元组（S,V,A,B,∏）来表示，其中

（1） S代表一组状态的几何，S={s1，…，sN}，其中的状态数为N，并用qt来表示t时刻

的状态。

（2） V代表一组可观察符号的集合，V={v1，…，vM}，M是从每一个状态可能输出的不

同的观察值的数目。

（3） A代表一组状态转移概率矩阵，A={aij}其中aij={qt+1=sj|qt=si}，1<=i，j<=N，这是个

N行N列的矩阵，aij表示从状态si转移到状态sj的概率。

（4） B表示可观察符号的概率分布，B={bijk}，1<=i,j<=N,1<=K<=M表示在sj状态输出观

察符号vk的概率。

（5） ∏代表初始状态的概率分布，∏={πi}，其中πi=P(q1=si)，它表示在时刻1选择某

个状态的概率。

一个确定的隐马尔可夫模型，其状态数和每个状态可能输出的观察值的数目都是可以确定的，因此可以用λ=（A,B, ∏）来表示模型的参数。其中∏，A描述马尔可夫链，产生的输出为状态序列，记为Q；B则描述随机过程，产生的输出为观察值序列，记为O。 一阶隐马模型做出了两个重要的假设：

（a） 状态转移的Markov假设：在t时刻（前一时刻）处于状态si，而在t+1时刻（当前

时刻）进入状态sj的状态转移概率只取决于前一时刻所处的状态，而与前一时刻以前的历史无关。

（b） 输出值的Markov假设：输出观察值的概率同样具有Markov性，即只取决于当前时

刻所处的状态，而与以前的历史无关。

应用隐马尔可夫模型主要解决三个方面的问题 （1） 评估问题：对于给定的模型λ=（A,B,π），和给定的观察序列O=（O1O2O3?OT），如

何有效的计算观察值序列O的概率P(O|λ)。

（2） 解码问题：对于给定的模型λ=（A,B,π），和给定的观察序列O=（O1O2O3?OT），如

何寻找一个状态转换序列Q=（q1q2?qT）,使得该状态转换序列最有可能产生上述观察序列。

（3） 学习问题或训练问题：在模型参数未知或不准确的情况下，如何根据观察序列O=

（O1O2O3?OT）球的模型参数或调整模型参数，即如何确定一组模型参数，使得P（O|λ）最大。

在讲解这三个问题之前，引入一个著名的抛硬币问题，假设有三枚硬币，在抛的过程中我们看不到其中的过程，只能得到每次抛出硬币的结果，这样对我们来说，每次抛硬币我们都不知道是哪枚硬币产生当前的观察结果（正面或者反面）。对我们来说，概率过程是隐藏的。模型化描述如下图。

可以将此描述为一个三个状态的隐马尔可夫模型λ。λ=（S,V,A,B,π），其中S=(1,2,3)，V=（H,T），π={1/3,1/3,1/3}

P(1|2)P(1|1)P(2|1)P(2|2)P(3|2)31|P()P(2|3)图1：三枚硬币的马尔可夫模型

对于隐马尔可夫模型而言，状态转换序列是隐藏的，一个观察序列可能由任何一种状态转换序列产生。因此要计算一个观察序列的概率值，就必须考虑所有可能的状态转换序列。

3P()|1P(3|3)

q3q1O1P(q3O2q2|q1)O3OT

图2：状态转移序列

上图表示了产生观察序列O=（O1O2O3?OT）的所有可能的状态转移序列。

评估问题：

那么，在这个给定的隐马模型中，若给定状态转移序列Q=（q1q2?qT），则其产生的观察序列O=（O1O2O3?OT）的概率可以通过下面的公式进行计算：

P(O|Q,?)?P(o1o2...oT|Q,?)

?bq(o1)bq(o2)...bq(oT)

12T给定λ，状态转移序列Q=（q1q2?qT）的概率可以通过下式计算：

P(Q|?)?P(q1q2...qT|?)

??qaqqaq112q2...3aqT?qT 1考虑所有的状态转移序列，得到第一个问题的答案

P(O|?)??P(O,Q|?)??Qq1q2...qT?qbq(o1)aqqbq(o2)...aq11122T?1qTbqT(oT)

理论上，可以通过穷举所有的状态转换序列的办法来计算观察序列O的概率，但是实际上这样做并不现实，因为可能的状态转换序列共有NT个，需要做（2T-1）NT次乘法运算，NT-1次加法运算，若N=5，T=100，则（2*100-1）*5100=1072，需要寻找更为有效的计算方法。向前--向后算法则可以更为有效计算P(O|?)。

向前算法： 定义向前变量：

?t(i)?P(o1o2...ot,qt?i|?)

?t(i)的含义是，给定模型λ，时刻t，处在状态i，并且部分观察序列为O1O2O3?Ot的概率。初始化：

?1(i)??ibi(o1)(1?i?N)

迭代计算：

N?t?1(j)?[??t(i)aij]bj(ot?1) 1?t?T?1,1?j?N

i?1终止：

NP(O|?)???i?1T(i)

计算量：容易计算，该方法的计算量近似为N2T，而不是直接计算时需要的2TNT次，大大

节省了计算量（精确地讲，需要N(N+1)(T-1)+N次乘法运算，N(N-1)(T-1)次加法运算）。（之所以直接计算的计算量很大，是因为重复计算，举个例子：对于观察序列o1o2o3的两个可能的状态转移序列q1q2q3和q1q2q2，如果直接计算则会将重复计算q1q2的转移概率，而向前算法则是在q1q2基础上只计算q3和q2的转移概率。）

回到抛硬币的问题，计算观察序列（HHT）的概率。 初始化：

?1(1)??1b1(H)?1/3?0.5?0.16667

?1(2)??2b2(H)?1/3?0.75?0.25 ?1(3)??3b3(H)?1/3?0.25?0.08333

迭代：

3?2(1)?[??1(i)ai1]b1(H)?0.3000?0.5?0.15000

i?13?2(2)?[??1(i)ai2]b2(H)?0.05312

i?13?2(3)?[??1(i)ai3]b3(H)?0.03229

i?1

3?3(1)?[??2(i)ai1]b1(T)?0.08672

i?13?3(2)?[??2(i)ai2]b2(T)?0.00684

i?13?3(3)?[??2(i)ai3]b3(T)?0.02597

i?1终止：

3P(O|?)???i?13(i)?0.08672?0.00684?0.02597?0.11953

向后算法：

向后算法与向前算法类似，定义向后变量：

?t(i)?P(ot?1ot?2...oT|qt?i,?)

?t(i)的含义是，在给定模型λ，时刻t，处在状态i，并且部分观察序列为ot+1ot+2…oT的概率。 初始化：

?T(i)?1(1?i?N)

迭代计算：

N?t(i)??aj?1ij bj(ot?1)?t?1(j) 1?t?T?1,1?j?N终止：

NP(O|?)???i?1ibi(o1)?1(i)

计算量分析与计算过程与向前算法类似，不重复说明。

解码问题：

隐马尔可夫模型的第二个问题是计算出一个能最好解释观察序列的状态转换序列。理论上，可以通过枚举所有的状态转换序列，并对每一个状态转换序列Q计算P(O,Q|λ)，能使P(O,Q|λ)取最大值的状态转换序列Q#就是能最好解释观察序列的状态转换序列，即：

Q?argmaxP(O,Q|?)

Q#同样，这不是一个有效的计算方法，需要寻找更好地计算方法。

韦特比算法（Viterbi Algorithm） 定义韦特比变量

?t(i)?maxP(q1q2...qt?1,qt?i,o1o2...ot|?)

q1q2...qt?1?t(i)的含义是，给定模型λ，在时刻t处于状态i，观察到o1o2o3?ot的最佳状态转换序列为q1q2?qt的概率。

如何记录路径？设定T个数组?1(N),?2(N),...,?T(N),?t(i)记录在时刻t到达状态i的最佳状态转换序列t-1时刻的最佳状态。（基于动态规划的思想，用备忘录记录当前最优值，为下阶段的策划做依据） 初始化：

?1(i)??ibi(o1)，1?i?N

?1(i)=0

迭代计算：

?2(3)?max[?1(i)ai3]b3(H)?0.1125?0.25?0.02812

1?i?N?2(2)?argmax[?1(i)ai2]?3

1?i?N终止：

P?max[?3(i)]?0.03375

1?i?N#q3?argmax[?3(i)]?1

1?i?N#最佳路径：

qt??t?1(qt?1),t?T?1,T?2,...,1

##

回到抛掷硬币的问题，若给定观察序列（HHT），寻找产生该观察序列的最佳路径以及最佳路径的概率。 初始化：

?1(1)??1b1(H)?1/3?1/2?0.16667 ?1(1)?0

?1(2)??2b2(H)?1/3?0.75?0.25 ?1(2)?0

?1(3)??3b3(H)?1/3?0.25?0.08333 ?1(3)?0

迭代计算：

?2(1)?max[?1(i)ai1]b1(H)?0.15003?0.5?0.07500

1?i?N?2(1)?argmax[?1(i)ai1]?1

1?i?N?2(2)?max[?1(i)ai2]b2(H)?0.03750?0.75?0.02812

1?i?N?2(2)?argmax[?1(i)ai2]?3

1?i?N?2(3)?max[?1(i)ai3]b3(H)?0.1125?0.25?0.02812

1?i?N?2(3)?argmax[?1(i)ai3]?2

1?i?N

?3(1)?max[?2(i)ai1]b1(T)?0.675?0.5?0.3375

1?i?N?3(1)?argmax[?2(i)ai1]?1

1?i?N?3(2)?max[?2(i)ai2]b2(T)?0.01265?0.25?0.00316

1?i?N?3(2)?argmax[?2(i)ai2]?3

1?i?N?3(3)?max[?2(i)ai3]b3(T)?0.01265?0.75?0.00949

1?i?N?3(3)?argmax[?2(i)ai3]?2

1?i?N终止：

P?max[?3(i)]?0.03375

1?i?N#q3?argmax[?3(i)]?1

1?i?N#最佳路径：

q2??3(q3)??3(1)?1q??2(q)??2(1)?1#1#2##

最佳路径为111。

学习问题或训练问题

隐马尔可夫模型的第三个问题是如何根据观察序列O=(o1o2…oT)求得模型参数或调整模型参数。

在模型未知的情况下，如果给定了观察序列的同时，也给定了状态转换序列，此时可以通过有指导的学习方法学习模型参数。例如给定下面的训练数据，可以通过最大似然估计法估计模型参数： H/1 H/1 H/1 T/2 H/3 T/5 … T/2 H/1 T/2 H/3 H/3 H/1 … 参数学习非常简单，在训练数据足够大的前提下效果不错。缺点是状态信息未知时无法使用，

或者需要由人工标注状态信息，代价高。 在模型未知的情况下，如果仅仅给定了观察序列，此时学习模型的方法被称作无指导的学习方法。对于隐马尔可夫模型而言，采用无指导学习方法，没有解析方法。通常要首先给定一组不准确的参数，再通过反复迭代逐步求精的方式调整模型参数，最终使参数稳定在一个可以接受的精度。利用无指导的学习方法估计隐马尔可夫模型参数时，并不能一定保证求得最优模型，一般能得到一个局部最优模型。

关于HMM无指导学习，Baum-Welch是比较成熟的算法，暂时没有深入研究。

层叠隐马尔可夫模型（CHMM）

至此，重新回到ICTCLAS系统中的CHMM模型中，这里详细讲解该模型中的第二层HMM基于类的隐马分词和第三层，第四层HMM未登录词的隐马识别，第一层的词性标注过程和未登录词的角色标注过程本质一样，不做重复性论述。第五层的原子切分，和N-ShortPath粗切分在代码讲解时描述更为直观，这里不做论述。

基于类的隐马分词：

首先，我们可以把所有的词进行分类：

w在核心词典中收录PER w是人名且是未登录词LOC w是地名且是未登录词ORG w是机构名且是未登录词Ci =NUM w是数词且是未登录词TIME w是时间词且是未登录词BEG w是句子的开始标记END w是句子的结束标记

其中核心词典中已有的每个词对应的类就是该词本身。给定一个分词原子序列S，S的某个分词结果记为W=(w1w2…wn)，W对应的类别序列记为C=(c1c2…cn)，同时我们取概率最大的分词结果W#作为最终的分词结果。则

W#OTHER 其他词?argmaxP(W)

W利用贝叶斯公式进行展开，得到

W#?argmaxP(W|C)P(C)

W

推导过程如下（个人推导）： P(W)?P(WC)P(C|W)?P(W|C)P(C)P(C|W)

这里值的注意的是P(C|W)，由于一个词序列与类序列是严格对应关系，一个词只能为一个类，一个类可以对应多个词，因此P(C|W)=1，原式可得P(W)?P(W|C)P(C)。

将词类看做状态，词语看做观察值，利用一阶HMM展开

NW#?argmax?p(wi|ci)p(ci|ci?1) （其中，c0为句子的开始标记BEG）

Wi?1推导过程如下（个人推导）： 由于给定的词序，我们是已知其类序列的，因此可以认为从观察值序列可以得到其状态转换序列，这实际上就是马尔可夫链模型，因此按照马尔可夫链模型的公式可得

NP(C)?P(c0)?P(ci|ci?1)

i?1NP(W|C)??i?0P(wi|ci)

词序c0必为BEG，P(c0)=1，P(w0|c0)=1，故，可得到上式。

为方便计算，常用负对数来运算，则

NW#?argminW?[?lni?1p(wi|ci)?lnp(ci|ci?1)]

则最终所求的分词结果就转化成了出各个词序中初始节点到结束节点的最短路径。

未登录词的隐马识别方法

我们在基于类地隐马分词中使用到的是已经分好类地词序，如：张磊，可以切分为张|张，磊|磊，也可作为一个词张磊|PER，那么将它识别成人名的未登录词则是本算法的任务，（1）确定未登录词wi的边界和类别ci，（2）计算P(wi|ci)。

和基于类地隐马分词类似，对初始切分得到的各个词按照其再未登录词识别中的作用进行分类，并将词所起的不同作用称为角色。与隐马分词中定义的类相比，角色不同的是：类和词是一对多的关系，而角色与词是多对多的关系，即：一个词可以充当多个角色，而一个角色也可以对应多个词。

对于一个给定的初始切分结果W=（w1w2…w3），在一个角色集合的范畴内，假定R=（r1,r2…rn）为C的某个角色序列。我们取概率最大的角色序列R#作为最终的角色标注结果。 论文上提出R#的求法与隐马分词的W#求法类似，得出的计算公式为

NR?argminW#?[?lni?1p(wi|ri)?lnp(ri|ri?1)]

这点我不认同，在这里W为观察序列，R为状态转移序列，R#代表的是得到观察序列W的最佳状态转移序列R，这是HMM中的第二个问题，而隐马分词中求的W#是求的是概率最大的观察序列W，这是HMM中的第一个问题，因此这个结论是错误的。

R#可以通过viterbi算法选优得到。（基于HMM的第二种问题解决方法）下图给出了在词序“毛/泽/东/TIME/诞生”的viterbi算法标注人名角色的过程。

Viterbi的计算过程已讲解过，不再重复论述。 在上图中，我们可以求解出最优的角色标注：“毛/C泽/D东/ETIME/B诞生/Z”而CDE正好构成一个典型的汉语人名，因此“毛泽东”被识别为人名PER。 识别出来的未登录词wi，类别为ci，利用隐马过程可得：

kP(wi|ci)??j?0p(wp?j|rp?j)p(rp?j|rp?j?1)

其中，wi由第p，p+1，…，p+k-1个初始切分单元组成。

复杂地名和机构名往往嵌套了普通无嵌套的人名，地名等未登录词，如“张自忠路”，“周恩来和邓颖超纪念馆”。对于这种嵌套的未登录词，论文中的做法是：在低层的HMM识别过程中，先识别出普通不嵌套的未登录词，然后在此基础上，通过角色标注计算出最优的角色序列，在此基础上，进一步识别出嵌套的未登录词，以切分序列片段“周/恩/来/和/邓/颖/超/的/纪念馆”为例，我们先识别出“周恩来”和“邓颖超”为人名PER，得到新的词序列“PER/和/PER/纪念馆”，最终就可以识别出该片段为机构名。这样的处理优点在于能够利用已经分析的结果，并降低数据的稀疏程度。

本文来源：https://www.bwwdw.com/article/zhjg.html