2 EM算法
2.1 算法描述
输入：观测变量数据X = ( x ( 1 ) , x ( 2 ) , . . . x ( m ) ，隐变量数据Z = ( z ( 1 ) , z ( 2 ) , . . . z ( m ) 输出：模型参数θ
观测数据X 又称不完全数据（incomplete-data），其概率分布是P ( X ∣ θ
X 和Z连在一起称完全数据（complete data），其联合概率分布是P ( Y , Z ∣ θ )
优化目标：
最大化观测数据X关于参数θ 的对数似然函数:
即
2.2 推导过程
令
由于Q i ( zi ) 是一个分布，满足
则
通过极大化包含隐藏数据的对数似然的下界，从而极大化对数似然$ L(\theta)$。
此时，优化目标成为:
去掉常数部分
上式也就是EM算法的M步。
E步则是log P (x i, zi ; θ )基于条件概率分布Q i (zi ) )的期望。
2.3 算法步骤
EM通过迭代的方式逐步逼近L ( θ )的极大值（反复构造新的下界）： j jj次迭代后θ 的估计值为θ j ，希望新的估计值θ j + 1
能使L ( θ ) 的值增加，即L ( θ j + 1 ) > L ( θ j )。
具体步骤如下：
选泽参数初始值θ 0 。
E步：计算联合分布的条件概率期望，完全数据的对数似然函数log P ( X , Z ∣ θ )在给定观测数据X 和当前参数θ j下对未观测数据Z ZZ的条件概率分布P ( Z ∣ X , θ j ) 的期望：
其中，
M步：求第j + 1次迭代的参数估计值θ j + 1 ：
重复EM步，直至满足收敛条件，
一般给出较小的正数ε 1 , ε 2，若满足
则停止迭代，输出此时的θ值。
L函数是EM算法的核心（有的教材中称其为Q QQ函数），每次迭代实际在求期望（E-步）及其极大化（M-步），实现参数θ j → θ j + 1 的更新，使似然函数增大或达到局部极值。
另一种理解
EM算法还可以看做用坐标下降法来最大化对数似然下界的过程，从而得到对数似然函数取得极大值时的参数估计，也就是极大似然估计的过程。
在迭代的过程中，每次固定一个变量，对另外的求极值，最后逐步逼近极值：
E步：固定θ ，优化L
M步：固定L，优化θ
交替将极值推向最大。
2.4 算法的收敛性
可以证明：
EM算法可以收敛到局部极大值，但是却不能保证收敛到全局的极大值，因此它是局部最优的算法。当然，如果我们的优化目标L ( θ , θ j ) 是凸的，则EM算法可以保证收敛到全局最大值，这点和梯度下降法相同。
3 EM算法与非监督学习
监督学习中，训练数据( x 1 , Y1) , ( x 2 ,Y2) , . . . , ( x ( m ) , y ( m ) ) 中的每个样本点由输入和输出对组成，通过学习决策函数y = f ( x ) （判别模型）或学习条件概率分布P ( y ∣ x ) （生成模型），实现数据的分类及回归。
非监督学习中，训练数据( x 1 , ) , (x 2 , ) , . . . , ( Xm , ) 中每个样本点只有输入没有对应的输出，如聚类。
EM算法可以用于生成模型的非监督学习，生成模型由联合概率分布P ( X , Y ) )表示，认为非监督学习训练数据是联合概率分布产生的数据。
EM算法是一种框架，逼近统计模型参数的最大似然或最大后验估计。
K-Means可以看做一种Hard EM算法，
E步：给定当前簇中心，每个对象都被指派到簇中心离该对象最近的簇（期望每个对象都属于最近的簇）。
M步：给定指定簇，对于每个簇，算法调整其中心，使得指派到该簇的对象到该中心的距离之和最小化（指派到一个簇的对象的相似度最大化）。
K-Means是模糊聚类的一种特例（隐变量是存在分布的），在模糊或基于概率模型的聚类，EM算法从初始参数出发，并且迭代直到不能改善聚类（聚类收敛或改变充分小）。
E-步：根据当前模糊聚类或概率簇的参数，把对象指派到簇中。
M-步：发现新的聚类或参数，最小化模糊聚类的SSE或基于概率模型的期望似然。
4 EM算法应用于高斯混合模型学习
4.1 高斯混合模型
高斯混合模型（Gaussian misture model）指具有如下形式的概率分布模型：
其中，α j ≥ 0 是系数，
ϕ(x∣θj)为高斯分布密度
称为第j 个分模型。
4.2 高斯混合模型参数估计
假设观测数据x 1 , x 2 , . . . , x m 高斯混合模型
生成，其中模型参数
可以设想观测数据x 1 , x 2 , . . . , x m产生过程如下：
首先根据概率α j选择第j 个高斯分布模型ϕ ( x ∣ θ j )然后根据第j 个模型的概率密度函数ϕ ( x ∣ θ j ) 生成观测数据x i 。
执行上述过程m 次来生成观测数据。
反映观测数据x i 来自第j个模型的隐变量γ 是未知的，定义如下：
γ ij是0-1随机变量。
E步：根据当前模型参数，计算模型i ii对观测数据y i 的响应度：
M步：计算新一轮迭代的模型参数：
EM算法还可以解释为F函数（F function）的极大-极大算法（maximization-maximization algorithm），基于这个解释有若干变形与推广，如广义期望极大算法（GEM，Generalized Expectation Maximization）
附：数学基础
（1）Jensen不等式
如果f ff是凸函数，X 是随机变量，则f ( E [ X ] ) ⩽ E [ f ( X ) ] f(E[X]) ，特别地，如果f ff是严格凸函数，那么等号成立当且仅当P ( x = E [ X ] ) = 1 时（X 是常量）；
如果f是凹函数，X 是随机变量，则f ( E [ X ] ) ⩾ E [ f ( X ) ] f(E[X])，特别地，如果f ff是严格凹函数，那么等号成立当且仅当P ( x = E [ X ] ) = 1时（X 是常量）；
当f 是（严格）凹函数当且仅当− f 是（严格）凸函数。
函数f ff是凸函数，X 是随机变量，有0.5的概率是a ，有0.5的概率是b 。X 的期望值E ( x )就是( a + b ) / 2 (，可以看出E [ f ( X ) ] ⩾ f ( E [ X ] ) 成立。
（2） 坐标下降法
坐标下降法是一种对多个参数分步迭代最终得到目标函数局部极大值（极小值）的方法
如求目标函数f ( μ , θ ) 极值，可给定初值θ ，然后分别计算：
显然，
不断迭代后，f ( μ i + 1 , θ i ) 的值也逐渐逼近f m a x ，此时θ i 和μ i + 1 即为参数估计的值。
