PGM

Report
概率图模型
林琛
博士、副教授
引子
• Siri: iphone 4S上应用的一项语音控制功能
– 生活大爆炸(5-14-0500)
– 一段对话
“Siri, how’s the weather tomorrow in London?”
“Sunny and mild”
“How about Shanghai?”
• Judea Pearl
– 贝叶斯网络的先驱
– 奠定不确定性和因果推理在计算机等多个学科中的
地位
概率基础
• 世界上许多事情都具有不确定性。
• 概率论是研究处理这类现象的数学理论
• 用概率表示事件发生的可能性。例如,P(硬币
正面朝上)=0.5。
– 可能发生多次(频率论)
– 可能只能发生一次(贝叶斯概率)
• 随机试验的所有可能结果组成该试验的样本空
间
3/33
http://www.xmu.edu.cn
课堂测试(1)
• 事件投1次硬币的样本空间是?
• 事件投2次硬币的样本空间是?
随机变量
• 随机变量是定义在样本空间上的函数,其所有可能取值的集合称为
它的值域,也称状态空间。掷骰子试验,设X为“扔骰子实验的所
有可能结果”,则X为一随机变量.
• 对单个随机变量X,可用概率函数P(X)来描述它的各个状态的概率
• 而对于多个随机变量X1,…,Xn,则可用 联合概率分布P(X1,…,
Xn)来描述各变量所有可能状态组合的概率
– 联合分布刻画了变量之间的各种关系,包含了变量关系的所有信息
• 随机变量X1在另外一个随机变量X2各个状态下的发生概率为条件概
率分布表示为P(X1| X2)
• 随机变量X1的各状态概率,与其他随机变量无关,叫做边际概率
5/33
http://www.xmu.edu.cn
乘法法则与加法法则
• 加法规则
• 乘法法则
– 事件 A,B同时发生的概率是:
• 如果X,Y不相关,则可以表示为
– P(X,Y)=P(X)P(Y)
课堂测试(2)
• 设有3个装有黑白两色球
的口袋,第一个口袋黑白
球各半,第二个口袋黑白
球比例为4:1,第三个则
全是黑球。用随机变量X,
Y,Z分别代表从这3个口
袋随机抽出的球的颜色,
w表示白,b表示黑。则联
合概率分布P(X,Y,Z)如右所
示:
• 计算
P(X=w),P(X=w|Y=b,Z=w)
X
Y
Z
P(X,Y,Z)
w
w
w
0
w
w
b
0.1
w
b
w
0
w
b
b
0.4
b
w
w
0
b
w
b
0.1
b
b
w
0
b
b
b
0.4
http://www.xmu.edu.cn
7/33
利用概率分布推理的例子
• 故事:Pearl教授家住洛杉
•
矶,那里地震和盗窃时有
发生。教授的家里装有警
铃,地震和盗窃都有可能
触发警铃。听到警铃后,
两个邻居Mary和John可能
会打电话给他。
• 问题: 一天,Pearl教授接到
Mary的电话,说听到他家
警铃响,Pearl教授想知道
他家遭盗窃的概率是多大。
常用的解决此类问题的途
径,即使用概率方法进行
不确定性推理就是:
1) 把问题用一组随机变
量来刻画;
2) 把关于问题的知识表
示为一个联合概率分布;
3) 按照概率论原则进行
推理计算。
朴素贝叶斯训练
• 训练数据集T={<x1,y1>,…,<xn,yn>}
– 由联合概率分布P(X,Y)独立同分布产生
• 朴素贝叶斯法学习以下先验概率分布及条件概
率分布
– 先验概率分布P(Y=c)
– 条件概率分布P(X=x|Y=c)
• 朴素贝叶斯假设在类别确定的条件下,各特征是条件独
立的即:
P ( X  x | Y  c )   i P ( X i  xi | Y  c )
• 降低了计算复杂度
• 但可能牺牲分类精度
朴素贝叶斯预测
• 计算后验概率P(Y=c|X=x),将后验概率最大
的类作为类别预测输出
• 后验概率计算根据贝叶斯定理
P (Y  c | X  x ) 

