hmmem算法
A. 大数据经典算法解析（5）一EM算法
姓名：崔升 学号：14020120005
【嵌牛导读】：
EM作为一种经典的处理大数据的算法，是我们在学习互联网大数据时不得不去了解的一种常用算法
【嵌牛鼻子】：经典大数据算法之EM简单介绍
【嵌牛提问】：EM是一种怎么的算法，其如何去观测其中隐变量的？
【嵌牛正文】：
1. 极大似然
极大似然（Maximum Likelihood）估计为用于已知模型的参数估计的统计学方法。比如，我们想了解抛硬币是正面（head）的概率分布θθ；那么可以通过最大似然估计方法求得。假如我们抛硬币1010次，其中88次正面、22次反面；极大似然估计参数θθ值：
θ^=argmaxθl(θ)=argmaxθθ8(1−θ)2θ^=argmaxθl(θ)=argmaxθθ8(1−θ)2
其中，l(θ)l(θ)为观测变量序列的似然函数（likelihood function of the observation sequence）。对l(θ)l(θ)求偏导
∂l(θ)∂θ=θ7(1−θ)(8−10θ)⇒θ^=0.8∂l(θ)∂θ=θ7(1−θ)(8−10θ)⇒θ^=0.8
因为似然函数l(θ)l(θ)不是凹函数（concave），求解极大值困难。一般地，使用与之具有相同单调性的log-likelihood，如图所示
凹函数（concave）与凸函数（convex）的定义如图所示：
从图中可以看出，凹函数“容易”求解极大值，凸函数“容易”求解极小值。
2. EM算法
EM算法（Expectation Maximization）是在含有隐变量（latent variable）的模型下计算最大似然的一种算法。所谓隐变量，是指我们没有办法观测到的变量。比如，有两枚硬币A、B，每一次随机取一枚进行抛掷，我们只能观测到硬币的正面与反面，而不能观测到每一次取的硬币是否为A；则称每一次的选择抛掷硬币为隐变量。
用Y表示观测数据，Z表示隐变量；Y和Z连在一起称为完全数据( complete-data )，观测数据Y又称为不完全数据(incomplete-data)。观测数据的似然函数：
P(Y|θ)=∑ZP(Z|θ)P(Y|Z,θ)P(Y|θ)=∑ZP(Z|θ)P(Y|Z,θ)
求模型参数的极大似然估计：
θ^=argmaxθlogP(Y|θ)θ^=argmaxθlogP(Y|θ)
因为含有隐变量，此问题无法求解。因此，Dempster等人提出EM算法用于迭代求解近似解。EM算法比较简单，分为两个步骤：
E步（E-step），以当前参数θ(i)θ(i)计算ZZ的期望值
Q(θ,θ(i))=EZ[logP(Y,X|θ)|Y,θ(i)]Q(θ,θ(i))=EZ[logP(Y,X|θ)|Y,θ(i)]
M步（M-step），求使Q(θ,θ(i))Q(θ,θ(i))极大化的θθ，确定第i+1i+1次迭代的参数的估计值θ(i+1)θ(i+1)
θ(i+1)=argmaxθQ(θ,θ(i))θ(i+1)=argmaxθQ(θ,θ(i))
如此迭代直至算法收敛。关于算法的推导及收敛性证明，可参看李航的《统计学习方法》及Andrew Ng的《CS229 Lecture notes》。 这里 有一些极大似然以及EM算法的生动例子。
3. 实例
[2]中给出极大似然与EM算法的实例。如图所示，有两枚硬币A、B，每一个实验随机取一枚抛掷10次，共5个实验，我们 可以 观测到每一次所取的硬币，估计参数A、B为正面的概率θ=(θA,θB)θ=(θA,θB)，根据极大似然估计求解
如果我们 不能 观测到每一次所取的硬币，只能用EM算法估计模型参数，算法流程如图所示：
隐变量ZZ为每次实验中选择A或B的概率，则第一个实验选择A的概率为
P(z1=A|y1,θ(0))=P(z1=A|y1,θ(0))P(z1=A|y1,θ(0))+P(z1=B|y1,θ(0))=0.65∗0.450.65∗0.45+0.510=0.45P(z1=A|y1,θ(0))=P(z1=A|y1,θ(0))P(z1=A|y1,θ(0))+P(z1=B|y1,θ(0))=0.65∗0.450.65∗0.45+0.510=0.45
按照上面的计算方法可依次求出隐变量ZZ，然后计算极大化的θ(i)θ(i)。经过10次迭代，最终收敛。
4. 参考资料
[1] 李航，《统计学习方法》.
[2] Chuong B Do & Serafim Batzoglou, What is the expectation maximization algorithm?
[3] Pieter Abbeel, Maximum Likelihood (ML), Expectation Maximization (EM) .
[4] Rudan Chen, 【机器学习算法系列之一】EM算法实例分析 .
B. 数据挖掘十大经典算法之EM
EM（Expectation-Maximum）算法也称期望最大化算法，它是最常见的隐变量估计方法，在机器学习中有极为广泛的用途，例如常被用来学习高斯混合模型（Gaussian mixture model，简称GMM）的参数；隐式马尔科夫算法（HMM）、LDA主题模型的变分推断等等。
EM算法是一种迭代优化策略，由于它的计算方法中每一次迭代都分两步，其中一个为期望步（E步），另一个为极大步（M步），一轮轮迭代更新隐含数据和模型分布参数，直到收敛，即得到我们需要的模型参数。
1. EM算法推导过程
补充知识：Jensen不等式：
如果f是凸函数，函数的期望 大于等于 期望的函数。当且仅当下式中X是常量时，该式取等号。（应用于凹函数时，不等号方向相反）
2. EM算法流程
3. EM算法的其他问题
上面介绍的传统EM算法对初始值敏感，聚类结果随不同的初始值而波动较大。总的来说，EM算法收敛的优劣很大程度上取决于其初始参数。
EM算法可以保证收敛到一个稳定点，即EM算法是一定收敛的。
EM算法可以保证收敛到一个稳定点，但是却不能保证收敛到全局的极大值点，因此它是局部最优的算法，当然，如果我们的优化目标是凸的，则EM算法可以保证收敛到全局最大值，这点和梯度下降法这样的迭代算法相同。
EM算法的简单实例： https://zhuanlan.hu.com/p/40991784
参考：
https://zhuanlan.hu.com/p/40991784
https://blog.csdn.net/u011067360/article/details/24368085
C. 02 隐马尔可夫模型 - HMM的三个问题 - 概率计算问题
01 隐马尔可夫模型 - 马尔可夫链、HMM参数和性质
假设有三个盒子，编号为1,2,3；每个盒子都装有黑白两种颜色的小球，球的比例。如下：
按照下列规则的方式进行有放回的抽取小球，得到球颜色的观测序列：
1、按照π的概率选择一个盒子，从盒子中随机抽取出一个球，记录颜色后放回盒子中；
2、按照某种条件概率选择新的盒子，重复该操作；
3、最终得到观测序列：“白黑白白黑”
例如： 每次抽盒子按一定的概率来抽，也可以理解成随机抽。
第1次抽了1号盒子①，第2次抽了3号盒子③，第3次抽了2号盒子②.... ； 最终如下：
①→③→②→②→③ 状态值
白→黑→白→白→黑 观测值
1、 状态集合： S={盒子1，盒子2，盒子3}
2、 观测集合： O={白，黑}
3、 状态序列和观测序列的长度 T=5 (我抽了5次)
4、 初始概率分布： π 表示初次抽时，抽到1盒子的概率是0.2，抽到2盒子的概率是0.5，抽到3盒子的概率是0.3。
5、 状态转移概率矩阵 A：a11=0.5 表示当前我抽到1盒子，下次还抽到1盒子的概率是0.5；
6、 观测概率矩阵 - 混淆矩阵 - 为了不和之前的混淆矩阵概念冲突，可以称之为发射矩阵，即从一个状态发射到另一个状态： B：如最初的图，b11=第一个盒子抽到白球概率0.4，b12=第一个盒子抽到黑球概率0.6;
在给定参数π、A、B的时候，得到观测序列为“白黑白白黑”的概率是多少?
这个时候，我们不知道隐含条件，即不知道状态值：①→③→②→②→③ ；
我们如何根据π、A、B求出测序列为“白黑白白黑”的概率？
下面给出解决方案。
前向-后向算法 给定模型λ=(A,B,π)和观测序列Q={q1,q2,...,qT}，计算模型λ下观测到序列Q出现的概率P(Q|λ)；
回顾上面的案例 ，λ=(A,B,π)已知。观测到序列 Q=白→黑→白→白→黑，但我们不知道 状态序列 I=①→③→②→②→③；我们要求解 P(Q|λ) ，即Q=白→黑→白→白→黑 这个观测序列发生的概率。 可以用前向-后向算法来实现 。
Baum-Welch算法(状态未知) 已知观测序列Q={q1,q2,...,qT}，估计模型λ=(A,B,π)的参数，使得在该模型下观测序列P(Q|λ)最大。
Baum-Welch算法是EM算法的一个特例，专门用来 求解 隐马尔科夫中隐状态参数 λ=(A,B,π) 。即：根据已知的 观测到序列 Q=白→黑→白→白→黑，去寻找整个模型的一组隐状态参数λ=(A,B,π)，使得在模型中 观测序列 发生的可能性P(Q|λ)最大。
Viterbi算法 给定模型λ=(A,B,π)和观测序列Q={q1,q2,...,qT}，求给定观测序列条件概率P(I|Q，λ)最大的状态序列I。
已知 观测到序列 Q=白→黑→白→白→黑，当我们得到λ=(A,B,π)后，我们用 Viterbi算法 求出在哪一种 状态序列 发生的可能性最大，即，求出 状态序列 I=①→③→②→②→③；即，抽取什么样的盒子顺序，更可能得到白→黑→白→白→黑这种结果。
1、直接计算法(暴力算法)
2、前向算法
3、后向算法
类似KNN计算最近邻时候的算法。《 01 KNN算法 - 概述 》
也就是说， 暴力算法 需要一个个遍历所有的状态去计算当前状态发生的概率。
按照概率公式，列举所有可能的长度为T的状态序列I={i1,i2,...,iT}，求各个状态序列I与观测序列Q={q1,q2,...,qT}的联合概率P(Q,I;λ)，然后对所有可能的状态序列求和，从而得到最终的概率P(Q;λ)；
分析： 先思考这样一个问题：生成“白-黑-白-白-黑”这样的结果，是不是会有很多种盒子组合的序列来抽取，都会生成这样一个结果？我把这些可能出现“白-黑-白-白-黑”结果的盒子序列的联合概率求出来-P(Q,I;λ)，即∑P(Q,I) = P(Q) ，P(Q) 是我们观测到“白-黑-白-白-黑”结果时，符合这个结果的所有状态序列I出现的概率。
公式运用：
设状态序列 I=③→②→①→①→②； T=5；
P(I;λ) = π 3 a 32 a 21 a 11 a 12
因为： 在给定状态序列I后，Q中的每个观测值都独立。（贝叶斯网络原理） 贝叶斯网络
所以： P(Q|I;λ)可以用联乘的方式表示 (独立可以使用联合概率)
I = ③→②→①→①→②
Q=白→黑→白→白→黑
P(Q|I;λ) = b 3白 b 2黑 b 1白 b 1白 b 2黑
P(Q,I;λ) = P(Q|I;λ) × P(I;λ)
= b 3白 b 2黑 b 1白 b 1白 b 2黑 × π 3 a 32 a 21 a 11 a 12
若：
I 1 = ③→②→①→①→②
I 2 = ①→②→③→①→②
...
I T = ②→②→①→③→②
都能得出：
Q = 白→黑→白→白→黑
因为我所有的盒子都能取出黑球和白球，所以T的值=3 5 ;
∑P(Q,I;λ) 计算的是 I 1 ~ I T 这些状态序列情况下，求出的P(Q,I;λ)的和。
前向 和 后向 算法是运用某种递归(递推)的方式，帮助我们尽快得求解最终结果。
解析: 如果 t 这一时刻观察到的状态是 q t = 雨天；其中y={干，湿，湿... 湿}共t个状态。
先不考虑λ。
α t 是 1时刻~t时刻 所有观测值y1，y2，...yt ，qt 出现的联合概率。
β t 是 t+1时刻~T时刻 所有观测值y t+1 ，y t+2 ，...y T 出现的联合概率。
前向概率-后向概率 指的其实是在一个观测序列中，时刻t对应的状态为si的概率值转换过来的信息。
分析2~3步的推导： 因为q 1 ~ q t 这些条件对 q t+1 ~ q T 的产生没有影响 (理由：贝叶斯网络)，所以这些条件可以去掉。
定义：给定λ，定义到时刻t部分观测序列为q1,q2,...,qt且状态为si的概率为 前向概率 。
记做：
在给定参数π、A、B的时候，得到观测序列为“白黑白白黑”的概率是多少?
定义：给定λ，定义到时刻t状态为si的前提下，从t+1到T部分观测序列为qt+1,qt+2,...,qT的概率为 后向概率 。
记做：
分析上面的公式：
如果一共只有t个时间点，t+1的时刻不存在。那么t+1以后发生的是必然事件。
所以 β t (i) = P(q t+1 ，q t+2 ，...，q T ) = 1;
如果实在不理解也没关系，我们姑且认为认为定义了一个初始值，即 β T (i) = 1 ；
从T-1时刻，倒推到1时刻。
首先，β t+1 (j)是什么？是t+1时刻，在状态sj的前提下，下图中圈起来这部分的联合概率。
β t (j)是什么？是t时刻，在状态sj的前提下，下图中圈起来这部分的联合概率。
求给定模型λ和观测序列Q的情况下，在时刻t处于状态si的概率，记做：
单个状态概率的意义主要是用于判断在每个时刻最可能存在的状态，从而可以得到一个状态序列作为最终的预测结果。
求给定模型λ和观测序列Q的情况下，在时刻t处于状态si并时刻t+1处于状态sj概率，记做：
03 隐马尔可夫模型 - HMM的三个问题 - 学习问题
D. em算法就是baum-welch 算法吗
baum-welch算法是一种对hmm模型做参数估计的方法，是EM算法的一个特例。
前向后向算法是已知模型和序列求概率的算法，也是用于训练的Baum-Welch算法的循环中的一个步骤。
E. （十）EM算法
EM算法的英文全称是 Expectation Maximization Algorithm——期望极大化算法 ，它采用迭代的方式逼近带隐变量的似然函数。通过对似然函数的一个下界求偏导，得到每一步参数估计的过程。
这个名称由于缺乏作用对象，让人一头雾水。这里的期望是什么？为什么我们要极大化这个期望，我们试图优化什么？
这里的期望的含义其实是针对 极大似然估计 中的 似然函数 来说的，这里的期望就是似然函数的一个 下界 ，我们的目的是求这样一个期望: 这个下界是根据 詹森不等式(Jensen's inequality） 放缩得到的，为什么要放缩呢？因为我们试图找出一个下界，极大化这个带参数的下界之后，可以无限近似于似然函数。你想，如果这个做法ok的话，意味着什么？意味着我们可以通过这个过程找出极大似然估计或最大后验估计的参数近似解。这也意味着我们可以搞一个迭代法来得到一个近似解。但是即便我说的天花乱坠，这个下界要是不收敛那也白搭。而下界要收敛必须满足两个条件：
1.这个下界的取值要单调递增（因为每回迭代的结果要比上一次的取值更大）
2.这个下界必须有上界(这个上界就是对数似然函数，且这一点可以由詹森不等式保证，这个也是EM的核心)
大白话就是 单调有界必有极限 。
我们来证明一下它确实是收敛的。
首先，在极大似然估计中，我们的目的是根据手头上的 个样本，最大化 后，将参数 估计出来；引入对数： ;此时引入辅助变量 ;我们的对数似然函数就变成了：
设置变分函数： ;那么：
根据琴生不等式,对数函数为凸函数(因为 ：等号在 为常数时取到)：
上面的这个下界，就是用来逼近原对数似然函数的，这里我们已经证明了算法收敛的一个条件， 有界性 ；但是在继续进行下一步的时候，我们还有一个问题没搞清楚，那就是变分函数 的具体形式,实际上，我们可以通过琴生不等式等号成立的条件导出我们要的这个变分函数q。
令 为常数：
接着我们代入变分函数 的形式，定义这个下界的第一项：
定义下界的第二项：
对于第二项，我们看看随着迭代步数的增大，它是否是递增的，
我们将不同参数的 与 看作是两个分布，那么这个结果实际上是一个KL散度，它表征两个分布的相似度,其结果总是大于等于0的。
大于等于0的原因：
所以：
H为一个递增的序列，那么剩下的就是Q是否递增了，基于前面提到的这个下界是有上界的，上界就是我们的对数似然函数。在这个前提下，现在我们只要证明，Q递增是整个下界递增的充分必要条件即可。
必要性：
当整个下界递增，即：
那么：
所以 单调递增，必要性得证。
充分性：
因为：
前面已经证明：
又因为：
所以：
即，在 递增的情况下，整个下界递增。
充分性得证。
证毕。
这个算法名称里提及的期望究竟是什么？
我们说了这么多，实际都是要做一件事，那就是：
由于前面证明过整个下界有界。且只要找到让第i次迭代的Q函数最大的 作为下一次迭代的参数，我们就可以让Q递增，让算法收敛。
我们来看看Q的形式。
这就是为什么叫期望最大算法的原因。
我们以概率PCA，来展开EM的应用：
当然这里的应用只涉及变分函数已知情况下的应用，并不涉及广义EM的内容，日后看完文献在来唠唠广义EM，AVE，GAN等内容。
我们先来算一下PPCA的EM期望的形式：
在 概率PCA 中，我们有提到：
所以：
所以期望里面是这个式子：
我们的目的是要估计出 和 ;那么我们分别对它们求偏导:
所以：
因为：
代入偏导中
所以：
我们偏导得到的结果就是：
我们会发现我们还有两个估计量没解决，一个是一阶估计量 ,另一个是二阶估计量
在概率PCA中，我们提到过：
那么我们就有了一阶估计量：
二阶估计量可以通过简单的计算得到：
剩下的代入即可.
结果展示：