隐马尔可夫模型无指导学习的一些相关推导

t∈T yk =s
3
可以看到，这个求解过程符合动态规划算法的一些性质：如最优子结构、子问题结果重 用。初始条件为： π (0, s = START) = 1 π (0, s ̸= START) = 0 (11)
如上公式中，只是求出最大概率，可以通过回溯（backward-trace）指针，获得对应 最大概率的词性序列。
Backward 算法和 Forward 算法基本一致，区别在于 Backward 算法从右向左计算。 我们令 β (k, s) 为第 k 个词 wk 的词性为 s（并以此为条件）的所有可能的后续词性路径 4
（前面的词不考虑）的概率之和，即： ∑ p(wk+1 ...wn , yk+1 ...yn |yk ) β (k, s) =
p(yi = s|S j ; µk )
其中，p(yi−1 = s|S j ; µk ) 和 p(yi−1 = s, yi = t|S j ; µk ) 表示在当前参数 µk 上计算得到的 边缘概率，其定义见公式 (20)。 求解过程和 ngram langauge model 和 supervised HMM 中的极大似然估计的推导 过程类似，大家可以尝试推导一遍。
比较 Forward 算法和 Viterbi 算法，可以发现这两个算法唯一的不同之处在于 Operator，前者是 sum-product，后者是 max-product，这个概念我是从 Noah Smith 前几年 写的一本 Structure Learning 的书中看到的。
6.3 Backward
y1 ...yk−1 ∈T yk =s
k −1
α(k, s) × β (k, s) =
p(w0 ...wk , y0 ...yk ) ×
∑
yk+1 ...yn ∈T yk =s
n−k
p(wk+1 ...wn , yk+1 ...yn |yk )
=
∑
p(w0 ...wn , y0 ...yn )
k−1
max
p(wk |yk ) × p(yk |yk−1 ) × p(w0 ...wk−1 , y0 ...yk−1 )
= max p(wk |yk ) × p(yk |t) ×
y1 ...yk−2 ∈T k−2 yk−1 =t
max
p(w0 ...wk−1 , y0 ...yk−1 )
= max p(wk |yk ) × p(yk |t) × π (k − 1, t)
2 隐马尔可夫模型（hidden markov model, HMM）
根据贝叶斯公式，我们可以如下定义一个句子 S = w0 ...wn 和对应词性序列 Y = y0 ...yn 的联合概率（解释句子的生成过程） ： p(S, Y ) = p(w0 ...wn , y0 ...yn ) = p(y0 ...yn ) × p(w0 ...wn |y0 ...yn ) n ∏ = [p(yi |y0 ...yi−1 ) × p(w1 ...wn |y1 ...yn )] =
i=1 n ∏ i=1
(2)
[p(yi |yi−1 ) × p(wi |yi )]
无指导学习的目的是，利用数据集 D，估计语言模型所使用的所有参数： qs,t ≡ p(t|s) : ∀s ∈ T , ∀t ∈ T et,w ≡ p(w|t) : ∀t ∈ T , ∀w ∈ V (3)
为了便于后续推导和理解，我们有时候会使用变量的形式，即 qs,t 和 et,w ，分别表示转 移概率和发射概率。可以看到，模型需要估计 |T |2 + |T ||V | 个参数。 1
5 Q 函数及最大化推导
Expectation: Q(µ, µ ) =
k N ∑ j =1
EY |S j ;µk log p(S j , Y ; µ) (5) p(Y |S j ; µk ) log p(S j , Y ; µ)
=
N ∑ ∑ j =1 Y ∈T
nj
µk 为上一次迭代后确定的参数，因此 Q(µ, µk ) 中唯一的变量是 µ，也就是说 Maximization: µk+1 = arg max Q(µ, µk )
y1 ...yk−1 ∈T k−1 yk =s
=
∑
y1 ...yk−1 ∈T yk =s
k −1
k ∏ i=1
p(yi |yi−1 ) × p(wi |yi )
= ∑
∑
p(wk |yk ) × p(yk |yk−1 ) × p(w0 ...wk−1 , y0 ...yk−1 )
k −2
y1 ...yk−2 ∈T yk−1 ∈T yk =s
y1 ...yk−1 ∈T k−1 yk =s
max
p(w0 ...wk , y0 ...yk )
k ∏
= =
y1 ...yk−1 ∈T k−1 i=1 yk =s y1 ...yk−2 ∈T k−2 yk−1 ∈T yk =s t∈T yk =s
max
p(yi |yi−1 ) × p(wi |yi ) (10)
6.2 Forward
Forward 算法的目的是，给定句子 S ，求解其所有可能的词性序列的概率之和，或 者称作句子 S 的边缘概率： ∑ p(S, Y ) p( S ) =
Y ∈T n
=
∑
(12) p(w0 ...wn , y0 ...yn )
Y ∈T n
前向概率由左向右进行计算。我们令 α(k, s) 为第 k 个词 wk 的词性为 s 的所有部分 路径（后面的词不考虑）的概率之和，即： ∑ p(w0 ...wk , y0 ...yk ) α(k, s) =
6.1 Viterbi
Viterbi 算法的目的是，给定句子 S ，求解其最优的词性序列 Y ∗ ： Y ∗ = arg max p(S, Y ) n
Y ∈T Y ∈T
= arg max p(w0 ...wn , y0 π (k, s) 为第 k 个词 wk 的词性为 s 的所有部分路径（后面的词不考虑）的最 大概率，即： π (k, s) =
为了简化数学表达，我们在每个句子开始和结束位置插入了伪词和伪词性，即：
j w0 = START j y0 = START j = STOP wn j j yn = STOP j
(1)
并且在学习和解码过程中，这些位置的词性都是固定的（不合法的发射概率和转移概率 都为 0） 。
j T ：表示词性集合，即隐状态的所有可能取值，yi ∈T。 j V ：表示词表 (vocabulary)，即数据 D 所有词语的集合，wi ∈ V。
y1 ...yk−1 ∈T yk =s yk+1 ...yn ∈T n−k
≡ p(w0 ...wn , yk = s) (17) 其中，p(w0 ...wn , yk = s) 表示边缘概率，即除了 yk = s 外，其他位置的词性都被边缘化 （marginalized） 。
α(n, STOP) = β (0, START) ∑ = α(k, s) × β (k, s) #∀0 ≤ k ≤ n
j =1 Y ∈T nj i=1
j i−1 ,yi
eyj ,wj
i i
4 EM 算法流程
定义 Q 函数（其实是数据的某种 likelihood 表示在不同参数 µ 上的期望） 1、随机初始化变量（如何用 rand 函数初始化，以保证概率分布？ ） 2、求 Q 函数（其实由于 µ 未知，因此无法求解，只是表示出来） 3、最大化 Q 函数，得到新的 µ（其实是求解可以使 Q 函数最大的 µ） 4、基于新的 µ，计算数据的真实的 likelihood，是否满足停止条件？如果是，则保 存最新的 µ，否则进入步骤 2
t∈T yk =s
同样， 这个求解过程符合动态规划算法的一些性质： 如最优子结构、 子问题结果重用。 初 始条件为： β (0, s = STOP) = 1 β (0, s ̸= STOP) = 0 (16)
6.4 Forward-Backward 相互合作
利用 Forward-Backward 的结果，我们可以得到很多有用的信息： ∑
隐马尔可夫模型无指导学习的一些相关推导
张月，李正华 2015 年 11 月 10 日
1 符号定义
一个句子 S = w0 ...wn 和对应词性序列 Y = y0 ...yn D = {S j }N j =1 ：表示一个数据集，包含 N 个句子，注意在无指导的学习中，句子对 应的正确词性序列未知。
j j j S j = w0 w1 ...wi ...xj nj ：表示第 j 个句子，由 nj + 1 个词语组成。
3 似然函数
L(D) = p(D) =
N ∏ j =1
p(S j )
=
N ∏ ∑ j =1 Y ∈T nj
p(S j , Y ) (4)
nj j j j j p(yi |yi−1 )p(wi |yi )
=
N ∏ ∑ ∏ j =1 Y ∈T nj i=1 nj N
=
∏ ∑ ∏
qy j
∑ 注意，p(S j ) = Y ∈T nj p(S j , Y ) 是通过对联合概率求边缘概率的过程，Y 遍历所有合法 的词性序列，T nj 表示 nj 个 T 做笛卡尔乘积。 我们无法通过像有指导学习中对公式 (4) 求偏导（即使引入变量之间的约束，并使 用拉格朗日乘子） ，而解决问题。原因是，隐状态和待估计参数之间互相依赖（大家可以 尝试一下） 。
yk+1 ...yn ∈T n−k yk =s
=
∑
yk+1 ...yn ∈T yk =s
n−k
n ∏ i=k+1
p(yi |yi−1 ) × p(wi |yi )