关键词：
隐马尔科夫模型HMM（三）鲍姆-韦尔奇算法求解HMM参数
在本篇我们会讨论HMM模型参数求解的问题，这个问题在HMM三个问题里算是最复杂的。在研究这个问题之前，建议先阅读这个系列的前两篇以熟悉HMM模型和HMM的前向后向算法，以及EM算法原理总结，这些在本篇里会用到。在李航的《统计学习方法》中，这个算法的讲解只考虑了单个观测序列的求解，因此无法用于实际多样本观测序列的模型求解，本文关注于如何使用多个观测序列来求解HMM模型参数。
1. HMM模型参数求解概述
HMM模型参数求解根据已知的条件可以分为两种情况。
第一种情况较为简单，就是我们已知$D$个长度为$T$的观测序列和对应的隐藏状态序列，即$\{(O_1, I_1), (O_2, I_2), ...(O_D, I_D)\}$是已知的，此时我们可以很容易的用最大似然来求解模型参数。
假设样本从隐藏状态$q_i$转移到$q_j$的频率计数是$A_{ij}$,那么状态转移矩阵求得为：$$A = \Big[a_{ij}\Big], \;其中a_{ij} = \frac{A_{ij}}{\sum\limits_{s=1}^{N}A_{is}}$$
假设样本隐藏状态为$q_j$且观测状态为$v_k$的频率计数是$B_{jk}$,那么观测状态概率矩阵为：$$B= \Big[b_{j}(k)\Big], \;其中b_{j}(k) = \frac{B_{jk}}{\sum\limits_{s=1}^{M}B_{js}}$$
假设所有样本中初始隐藏状态为$q_i$的频率计数为$C(i)$,那么初始概率分布为：$$\Pi = \pi(i) = \frac{C(i)}{\sum\limits_{s=1}^{N}C(s)}$$
可见第一种情况下求解模型还是很简单的。但是在很多时候，我们无法得到HMM样本观察序列对应的隐藏序列，只有$D$个长度为$T$的观测序列，即$\{(O_1), (O_2), ...(O_D)\}$是已知的，此时我们能不能求出合适的HMM模型参数呢？这就是我们的第二种情况，也是我们本文要讨论的重点。它的解法最常用的是鲍姆-韦尔奇算法，其实就是基于EM算法的求解，只不过鲍姆-韦尔奇算法出现的时代，EM算法还没有被抽象出来，所以我们本文还是说鲍姆-韦尔奇算法。
2. 鲍姆-韦尔奇算法原理
鲍姆-韦尔奇算法原理既然使用的就是EM算法的原理，那么我们需要在E步求出联合分布$P(O,I|\lambda)$基于条件概率$P(I|O,\overline{\lambda})$的期望，其中$\overline{\lambda}$为当前的模型参数，然后再M步最大化这个期望，得到更新的模型参数$\lambda$。接着不停的进行EM迭代，直到模型参数的值收敛为止。
首先来看看E步，当前模型参数为$\overline{\lambda}$, 联合分布$P(O,I|\lambda)$基于条件概率$P(I|O,\overline{\lambda})$的期望表达式为：$$L(\lambda, \overline{\lambda}) = \sum\limits_{I}P(I|O,\overline{\lambda})logP(O,I|\lambda)$$
在M步，我们极大化上式，然后得到更新后的模型参数如下： $$\overline{\lambda} = arg\;\max_{\lambda}\sum\limits_{I}P(I|O,\overline{\lambda})logP(O,I|\lambda)$$
通过不断的E步和M步的迭代，直到$\overline{\lambda}$收敛。下面我们来看看鲍姆-韦尔奇算法的推导过程。
3. 鲍姆-韦尔奇算法的推导
我们的训练数据为$\{(O_1, I_1), (O_2, I_2), ...(O_D, I_D)\}$，其中任意一个观测序列$O_d = \{o_1^{(d)}, o_2^{(d)}, ... o_T^{(d)}\}$,其对应的未知的隐藏状态序列表示为：$I_d = \{i_1^{(d)}, i_2^{(d)}, ... i_T^{(d)}\}$
首先看鲍姆-韦尔奇算法的E步，我们需要先计算联合分布$P(O,I|\lambda)$的表达式如下：$$P(O,I|\lambda) = \prod_{d=1}^D\pi_{i_1^{(d)}}b_{i_1^{(d)}}(o_1^{(d)})a_{i_1^{(d)}i_2^{(d)}}b_{i_2^{(d)}}(o_2^{(d)})...a_{i_{T-1}^{(d)}i_T^{(d)}}b_{i_T^{(d)}}(o_T^{(d)})$$
我们的E步得到的期望表达式为：$$L(\lambda, \overline{\lambda}) = \sum\limits_{I}P(I|O,\overline{\lambda})logP(O,I|\lambda)$$
在M步我们要极大化上式。由于$P(I|O,\overline{\lambda}) = P(I,O|\overline{\lambda})/P(O|\overline{\lambda})$,而$P(O|\overline{\lambda})$是常数，因此我们要极大化的式子等价于：$$\overline{\lambda} = arg\;\max_{\lambda}\sum\limits_{I}P(O,I|\overline{\lambda})logP(O,I|\lambda)$$
我们将上面$P(O,I|\lambda)$的表达式带入我们的极大化式子，得到的表达式如下：$$\overline{\lambda} = arg\;\max_{\lambda}\sum\limits_{d=1}^D\sum\limits_{I}P(O,I|\overline{\lambda})(log\pi_{i_1} + \sum\limits_{t=1}^{T-1}log\;a_{i_t,i_{t+1}} + \sum\limits_{t=1}^Tlog b_{i_t}(o_t))$$
我们的隐藏模型参数$\lambda =(A,B,\Pi)$,因此下面我们只需要对上式分别对$A,B,\Pi$求导即可得到我们更新的模型参数$\overline{\lambda}$
首先我们看看对模型参数$\Pi$的求导。由于$\Pi$只在上式中括号里的第一部分出现，因此我们对于$\Pi$的极大化式子为：$$\overline{\pi_i} = arg\;\max_{\pi_{i_1}} \sum\limits_{d=1}^D\sum\limits_{I}P(O,I|\overline{\lambda})log\pi_{i_1} = arg\;\max_{\pi_{i}} \sum\limits_{d=1}^D\sum\limits_{i=1}^NP(O,i_1^{(d)} =i|\overline{\lambda})log\pi_{i}$$
由于$\pi_i$还满足$\sum\limits_{i=1}^N\pi_i =1$，因此根据拉格朗日子乘法，我们得到$\pi_i$要极大化的拉格朗日函数为：$$arg\;\max_{\pi_{i}}\sum\limits_{d=1}^D\sum\limits_{i=1}^NP(O,i_1^{(d)} =i|\overline{\lambda})log\pi_{i} + \gamma(\sum\limits_{i=1}^N\pi_i -1)$$
其中，$\gamma$为拉格朗日系数。上式对$\pi_i$求偏导数并令结果为0， 我们得到：$$\sum\limits_{d=1}^DP(O,i_1^{(d)} =i|\overline{\lambda}) + \gamma\pi_i = 0$$
令$i$分别等于从1到$N$，从上式可以得到$N$个式子，对这$N$个式子求和可得：$$\sum\limits_{d=1}^DP(O|\overline{\lambda}) + \gamma = 0 $$
从上两式消去$\gamma$,得到$\pi_i$的表达式为：$$\pi_i =\frac{\sum\limits_{d=1}^DP(O,i_1^{(d)} =i|\overline{\lambda})}{\sum\limits_{d=1}^DP(O|\overline{\lambda})} = \frac{\sum\limits_{d=1}^DP(O,i_1^{(d)} =i|\overline{\lambda})}{DP(O|\overline{\lambda})} = \frac{\sum\limits_{d=1}^DP(i_1^{(d)} =i|O, \overline{\lambda})}{D} = \frac{\sum\limits_{d=1}^DP(i_1^{(d)} =i|O^{(d)}, \overline{\lambda})}{D}$$
利用我们在隐马尔科夫模型HMM（二）前向后向算法评估观察序列概率里第二节中前向概率的定义可得：$$P(i_1^{(d)} =i|O^{(d)}, \overline{\lambda}) = \gamma_1^{(d)}(i)$$
因此最终我们在M步$\pi_i$的迭代公式为：$$\pi_i = \frac{\sum\limits_{d=1}^D\gamma_1^{(d)}(i)}{D}$$
现在我们来看看$A$的迭代公式求法。方法和$\Pi$的类似。由于$A$只在最大化函数式中括号里的第二部分出现，而这部分式子可以整理为：$$\sum\limits_{d=1}^D\sum\limits_{I}\sum\limits_{t=1}^{T-1}P(O,I|\overline{\lambda})log\;a_{i_t,i_{t+1}} = \sum\limits_{d=1}^D\sum\limits_{i=1}^N\sum\limits_{j=1}^N\sum\limits_{t=1}^{T-1}P(O,i_t^{(d)} = i, i_{t+1}^{(d)} = j|\overline{\lambda})log\;a_{ij}$$
由于$a_{ij}$还满足$\sum\limits_{j=1}^Na_{ij} =1$。和求解$\pi_i$类似，我们可以用拉格朗日子乘法并对$a_{ij}$求导，并令结果为0，可以得到$a_{ij}$的迭代表达式为：$$a_{ij} = \frac{\sum\limits_{d=1}^D\sum\limits_{t=1}^{T-1}P(O^{(d)}, i_t^{(d)} = i, i_{t+1}^{(d)} = j|\overline{\lambda})}{\sum\limits_{d=1}^D\sum\limits_{t=1}^{T-1}P(O^{(d)}, i_t^{(d)} = i|\overline{\lambda})}$$
利用隐马尔科夫模型HMM（二）前向后向算法评估观察序列概率里第二节中前向概率的定义和第五节$\xi_t(i,j)$的定义可得们在M步$a_{ij}$的迭代公式为：$$a_{ij} = \frac{\sum\limits_{d=1}^D\sum\limits_{t=1}^{T-1}\xi_t^{(d)}(i,j)}{\sum\limits_{d=1}^D\sum\limits_{t=1}^{T-1}\gamma_t^{(d)}(i)}$$
现在我们来看看$B$的迭代公式求法。方法和$\Pi$的类似。由于$B$只在最大化函数式中括号里的第三部分出现，而这部分式子可以整理为：$$\sum\limits_{d=1}^D\sum\limits_{I}\sum\limits_{t=1}^{T}P(O,I|\overline{\lambda})log\;b_{i_t}(o_t) = \sum\limits_{d=1}^D\sum\limits_{j=1}^N\sum\limits_{t=1}^{T}P(O,i_t^{(d)} = j|\overline{\lambda})log\;b_{j}(o_t)$$
由于$b_{j}(o_t)$还满足$\sum\limits_{k=1}^Mb_{j}(o_t =v_k) =1$。和求解$\pi_i$类似，我们可以用拉格朗日子乘法并对$b_{j}(k)$求导，并令结果为0，得到$b_{j}(k)$的迭代表达式为：$$b_{j}(k) = \frac{\sum\limits_{d=1}^D\sum\limits_{t=1}^{T}P(O,i_t^{(d)} = j|\overline{\lambda})I(o_t^{(d)}=v_k)}{\sum\limits_{d=1}^D\sum\limits_{t=1}^{T}P(O,i_t^{(d)} = j|\overline{\lambda})}$$
其中$I(o_t^{(d)}=v_k)$当且仅当$o_t^{(d)}=v_k$时为1，否则为0. 利用隐马尔科夫模型HMM（二）前向后向算法评估观察序列概率里第二节中前向概率的定义可得$b_{j}(o_t)$的最终表达式为：$$b_{j}(k) = \frac{\sum\limits_{d=1}^D\sum\limits_{t=1, o_t^{(d)}=v_k}^{T}\gamma_t^{(d)}(j)}{\sum\limits_{d=1}^D\sum\limits_{t=1}^{T}\gamma_t^{(d)}(j)}$$
有了$\pi_i, a_{ij},b_{j}(k)$的迭代公式，我们就可以迭代求解HMM模型参数了。
4. 鲍姆-韦尔奇算法流程总结
这里我们概括总结下鲍姆-韦尔奇算法的流程。
输入： $D$个观测序列样本$\{(O_1), (O_2), ...(O_D)\}$
输出：HMM模型参数
1)随机初始化所有的$\pi_i, a_{ij},b_{j}(k)$
2) 对于每个样本$d = 1,2,...D$，用前向后向算法计算$\gamma_t^{(d)}(i)，\xi_t^{(d)}(i,j), t =1,2...T$
3) 更新模型参数：
$$\pi_i = \frac{\sum\limits_{d=1}^D\gamma_1^{(d)}(i)}{D}$$
$$a_{ij} = \frac{\sum\limits_{d=1}^D\sum\limits_{t=1}^{T-1}\xi_t^{(d)}(i,j)}{\sum\limits_{d=1}^D\sum\limits_{t=1}^{T-1}\gamma_t^{(d)}(i)}$$
$$b_{j}(k) = \frac{\sum\limits_{d=1}^D\sum\limits_{t=1, o_t^{(d)}=v_k}^{T}\gamma_t^{(d)}(j)}{\sum\limits_{d=1}^D\sum\limits_{t=1}^{T}\gamma_t^{(d)}(j)}$$
4) 如果$\pi_i, a_{ij},b_{j}(k)$的值已经收敛，则算法结束，否则回到第2）步继续迭代。
以上就是鲍姆-韦尔奇算法的整个过程。
（欢迎转载，转载请注明出处。欢迎沟通交流： liujianping-ok@163.com）
隐马尔科夫模型hmmhmm模型
隐马尔科夫模型HMM（一）HMM模型基础 隐马尔科夫模型HMM（二）前向后向算法评估观察序列概率（TODO） 隐马尔科夫模型HMM（三）鲍姆-韦尔奇算法求解HMM参数（TODO） 隐马尔科夫模型HMM（四）维特... 查看详情
隐马尔科夫模型hmm前向后向算法评估观察序列概率
隐马尔科夫模型HMM（一）HMM模型 隐马尔科夫模型HMM（二）前向后向算法评估观察序列概率 隐马尔科夫模型HMM（三）鲍姆-韦尔奇算法求解HMM参数（TODO） 隐马尔科夫模型HMM（四）维特比算法解码... 查看详情
隐马尔可夫模型(hiddenmarkovmodel,hmm)
...处理标注问题的统计机器学模型隐马模型发明者：鲍姆-韦尔奇（美）(Baum-Welch算法)隐马模型的三个基本问题：（1）概率计算问题：前向-后向算法—>动态规划给定模型λ=（A,B,π）和观测序列O=o1,02,…or,计算模型λ下观测序列O出... 查看详情
简单易懂的隐马尔可夫模型（hmm）讲解(代码片段)
学习目标：了解什么是马尔科夫链知道什么是HMM模型知道前向后向算法评估观察序列概率知道维特比算法解码隐藏状态序列了解鲍姆-韦尔奇算法知道HMM模型API的使用一、马尔科夫链在机器学习算法中，马尔可夫链(Markovcha... 查看详情
ml-13-4隐马尔科夫模型ｈｍｍ--预测问题viterbi（维特比）算法
【ML-13-1】隐马尔科夫模型HMM【ML-13-2】隐马尔科夫模型ＨＭＭ--前向后向算法【ML-13-3】隐马尔科夫模型ＨＭＭ--Baum-Welch（鲍姆-韦尔奇）【ML-13-4】隐马尔科夫模型ＨＭＭ--预测问题Viterbi（维特比）算法 目录基础--HMM常用概率的... 查看详情
隐马尔科夫模型(前向后向算法鲍姆-韦尔奇算法维特比算法)
...是使用无向图表示变量间的相关关系，称为无向图模型或马尔科夫网。 隐马尔科夫模型（简称HMM）是结构最简单的动态贝叶斯网，是一种著 查看详情
用隐马尔科夫模型来预测股价走势(代码片段)
一、初识HMM隐马尔科夫模型（HiddenMarkovModel，简称HMM）是用来描述隐含未知参数的统计模型，HMM已经被成功于语音识别、文本分类、生物信息科学、故障诊断和寿命预测等领域。HMM可以由三个要素组成： =&#... 查看详情
hmm模型和viterbi算法
...学家鲍姆提出的，隐含马尔可夫模型的训练方法（鲍姆-韦尔奇算法）也是以他名字命名的。隐含马尔可夫模型一直被认为是解决大多数自然语言处理问题最为快速、有效的方法。2、马尔可夫假设 随机过程中各个状态St的概... 查看详情
ml-13-2隐马尔科夫模型ｈｍｍ--前向后向算法
【ML-13-1】隐马尔科夫模型HMM【ML-13-2】隐马尔科夫模型ＨＭＭ--前向后向算法【ML-13-3】隐马尔科夫模型ＨＭＭ--Baum-Welch（鲍姆-韦尔奇）【ML-13-4】隐马尔科夫模型ＨＭＭ--预测问题Viterbi（维特比）算法目录引言直接计算前向... 查看详情
ml-13-1隐马尔科夫模型hmm
【ML-13-1】隐马尔科夫模型HMM【ML-13-2】隐马尔科夫模型ＨＭＭ--前向后向算法【ML-13-3】隐马尔科夫模型ＨＭＭ--Baum-Welch（鲍姆-韦尔奇）【ML-13-4】隐马尔科夫模型ＨＭＭ--预测问题Viterbi（维特比）算法目录基础知识-马尔可夫链HMM... 查看详情
机器学习hmm模型算法实例(代码片段)
...特比算法流程总结2.4HMM维特比算法求解实例2.5小结3鲍姆-韦尔奇算法简介3.1鲍姆-韦尔奇算法简介3.2鲍姆-韦尔奇算法原理4HMM模型API介绍4.1API的安装：4.2hmmlearn介绍4.3MultinomialHMM实例1前向算法求HMM观测序列的概率前向后向算法是... 查看详情
hmm啥意思?
...思为：嗯，鱼很好。扩展资料hmm的其他含义：隐马尔可夫模型（HMM）统计模型，它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析，例如... 查看详情
概率图：hmm（隐马尔可夫模型）
一个模型，两个假设，三个问题。思路：HMM=>在机器学习大框架中的位置=>模型参数（示意图及定义）=>模型假设=>模型的应用：三个问题（及其数值求解算法）=>各个问题的具体应用场景（看文献） &n... 查看详情
hmm是啥意思？
意思？隐马尔可夫模型(HMM)是指隐马尔可夫模型，是一种用于描述参数未知的马尔可夫过程的统计模型。困难在于从可观察的参数中确定过程的隐藏参数。这些参数然后被用于进一步的分析，例如模式识别。隐马尔可夫模型最早... 查看详情
标注-隐马尔可夫模型hmm的探究
...算法3.1监督学习3.2非监督学习——Baum-Welch算法3.3Baum-Welch模型参数估计公式4预测算法4.1近似算法4.2维特比算法Viterbialgorithm隐马尔可夫模型（hidden 查看详情
隐马尔科夫模型hmm详解
目录隐马尔科夫模型基本概念隐马尔科夫模型的三个基本问题概率计算预测算法-Viterbi算法HMM学习算法参考下篇文章代码地址：https://gitee.com/liangcd/speech_learning/tree/master/HMM隐马尔科夫模型基本概念先看一个小问题：问题&#x... 查看详情
机器学习之隐马尔科夫模型hmm
...，HMM）是统计模型，它用来描述一个含有隐含未知参数的马尔科夫过程。其难点是从可观察的参数中确定该过程的隐含参数，然后利用这些参数来作进一步的分析。在早些年HMM模型被非常广泛的应用，而现在随着机器学习的发展... 查看详情
理解隐马尔科夫（hmm）模型
前言在李航的《统计学方法》第十章有对隐马尔科夫模型（HiddenMarkovModel，HMM）比较详细的介绍和推导公式，我参考公式结合中文分词应用实现了隐马模型观测序列的生成、前向算法、维特比算法。本文在此针对HMM模型在中文分... 查看详情