目录

9.1 K-means ClusteringP429 K中心点算法K-medoids9.2 Mixtures of GaussiansP433 高斯混合的奇异性9.3 An Alternative View of EMP442 EM观点下的高斯混合P443 EM观点下的K-meansP444 伯努利分布混合模型P228 EM观点下的贝叶斯线性回归9.4 The EM Algorithm in GeneralP454 推广EM算法 generalized EM（GEM）

隐变量的引入使得复对于观测变量的复杂概率表示由简单分量组成

这一章和12、13章的重点都是隐变量

9.1 K-means Clustering

经典聚类算法了，目标函数为失真度量distortion measure

其中rnk∈{0,1}r_{nk} \in \{0, 1\}rnk​∈{0,1}，表示是否nnn属于类kkk

最小化这个东西，导致K-means一定收敛

K-means的初始化很重要。实践中一种好的初始化方法为随机选K个点的集合。K-means算法也用于初始化高斯混合模型的参数直接算K-means很慢，有一些加速方法K-means有一个在线学习算法，将Robbins-Monro算法用于均值估计

P429 K中心点算法K-medoids

K-means对离群点不鲁棒，K-medoids是一种更广泛的方法，其中V(⋅,⋅)\mathcal V(\cdot, \cdot)V(⋅,⋅)是一个距离度量

E步好说，M步不好求，所以经常会把限制类中心在类里的某个数据点上。这样对于第kkk类有NkN_kNk​个数据点，计算复杂度为O(Nk2)O(N_k^2)O(Nk2​)

下图为用K-means做分割（直接在RGB空间度量，这也可以用来做压缩）

9.2 Mixtures of Gaussians

经典算法了

γ(zk)\gamma(z_k)γ(zk​)叫做第kkk类的responsibility责任

该问题没有解析解。EM算法的更新公式为

其中

在梯度优化中，

对于任意给定的最大似然解，KKK个分量混合而成的概率共有K!K!K!个等价的解

在EM算法中，优化的E步算每个点的后验概率，M步算新的π,μ,Σ\pi, \bm \mu, \bm \Sigmaπ,μ,Σ

高斯混合模型的条件分布仍然是高斯混合模型

p(xb∣xa)=∑k=1Kp(k∣xa)p(xb∣xa,k)=∑k=1Kπkp(xa∣k)∑jπjp(xa∣j)p(xb∣xa,k)p(\bm x_b| \bm x_a)=\sum_{k=1}^K p(k|\bm x_a)p(\bm x_b |\bm x_a, k)=\sum_{k=1}^K \frac{\pi_k p(\bm x_a|k)}{\sum_j \pi_j p(\bm x_a|j)}p(\bm x_b |\bm x_a, k)p(xb​∣xa​)=k=1∑K​p(k∣xa​)p(xb​∣xa​,k)=k=1∑K​∑j​πj​p(xa​∣j)πk​p(xa​∣k)​p(xb​∣xa​,k)

见习题9.10

P433 高斯混合的奇异性

如果某一类的均值位于某个数据点上，方差可以无穷小，使对数似然概率达到正无穷，这导致了高斯混合的病态解。

注意，如果只有一类高斯，那么这种病态解是不会存在的，但是如果有多类，那么这种解就会存在，因为可以让另一个类有有限的正常的方差。

如果检测到高斯分量收缩到一个点，那么将它的均值重新设定为一个随机选择的值，并将方差设置为某个较大的值，然后继续优化。

9.3 An Alternative View of EM

PRML的EM算法引入太突兀。看李航《统计学习方法》会好不少。

即利用Jenson不等式构造

B(θ,θ(i))=∑Zp(Z∣X,θ(i))ln⁡p(X,Z∣θ)p(Z∣X,θ(i))B(\theta, \theta(i))=\sum_Z p(Z|X,\theta^{(i)})\ln \frac{p(X,Z|\theta)}{p(Z|X,\theta^{(i)})} B(θ,θ(i))=Z∑​p(Z∣X,θ(i))lnp(Z∣X,θ(i))p(X,Z∣θ)​

