NLPLAB
19
分段K-均值算法
1、随机选个N个观察符号(每个符号用D维向量表示)，将给定的T 个D维向量分配到上面N个观察符号中去(聚类)，聚类的原则是将
T个中的每个向量分配到与自己欧氏距离最短的N个向量中的那个
向量中去。至此我们得到N个簇，每个簇代表一个状态。这个一开 始的聚类过程并不决定最后的HMM，而只是决定模型的训练次数。 2、计算起始概率和转移概率：
t 1 T
所以P(O| )=
P(O, Q | ) P(O | Q, ) P(Q | )
I I i1..iT
i1 i1
b O1 ait 1itbitOt
t 2
T
NLPLAB
7
直接计算法
NLPLAB
8
前向算法
首先定义前向变量 t(i)=P(O1O2...Ot，qt=i| )， 表示在模型中t时刻状态为i且输出为O1O2...Ot的概率。 前向算法过程： 1.初始化 1 (i)= ibiO1
j
这种递归关系使我们能够运用动态规划搜索技术。
NLPLAB
14
维特比算法
NLPLAB
15
维特比算法
1.初始化： 1(i) ibi (O1)， 1 i N 1(i)=0 2.归纳计算： t (i )= max[ t-1(i) aij ] bj (Ot ), 2 t T ;1 j N
a =1
ij j=1
n
= 1， 2，... N