P ( X  x | Y  c ) P (Y  c )
 k P ( X  x | Y  c k ) P (Y  c k )
P (Y  c )  i P ( X i  x i | Y  c )
 k P ( X  x | Y  c k ) P (Y  c k )
同样是条件独立性假设
朴素贝叶斯的损失函数
• 假设朴素贝叶斯的决策模型是f(x)
• 对于一个训练样本x,损失函数L(y,f(x))
L ( y , f ( x ))  {
1, y  f ( x )
0, y  f ( x )
• 对联合分布P(X,Y),损失函数的期望为
E x  c [ L ( c , f ( x ))] P ( c | x )
– 最小期望损失,只需要对每个x极小化
f ( x )  arg m in y Y  c L ( c , y ) P ( c | X  x )
 arg m in y Y  c P ( y  c | X  x )
 arg m in y Y (1  P ( y  c | X  x ))
 arg m ax y Y P ( y  c | X  x )
 arg m ax c P ( y  c | X  x )
朴素贝叶斯算法
• 学习
– 估算P(y=c)和P(Xi=xi|Y=c)的概率
• 一般采用最大似然
• 预测
– 估算后验概率P(Y=c|X=x)
– 确定其中概率最大的类别标记
平滑
• 概率值为0的情况
– 未观测到的样本
– 拉普拉斯平滑 
 0, 常 取   1
• 对特征的条件产生概率
P ( X
j
 a | Y  c) 
N ( x j  a, y  c)  
• 对类别的先验概率
P (Y  c ) 
N (Y  c )  
N  C
N ( y  c )  A
Xj的不同特征值总数
这样确保了还是概率分布
•>0
•和为1
课堂测试(3)
• 故事:Pearl教授家住洛杉
矶,那里地震和盗窃时有
发生。教授的家里装有警
铃,地震和盗窃都有可能
触发警铃。听到警铃后,
两个邻居Mary和John可能
会打电话给他。
• 问题: 一天,Pearl教授接到
Mary的电话,说听到他家
警铃响,Pearl教授想知道
他家是否遭盗窃了
• B=盗窃,A=警铃,E=地震,
M=Mary电话,J=John电话
贝叶斯网络
• 朴素贝叶斯假设各特征间是独立的,实际上可
要多少次运算?
能是互相依赖的
(多少个参数)
• 全依赖的联合概率
2n-1
P(A,B,C,…M)=P(A)P(B|A)P(C|A,B)….P(M|A,B,C,…L)
• Pearl提出了用如下方法构造一个有向无环图
– 把每个变量都表示为一个节点;
– 对于每个节点Xi,都从跟其直接相关的节点画一条
有向边到Xi.
贝叶斯网络的链规则
P(B,E,A,J,M)
=P(B)P(E|B)P(A|B,E)P(J|B,E,A)P(M|B,E,A,J) (1)
=P(B)P(E)P(A|B,E)P(J|A)P(M|A)
(2)
要多少次运算?
(多少个参数)
1+1+4+2+2=10
P(E)
P(B)
P(E=1)
0.5
P(B=1)
0.3
P(J|A)
J
P(J=1)
P(A|B,E)
0
B
E
0
0
0
1
1
0
1
1
M
1
P(M|A)
P(A=1)
0.29
0.95
P(M=1)
0
1
• 从图中可以看出,变量A依赖于B和E,那么A具体是如何依赖于B和E的呢?
条件概率分布P(A|B,E)定量的刻画了这个问题:
1) 盗窃和地震都发生时,警铃响的概率为P(A=y|B=y,E=y)=0.95
2) 只发生盗窃但没有发生地震时,警铃响的概率为P(A=y|B=n,E=y)=0.29
3) 所有其它情形
• 类似地,P(M|A)、P(J|A)定量刻画了M和J如何依赖于A . 变量B和E不依赖于
其它变量,P(B)和P(E)给出它们的边缘分布
• 贝叶斯网络=有向五环图+条件概率表
http://www.xmu.edu.cn
16/33
贝叶斯网络的主要内容
• Inference(推理)
– 给定结构和CPT(条件
概率表)
• 可以是离散/连续型变量
• 可以结合专家知识
• 可以结合数据
– 回答下面的问题
• 已经观察到某些变量
• 回答另一些变量发生的
概率
• Learning(学习)
– 学习CPT
• 可以是某种指定概率分
布的参数
– 学习结构
– 可以是不完全数据
• 即有隐含变量
贝叶斯网络应用
• 贝叶斯网络属于产生式模型/生成模型
(Generative model)
– 目标是P(y|x)
– 步骤
• 给出贝叶斯网络
– P(y),P(x|y)的函数形式
• 学习
– 通过最大似然估计参数p(y),p(x|y)
• 推理
– 得到p(y|x)
课堂讨论
• 尝试使用贝叶斯网络建立一个自动肺癌诊
断系统
常用的概率分布函数(1)
• 离散变量
– 二元
• 假设掷硬币正面朝上(x=1)概率是u
Bernoulli分布
• 假设投了N次,则其中出现m次正面朝上的概率是
Binomial二项分布
常用的概率分布函数(2)
• 离散变量
– 多元变量
• 可以把变量表示为 (0,0,0,1,0,0),那么和二元变量类似,结果为
xk的概率为
• 统计N次试验结果,其中第1、2…K类结果出现次数分别为
m1,m2,…mK次的概率
Multinomial多项分布
常用的概率分布函数(3)
• 连续变量
任何一种概率分布可以表示为多个高斯分布的组合
又叫做混合高斯模型
• 多元高斯分布
协方差矩阵
参数学习(1)
• 最大似然
– 频率派观点:参数是固定的
• 对于给定的数据集,参数使产生该数据集的可能性
最大(即最大似然)
• 由于参数固定,因此给定自变量x,结果y也是固定
的
课堂测试
• 二项分布的最大似然估计
假设三次掷硬币结果是『1,1,1』,则最大似然估计下参数是多少?预测
下一次掷硬币结果
最大似然估计参数u=1
每一次掷硬币结果都为正面
参数学习(2)
• 贝叶斯估计
如果数据量足够大,最大后验概率和最大似然
估计趋向于一致,如果数据为0,最大后验仅由
先验决定。
– 贝叶斯派:参数也是随机变量
• 贝叶斯法则
似然
先验概率
后验概率
– 无法找到解析解,所以一般用近似的最大后验概率
• 由于参数不固定,结果也是随机的,因此给出预测
的是期望值
课堂测试
• 假设Bernoulli分布的参数u符合一个先验分布(Beta分布)
– 参数自己设定
• 使用贝叶斯估计参数
– 并解释最大后验概率和最大似然的相关性
解释
• 贝叶斯估计的性质
• 预测下一次掷硬币结果
由于分子=a0+m,分母
=b0+N-m,所以不会=1
贝叶斯网络v.s.线性回归
贝叶斯网络v.s.Logistic回归
伯努利分布:掷硬币的分布,x=正/反
贝叶斯网络中可以有隐含变量
• 隐含变量(观测不到的变量)
– 例:假设有3枚硬币,分别记作A,B,C。这些硬
币正面出现的概率分别是o,p,q。进行如下实验
– 先掷硬币A
• 如果是正面选择硬币B
• 否则选择硬币C
– 只能记录最终结果,看不到过程(即硬币A的
结果)
– 独立重复10次试验,结果
Z
• 1,1,0,1,0,0,1,0,1,1
Y
含有隐含变量的参数估计
• 观测结果的似然函数为
P (Y | o , p , q )   Z P ( Z | o , p , q ) P (Y | Z , o , p , q )
  j [ op
y
j
(1  p )
1 y
j
 (1  o ) q
y
j
(1  q )
1 y
j
]
最大似然取log,由于log里是和,所以没有解析解
一种迭代的方法 EM算法
1. 选取初值
2. 迭代,直到收敛
1. E步:计算在给定的o,p,q参数下,观测结果来自掷硬币B的概率
2. 根据观测结果来自硬币B,C的概率重新推断o,p,q的值
EM算法
• 输入:观测变量Y,隐变量Z,联合分布
P(Y,Z|θ),条件分布P(Z|Y, θ)
• 输出: 模型参数θ
可以任意初始化,但是EM算法对初值敏感
• 初始化θ
• 迭代
停止条件一般是模型参数变化收敛
– 在迭代的第i+1轮
Q ( ,  )  E
– E步
i
[log P (Y , Z |  ) | Y ,  ]
Z
i
  Z log P (Y , Z |  ) P ( Z | Y ,  )