抄一张CVMLI的图

E步，把B(θ,θ(i−1))B(\theta, \theta^{(i-1)})B(θ,θ(i−1))换成B(θ,θ(i))B(\theta, \theta^{(i)})B(θ,θ(i))。注意，一定有B(θ(i),θ(i))⩾B(θ(i),θ(i−1))B(\theta^{(i)}, \theta^{(i)})\geqslant B(\theta^{(i)}, \theta^{(i-1)})B(θ(i),θ(i))⩾B(θ(i),θ(i−1))，M步，优化B(θ,θ(i))B(\theta, \theta^{(i)})B(θ,θ(i))中的θ\thetaθ，得到θ(i+1)\theta^{(i+1)}θ(i+1)

CVMLI一书关于EM的描述见EM算法极简总结——CVMLI Prince读书随笔第7章，其中也定义了B函数，只不过参数顺序改了，这两个其实是一回事

PRML书里是这么写的

EM也可以用来找MAP，E步不变（想一下，E步是找关于zzz的函数，和θ\thetaθ无关）M步改成最大化

Q(θ,θold)+ln⁡p(θ)Q(\bm \theta, \bm \theta^{old})+\ln p(\bm \theta) Q(θ,θold)+lnp(θ)

好的先验p(θ)p(\bm\theta)p(θ)会消除高斯混合中的奇异性

P442 EM观点下的高斯混合

全数据对数似然概率公式（全数据这样避免了对数里面的sum）

P443 EM观点下的K-means

考虑高斯混合模型，其中协方差为ϵI\epsilon \bm IϵI，并把它视作一个定值，而不是参数

如果ϵ→0\epsilon \to 0ϵ→0，上下同乘exp⁡{∥xn−μk∥2/2ϵ}\exp \{\|\bm x_n-\bm \mu_k\|^2/2\epsilon\}exp{∥xn​−μk​∥2/2ϵ}，分子为πk\pi_kπk​，对于分母，如果∥xn−μk∥\|\bm x_n - \bm \mu_k\|∥xn​−μk​∥如果不是最小的，则分母会到正无穷，也即γ(znk)=0\gamma(z_{nk})=0γ(znk​)=0，只有最小的距离对应的γ(znk)=1\gamma(z_{nk})=1γ(znk​)=1

μ\bm \muμ的更新公式不变，而π\bm \piπ也能优化，但失去意义（先验在EM里对推算后验没啥用了，高斯分布太极端了）

此时，全数据对数似然变为（这好像没写π\bm \piπ啊）

P444 伯努利分布混合模型

真的是一堆高维伯努利分布（注意高维伯努利分布和多类分布是不一样的）

其中μ={μ1,⋯,μK}\bm \mu = \{\bm \mu_1,\cdots, \bm \mu_K\}μ={μ1​,⋯,μK​}，π={π1,⋯,πK}\bm \pi = \{\pi_1, \cdots, \pi_K\}π={π1​,⋯,πK​}

可以得到均值和方差分别为（实际上混合分布的均值和方差都可以这么写，见习题9.12）

开始EM，先写出

联合数据的对数最大似然

其中E步后验为

在M步，可以求出每类系数

其中

类的先验概率为

混合伯努利分布中，不同于高斯混合，没有奇异性。对数似然概率不会到正无穷，存在对数似然概率极低的病态情况，但是只要初始化的合理，就没问题，毕竟EM只会把对数最大似然往上提

示例，{2,3,4}\{2,3,4\}{2,3,4}三类二值图像：伯努利分布的先验是Beta分布，可以引入，当作对xxx的额外观测（想象一下Beta分布的含义）

如果即对μ\bm \muμ加上伯努利分布先验，又对π\bm \piπ加上迪利克雷分布先验，则更新公式为（习题9.18）

类内的伯努利分布也可以推广到多类分布，对应共轭分布先验是迪利克雷分布

P228 EM观点下的贝叶斯线性回归

在第三章中，计算模型证据，用MLE找超参数α,β\alpha,\betaα,β

可以把w\bm ww视作隐变量，这样就可以用EM了！

