李航-第9章EM算法及其推广

EM算法的每次迭代由两步组成：E步，求期望；M步，求极大。
所以这一算法称为期望极大法（expectation maximization），简称EM算法。

EM算法的最大优点是简单性和普适性。

关于概率和似然：
在统计学中，似然函数（likelihood function，通常简写为likelihood，似然）是一个非常重要的内容，在非正式场合似然和概率（Probability）几乎是一对同义词，但是在统计学中似然和概率却是两个不同的概念。概率是在特定环境下某件事情发生的可能性，也就是结果没有产生之前依据环境所对应的参数来预测某件事情发生的可能性，比如抛硬币，抛之前我们不知道最后是哪一面朝上，但是根据硬币的性质我们可以推测任何一面朝上的可能性均为50%，这个概率只有在抛硬币之前才是有意义的，抛完硬币后的结果便是确定的；而似然刚好相反，是在确定的结果下去推测产生这个结果的可能环境（参数），还是抛硬币的例子，假设我们随机抛掷一枚硬币1,000次，结果500次人头朝上，500次数字朝上（实际情况一般不会这么理想，这里只是举个例子），我们很容易判断这是一枚标准的硬币，两面朝上的概率均为50%，这个过程就是我们运用出现的结果来判断这个事情本身的性质（参数），也就是似然。

参考链接：
似然与极大似然估计

EM算法与K-means算法的联系

高斯混合模简写为GMM（Gaussian misture model），而EM算法是学习高斯混合模型的有效方法。

对比K-Means算法和GMM的EM解法，我们会发现二者具有很强的相似性。K-Means算法对数据点的聚类进行了“硬分配”，即每个数据点只属于唯一的聚类；而GMM的EM解法则基于后验概率分布，对数据点进行“软分配”，即每个单独的高斯模型对数据聚类都有贡献，不过贡献值有大有小。

Kmeans是一个聚类模型；EM算法是一个求模型参数的优化算法；

Kmeans模型可以认为是GMM混合高斯模型的特例。k-means算法与EM算法的关系是这样的：k-means是两个步骤交替进行，可以分别看成E步和M步；M步中将每类的中心更新为分给该类各点的均值，可以认为是在「各类分布均为单位方差的高斯分布」的假设下，最大化似然值；E步中将每个点分给中心距它最近的类（硬分配），可以看成是EM算法中E步（软分配）的近似。

EM算法（期望最大化）——从EM算法角度理解K-Means与GMM的区别

EM算法要解决的问题

EM算法，为了解决含有隐变量的概念模型的学习。

应用：
EM算法可以用于生成模型的非监督学习，比如隐马尔可夫模型。
EM算法用于高斯混合模型的参数估计。
另外，还有很多算法变形，比如GEM算法。

EM算法的推导

EM算法.jpg EM算法的解释.jpg

EM算法是通过迭代逐步近似极大化L(Θ)的，假设在第i次迭代后Θ的估计值是Θ(i)。我们希望新估计值Θ能使L(Θ)增加，即L(Θ) > L(Θ(i))并逐步达到极大值。

EM算法的收敛性思考

EM算法收敛性定理9.1.jpg EM算法收敛性定理9.2.jpg

定理只能保证参数估计序列收敛到对数似然函数序列的稳定点，不能保证收敛到极大值点。所以在应用中，初值的选择变的非常重要，常用的方法是选取几个不同的初值进行迭代，然后对得到的各个估计值加以比较，从中选择最好的。

最大似然估计与EM算法的关系

EM算法是用来求解含有隐变量(未能观测的变量)模型的极大似然估计。故其本质还是极大似然估计。EM算法是在极大化Q函数，而可以证明的是Q函数变大的时候，似然函数也在变大，所以本质还是在做极大似然估计

例9.1 三硬币模型

In [2]: import numpy as np
   ...: import math
   ...: 

In [3]: pro_A, pro_B, pro_C = 0.5,0.5,0.5
   ...: def pmf(i, pro_A, pro_B, pro_C):    
   ...:     pro_1 = pro_A * math.pow(pro_B, data[i]) * math.pow((1-pro_B), 1-data[i])
   ...:     pro_2 = pro_A * math.pow(pro_C, data[i]) * math.pow((1-pro_C), 1-data[i])
   ...:     return pro_1 / (pro_1 + pro_2)
   ...: 

In [4]: class  EM:
   ...:     def __init__(self, prob):
   ...:         self.pro_A, self.pro_B, self.pro_C = prob
   ...: 
   ...:     # e_step
   ...:     def pmf(self, i):
   ...:         pro_1 = self.pro_A * math.pow(self.pro_B, data[i]) * math.pow((1-self.pro_B), 1-data[i])
   ...:         pro_2 = (1 - self.pro_A) * math.pow(self.pro_C, data[i]) * math.pow((1-self.pro_C), 1-data[i])
   ...:         return pro_1 / (pro_1 + pro_2)
   ...: 
   ...:     # m_step
   ...:     def fit(self, data):
   ...:         count = len(data)
   ...:         print('init prob:{}, {}, {}'.format(self.pro_A, self.pro_B, self.pro_C))
   ...:         for d in range(count):
   ...:             _ = yield
   ...:             _pmf = [self.pmf(k) for k in range(count)]
   ...:             pro_A = 1/ count * sum(_pmf)
   ...:             pro_B = sum([_pmf[k]*data[k] for k in range(count)]) / sum([_pmf[k] for k in range(count)])
   ...:             pro_C = sum([(1-_pmf[k])*data[k] for k in range(count)]) / sum([(1-_pmf[k]) for k in range(count)])
   ...:             print('{}/{}  pro_a:{:.3f}, pro_b:{:.3f}, pro_c:{:.3f}'.format(d+1, count, pro_A, pro_B, pro_C))
   ...:             self.pro_A = pro_A
   ...:             self.pro_B = pro_B
   ...:             self.pro_C = pro_C
   ...:             

In [5]: data=[1,1,0,1,0,0,1,0,1,1]

In [6]: em = EM(prob=[0.5, 0.5, 0.5])
   ...: f = em.fit(data)
   ...: next(f)
   ...: 
init prob:0.5, 0.5, 0.5

In [7]: #第一次迭代
   ...: f.send(1)
1/10  pro_a:0.500, pro_b:0.600, pro_c:0.600

In [8]: #第二次迭代
   ...: f.send(2)
2/10  pro_a:0.500, pro_b:0.600, pro_c:0.600

In [9]: em = EM(prob=[0.4, 0.6, 0.7])
   ...: f2 = em.fit(data)
   ...: next(f2)
   ...: 
init prob:0.4, 0.6, 0.7

In [10]: f2.send(1)
1/10  pro_a:0.406, pro_b:0.537, pro_c:0.643

In [11]: f2.send(2)
2/10  pro_a:0.406, pro_b:0.537, pro_c:0.643

参考链接：
通俗解释EM算法并举例
最大似然估计与EM算法的关系
EM算法（期望最大化）——从EM算法角度理解K-Means与GMM的区别
数理统计与参数估计杂记
EM算法