EM算法
（1）琴生不等式（Jensen’s inequality）
如果函数$f(X)$是一个凸函数(convex function)，$X$是随机变量。我们有
相反，如果函数$f(X)$是一个凹函数(concave function)，则有
如果函数$f(X)$是严格凸(strictly convex)的，使不等式等号成立的充要条件是$P(X=\mathrm{E}[X]) = 1$，随机变量X是一个常数。
凸函数和凹函数的定义：若一个函数二阶可导，且$f^{\prime \prime}(x) \geq 0(\forall x \in \mathbb{R})$。或者如果函数的输入是一个向量，其Hessian矩阵是半正定的$H \succeq 0$。则函数是个凸函数。注意这是充分不必要条件，凸函数也可能是不可导的。相反，如果$f^{\prime \prime}(x) \leq 0(\forall x \in \mathbb{R})$或者$H \preceq 0$，则函数是凹函数。
如果$f^{\prime \prime}(x) > 0(\forall x \in \mathbb{R})$或者$H \succ 0$，则称$f(X)$是严格凸(strictly convex)的。凹函数同理。
（2）the EM algorithm
假设我们有一个估计问题，有一个训练集：$\left{x^{(1)}, \ldots, x^{(m)}\right}$，其中包含m个独立的样本。我们的模型是$p(x, z; \theta)$。我们希望拟合模型的参数$\theta$，模型的对数似然是：
其中$z^{(i)}$是隐变量，是未知的，观察不到的。EM算法能有效地求解含隐变量最大似然估计问题。因为$z^{(i)}$是隐变量，显式地求解这个似然$\ell(\theta)$很难。EM算法的策略就是不断地为对数似然构建一个下界(lower-bound)(E-step)，然后优化这个下界(M-step)。
对每个样本，随机变量$z^{(i)}$具有某种分布$Q{i}$，满足$(\sum{z} Q{i}(z)=1, Q{i}(z) \geq 0)$。
最后一步利用了琴生不等式，因为$f(x)=\log (x)$ 是一个严格凹函数，其二阶导$f^{\prime \prime}(x)=-1 / x^{2}<0$。
通过琴生不等式，我们有：
下标$z^{(i)} \sim Q{i}$表明这个期望是关于变量$z^{(i)}$的，其分布为$Q{i}$。
现在，对任意分布$Q{i}$，我们给出了似然$\ell(\theta)$的下界。$Q{i}$的分布有无数可能，我们选择哪一个比较好呢？给定当下对参数$\theta$的猜测，我们希望选择一个$Q_{i}$，使这个下界紧贴着我们的似然$\ell(\theta)$。根据琴生不等式等号成立的条件，我们需要
其中c是常量，说明：
而我们又知道：
所以：
所以，使琴生不等式等号成立，我们只需要令$Q_{i}$等于随机变量$z^{(i)} \mid x^{(i)}$的后验分布。
EM算法的步骤
Repeat until convergence {
(E-step) For each $i$, set
(M-step) Set
}
随着算法不断迭代，为什么这个算法会收敛呢？为什么对数似然会单调递增呢？假设我们迭代第t步，参数为$\theta^{(t)}$，在E-step我们选择$Q_{i}^{(t)}\left(z^{(i)}\right):=p\left(z^{(i)} \mid x^{(i)} ; \theta^{(t)}\right)$，这个选择确保琴生不等式等号成立，也就是在$\theta^{(t)}$时，似然紧贴着它的下界。我们有：
我们在M-step找一个$\theta^{(t+1)}$，
我们有
所以
所以EM算法一定是单调收敛的。
其实可以把EM算法看成是coordinate ascent。E-step看成是固定$\theta$优化$Q$。M-step可以看成是固定$Q$优化$\theta$。