对w\bm ww的后验求期望，得到E步

M步，求导后得到

这和第三章的形式稍有区别，但会收敛到同样的结果，（如果能收敛到同一个局部极小值的话）。注意第三章中极小值导数为0的等式（注意逆矩阵特征值为原矩阵的倒数）

EM也可以用于求RVM中的α,β\alpha, \betaα,β，w\bm ww的先验为。RVM和贝叶斯线性回归的证据函数很像，只不过就是α\alphaα打散了

E步有w\bm ww后验

其中Φ∈RN×M,A=diag(αi)\bm \Phi \in \mathbb R^{N\times M}, \bm A=\text{diag}(\alpha_i)Φ∈RN×M,A=diag(αi​)

M步优化参数

可以看出，这和第七章的极值点情况一样

9.4 The EM Algorithm in General

（这一块内容感觉博客没组织好），其实还是在说ln⁡p(X∣θ)\ln p(\bm X|\bm \theta)lnp(X∣θ)这个事情

我们假定直接优化p(X∣θ)p(\bm X|\bm \theta)p(X∣θ)很难，但优化p(X,Z∣θ)p(\bm X, \bm Z|\bm \theta)p(X,Z∣θ)很容易。从而

其中定义了

注意L(q,θ)\mathcal L(q,\bm \theta)L(q,θ)是一个泛函

E步：当q(Z)=p(Z∣X,θold)q(\bm Z)=p(\bm Z|\bm X, \bm \theta^{old})q(Z)=p(Z∣X,θold)，L(q,θ)\mathcal L(q,\bm \theta)L(q,θ)达到最大M步：

其实就是在优化如下的Q\mathcal QQ，这样能优化L\mathcal LL，L\mathcal LL是ln⁡p(X∣θ)\ln p(\bm X|\bm \theta)lnp(X∣θ)的下界。注意L\mathcal LL抬升，必然导致对数似然的抬升，因为KL那一项更高了。。。

EM的总体优化感受如图（跟上面CVMLI那图差不多）

注意蓝线和红线相切那一点，也就是E步之后那一点，可以证明两线是相切的。（ 习题9.25）

如果p(Z,X∣θ)p(\bm Z,\bm X|\bm \theta)p(Z,X∣θ)是指数族函数的话，ln⁡\lnln会使得指数消失，非常方便。EM方便的地方还是在于把ln⁡\lnln里面对于隐变量积分的操作去掉了，算起来容易！

对于指数族分布混合来说，上图蓝线是上凸函数（我也不知道为啥）

对于带先验p(θ)p(\bm \theta)p(θ)的情况，EM的原理分析类似

对于iid的数据集

也即zn\bm z_nzn​只和xn\bm x_nxn​有关，和其他x\bm xx无关。这使得EM也可以在每轮迭代中只采用一个数据点。。如果混合分量是指数族，则新数据点的后验（responsibility）是充分统计量，只更新一个数据点的后验即可。例如高斯混合模型中，对于数据点mmm的迭代（习题9.26）

其中

方差和混合系数也能写出来（习题9.27）

这样EM的计算速度就和数据量无关了。这种EM收敛更快。注意和梯度下降不同的是，这种EM仍然保证L\mathcal LL单调递增！

P454 推广EM算法 generalized EM（GEM）

EM让E步和M步都变得可解，如果E步和M步仍然不可解，那么就需要generalized EM（GEM）。

对于优化M步，方法可以是 在M步用共轭梯度法之类的非线性优化方法期望条件最大化expectation conditional maximization（ECM），在M步中进行了若干具有限制条件的优化，例如把参数划分为若干组，M步被分为很多步，每一步只优化一个子集参数 对于优化E步，方法可以是 对q(Z)q(\bm Z)q(Z)也进行局部优化

参考文献：

[1] Christopher M. Bishop. Pattern Recognition and Machine Learning.

PRML第九章读书笔记——Mixture Models and EM K均值/K中心点 高斯混合奇异性 EM观点下的高斯混合/K-means/混合伯努利分布/贝叶斯线性回归 推广EM算法