i
– M步:求上述Q最大的θ
L ( q ,  )   Z q ( Z ) log[
EM算法原理
Q ( ,  )  E Z [log P (Y , Z |  ) | Y ,  ]
  Z P ( Z | Y ,
  Z log P (Y , Z |  ) P ( Z | Y ,  )
  Z P (Z | Y ,
i
i
i
• 挑战:P (Y |  )  
Z
old
old
P (Y , Z | theta )
q(Z )
) log P (Y , Z |  )
) log P ( Z | Y , 
old
)
P (Y , Z |  )
Log( 括号内有加法操作无法获得解析解 )
• 解决:最大下界
引入Z上的另一个分布q(Z)
log P (Y |  )  L ( q ,  )  K L ( q‖ p )
下界
q(Z)=p(Z|Y,θ)
L ( q ,  )   Z q ( Z ) log[
p (Y , Z |  )
]
q(Z )
K L ( q‖ p )    Z q ( Z ) log[
p (Z | Y , )
上面这个等式是否成立?代入
q(Z )
]
0
•E步:通过q(Z)最大下界L(q,θ)
•这时候θ没变
•q(Z)=p(Z|Y,θ)
•M步:通过θ最大下界L(q,θ)
•q(Z)不变, θ变
•所以KL距离大于0
•似然增大
log P (Y , Z |  )  log P ( Z | Y ,  )  log P (Y |  )
]
课堂测试
1. 假设有3枚硬币,分别记作A,B,C。这些硬币
正面出现的概率分别是o,p,q。进行如下实验。
先掷硬币A,如果是正面选择硬币B,否则选
择硬币C。独立重复10次试验,结果【1,1,
0,1,0,0,1,0,1,1】。估计o,p,q
2. 假设观测数据【-67,48,6,8,14,16,23,24,28,29,41,49,56,60,75】是由
两个分量的高斯混合模型生成,试估计模型
的5个参数(系数、高斯模型的参数)
随机变量序列
• 生活大爆炸(5-14-0500)
What's your
name?
My name? It's
Siri.
Are you single?
I don't have a
marital status, if
that's what you're
asking.
How about a cup
of coffee?
I've found six
coffee shops.
自然语言处理中的一系列问
题
•语音识别
•词性标注
•机器翻译
•…
•Online demo
其他涉及到时间的问题
•人的行为分析
•视频中预测走路/步行/
网球动作
•网络中的入侵检测
•…
其他涉及到序列的问题
•基因组序列中蛋白质编码
区域的预测
观测与状态序列
wo3 ai4 bei3 jing1 tian1 an1 men1
额的神
语音识别
我爱北京天安门
吗
观测
方
状态(隐含)
中文分词
我 爱 北京 天安门
词性标注
我爱/VV 北京/NR 天安门/NN
模型
• 隐马尔可夫模型定义
– 隐马尔可夫模型是关于时序的概率模型,描述
由一个隐藏的马尔可夫链随机生成不可观测的
状态随机序列;再由各个状态生成一个观测而
产生观测随机序列的过程。
– 隐藏的马尔可夫链随机生成的状态的序列,称
为状态序列
– 每个状态生成一个预测,由此产生的观测的随
机序列,称为观测序列
– 序列的每一个位置可以看作是一个时刻
隐马尔可夫模型的基本假设
• 齐次马尔可夫性假设
– 假设隐藏的马尔可夫链在任意时刻t的状态只依
赖于其前一时刻的状态,与其他时刻的状态及
观测无关,也与时刻t无关
• 观测独立性假设
– 假设任意时刻的观测只依赖于该时刻的马尔可
夫链的状态,与其他观测及状态无关
HMM实例——描述
• 设有N个缸,每个缸中装有很多彩球,球的颜
色由一组概率分布描述。实验进行方式如下
– 根据初始概率分布,随机选择N个缸中的一个开始
实验
– 根据缸中球颜色的概率分布,随机选择一个球,记
球的颜色为O1,并把球放回缸中
– 根据描述缸的转移的概率分布,随机选择下一口缸,
重复以上步骤。
• 最后得到一个描述球的颜色的序列O1,O2,…,
称为观察值序列O。
– 不知道缸序列
HMM实例——示意
Urn 3
Urn 1
Urn 2
Veil
观测数据:
HMM组成
Markov链
(, A)
状态序列
q1, q2, ..., qT
随机过程
(B)
HMM的组成示意图
观察值序列
o1, o2, ..., oT
HMM的基本要素
• 用模型五元组  =( N, M, π ,A,B)用来描述
HMM,或简写为  =(π ,A,B)
参数
含义
实例
N
状态数目
缸的数目
M
每个状态可能的观察值数
目
彩球颜色数目
A
与时间无关的状态转移概
率矩阵
在选定某个缸的情况下,
选择另一个缸的概率
B
给定状态下,观察值概率
分布
每个缸中的颜色分布

