1. 极大似然估计

1.1. 经典问题——学生身高问题

需要调查学校的男生和女生的身高分布。假设你在校园里随便找了100个男生和100个女生。他们共200个人。将他们按照性别划分为两组，然后先统计抽样得到的100个男生的身高。假设他们的身高是服从高斯分布的。但是这个分布的均值u和方差∂2我们不知道，这两个参数就是我们要估计的。记作θ=[u, ∂]T。

问题：我们知道样本所服从的概率分布的模型和一些样本，而不知道该模型中的参数。

我们已知的有两个：

（1）样本服从的分布模型

（2）随机抽取的样本需要通过极大似然估计求出的包括：模型的参数

总的来说：极大似然估计就是用来估计模型参数的统计学方法。

1.2. 如何估计

问题数学化：（1）样本集X={x1,x2,…,xN} N=100 （2）概率密度：p(xi|θ)抽到男生i（的身高）的概率 100个样本之间独立同分布，所以我同时抽到这100个男生的概率就是他们各自概率的乘积。就是从分布是p(x|θ)的总体样本中抽取到这100个样本的概率，也就是样本集X中各个样本的联合概率，用下式表示：

这个概率反映了，在概率密度函数的参数是θ时，得到X这组样本的概率。需要找到一个参数θ，其对应的似然函数L(θ)最大，也就是说抽到这100个男生（的身高）概率最大。这个叫做θ的最大似然估计量，记为

1.3. 求最大似然函数估计值的一般步骤

首先，写出似然函数：

其次，对似然函数取对数，并整理：

然后，求导数，令导数为0，得到似然方程；

最后，解似然方程，得到的参数即为所求。

1.4. 总结

多数情况下我们是根据已知条件来推算结果，而极大似然估计是已经知道了结果，然后寻求使该结果出现的可能性最大的条件，以此作为估计值。

2. Jensen不等式

2.1. 定义

设f是定义域为实数的函数，如果对于所有的实数x，f(x)的二次导数大于等于0，那么f是凸函数。 Jensen不等式表述如下：如果f是凸函数，X是随机变量，那么：E[f(X)]>=f(E[X]) 。当且仅当X是常量时，上式取等号。

2.2. 举例

图中，实线f是凸函数，X是随机变量，有0.5的概率是a，有0.5的概率是b。X的期望值就是a和b的中值了，图中可以看到E[f(X)]>=f(E[X])成立。Jensen不等式应用于凹函数时，不等号方向反向。

3. 传统EM算法详述

3.1. 问题描述

我们抽取的100个男生和100个女生样本的身高，但是我们不知道抽取的那200个人里面的每一个人到底是从男生的那个身高分布里面抽取的，还是女生的那个身高分布抽取的。用数学的语言就是，抽取得到的每个样本都不知道是从哪个分布抽取的。这个时候，对于每一个样本，就有两个东西需要猜测或者估计：

（1）这个人是男的还是女的？

（2）男生和女生对应的身高的高斯分布的参数是多少？

EM算法要解决的问题是：

（1）求出每一个样本属于哪个分布

（2）求出每一个分布对应的参数

3.2. 举例说明

身高问题使用EM算法求解步骤：

（1）初始化参数：先初始化男生身高的正态分布的参数：如均值=1.7，方差=0.1

（2）计算每一个人更可能属于男生分布或者女生分布；

（3）通过分为男生的n个人来重新估计男生身高分布的参数（最大似然估计），女生分布也按照相同的方式估计出来，更新分布。

（4）这时候两个分布的概率也变了，然后重复步骤（1）至（3），直到参数不发生变化为止。

4. 算法推导

已知：样本集X={x(1),…,x(m))}，包含m个独立的样本；

未知：每个样本i对应的类别z(i)是未知的（相当于聚类）；

输出：我们需要估计概率模型p(x,z)的参数θ；

目标：找到适合的θ和z让L(θ)最大。

上面的式（2）和式（3）不等式可以写成：似然函数L(θ)>=J(z,Q)，那么我们可以通过不断的最大化这个下界J，来使得L(θ)不断提高，最终达到它的最大值。

什么时候下界J(z,Q)与L(θ)在此点θ处相等？

我们固定θ，调整Q(z)使下界J(z,Q)上升至与L(θ)在此点θ处相等（绿色曲线到蓝色曲线），然后固定Q(z)，调整θ使下界J(z,Q)达到最大值（θt到θt+1），然后再固定θ，调整Q(z)……直到收敛到似然函数L(θ)的最大值处的θ*。这里有两个问题：什么时候下界J(z,Q)与L(θ)在此点θ处相等？为什么一定会收敛？

这个过程可以看作是对φ(θ) 求了下界。对于Qi 的选择，有多种可能，那种更好的？假设θ已经给定，那么φ(θ)的值就决定于Qi(zi) 和 P(xi,zi) 了。我们可以通过调整这两个概率使下界不断上升，以逼近φ(θ)的真实值，那么什么时候算是调整好了呢？

当不等式变成等式时，说明我们调整后的概率能够等价于φ(θ) 了。按照这个思路，我们要找到等式成立的条件。根据Jensen不等式，要想让等式成立，需要让随机变量变成常数值，这里得到：

又因为Q（z）是z的分布函数，所以

则可以得到：分子的和等于c

至此，我们推出了在固定其他参数θ 后， $Q_i(z^{(i)})$ 的计算公式就是后验概率，解决了 $Q_i(z^{(i)})$ 如何选择的问题。这一步就是E步，建立φ(θ) 的下界。接下来的M步，就是在给定 $Q_i(z^{(i)})$ 后，调整θ，去极大化φ(θ) 的下界（在固定Qi(zi) 后，下界还可以调整的更大）。