i 1
n
i
1
NLPLAB
3
隐马尔科夫模型中两个重要的假设：
1. 一个特定状态的概率仅仅依赖于前一个状态：
P(qi | q1...qi 1) P(qi | qi 1)
2. 观察值
oi 的概率仅仅依赖于产生这个观察值的状态 q i：
P(oi| q1...qi...qT,o1...oi...oT) P(oi | qi)
NLPLAB
4
隐马尔科夫模型中的三个问题：
1. 估计问题
给定一个观察序列O=O1O2...OT和模型λ=(A,B,π)，如何计 算给定模型λ情况下，观察序列O的概率P(O|λ)。
2. 序列问题
给定一个观察序列O=O1O2...OT和模型λ=(A,B,π)，如何快速有效 地选择在一定意义下“最优”的状态序列Q=q1q2...qT，使得该 状态序列“最好地解释”观察序列？
k likelihood criterion )。函数P(O，Q* K | )被称为状态最优似然函数(state
optimized likelihood function )。在这种算法中，要求有多个观察符号 序列供训练。假设算法提供一个很长的观察序列，把它分为段，每段有 T个观察符号。每个观察符号都看成一个D(D>1)维向量。算法过程如下：
NLPLAB
18
分段K-均值算法
k * k +1 分段K 均值算法的目标就是找到 k 1使得P(O，Q* ) K | ) P(O，Q K+1| k 其中Q* K 是在已知 和O的情况下，利用Viterbi算法求出的最优状态序列。
该最优准则被称为最大状态最优似然准则(maximum state optimized
i =
O1在i中出现的次数 ， 1 i N O1出现的总数(即 ) 对所有的t，Ot在i中出现且Ot+1在j中出现的次数 a ij= ， 1 i N， 1 j N 对所有的t，O在i中出现的次数

NLPLAB
20
分段K-均值算法
3、对每个状态计算均值向量和协方差矩阵 对每个1 i N，计算 1 i= Ot Ni Oti 1 T Vi (Ot i) (Ot i) Ni Oti 4、对每个训练向量和每个状态，计算符号的概率分布(假设服 从高斯分布)：
N
1 i N
2. 归纳
t+1(j)=( t (i )aij )bjOt+1
i 1 N
3.总计算 P(O| )= T (i) 推导过程 P(O| )= P(O1，O 2...OT，qT =i| )
i i 1
NLPLAB
9
前向算法
NLPLAB
10
后向算法
NLPLAB
2
首先给出符号表示： Q=q1q2...qN 状态序列
A=a11a12...an1...ann 转移概率矩阵A，aij表示从状态i转移到状态j的概率 O=o1o2...oT B=bi(ot) 观测序列，o1表示在状态q1观测到o1 符号发射概率矩阵B，表示在状态i观测到ot的概率 初始状态， i表示初始状态为i的概率
定义：维特比变量 t (i)是在时间t时，HMM沿着某一条路径到达 状态si，并输出观察序列O1O2...Ot的最大概率： t (i)= max P(q1,q2,...,qt=si，O1O2...Ot| )
q1,q2,...,qt-1
与前向变量类似， t (i )有如下递归关系： t+1(i)= max[ t (i) aji] bi(Ot 1)
同样的，先定义后项变量 t(i)=P(Ot+1...OT|qt=i, )， 表示在给定模型，并且t时刻状态为i的情况下， 输出序列Ot+1...OT的概率。 后项算法过程： 1.初始化 T(i)=1
N
1i N 1 t T 1, 1 i N
2.归纳
t(i)= aijbjOt+1 t+1(j)
3. 训练问题或参数估计问题
给定一个观察序列O=O1O2...OT，如何根据最大似然估计来求模型 的参数值？即如何调节模型λ=(A,B,π)的参数，使得P(O|λ)最大？
NLPLAB
5
1. 估计问题
问题描述：
给定一个观察序列O=O1O2...OT和模型λ=(A,B,π)， 如何计算给定模型λ情况下，观察序列O的概率P(O|λ)。
1 1 T b iOt = exp[ ( O t i ) Vi (Ot i ) ] ， 1 i N 2 (2 ) D 2 | Vi |1 2
1
NLPLAB
21
分段K-均值算法
5、利用第2到第4求得的模型参数和Viterbi算法可以求出最优状态序列Q*， 如果一个向量的原来分配与估计出的最优状态不同的话，这个向量就要 重新分配。例如，假设第五次训练序列的第二个符号(O2)分配给状态3 (即第三簇)，但是计算得到的最优状态序列Q的第二个状态(Q2)为状态4 而非状态3。这时，我们就要将O2重新分配到状态4(第四簇)中去。 一般的，如果对第k次训练序列求得的Q* t为状态i时，我们将Ot分配到 状态i，这样一直到所有的训练序列经过训练(k从1到 )。 6、如果在第5步中，任一向量被重新分配一个新的状态，那么就使用这个 新的分配重复2到6的过程，否则算法结束。
NLPLAB
22
用以下四种方法解决这个问题： 直接计算法 前向算法 后向算法
前向后项结合算法
NLPLAB
6
直接计算法
求P(O| )，有P(O| )= P(O,Q| )
I
对任一状态序列Q=q1,q2...qT有P(O,Q| )=P(O|Q, )P(Q| ) 其中 P(Q| )= i1ai1i2...aiT-1iT P(O | Q, ) P(Ot | qt , ) bi1O1bi 2O 2...biTOT
i 1 N
NLPLAB
12
2. 序列问题
问题描述 给定一个观察序列O=O1O2...OT和模型λ=(A,B,π)，如何快速有效
地选择在一定意义下“最优”的状态序列Q=q1q2...qT，使得该 状态序列“最好地解释”观察序列？
解决问题的算法：
维特比算法(Viterbi)
NLPLAB
13
维特比算法
j 1 N i
3.总计算 P(O| )= ibiO1 1(i ) 其时间复杂度类似于前向算法O( N T)
NLPLAB
2Байду номын сангаас
11
前向后向结合算法
P (O, it i | ) P (O1O 2...OT , it i | )
P(A,B)=P(A)P(B|A)
P (O1...Ot , it i, Ot 1...OT | ) P (O1...Ot , it i | ) P(Ot 1...OT | O1...Ot 1, it i, ) P (O1...Ot , it i | ) P(Ot 1...OT | it i, ) t (i ) t (i) P (O | ) t (i ) t (i),1 t T
4.路径(状态序列)回溯: qt= t+1(qt+1)，t=T-1，T-2，...,1
NLPLAB
16
维特比算法
NLPLAB
17
3. 训练问题或参数估计问题
问题描述：
给定一个观察序列O=O1O2...OT，如何根据最大似然估计来求模型 的参数值？即如何调节模型λ=(A,B,π)的参数，使得P(O|λ)最大？
隐马尔科夫模型 Hidden Markov Model
NLPLAB
1
何为“隐”?
1. 如从四个盒子中各取一个球，开始从四个盒子随机选取一个盒子，从这 个盒子中随机抽出1个球，记录其颜色后，放回；然后从当前盒子随机 转移到下一个盒子，再取一个球；如此重复，直到取出四个球。这样可 以得到一个球的颜色的观测序列： 如：O={红，白，红，白}，在这个过程中观察者只能观测到球的颜色 序列，观测不到球是从哪个盒子中取出的，即观测不到盒子的序列。 2. 如在词性标注这样的应用中，对于给定的要标注单词词性的一个句子， 我们看不到单词的词性，只能观察到每个单词，必须从单词序列去推断 正确的标记。我们说词性标注序列是隐藏的。