1 EM算法的背景介绍
如何用迭代法估计模型的参数，这是EM算法的基础。
在极大似然估计中，用最值的方法，将使得
P(X|\theta)取得最大值的参数
\theta作为估计值，有一类概率模型比较简单，只含有观测变量
X，比如中心一元高斯模型，可以直接利用模型分布的观测变量，然后基于极大似然估计法，估计出这个模型的参数
\mu和
\sigma；
而有一些模型中含有一类隐藏变量
Z，这类变量是不可观测的，这也使得模型无法利用观测变量
X来直接求导得出估计值
\theta，那么就必须要换一种求解的思路，采用一轮一轮迭代的方法，尽可能的逼近真实解。
那么问题来了，
如何迭代？
为什么一定能逼近真实解？
2 抛出EM算法的迭代公式
首先，先看看如何进行迭代，这里先给出EM算法中的参数迭代公式：
\theta^{(t+1)} = \underset {\theta} {argmax} \int _Z logP(X,Z|\theta)P(Z|X,\theta^{(t)})dZ
上式表示在第
t轮迭代的过程中，能够利用第
t轮的参数估计值
\theta^{(t)}，去迭代估计出第
t+1轮的参数
\theta^{(t+1)}。
那么，在假定一个初值
\theta ^{(0)}的情况下，就能通过上述的迭代公式一轮一轮的迭代下去。
这种迭代方法为何有效？换句话说，如何能保证从
\theta^{(0)}开始，
\theta^{(1)},\theta^{(2)},\theta^{(3)}, \theta^{(4)},...,一直到
\theta^{(t)}的迭代过程中，每一次迭代都能使似然函数
P(X|\theta)的值不断增大，实现最终的收敛性。本质上，只要保证每次迭代
P(X|\theta)的值都在增大，那么这个方法就是可行的、有效的。
3 EM算法为什么有效？？？
这里就先说为什么每一轮迭代都可以使似然函数
P(X|\theta)的值不断增大。
利用公式形式化的描述和证明这个问题，即：
对于任意轮数
t，通过迭代公式的方法实现
\theta^{(t)}\rightarrow \theta^{(t+1)}的迭代之后，一定能够满足logP(X|
\theta^{(t)})小于等于logP(X|
\theta^{(t+1)})，等价于
P(X|\theta^{(t)})\leq P(X|\theta^{(t+1)})。
下面开始证明。
首先，利用贝叶斯公式可以得到观测变量X和隐变量Z的概率关系式：
P(X|\theta)P(Z|X,\theta)=P(X,Z|\theta)
\implies logP(X|\theta) + logP(Z|X,\theta)
=logP(X,Z|\theta)
因此，将隐变量引入log似然函数：
logP(X|\theta)
=logP(Z|X,\theta)-logP(X,Z|\theta)
对等式两边同时求关于
P(Z|X,\theta^{(t)})的期望，也就是求积分：
\int_Z P(Z|X,\theta^{(t)})logP(X|\theta)dZ
=\int_Z P(Z|X,\theta^{(t)})logP(X,Z|\theta)dZ
-\int_Z P(Z|X,\theta^{(t)})logP(Z|X,\theta)dZ
对于等式左边进行化简得到：
\int_Z P(Z|X,\theta^{(t)})logP(X|\theta)dZ
=logP(X|\theta)\int_Z P(Z|Z,\theta^{(t)})dZ
=logP(X|\theta)\times 1=logP(X|theta)
简单说一下，因为
logP(X|\theta)与变量Z无关，因此可以拿出到外面，同时，
\int_Z P(Z|X,\theta^{(t)})dZ相当于所有概率的和，因此等于1。
因此等式最终变为:
logP(X|\theta)
=\int_Z P(Z|X,\theta^{(t)})logP(X,Z|\theta)dZ
-\int_Z P(Z|X,\theta^{(t)})logP(Z|X,\theta)dZ
那么，最开始验证
P(X|\theta^{(t+1)})\geq P(X|\theta^{(t)})，就转化为验证下面这个不等式是否成立：
\int_Z P(Z|X,\theta^{(t)})logP(X,Z|\theta^{(t+1)})dZ
-\int_Z P(Z|X,\theta^{(t)})logP(Z|X,\theta^{(t+1)})dZ
\geq \int_Z P(Z|X,\theta^{(t)})logP(X,Z|\theta^{(t)})dZ
-\int_Z P(Z|X,\theta^{(t)})logP(Z|X,\theta^{(t)})dZ
将不等式拆解成2个部分，如果能够验证下面2部分不等式都成立，那么自然
P(X|\theta^{(t+1)})\geq P(X|\theta^{(t)})就是成立的。
不等式1：
\int_Z P(Z|X,\theta^{(t)})logP(X,Z|\theta^{(t+1)})dZ
\geq \int_Z P(Z|X,\theta^{(t)})logP(X,Z|\theta^{(t)})dZ
不等式2：
\int_Z P(Z|X,\theta^{(t)})logP(Z|X,\theta^{(t+1)})dZ
\leq \int_Z P(Z|X,\theta^{(t)})logP(Z|X,\theta^{(t)})dZ
先看不等式1
更具迭代公式的定义，
\theta=\theta^{(t+1)}是使得迭代公式取得最大值的值，换言之就是比
\theta取其他值都要大，自然这个其他值也包含了
\theta^{(t)}。
所以说，对于：
\int_Z P(Z|X,\theta^{(t)})logP(X,Z|\theta^{(t+1)})dZ
\geq \int_Z P(Z|X,\theta^{(t)})logP(X,Z|\theta^{(t)})dZ
这个不等式而言，迭代法本身的定义就能够保证其成立。
再看不等式2
这里对于不等式2进行稍微的变形：
\int_Z P(Z|X,\theta^{(t)})logP(Z|X,\theta^{(t+1)})dZ
- \int_Z P(Z|X,\theta^{(t)})logP(Z|X,\theta^{(t)})dZ
\int_Z P(Z|X,\theta^{(t)})\frac{logP(Z|X,\theta^{(t)})}{logP(Z|X,\theta^{(t+1)})}dZ
这里要使用KL三度来进行相关的计算，也就是相对熵。
KL散度
设
P(X)和
Q(X)是随机变量X上的2个概率分布，则在离散和连续变量的情形下，相对熵的定义分别为：
KL(P||Q)=\sum P(X)log \frac{P(X)}{Q(X)}
KL(P||Q)=\int P(X)log \frac{P(X)}{Q(X)}dX
KL散度是用来衡量
P(X)和
Q(X)分布之间的距离，因此具有一个非常重要的性质，那就是非负性，即
KL(P||Q)\geq 0，当
P(X)和
Q(X)2个分布相同的时候取等号。
下面使用KL散度来辅助不等式2的证明，过程如下：
\int_Z P(Z|X,\theta^{(t)})logP(Z|X,\theta^{(t+1)})dZ
- \int_Z P(Z|X,\theta^{(t)})logP(Z|X,\theta^{(t)})dZ
\int_Z P(Z|X,\theta^{(t)})\frac{logP(Z|X,\theta^{(t)})}{logP(Z|X,\theta^{(t+1)})}dZ
KL[P(Z|X,\theta^{(t)})||P(Z|X,\theta^{(t+1)})]
\geq 0
于是不等式2也得到证明。
那么经过
\theta^{(t)}\rightarrow \theta^{(t+1)}的迭代之后
logP(X|\theta^{(t)})\leq logP(X|\theta^{(t+1)})的问题也就得到了证明，也就是说通过一轮一轮的迭代，log似然函数的取值也在不断的增大，最终log似然函数收敛到最大值，待估计参数
\theta也就不断趋近于参数的真实值。
