小象-机器学习-21.hmm与中文分词

法本课件包括演示文稿、示例、代码、题库、和在课程范围外向任何第散播。任何其他人或机构不得盗版、、仿造其中的创意及内容，我们 课 咨

邹主要内概率计算：前向后向算参数估计：Baum-Welch算模型预测：Viterbi算

中文分

JasonBell.MachineLearning:Hands-OnforDevelopersandTechnicalHMM的参数表 A,B,

HMM的两个基本性 , ,i , !i, Pi t t t

t

t Poi,o,i , !i, Pot

T

T

HMM的3个基本问 给定模型A,B,和观 列Oo,o,…o计 列Oo1,o2,…oT，估计模型A,B,的参数，使得在该模型下 列P(O|λ)最 问题：已知模型A,B,和 列Oo1,o2,…oT 列条件概率P(I|O,λ)最大的状态序列

定义：前向概率-后向概

前向算 t

iPo,o,!o,iq可以递推计算前向概率αt(i)及观

前向算iPooo,iq 1初值：1i1tt

N

T

后向算下，从t+1到T的部分观列为ot+1,ot+2…oT t t iPo, t t 可以递推计算后向概率βt(i)及 列概

T t

aijbjot1t

N

前后向关 Piq,O POiq,Pi t Po,!o, ,! i t Po,! iq, ,! iq,Piq

t

Po,!o,i

,!

iq,

t

记：iqO

单个状态的概 iPiqO,

Piq,Oit it

N tN

γ的意态i*，从而得到一个状态序列I*={i*i*…it

给定模型和

N N

t

两个状态的联合概i,jPiq,i qO, t

两个状态的联合概 tji,jPiq, tjPiq, q,Oj tjPOPiq, q,O t j

Piq, q,O t q,i t

t

期T在观测O下状态i出现的期Tt1在观测O下状态i转移到状态j的期望Tti,Tt

学习算 HMM的学习非常简单，是监督学

大数定列和对应的状态序列{(O1,I1),(O2,I2)…(Os,Is)}，那么，可以直接利用BernoulliHMM的参数估计

监督学习方

i ii

ˆij

N

j

k

Baum-Welch算

附：EM算法整体框

Baum-Welch算所有观测数据写成O=(o1,o2…oT)，所有隐数据写成是HMM参数的当前估计值，λ

I

lnPO,III

EM过

i

ai

bi

!a

ibi 1 1 2 T1 T

III

i tt1

I

itot极大极大化Q，求得参数

lniPO,IlniPO,ii1 1 NN

ln

i

i NiNi

NNN

初始状态概率

11

11

1 1PO

1

转移概率和观测概T

NT1lnaPO,ii, j

t

i1j1t

tT1

T O,iti,it1 aijt t1 ttt

i ttt

tTT t t1,otvk TTTTTTt

i

t

t

预测算

预测的近似算态i*，从而得到一个状态序列I*={i*i*…it

给定模型和

N N

t会出现此状态在实际中可能不会发生的情

算法：走棋盘/格子取

问题分dp[0,0]=a[0,0]/第一行(列)累dp[x,y]=min(dp[x-1,y]+a[x,y],dp[x,y-即：dp[x,y]min(dp[x-1,y],dp[x,y-1])

Viterbi

ViterbiimaxPii,

,...i,o,...o

i1,i2

t

imax

i,i,...i, ,...ot

t

t 1j

P*max

例

0.5 0.5

A

B0.4

B

解：观测向量O=“红白红

到o1=红的概率，记此概率为 i 求得

0.5

A

解：观测向量O=

maxja

t

同理

解：观测向量O=“红白红

求最优路径图

Baum-Welchcode：初始

Baum-Welch

前向-后

隐状态概率–隐状态转移概EM迭

分

HMM与中文分

JasonBell.MachineLearning:Hands-OnforDevelopersandTechnical总马尔科夫模型可以用来解释贪心法和动态规思考：可否用深度学习代替

参考