初始状态空间的概率分布
初始时选择某口缸的概率
HMM可解决的问题
• 问题1:给定观察序列O=O1,O2,…OT,以及模
型   ( A , B ,  ,) 如何计算P(O|λ)?
– 概率计算问题
• 问题2:给定观察序列O=O1,O2,…OT以及模型λ,
如何选择一个对应的状态序列 S =q1,q2,…qT,使
得S能够最为合理的解释观察序列O?
– 预测问题
• 问题3:如何调整模型参数 
P(O|λ)最大?
– 学习问题
 ( A , B ,  ) 使得
概率计算问题(朴素解法)
• 直接枚举所有可能的状态序列
– 给定一个固定的状态序列S=(q ,q ,q …)
1
2
3
T
P (O / S ,  )   P (Ot / qt ,  )  bq1 (O1 )bq2 (O2 ) bqt (OT )
t 1
– bq (Ot ) 表示在q 状态下观测到O 的概率
t
t
– 概率加法法则 P (O /  ) 
t
 P(O / S ,  ) P( S /  )
所有S
• N=5, M=100, => 计算量10^72
前向算法
• 动态规划
 t (i )  P (O1 , O 2 ,  Ot , q t
• 递推
  i /  ) 1 t T
– 定义到时刻t,部分观测序列O1,O2,…Ot,且时刻t的
状态为qt的概率为前向概率
– 利用状态序列的路径结构递推计算,将前向概率
“推”往全局,从而避免重复计算
– 初始化:  (i)   b (O ) 1 t  T
1
– 递归:
i i
1
N
 t 1 ( j )  [  i (i )aij ]b j (Ot 1 ) 1  t  T  1,1  j  N
