EM Expectation Maximization
为什么要有EM算法
一般我们要利用一个最大似然法（MLE）求一个最大似然概率，那么问题来了，对原函数的MLE很可能求不出（函数太复杂，数据缺失等）。因为数据缺失而不能直接使用MLE方法的时候，我们可以用这个缺失数据的期望值来代替缺失的数据，而这个缺失的数据期望值和它的概率分布有关。那么我们可以通过对似然函数关于缺失数据期望的最大化，来逼近原函数的极大值（数学证明复杂），所以EM的两个步骤也是很明显了。
E-step, 假如缺失数据y(missing data, latent variable)， 那么就要求
，而y的分布式通过上一步迭代的模型求出的，即
M-step, 尽情使用MLE吧
目的：我们要maximize原likelihood function
备选方案：各种gradient的方法，还有simplex这类的粗暴猜，还有就是EM
困难：很有可能这个function很难求导，或者intractable，那么常规的gradient based方法就不能用.
以mixture modeling 为例EM在这里就可以登场了，它在这里是可以把 log of summation 转化成 summation of log，而且由于indicator function是互斥的，这个summation变的非常好算，通常有closed form为什么可以这么做是因为Jensen's Inequality告诉我们 对concave 的log 函数做这个转化是可以保证 summation of log 是 log of summation的lower bound，所以每一次最大化转化后的函数可以得到一个更接近原函数最大值的公共参数。
什么是隐变量
要知道隐变量并非是我们构造的变量，而是在实际问题中确实会存在的变量，只是我们无法观测到，也就是记录的数据不含隐变量。这样我们也就能够理解为什么含有隐变量就需要用EM算法而不用MLE算法，都没有观测到，确实没理由去直接估计，事实上对数似然函数确实也没有解析解。
这时候EM算法就闪亮登场了，我们无非就是取似然函数最优解对应的参数值，直接最大化似然函数不行，那么我们就间接去做。
EM算法的流程
- E步本质是改进Qi，
- M步的本质是优化参数，反复迭代，直到收敛。
推导过程
首先写出带有隐变量的似然函数，接着利用Jensen不等式，取到该似然函数的下界，同时确定隐变量的分布。
下一步是利用已知的隐变量分布去更新参数，这更新参数使用MLE，不过计算过程比较麻烦。收敛性的证明，我们要知道，极大似然估计是单调增加的，因此得到的结果是最终肯定会收敛到某个固定顶值。