目录
一、马尔可夫模型1. 马尔可夫性2. 马尔可夫链3. 马尔可夫链案例二、隐马尔可夫模型HMM1. named entity recognition(命名实体识别)问题概述2. 什么是隐马尔可夫模型 a.k.a.HMM?a.k.a.HMM?a.k.a.HMM?3. HMM模型的参数4. 用HMM解决序列标注问题, HMM的学习算法三、维特比算法(Viterbi Algorithm)(HMM的预测算法)四、代码实现一、马尔可夫模型
1. 马尔可夫性
设{X(t),t∈T}\{X(t), t ∈ T\}{X(t),t∈T}是一个随机过程，E为其状态空间，若对于任意的t1<t2<...<tn<tt_1<t_2< ...<t_n<tt1<t2<...<tn<t，任意的x1,x2,...,xn,x∈Ex_1,x_2,...,x_n,x∈Ex1,x2,...,xn,x∈E，随机变量X(t)X(t)X(t)在已知变量X(t1)=x1,...,X(tn)=xnX(t_1)=x_1,...,X(t_n)=x_nX(t1)=x1,...,X(tn)=xn之下的条件分布函数只与X(tn)=xnX(t_n)=x_nX(tn)=xn有关，而与X(t1)=x1,...,X(tn−1)=xn−1X(t_1)=x_1,...,X(t_{n-1})=x_{n-1}X(t1)=x1,...,X(tn−1)=xn−1无关，即条件分布函数满足下列等式，此性质称为马尔可夫性；如果随机过程满足马尔可夫性，则该过程称为马尔可夫过程。
连续变量：p(x(t)≤x∣X(t1)=x1,...,X(tn)=xn)=p(X(t)≤x∣X(tn)=xn)p(x(t)\le x|X(t_1)=x_1,...,X(t_n)=x_n)=p(X(t)\le x|X(t_n)=x_n)p(x(t)≤x∣X(t1)=x1,...,X(tn)=xn)=p(X(t)≤x∣X(tn)=xn)
离散变量：p(xn+1≤x∣X1=x1,...,Xn=xn)=p(Xn+1=x∣Xn=xn)p(x_{n+1}\le x|X_1=x_1,...,X_n=x_n)=p(X_{n+1}= x|X_n=x_n)p(xn+1≤x∣X1=x1,...,Xn=xn)=p(Xn+1=x∣Xn=xn)
2. 马尔可夫链
马尔可夫链是指具有马尔可夫性质的随机过程。在过程中，在给定当前信息的情况下，过去的信息状态对于预测将来状态是无关的。马尔可夫链在马尔可夫链的每一步，系统根据概率分布，可以从一个状态变成另外一个状态，也可以保持当前状态不变。状态的改变叫做转移，状态改变的相关概率叫做转移概率。马尔可夫链中的三元素是：状态空间SSS、转移概率矩阵PPP、初始概率分布πππ。3. 马尔可夫链案例
设将天气状态分为晴、阴、雨三种状态，假定某天的天气状态只和上一天的天气状态有关，状态使用1(晴)、2(阴)、3(雨)表示，转移概率矩阵PPP如下：
第n+1天天气状态为j的概率为：
π(Xn+1=j)=∑i=1kπ(Xn=i)⋅P(Xn+1∣Xn=j)⇒πn+1=πn⋅P\pi(X_{n+1}=j)=\sum^k_{i=1}\pi(X_n=i)·P(X_{n+1}|X_n=j) \Rightarrow \pi^{n+1}=\pi^n·Pπ(Xn+1=j)=∑i=1kπ(Xn=i)⋅P(Xn+1∣Xn=j)⇒πn+1=πn⋅P因此，矩阵P即为条件概率转移矩阵。
矩阵P的第iii行元素表示，在上一个状态为i的时候的分布概率，即每行元素的和必须为1。
初始概率：π=[0.5,0.3,0.2]π=[0.5,0.3,0.2]π=[0.5,0.3,0.2]
转移概率矩阵：P=[0.750.1250.1250.50.250.250.250.50.25]P=\left[ \begin{matrix} 0.75&0.125&0.125 \\ 0.5&0.25&0.25 \\ 0.25&0.5&0.25 \end{matrix} \right]P=⎣⎡0.750.50.250.1250.250.50.1250.250.25⎦⎤
当初始概率：π=[0.1,0.6,0.3]π=[0.1,0.6,0.3]π=[0.1,0.6,0.3]
可以发现，无论初始概率设置为多少（不为0），经过很多次迭代，第n天晴、阴、雨的概率会趋于一个稳定的相同数值。
二、隐马尔可夫模型HMM
自然语言处理中的序列标注问题, 目前比较主流的技术是语言模型(如LSTM, BERT)+CRF(条件随机场), 要了解CRF(条件随机场), 需要首先了解隐马尔可夫模型(Hidden Markov Model), HMM是一种概率图模型, 只要理解了HMM模型和维特比解码算法(viterbi algorothm), 理解条件随机场就比较简单了。
1. named entity recognition(命名实体识别)问题概述
命名实体识别（英语：Named Entity Recognition，简称NER）, 是指识别文本中具有特定意义的实体，主要包括人名、地名、机构名、专有名词等等, 并把需要识别的词在文本序列中标注出来。
例如有一段文本:上海市成立自由贸易试验区.
要在上面文本中识别一些区域和地点, 那么需要识别出来内容有:
上海市(地点), 自由贸易试验区(地点).
在使用的NER数据集中, 一共有7个标签:
“B-ORG”: 组织或公司(organization)“I-ORG”: 组织或公司“B-PER”: 人名(person)“I-PER”: 人名“O”: 其他非实体(other)“B-LOC”: 地名(location)“I-LOC”: 地名
文本中以每个字为单位, 每个字必须分别对应上面的任一标签。
但为什么上面标签除了"O"(其他)之外都是一个实体类型对应两个标签呢?
请小伙伴们仔细看标签前面有分为"B"和"I"的不同, "B"表示begin, 实体开头的那个字使用"B"对应的标签来标注, 在实体中间或结尾的部分, 用"I"来标注。
比如说"自贸区"对应的标注是:自(B-LOC)贸(I-LOC)区(I-LOC), 这三个字都对应一个"地名"的标签, 但是第一个字属于实体开头的字, 所以使用"B"开头的标签, 后面两个字的标签都是"I"开头。
注意, "B"后面是不可以跟其他类型的"I"的, 例如:自(B-PER)贸(I-LOC)区(I-LOC)就是属于错误的标注, 因为实体开头"B"标注成了人名, 即使实体中间标注成了地名, 这个实体的标注方法也是非法的。
上面的原因就是要从语言模型(例如BERT, LSTM)后面再加上概率图模型, 例如条件随机场, 用来约束模型的输出, 防止出现不合规的标注输出。
2. 什么是隐马尔可夫模型 a.k.a.HMM?a.k.a.HMM?a.k.a.HMM?
HMM模型是概率图模型的一种, 属于生成模型, 笼统的说, 上面说的"BIO"的实体标签, 就是一个不可观测的隐状态, 而HMM模型描述的就是由这些隐状态序列(实体标记)生成可观测状态(可读文本)的过程。
在本文的问题当中, 隐状态序列是实体标记序列, 而可观测序列是可读的原始语料文本序列。
例如:
隐藏状态序列: B−LOC∣I−LOC∣I−LOCB-LOC | I-LOC | I-LOCB−LOC∣I−LOC∣I−LOC
观测状态序列: 自贸区自 \quad \quad \quad \quad 贸 \quad \quad \quad \quad 区自贸区
设的可观测状态序列是由所有汉字组成的集合, 用VObsevationV_{Obsevation}VObsevation来表示:
Vobs.={v1,v2,...,vM}V_{obs.}=\{v_1, v_2, ... , v_M \}Vobs.={v1,v2,...,vM}
上式中, vvv表示字典中单个字, 假设已知的字数为MMM。
设所有可能的隐藏状态集合为QhiddenQ_{hidden}Qhidden, 一共有NNN种隐藏状态, 例如现在的命名实体识别数据里面只有7种标签:
Qhidden={q1,q2,...,qN}Q_{hidden} = \{ q_1, q_2, ... , q_N\}Qhidden={q1,q2,...,qN}
设有观测到的一串自然语言序列文本OOO, 一共有TTT个字, 又有这段观测到的文本所对应的实体标记, 也就是隐状态III:
I={i1,i2,...,iT}(隐状态)O={o1,o2,...,oT}(观测)I=\{i_1, i_2, ... , i_T \}(隐状态) \quad O=\{o_1, o_2, ... , o_T \}(观测)I={i1,i2,...,iT}(隐状态)O={o1,o2,...,oT}(观测)
注意上式中,常称ttt为时刻, 如上式中一共有TTT个时刻(TTT个汉字)。
HMM模型有两个基本假设(非常重要):
第ttt个隐状态(实体标签)只跟前一时刻的t−1t-1t−1隐状态(实体标签)有关, 与除此之外的其他隐状态(如t−2,t+3t-2,\ t+3t−2,t+3)无关。
例如上图中: 蓝色的部分指的是iti_tit只与it−1i_{t-1}it−1有关, 而与蓝色区域之外的所有内容都无关, 而P(it∣it−1)P(i_{t}|i_{t-1})P(it∣it−1)指的是隐状态iii从t−1t-1t−1时刻转向ttt时刻的概率, 具体转换方式下面会细讲。观测独立的假设, 上面说过, HMM模型中是由隐状态序列(实体标记)生成可观测状态(可读文本)的过程,
观测独立假设是指在任意时刻观测oto_tot只依赖于当前时刻的隐状态iti_tit, 与其他时刻的隐状态无关。
例如上图中: 粉红色的部分指的是it+1i_{t+1}it+1只与ot+1o_{t+1}ot+1有关, 跟粉红色区域之外的所有内容都无关。
3. HMM模型的参数
HMM的转移概率(transition probabilities):上面提到了P(it∣it−1)P(i_{t}|i_{t-1})P(it∣it−1)指的是隐状态iii从t−1t-1t−1时刻转向ttt时刻的概率, 比如现在实体标签一共有777种, 也就是N=7N=7N=7(注意NNN是所有可能的实体标签种类的集合), 也就是Qhidden={q0,q1,...,q6}Q_{hidden} = \{ q_0, q_1, ... , q_6\}Qhidden={q0,q1,...,q6}(注意实体标签编号从000算起), 假设在t−1t-1t−1时刻任何一种实体标签都可以在ttt时刻转换为任何一种其他类型的实体标签, 则总共可能的转换的路径一共有N2N^2N2种, 所以可以做一个N∗NN*NN∗N的矩阵来表示所有可能的隐状态转移概率。
上图就是转移概率矩阵, 也就是transitionmatrixtransition \ matrixtransitionmatrix, 设这个矩阵为AAA矩阵, 则AijA_{ij}Aij表示矩阵中第i行第j列:
Aij=P(it+1=qj∣it=qi)qi∈QhiddenA_{ij}=P(i_{t+1}= q_j | i_{t} = q_i) \quad q_i \in Q_{hidden}Aij=P(it+1=qj∣it=qi)qi∈Qhidden
上式表示指的是在ttt时刻实体标签为qiq_iqi, 而在t+1t+1t+1时刻实体标签转换到qjq_jqj的概率。HMM的发射概率(emission probabilities):
之前提到了任意时刻观测oto_tot只依赖于当前时刻的隐状态iti_tit, 也就是P(ot∣it)P(o_t | i_t)P(ot∣it), 也叫做发射概率, 指的是隐状态生成观测结果的过程。
设字典里有MMM个字, Vobs.={v0,v1,...,vM−1}V_{obs.}=\{v_0, v_1, ... , v_{M-1} \}Vobs.={v0,v1,...,vM−1}(注意这里下标从0算起, 所以最后的下标是M−1M-1M−1, 一共有MMM种观测), 则每种实体标签(隐状态)可以生成MMM种不同的汉字(也就是观测), 这一过程可以用一个发射概率矩阵来表示, 他的维度是N∗MN*MN∗M。
上图就是发射概率矩阵, 也就是emissionmatrixemission \ matrixemissionmatrix, 设这个矩阵为BBB矩阵, 则BjkB_{jk}Bjk表示矩阵中第jjj行第kkk列:
Bjk=P(ot=vk∣it=qj)qi∈Qhiddenvk∈Vobs.={v0,v1,...,vM−1}B_{jk}=P(o_{t}= v_k | i_{t} = q_j) \quad q_i \in Q_{hidden} \quad v_k \in V_{obs.}=\{v_0, v_1, ... , v_{M-1} \}Bjk=P(ot=vk∣it=qj)qi∈Qhiddenvk∈Vobs.={v0,v1,...,vM−1}
上式表示指的是在ttt时刻由实体标签(隐状态)qjq_jqj生成汉字(观测结果)vkv_kvk的概率。HMM的初始隐状态概率:又称为initialprobabilitiesinitial \ probabilitiesinitialprobabilities, 通常用π\piπ来表示, 注意这里可不是圆周率:
π=P(i1=qi)qi∈Qhidden={q0,q1,...,qN−1}\pi=P(i_1=q_i) \quad q_i \in Q_{hidden} = \{ q_0, q_1, ... , q_{N-1}\}π=P(i1=qi)qi∈Qhidden={q0,q1,...,qN−1}
上式指的是自然语言序列中第一个字o1o_1o1的实体标记是qiq_iqi的概率, 也就是初始隐状态概率。
4. 用HMM解决序列标注问题, HMM的学习算法
现在已经了解了HMM的三大参数A,B,πA, \ B, \ \piA,B,π, 假设已经通过建模学习, 学到了这些参数（学习算法见笔记二）, 得到了模型的概率, 怎么使用这些参数来解决序列标注问题呢?
设目前在时刻ttt, 有当前时刻的观测到的一个汉字ot=vko_t=v_kot=vk(指的第ttt时刻观测到vkv_kvk), 假设还知道在t−1t-1t−1时刻(前一时刻)对应的实体标记类型it−1=q^it−1i_{t-1} = \hat{q}^{t-1}_iit−1=q^it−1(指的t−1t-1t−1时刻标记为q^it−1\hat{q}^{t-1}_iq^it−1)。要做的仅仅是列举所有iti_{t}it可能的实体标记q^jt\hat{q}^{t}_{j}q^jt, 并求可以使下式输出值最大的那个实体类型qjtq^{t}_{j}qjt(也就是隐状态类型):
q^jt=argmaxq^jt∈QhiddenP(it=q^jt∣it−1=q^it−1)P(ot=vk∣it=q^jt)\hat{q}_j^{t} = argmax_{\hat{q}_j^{t} \in Q_{hidden}} P(i_t = \hat{q}_j^{t} | i_{t-1} = \hat{q}^{t-1}_i) P(o_t=v_k| i_t = \hat{q}_j^{t})q^jt=argmaxq^jt∈QhiddenP(it=q^jt∣it−1=q^it−1)P(ot=vk∣it=q^jt)
将所有ttt时刻当前可取的实体标签带入下式中, 找出一个可以使下式取值最大的那个实体标签作为当前字的标注:
P(当前可取实体标签∣上一时刻实体标签)P(测到的汉字∣当前可取实体标签)P(当前可取实体标签|上一时刻实体标签)P(测到的汉字|当前可取实体标签)P(当前可取实体标签∣上一时刻实体标签)P(测到的汉字∣当前可取实体标签)
注意: 这里只讲到了怎样求第ttt时刻的最优标注, 但是在每一时刻进行这样的计算, 并不一定能保证最后能得出全局最优序列路径, 例如在第ttt时刻最优实体标签是qjq_jqj, 但到了下一步, 由于从qjq_jqj转移到其他某些实体标签的转移概率比较低, 而降低了经过qjq_jqj的路径的整体概率, 所以到了下一时刻最优路径就有可能在第ttt时刻不经过qjq_jqj了, 所以每一步的局部最优并不一定可以达成全局最优, 所以之后会用到维特比算法来找到全局最优的标注序列, 这个后面会有详细讲解。
生成模型与判别模型:
对于生成模型与判别模型, 因为篇幅问题, 暂不做讲述, 网上有很多资料。
这里稍稍回顾一下, 假设xxx为数据点, yyy为数据标记, 比如说逻辑回归属于典型的判别模型, 要计算P(y∣x)P(y|x)P(y∣x)并形成一条分类边界, 而在HMM中, 计算的是P(x∣y)P(x|y)P(x∣y), 而且要计算出所有yyy可取的类型, 并比较一下所有P(x∣y=yi)P(x|y=y_{i})P(x∣y=yi)的结果, 并取可以使P(x∣y)P(x|y)P(x∣y)最大的那个, 而得到预测结果.
HMM参数学习(监督学习):
今天要用HMM解决的是序列标注问题, 所以解决的是监督学习的问题。也就是说现在有一些文本和与之对应的标注数据, 要训练一个HMM来拟合这些数据, 以便之后用这个模型进行数据标注任务, 最简单的方式是直接用极大似然估计来估计参数:
初始隐状态概率π\piπ的参数估计:
π^qi=count(qi1)count(o1)\hat{\pi}_{q_i}=\frac{count(q^{1}_{i})}{count(o_1)}π^qi=count(o1)count(qi1)
上式指的是, 计算在第111时刻, 也就是文本中第一个字, qi1q^{1}_{i}qi1出现的次数占总第一个字o1o_1o1观测次数的比例, qi1q^{1}_{i}qi1上标1指的是第1时刻, 下标iii指的是第iii种标签(隐状态), countcountcount是的是记录次数。转移概率矩阵AAA的参数估计:
之前提到过transitionmatrixtransition \ matrixtransitionmatrix里面AijA_{ij}Aij(矩阵的第i行第j列)指的是在ttt时刻实体标签为qiq_iqi, 而在t+1t+1t+1时刻实体标签转换到qjq_jqj的概率, 则转移概率矩阵的参数估计相当与一个二元模型bigrambigrambigram, 也就是把所有的标注序列中每相邻的两个实体标签分成一组, 统计他们出现的概率:
A^ij=P(it+1=qj∣it=qi)=count(qi后面出现qj的次数)count(qi的次数)\hat{A}_{ij}=P(i_{t+1}= q_j | i_{t} = q_i)=\frac{count(q_i后面出现q_j的次数)}{count(q_i的次数)}A^ij=P(it+1=qj∣it=qi)=count(qi的次数)count(qi后面出现qj的次数)发射概率矩阵BBB的参数估计:
提到过emissionmatrixemission \ matrixemissionmatrix中的BjkB_{jk}Bjk(矩阵第j行第k列)指的是在ttt时刻由实体标签(隐状态)qjq_jqj生成汉字(观测结果)vkv_kvk的概率。
B^jk=P(ot=vk∣it=qj)=count(qj与vk同时出现的次数)count(qj出现的次数)\hat{B}_{jk}=P(o_{t}= v_k | i_{t} = q_j)=\frac{count(q_j与v_k同时出现的次数)}{count(q_j出现的次数)}B^jk=P(ot=vk∣it=qj)=count(qj出现的次数)count(qj与vk同时出现的次数)
到此为止, 就可以遍历所有语料, 根据上面的方式得到模型的参数A,B,πA, \ B, \ \piA,B,π的估计。
注意, 通过上面的计算过程, 可以得出HMM的参数(A,B,π)(A, B, \pi)(A,B,π)有以下特性:
∑iπqi=1\sum_{i}\pi_{q_i} = 1i∑πqi=1
∑jAij=∑jP(it+1=qj∣it=qi)=1\sum_{j}A_{ij} = \sum_{j}P(i_{t+1}= q_j | i_{t} = q_i) = 1j∑Aij=j∑P(it+1=qj∣it=qi)=1
∑kBjk=∑kP(ot=vk∣it=qj)=1\sum_{k}B_{jk} = \sum_{k}P(o_{t}= v_k | i_{t} = q_j) =1k∑Bjk=k∑P(ot=vk∣it=qj)=1
三、维特比算法(Viterbi Algorithm)(HMM的预测算法)
维特比算法viterbialgorithmviterbi \ algorithmviterbialgorithm使用了动态规划算法来解决类似HMM和CRF的预测问题, 用维特比算法可以找到概率最大路径, 也就是最优路径, 在今天要解决的序列标注问题中, 就要通过维特比算法, 来找到文本所对应的最优的实体标注序列。
如果用一句话来概括维特比算法, 那就是:
在每一时刻, 计算当前时刻落在每种隐状态的最大概率, 并记录这个最大概率是从前一时刻哪一个隐状态转移过来的, 最后再从结尾回溯最大概率, 也就是最有可能的最优路径。这话对于没有学过维特比算法的同学是无法理解的, 但是我觉得今天学完维特比算法之后再来看这句话, 可以加深记忆。
这里为了学习维特比方便, 所以转换一下标签:
Ai,jt−1,tA_{i, j}^{t-1, t}Ai,jt−1,t, 是转移概率矩阵AAA中的第iii行第jjj列(下标), 指的是在t−1t-1t−1时刻实体标签为qiq_iqi, 而在ttt时刻实体标签转换到qjq_jqj的概率。BjkB_{jk}Bjk是发射矩阵的第j行第k列, 指的是在第ttt时刻, 由隐状态qjq_jqj生成观测vkv_kvk的概率。有了上面两点, 则q^j=AijBjk\hat{q}_j = A_{ij}B_{jk}q^j=AijBjk表示在ttt时刻的隐状态qjq_jqj得到的观测结果vkv_kvk的概率估计。
在这里直接以实例的方式来说明维特比算法的计算过程(注意在这里下标从000开始算起):
假设现在有所有可能的观测结果的集合Vobs.={v0,v1}V_{obs.}=\{v_0, v_1\}Vobs.={v0,v1};所有可能的隐状态的集合Qhidden={q0,q1,q2}Q_{hidden}=\{q_0, q_1, q_2\}Qhidden={q0,q1,q2};已经观测到的观测结果序列O=(o1=v0,o2=v1,o3=v0)O=(o_1=v_0, \ o_2=v_1, \ o_3 = v_0)O=(o1=v0,o2=v1,o3=v0);然后假设通过HMM建模并学习, 得到了模型所估计的参数(A,B,π)(A, B, \pi)(A,B,π), 注意下面的A,BA, BA,B矩阵按行求和为111;要求出对应当前观测结果OOO的最有可能的隐状态序列I=(i0,i1,i2)I=(i_0, i_1, i_2)I=(i0,i1,i2)。
现在要初始化两个暂存表格, 来暂存在每一时刻的计算结果, 稍后会说明怎么使用这两个表, 下面看到T1表格和T2表格, 他们的规格都是num_hidden_states∗sequence_lengthnum\_hidden\_states * sequence\_lengthnum_hidden_states∗sequence_length, 这两个表格在每一时刻ttt都由333个方块组成, 333是所有可能隐状态的个数, 即∣Qhidden∣=3|Q_{hidden}|=3∣Qhidden∣=3, 注意这里表格内填充的颜色无意义, 只有好看的作用。
计算过程:
首先有初始隐状态概率矩阵π\piπ, 和第1时刻的观测结果o1=v0o_1=v_0o1=v0, 则在第一时刻, 由隐状态生成观测结果的概率计算可以写成qjt=1=πjBjkq_j^{t=1} = \pi_{j}B_{jk}qjt=1=πjBjk。
现在说明T1,T2T1, T2T1,T2表格的用途:如果T1,T2T1, T2T1,T2表格是i∗ji*ji∗j的矩阵, 则矩阵中第jjj列指的是第jjj时刻, 第iii行指的是第iii种隐状态, T1[i,j]T1[i, \ j]T1[i,j]指的是在第jjj时刻, 落到隐状态iii的最大可能的概率是多少(不要着急, 到了下一个时刻就会明白最大是什么意思), 而T2[i,j]T2[i, \ j]T2[i,j]记录的是这个最大可能的概率是从第j−1j-1j−1时刻(上一时刻)的哪一种隐状态iii转移过来的, 也就是说记录的是最大可能的概率的转移路径。
现在将第一时刻的计算结果填入T1,T2T1, T2T1,T2表格, 注意在第000时刻的隐状态是由初始隐状态概率矩阵提供的, 而不是从上一时刻的隐状态转移过来的, 所以直接在T2T2T2表格上记为NAN(notanumber)NAN(not \ a \ number)NAN(notanumber)
现在来到第111时刻(时刻下标从000起算), 首先先计算T1[i=0,j=1]T1[i=0, j=1]T1[i=0,j=1](也就是第j=1j=1j=1时刻, 落到隐状态i=q0i=q_0i=q0上的最大可能的概率是多少), 可以看出, 从上一时刻到当前时刻, 要想让当前时刻的隐状态为i1=q0i_1=q_0i1=q0, 则有3条路径可走, 分别是: (i0=q0,i1=q0),(i0=q1,i1=q0),(i0=q2,i1=q0)(i_0=q_0, i_1=q_0), \ (i_0=q_1, i_1=q_0), \ (i_0=q_2, i_1=q_0)(i0=q0,i1=q0),(i0=q1,i1=q0),(i0=q2,i1=q0),
在T1[i=0,j=1]T1[i=0, j=1]T1[i=0,j=1]的位置就是要算出, 这三条路径哪一条是最有可能的路径, 也就是取概率最大的一条, 这样的话, 计算公式为:
T1[0,1]=maxi(P(i1=q0∣i0=qi)P(o1=v1∣i1=q0))=T1[qi,time_step=0]∗At−1=qi,t=q0∗Bi1=q0,o1=v1T1[0, 1]=\max_{i} (P(i_1 = q_0 | i_0 = q_i) P(o_1=v_1| i_1 = q_0)) = T1[q_i, time\_step=0] * A_{t-1=q_i, \ t=q_0} * B_{i_1 = q_0, o_1=v_1}T1[0,1]=imax(P(i1=q0∣i0=qi)P(o1=v1∣i1=q0))=T1[qi,time_step=0]∗At−1=qi,t=q0∗Bi1=q0,o1=v1
上式最右边T1[qi,time_step=0]T1[q_i, time\_step=0]T1[qi,time_step=0]也就是T1[:,0]T1[:, \ 0]T1[:,0]的意思是在t−1t-1t−1时刻(也就是上一时刻), 每个隐状态对应的概率, 是长度为333的向量;
At−1=qi,t=q0A_{t-1=q_i, \ t=q_0}At−1=qi,t=q0是AAA矩阵的第iii行第000列, 指的是在t−1t-1t−1时刻隐状态为qiq_iqi, 而在ttt时刻隐状态为q0q_0q0的概率, 一共有三种可能的路径, 所以也是长度为333的向量;
Bi1=q0,o1=v1B_{i_1 = q_0, o_1=v_1}Bi1=q0,o1=v1是BBB矩阵的第000行第111列, 指的是隐状态q0q_0q0生成观测v1v_1v1的概率, 是一个数值。
通过查表计算, 算出:
T1[0,1]=max{0.10∗0.5∗0.5,0.16∗0.3∗0.5,0.28∗0.2∗0.5}=0.028T1[0,1]=max\{0.10 * 0.5 * 0.5, \ 0.16 * 0.3* 0.5, \ 0.28*0.2* 0.5\}=0.028T1[0,1]=max{0.10∗0.5∗0.5,0.16∗0.3∗0.5,0.28∗0.2∗0.5}=0.028
之前说过, 还要知道目前计算出来的这个最大可能的概率前一时刻的哪一种隐状态iii转移过来的, 也就是要在T2[0,1]T2[0,1]T2[0,1]记录转移路径, 计算公式为:
T2[0,1]=argmax{0.10∗0.5∗0.5,0.16∗0.3∗0.5,0.28∗0.2∗0.5}=2T2[0,1]=argmax\{0.10 * 0.5 * 0.5, \ 0.16 * 0.3* 0.5, \ 0.28*0.2* 0.5\}=2T2[0,1]=argmax{0.10∗0.5∗0.5,0.16∗0.3∗0.5,0.28∗0.2∗0.5}=2
把计算结果填到表里, 注意在下图中, 红色的线表示最大的转移路径, 是从前一时刻的q2q_2q2转移过来的。
接下来用同样的方式, 把表填完, 下面开始说明维特比算法是怎样通过这些暂存的概率和路径找到最优路径的:
最优路径有以下特性: 假设有一条最优路径在ttt时刻通过一个隐状态iti_tit, 那么这一路径从iti_tit到最优路径的终点iTi_TiT相对于在这段距离里所有可能出现的路径里, 也必须是最优的. 否则从iti_tit到iTi_TiT就会有更优的一条路径, 如果把他和从i1i_1i1到iti_tit的路径(最优路径iti_tit之前的部分)连起来, 等于又有一条更优路径, 这是矛盾的。
利用这一特性, 只要按上面的步骤计算直到得出最后一步达到的最大概率的隐状态, 再确认最大概率是从前一步哪一个隐状态转移过来的, 然后从T2T2T2表格里面递推回溯直到第一时刻(也就是NANNANNAN的地方), 就可以找出最优路径了。
回溯的计算:
首先算出最后一步达到最大路径的隐状态, 也就是在T1T1T1表格的第333列求argmaxargmaxargmax:
i2=argmaxT1[:,time_step=2]=2i_2 = argmax \ T1[:, \ time\_step = 2] = 2i2=argmaxT1[:,time_step=2]=2之后通过T2T2T2表格向前追溯一步, 当前最大概率是从前一步哪个隐状态转移过来的:
i1=T2[i2=2,time_step=2]=2i_1 = T2[i_2 = 2, \ time\_step = 2] = 2i1=T2[i2=2,time_step=2]=2到达了倒数第一步, 追溯最优路径是从哪个起始隐状态转移过来的:
i0=T2[i1=2,time_step=1]=2i_0 = T2[i_1 = 2, \ time\_step = 1] = 2i0=T2[i1=2,time_step=1]=2至此得出了最有可能的隐状态序列:
I=(q2,q2,q2)I=(q_2, \ q_2, \ q_2)I=(q2,q2,q2)
结论:
时间复杂度: 假设有NNN种隐状态, 在每个时刻之间, 一共可能的路径一共有N2N^2N2种, 假设有TTT个时刻, 则维特比算法的时间复杂度为O(TN2)O(TN^2)O(TN2)。在实际的预测计算当中, 为了防止计算结果下溢, 通常将乘法变为取对数之后的加法。具体范例代码见视频讲解。
四、代码实现
下面代码部分为维特比算法中正向递推算法的矩阵化算法, 即从t-1时刻到t时刻求出需要填入T1和T2表暂存的算法,这里计算的是上例从第0时刻到第1时刻的计算过程。
输入：
import numpy as npA = np.array([[.5, .2, .3],[.3, .5, .2],[.2, .3, .5]])B = b = np.array([[.5,.5],[.4,.6],[.7,.3]])pi = np.array([[.2],[.4],[.4]])print("transitions: A")print(A)print("emissions: B")print(B)print("pi:")print(pi)
输出：
transitions: A[[0.5 0.2 0.3][0.3 0.5 0.2][0.2 0.3 0.5]]emissions: B[[0.5 0.5][0.4 0.6][0.7 0.3]]pi:[[0.2][0.4][0.4]]
输入：
T1_prev = np.array([0.1, 0.16, 0.28])T1_prev = np.expand_dims(T1_prev, axis=-1)print(T1_prev)print(T1_prev.shape)
输出：
[[0.1 ][0.16][0.28]](3, 1)
输入：
# 因为第1时刻的观测为v_1, 所以取B矩阵的第1列, 即所有隐状态生成观测v_1的概率p_Obs_State = B[:, 1]p_Obs_State = np.expand_dims(p_Obs_State, axis=0)print(p_Obs_State)print(p_Obs_State.shape)
输出：
[[0.5 0.6 0.3]](1, 3)
输入：
T1_prev * p_Obs_State * A
输出：
array([[0.025 , 0.012 , 0.009 ],[0.024 , 0.048 , 0.0096],[0.028 , 0.0504, 0.042 ]])
输入：
# 在行的维度求maxnp.max(T1_prev * p_Obs_State * A, axis=0)
输出：
array([0.028 , 0.0504, 0.042 ])
输入：
# 看看所得的max概率的路径是从哪里来的, 在上一步从哪个隐状态转移过来的np.argmax(T1_prev * p_Obs_State * A, axis=0)
输出：
array([2, 2, 2])
参考资料:
中文命名实体识别标注数据: /SophonPlus/ChineseNlpCorpus统计学习方法 (第2版) 李航 著 193页 第十章 隐马尔可夫模型wikipedia Viterbi algorithm /wiki/Viterbi_algorithmwikipedia Hidden Markov model /wiki/Hidden_Markov_model