i 1
– 终结:
N
P (O /  ) 

i 1
T
(i )
前向法示意图
tN
qN
.
qi
.
qj
.
.
q1
ti
aNj

aij
t1
1
...
t
N=5, M=100, => 计算量3000
j
t 1
a1j
t+1
...
后向法
• 定义后向变量
 t (i )  P (Ot 1 , Ot  2 ,  OT , qt   i /  ) 1  t  T 1
– 初始化:
T (i )  1 1 t  T
– 递归:
N
– 终结:
 t (i )   aij b j (Ot 1 )  t 1 ( j ) t  T  1, T  2,...,1,1  i  N
i 1
N
P (O /  )    1 (i )
i 1
课堂测试
• 假设从三个箱子中取球,每个箱子中分别
有红球、白球若干
– 状态转移概率矩阵A,观测概率矩阵B,初始状
态概率矩阵π
– T=3 观测序列{红,白,红}
0.5
0.2
0.3
A  0.3
0.5
0.2
B  0.4 0.6
0.2
0.3
0.5
0.7 0.3
0.5 0.5
  [ 0.2 ,
0.4 ,
0. 4 ]
课堂测试(续)
• 计算初值
– a1(1)=0.2x0.5=0.1
– a1(2)=0.4x0.4=0.16
– a1(3)=0.4x0.7=0.28
• 递推计算
–
–
–
–
–
–
a2(1)=(0.1x0.5+0.16x0.3+0.28x0.2)x0.5=0.077
a2(2)=(0.1x0.2+0.16x0.5+0.28x0.3)x0.6=0.1104
a2(3)= (0.1x0.3+0.16x0.2+0.28x0.5)x0.3=0.0606
a3(1)=(0.077x0.5+0.1104x0.3+0.0606x0.2)x0.5=0.04187
a3(2)=(0.077x0.2+0.1104x0.5+0.0606x0.3)x0.4=0.03551
a3(3)=(0.077x0.3+0.1104x0.2+0.0606x0.5)x0.7=0.05284
• 终止
– P(O|λ)=a3(1)+a3(2)+a3(3)=0.13022
引申:其他概率的计算
• 给定模型和观测,在时刻t处于状态qi的概
率 P (s  q | O ,  )  P (s  q , O |  )
t
t

