机器学习：原理简明教程09-EM算法
欢迎转载，作者：Ling，注明出处：机器学习：原理简明教程09-EM算法
一句话总结：以二硬币为例，EM是用于估计θ的，随机初始化不同硬币出现正方面的概率θ，E步：迭代所有样本，根据每个样本正反面情况，计算在θ下的不同硬币的概率，通过概率可以为不同硬币分配权值，通过分配的权值计算不同硬币出现正方面的次数，E步结果是不同硬币正反面出现的次数，M步：根据不同硬币出现正方面次数，统计新的θ，即不同硬币出现正面的概率，直到θ变化不大，从而得到最终的不同硬币出现正方面的概率。
换一句话总结：通俗地说，你有N回硬币正反面序列，但是不知道它们每回从哪个硬币来的，你可以随机给个每个硬币正反面可能的概率值，然后根据每回实际硬币正反面序列，统计每个硬币的可能情况，根据可能的比值分配权值，从而分配每个硬币正反面次数，当所有样本都统计完，即可计算新的每个硬币的正反面可能的概率值，直到该概率值不再怎么变化。
再换一句话总结：以隐马尔可夫参数估计为例，形式化地，写出EM算法的Q公式，E步：带入第i步已知的值，得到L公式，M步：然后对参数求导计算极值（如果求导好算的话），得到第i+1步参数的值
EM算法：
- 一种迭代算法
- 1977年 由 Dempster等人总结提出
- 用于有隐变 量（hidden variable）的概率模型参数的极大似然估计
- 两步：E 步，求 期 望 （ expectation); M 步，求极大 (maximization)
- 一个典型应用：为HMM第三类问题估计参数用
如果概率模型的变量都是观测变量（数据中可见的变量），则可以直接用极大似然估计，或者用贝叶斯估计模型参数。但是，当模型含有隐变量（数据中看不到的变量）时，就不能简单地使用这些估计方法，而应该使用含有隐变量的概率模型参数的极大似然估计法，也即EM算法。
EM算法的引入
引入EM算法有两个常见的例子，一个是三硬币模型，一个是双硬币模型。
三硬币模型
注：
1）该例子很好地解释了EM的计算步骤
2）式子里面的θ=（π，p，q）
3）p(y|θ) 注意这个不是条件概率，只是表示y的概率，只不过是用当前θ表示
4）9.1式表示y的概率，推导表示，y的概率等于所有z可能情况对应的（y,z）联合概率的和，第二个推导表示，联合概率转成条件概率乘以p（z）概率，z为隐含变量，它表示取B或者C硬币的概率，第三个推导表示（B硬币概率乘以B为正向概率乘以负向概率+C硬币概率乘以C为正概率乘以C为负概率）
5）9.2表示y的概率等于，隐含变量Z所有可能情况乘以在每个Z下的Y的概率和
6）9.3表示的其实是L最大似然函数，就是所有样本概率乘积，L=∏p(y=yi|θ)
7）9.4表示取log后求最大似然的θ，不好求，因为有指数，所以要采用EM进行近似求解
8）9.5表示一个样本yj来自B的概率，其实就是(样本yj来自B概率)/(样本yj来自B概率+样本yj来自C概率)，由θi的各个值计算得到i+1的μ
9）9.6 对所有样本来自B的概率求和除以n，得到i+1的来自B的概率
10）9.7 来自B且为正面的概率
11）9.8来自C且为正面的概率
12）
EM算法思路：随机初始化θ，这时候θ已知，也就是第0次迭代的，来自B或C的概率已知，来自B且正面的概率已知，来自C且正面的概率已知，从而可以根据他们计算符合j样本，且来自硬币B的概率（μ），累加所有样本来自B的概率得到来自B的概率π，同理得到p和q，直到θ变化不大停止
标准EM算法：
EM算法的导出
看完了冗长的标准定义，认识了一点也不Q的Q函数，终于可以了解EM算法是怎么来的了。
寻找模型参数的目标（或称标准）是找到的参数使观测数据的似然函数最大，一般用对数似然函数取代似然函数，这样可以把连乘变为累加，方便优化，也就是极大化
这个式子里面有未知的隐变量Y，无法直接优化。
但是如同在“EM算法简单理解”中看到那样，给定模型参数，就可以估计Y的条件概率（后验概率，已经有Z这个结果，求原因Y的概率）。所以我们就挑一个模型参数的初值，也就是EM算法的第1步。
有了初值，就可以代入似然函数得到一个值，但这个值不一定是最大的，我们想要更大，所以需要调整参数，这也是EM算法为什么要迭代的原因。
注：
1）Jensen不等式（Jensen inequality)
2）式子第一个公式乘以和除以同一个数错了，应该是：
3）第一个不等号是根据jensen不等式得到
4）logP(Y|θ(i)) = ∑P（Z|Y, θ(i)）*P(Y|θ(i)) 成立吗？前面为1？
注：
1）
2）9.17去掉上式中所有与θ无关的常数项
EM 算法在非监督学习中的应用
EM算法的收敛性(了解)
EM算法在高斯混合模型学习中的应用（了解）
高斯混合模型
其他略
留言