Chapter 9 混合模型和EM

第九章的前面几节介绍了k-means, k-medoids, 混合高斯模型(GMM)等算法，并以GMM为例子介绍了EM算法

本节主要记录EM算法的理解

EM 的一种观点

引入辅助隐变量\(Z\), 对数似然函数变为

实际情况下没有完整数据集\(\{X, Z\}\), 只有\(X\), 因此\(Z\)的取值只来自于后验概率分布 \(lnp\{Z|X,\theta\}\)

当后验估计得到\(Z\)之后，根据完整数据集\(\{X, Z\}\)推断对数似然函数是很容易的。

EM的步骤如下：

以上的M步骤做的是Maximum Likelihood Estimation(MLE), 如果优化目标加上参数的先验分布\(p(\theta)\), 则变成了Maximum posterior probability (MAP), 可以避免病态解

###GMM 例子

GMM的EM步骤如下

其中\(\gamma\)就是关键的隐变量，表示每个点属于各个高斯模型的概率分布

让我们重新考察高斯混合模型

M步骤

GMM中完整的数据集的似然函数为

对应的对数似然函数为

可以据此方便地求出模型参数\(\mu, \Sigma, \pi\)

E步骤

隐变量\(Z\)的后验概率分布为

从而得到

伯努利分布的混合

模型也被称为潜在类别分析 (latent class analysis)

类似，自己试着推导

一般形式的EM算法

\(\mathcal{L}(q, \theta)\)是\(ln\ p(X|\theta)\)的一个下界，称作 Evidence Lower Bound (ELOB) [1]

我们可以使用该公式来定义EM算法，证明它确实最大化了对数似然函数

E 步骤

当\(\theta\)给定为\(\theta^{old}\)时，优化\(q = p, s.t. KL(q||p) = 0\),也就是令\(Z\)的近似分布为后验概率分布\(p(Z|X,\theta)\)

则在\(\theta^{old}\)点， \(\mathcal{L}(q, \theta)\)逼近\(ln\ p(X|\theta)\)

M 步骤

分布\(q(Z)\)固定，对下界 \(\mathcal{L}(q, \theta)\)对参数\(\theta\)最大化，得到\(\theta^{new}\)

\(L(q, \theta) = Q(\theta, \theta^{old}) + H(q)\), 即这里优化的\(L\)与前面的\(Q\)在\(q\)给定下只差了一个常数项\(H(q)\)

整个EM过程如图

我的理解

用矩阵的形式理解多维概率 (画个图？)，EM的本质是在待优化变量中引入隐变量，相当于2个变量。 观测数据X是固定的，在“二维空间”\((Z, \theta)\)中搜索最优值。EM的两个步骤相当于固定一个优化另一个，有点类似于坐标轴轮换的梯度下降(坐标上升法)，只要问题是凸的，就可以收敛到最优点，当然不是凸的情况下可能收敛到maximal 注意理解，无论哪个优化式子都是这个联合分布，只是哪个看作是已知的，如果\(\theta\)看作是已知，那么已经归一化了。而其它的看看作是已知的可能需要归一化，但是点估计的话，不用归一化系数也可以

GEM

对于复杂的模型来说，E步骤或者M步骤仍然无法计算。推广EM算法(generalized EM algorithm)解决的是E, M步骤无法计算的问题。本质上就是原先E, M每次优化都是求最优的解，而GEM迭代地优化，每次只去找到一个可以优化目标的点。

一种使用GEM的方法是在M步骤中使用某种非线性最优化策略，例如共轭梯度算法。 另一种形式的GEM算法，被称为期望条件最大化算 法(expectation conditional maximization algorithm)，或者简称ECM算法，涉及到在每个M步骤 中进行若干了具有限制条件的最优化

这样做可以增量迭代求解，类似于梯度下降这类算法，每步的计算量小，但是速度快，迭代收敛(因为收敛性没变，每次都能保证比上一次优)

参考资料

[1] http://www-staff.it.uts.edu.au/~ydxu/ml_course/variational.pdf