i
i
P (O |  )
 t (i )  t (i )
 j 1 t ( j )  t ( j )
N
• 给定模型和观测,在时刻t处于状态qi,且
在时刻t+1处于状态qj的概率
P ( s t  q i , s t 1  q j | O ,  ) 

P ( s t  q i , s t 1  q j , O |  )
 t ( i ) a ij b j ( o t  1 )  t  1 ( j )
 i 1  j 1 t ( i ) a i j b j ( o t  1 )  t  1 ( j )
N
N
P (O |  )
预测问题
• 近似算法
– 目标:对给定观测序列最可能的状态序列
– 近似:每个时刻选择最可能的状态
P ( st  q i | O ,  ) 

 t (i )  t (i )
P ( st  q i , O |  )
P (O |  )
最大
 j 1 t ( j )  t ( j )
N
– 缺陷:不能保证整体是最可能的,因为有的状
态转移是不可能出现的(概率为0)
Viterbi算法
• 动态规划
– 状态序列=路径
– 最优路径原理:如果最优路径在时刻t通过节点
s*,则从节点s*到终点的部分路径必然是最优
的
– 递推:
 t ( i )  m ax P [ q1 q 2 ...q t 1 , q t  i , O1, O 2 , … O t , |  ]
q1 , q 2 ,... q t 1
 t  1 ( i )  m ax  t ( j ) a ji bi ( o t  1 )
1 j  N
Viterbi算法(续)
• 初始化:
 1 (i )   i bi (O1 ), 1  i N
1 (i )  0, 1 i  N
• 递归:
记录下前一个节点
 t ( j )  max[ t 1 (i )aij ]b j (Oi ), 2  t  T ,1  j  N
1i  N
 t ( j )  arg max[ t 1 (i )aij ], 2  t  T ,1  j  N
