EM算法是期望最大化 (Expectation Maximization) 算法的简称，用于含有隐变量的情况下，概率模型参数的极大似然估计或极大后验估计。EM算法是一种迭代算法，每次迭代由两步组成：E步，求期望 (expectation)，即利用当前估计的参数值来计算对数似然函数的期望值；M步，求极大 (maximization)，即求参数\(\theta\) 来极大化E步中的期望值，而求出的参数\(\theta\)将继续用于下一个E步中期望值的估计。EM算法在机器学习中应用广泛，本篇和下篇文章分别探讨EM算法的原理和其两大应用 —— K-means和高斯混合模型。
凸函数、凹函数和 Jensen不等式
设\(f(x)\)为定义在区间\(I = [a,b]\)上的实值函数，对于任意\(\forall \, x_1, x_2 \in I, \lambda \in [0,1]\)，有：
\[
f(\lambda \,x_1 + (1-\lambda)\,x_2) \leq \lambda f(x_1) + (1-\lambda)f(x_2)
\]
则\(f(x)\)为凸函数 (convex function)，如下图所示。相应的，若上式中 \(\leqslant\) 变为 \(\geqslant\) ，则\(f(x)\)为凹函数 (concave function)。 凸函数的判定条件是二阶导 \(f^{''}(x) \geqslant 0\)，而凹函数为 \(f^{''}(x) \leqslant 0\) 。后文要用到的对数函数\(ln(x)\)的二阶导为\(-\frac{1}{x^2} < 0\)，所以是凹函数。
Jensen不等式就是上式的推广，设\(f(x)\)为凸函数，\(\lambda_i \geqslant 0, \;\; \sum_i \lambda_i = 1\)，则：
\[
f\left(\sum\limits_{i=1}^n \lambda_i x_i\right) \leq \sum\limits_{i=1}^n \lambda_i f(x_i)
\]
如果是凹函数，则将不等号反向，若用对数函数来表示，就是：
\[
ln\left(\sum\limits_{i=1}^n \lambda_i x_i\right) \geq \sum\limits_{i=1}^n \lambda_i ln(x_i)
\]
若将\(\lambda_i\)视为一个概率分布，则可表示为期望值的形式，在后文中同样会引入概率分布：
\[
f(\mathbb{E}[\mathrm{x}]) \leq \mathbb{E}[f(\mathrm{x})]
\]
KL散度
KL散度(Kullback-Leibler divergence) 又称相对熵 (relative entropy)，主要用于衡量两个概率分布p和q的差异，也可理解为两个分布对数差的期望。
\[
\mathbb{KL}(p||q) = \sum_i p(x_i)log \frac{p(x_i)}{q(x_i)}= \mathbb{E}_{\mathrm{x}\sim p}\left[log \frac{p(x)}{q(x)}\right] = \mathbb{E}_{\mathrm{x}\sim p}\left[log\,p(x) - log\,q(x) \right ]
\]
KL散度总满足\(\mathbb{KL}(p||q) \geqslant 0\)，而当且仅当\(q=p\)时，\(\mathbb{KL}(p||q) = 0\) 。 一般来说分布\(p(x)\)比较复杂，因而希望用比较简单的\(q(x)\)去近似\(p(x)\)，而近似的标准就是KL散度越小越好。
KL散度不具备对称性，即\(\mathbb{KL}(p||q) \neq \mathbb{KL}(q||p)\)，因此不能作为一个距离指标。
极大似然估计和极大后验估计
极大似然估计 (Maximum likelihood estimation) 是参数估计的常用方法，基本思想是在给定样本集的情况下，求使得该样本集出现的“可能性”最大的参数\(\theta\)。将参数\(\theta\)视为未知量，则参数\(\theta\)对于样本集X的对数似然函数为：
\[
L(\theta) = ln \,P(X|\theta)
\]
这个函数反映了在观测结果X已知的条件下，\(\theta\)的各种值的“似然程度”。这里是把观测值X看成结果，把参数\(\theta\)看成是导致这个结果的原因。参数\(\theta\)虽然未知但是有着固定值 (当然这是频率学派的观点)，并非事件或随机变量，无概率可言，因而改用 “似然(likelihood)" 这个词。
于是通过求导求解使得对数似然函数最大的参数\(\theta\)，\(\theta = \mathop{\arg\max}\limits_{\theta}L(\theta)\)，即为极大似然法。
极大后验估计 (Maximum a posteriori estimation) 是贝叶斯学派的参数估计方法，相比于频率学派，贝叶斯学派将参数\(\theta\)视为随机变量，并将其先验分布\(P(\theta)\)包含在估计过程中。运用贝叶斯定理，参数\(\theta\)的后验分布为：
\[
P(\theta|X) = \frac{P(X,\theta)}{P(X)} = \frac{P(\theta)P(X|\theta)}{P(X)} \propto P(\theta)P(X|\theta)
\]
上式中\(P(X)\)不依赖于\(\theta\)因而为常数项可以舍去，则最终结果为 \(\theta = \mathop{\arg\max}\limits_{\theta}P(\theta)P(X|\theta)\)