1i  N
• 终结:
P  max[ T (i )])
*
1i  N
qT  arg max[ T (i )]
*
1i  N
• 求S序列:
qt   t 1 ( qt 1 ), t  T  1, T  2,...,1
*
*
课堂测试
• 假设从三个箱子中取球,每个箱子中分别
有红球、白球若干
– 状态转移概率矩阵A,观测概率矩阵B,初始状
态概率矩阵π
– T=3 观测序列{红,白,红}
0.5
0.2
0.3
A  0.3
0.5
0.2
B  0.4 0.6
0.2
0.3
0.5
0.7 0.3
0.5 0.5
  [ 0.2 ,
0.4 ,
0. 4 ]
课堂测试(续)
1 (1)  0.2 x0.5  0.10, 1 (2)  0.4 x0.4  0.16, 1 (3)  0.4 x0.7  0.28
1 (i )  0
• 初始化
 2 (1)  max[0.10 x0.5, 0.16 x0.3, 0.28 x0.2] x0.5  0.028
1 i  N
2 (1)  3
 2 (2)  max[0.10 x0.2, 0.16 x0.5, 0.28 x0.3] x0.6  0.0504
1 i  N
• 递归
2 (2)  3
 2 (3)  max[0.10 x0.3, 0.16 x0.2, 0.28 x0.5] x0.3  0.042
1 i  N
2 (3)  3
 3 (1)  0.0504 x0.3 x0.5  0.0756, 3 (1)  2
 3 (2)  0.0504 x0.5 x0.4  0.01008, 3 (2)  2
 3 (3)  0.042 x0.5 x0.7  0.0147, 3 (3)  3
回溯最优路径【倒】:3,3,3
学习算法
• 监督学习算法
– 训练数据中已知观测序列和对应的状态序列
– 利用极大似然估计
• 转移概率、观测概率、初始状态概率都可以使用频
度的比率来计算
• 非监督学习算法
– 训练数据中已知观测序列,不知道对应的状态
序列
• 由于人工标注耗时耗力,一般情况下非监督学习
– EM算法(Baum-welch)
Baum-Welch算法
• 目的:给定观察值序列O,通过计算确定一个
模型 , 使得P(O| )最大。
• E步
Q (  ,  )   S log P ( O , S |  ) P ( S | O ,  )
i
i
P (O , S |  ) / P (O |  )
i
Q (  ,  )   S log P ( O , S |  ) P ( S , O |  )
i
i
  s log  s 0 P ( O , S |  )   s [  t log a st st 1 ] P ( O , S |  )   s [  t log b st ( o t )] P ( O , S |  )
i
i
• M步
– 利用概率约束,拉格朗日乘子法求最大
i
Baum-Welch算法(续)
• 定义:
给 定 模 型  和 观 察 序 列 条 件 下 , 从 i到 j的
转 移 概 率 定 义 为  t (i, j )
 t ( i , j )  P ( s t  i , s t 1  j | X ,  )
 t ( i ) a ij b j ( O t  1 )  t  1 ( j )

N
N

i 1
t
( i ) a ij b j ( x t  1 )  t  1 ( j )
j 1
N
 t (i ) 

t
(i, j )
t 时 刻 处 于 状 态 S i的 概 率
j 1
T 1

t
( i )  整 个 过 程 中 从 状 态 S i 转 出 的 次 数 ( number of t i me) 的 预 期
t 1
T 1

t 1
t
( i , j )  从 S i 跳 转 到 S j次 数 的 预 期
Baum-Welch算法(续2)
• 参数估计:
R eestim ate
aˆ ij 

:
expected count of transitions from i to j
expected count of stays at i

(i , j )
t
t

t
t
(i , j )
j
expected
bˆ j ( k ) 


num ber
of
expected
tim es
in
num ber
state
of
j
tim es
and
in
 t ( j)
t ,O t  k

t
( j)
t

i
 当 t =1时 处 于 S i的 概 率   1 ( i )
observing
state
j
sym bol
k

similar documents