第七章 K-均值 混合模型与期望最大 K-Means, Mixed Model & Expected Maximum

K-Means、混合高斯和EM算法原理、性质

7.1 EM算法

EM算法

EM算法（Expectation-maximization）：期望最大算法，是一种从不完全数据或有数据丢失的数据集（存在隐含变量）中求解概率模型参数的最大似然估计方法。

EM（Expectation-Maximum）算法也称期望最大化算法，是最常见的隐变量估计方法，在机器学习中有极为广泛的用途，例如常被用来学习高斯混合模型（Gaussian mixture model，简称GMM）的参数；隐式马尔科夫算法（HMM）、LDA主题模型的变分推断等等。

EM算法是一种迭代优化策略，由于它的计算方法中每一次迭代都分两步，其中一个为期望步（E步），另一个为极大步（M步），所以算法被称为EM算法（Expectation-Maximization Algorithm）。

EM算法受到缺失思想影响，最初是为了解决数据缺失情况下的参数估计问题.

EM算法的基本思想

• 首先根据己经给出的观测数据，估计出模型参数的值；
• 然后再依据上一步估计出的参数值估计缺失数据的值；
• 再根据估计出的缺失数据加上之前己经观测到的数据重新再对参数值进行估计；
• 然后反复迭代，直至最后收敛，迭代结束。

预备知识：“极大似然估计”和“Jensen不等式”。

极大似然估计：

Jensen不等式：

例

目前有100个男生和100个女生的身高，但是我们不知道这200个数据中哪个是男生的身高，哪个是女生的身高，即抽取得到的每个样本都不知道是从哪个分布中抽取的。对于每个样本，就有两个未知量需要估计：
（1）这个身高数据是来自于男生数据集合还是来自于女生？
（2）男生、女生身高数据集的正态分布的参数分别是多少？

具体的身高问题使用EM算法求解步骤

（1）初始化参数：先初始化男生身高的正态分布的参数：如均值=1.65，方差=0.15
（2）计算每一个人更可能属于男生分布或者女生分布；
（3）通过分为男生的n个人来重新估计男生身高分布的参数（最大似然估计），女生分布也按照相同的方式估计出来，更新分布。
（4）这时候两个分布的概率也变了，然后重复步骤（1）至（3），直到参数不发生变化为止。

EM算法流程

EM的算法步骤：

• 初始化分布参数θ（我们最终需要的模型参数）；
• E：根据当前参数θ计算出隐性变量的后验概率，然后计算在该后验概率下全数据对数似然的期望。
• M：通过最大化全数据对数似然的期望来求新的参数θ。
• 然后不断的迭代，就可以得到理想的θ。

EM算法实例

假设有A，B两枚硬币，其中正面朝上的概率分别为 ${\theta }_A$, ${\theta }_B$，这两组参数需要估计

设计5组实验，每次实验投掷5次硬币，但是每次实验都不知道用哪一枚硬币进行的本次实验。投掷结束后，会得到一个数组 $x=\{x_1,x_2,\dots ,x_5\}$，表示每组实验有几次硬币正面朝上， $0\le x_1\le 5$

假设5次试验的结果如下：

随机选取 ${\theta }_A$, ${\theta }_B$ 的初始值，比如 ${\theta }_A=0.2$, ${\theta }_B=0.7$

对于第一组实验，3正面2反面。

如果是 A 硬币得到这个结果的概率为: $0.2^3\times 0.8^2=0.00512$
如果是 B 硬币得到这个结果的概率为: $0.7^3\times 0.3^2=0.03087$

因此，第一组实验结果是A硬币得到的概率为：$0.00512/(0.00512+0.03087)=0.14$，第一组实验结果是B硬币得到的概率为：$0.03087/(0.00512+0.03087)=0.86$。

整个5组实验的A,B投掷概率如下：

根据隐含变量的概率，可以计算出两组训练值的期望。依然以第一组实验来举例子：3正2反中，如果是A硬币投掷的结果：$0.14\ast 3=0.42$个正面和$0.14\ast 2=0.28$个反面；如果是B硬币投掷的结果：$0.86\ast 3=2.58$个正面和$0.86\ast 2=1.72$个反面。

5组实验的期望如下表：

通过计算期望，我们把一个有隐含变量的问题变化成了一个没有隐含变量的问题，由上表的数据，估计 ${\theta }_A$, ${\theta }_B$ 变得非常简单。

$$\begin{array}{rl}& {\theta }_A=4.22/(4.22+7.98)=0.35\\ & {\theta }_B=6.78/(6.78+6.02)=0.5296875\end{array}$$

重新回到第一组实验，3正面2反面。。。依次迭代

7.2 ★聚类与 K-均值

聚类

基本思想

将相似的实例分组在一起

例子：2D 点的模式

“相似”是什么意思？

一种选择：欧式距离 $dist(x,y)={\Vert x-y\Vert }_2^2$

聚类结果在很大程度上取决于待聚类点之间的相似性（或距离）度量

聚类算法

• 原型聚类：k均值算法、高斯混合聚类
• 密度聚类：DBSCAN算法、Mean-Shift 算法
• 层次聚类：Agglomerative 算法、Divisive算法、BIRCH 算法
• 谱聚类

聚类例子

• 图像分割（目标：将图像分割成有意义的或感知上相似的区域）
• 基因表达数据聚类
• 聚类新闻文章
• 进化树

K-均值聚类

K-均值

对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。

K-均值的数据表达式表示

在 $D$ 维的欧式空间里，给定数据集 $\{x_1,...x_N\}$，划分为 $k$ 个簇（或类），这是给定的 $k$ 个编码之一。

引入指标变量

$$r_{nk}\in \{0,1\},k=1,...,K$$

表示数据点 $x_n$ 属于 $K$ 个聚类中的哪⼀个。

失真度量：平方误差和

$$J=\sum _{n=1}^N\sum _{k=1}^K{r}_{nk}||x_n-{\mu }_k|{|}^2$$

• $u_k$：K 簇中心

⽬标是找到 $r_{nk}$ 和 ${\mu }_k$ 的值，使得 $J$ 达到最⼩值。

我们可以⽤⼀种迭代的⽅法完成这件事，其中每次迭代涉及到两个连续的步骤，分别关于 $r_{nk}$ 的最优化和 ${\mu }_k$ 的最优化。

K-均值的两个更新阶段

首先选择 ${\mu }_k$ 的初始值

• 第一阶段：我们关于 $r_{nk}$ 最小化 $J$，保持 ${\mu }_k$ 固定
• 第二阶段：我们关于 ${\mu }_k$ 最小化 $J$，保持 $r_{nk}$ 固定

两个阶段分别对应于EM算法中的E（期望）步骤和M（最⼤化）步骤

• 期望： 什么是期望的分类
• 最大化：最大似然估计的是什么

E 步骤：参数 $r_{nk}$ 的选择

由于 $J={\sum }_{n=1}^N{\sum }_{k=1}^K{r}_{nk}||x_n-{\mu }_k|{|}^2$ 是一个关于 $r_{nk}$ 线性函数 ，这个优化问题有解析解。

有不同的 $n$ 的项是相互独⽴的，因此可以对每个 $n$ 分别进⾏最优化，只要 $k$ 的值使 $||x_n-{\mu }_k|{|}^2$ 最⼩，就令 $r_{nk}$ 等于 $1$。

因此

$$r_{nk}=\{\begin{array}{l}1,如果k=\arg {\min }_j\Vert {\mathbf{x}}_n-{\mathbf{\mu }}_j{\Vert }^2\\ 0,其他情况\end{array}$$

解释：将 $x_n$ 分到与之最近的类。

M 步骤：优化 ${\mu }_k$

固定 $r_{nk}$，⽬标函数 $J={\sum }_{n=1}^N{\sum }_{k=1}^K{r}_{nk}||x_n-{\mu }_k|{|}^2$ 是 ${\mu }_k$ 的⼀个⼆次函数，令它关于 ${\mu }_k$ 的导数等于零，即可达到最⼩值，即

$$2\sum _{n=1}^N{r}_{nk}({\mathbf{x}}_n-{\mathbf{\mu }}_k)=0$$

解出结果为

$${\mu }_k=\frac{{\sum }_n{r}_{nk}{x}_n}{{\sum }_n{r}_{nk}}$$

其中 ${\sum }_n{r}_{nk}$ 等于分配给类别 $k$ 的点数。

解释：令 ${\mu }_k$ 等于类别 $k$ 的所有数据点的均值。

K-均值算法终止

K均值（K-means）算法两个阶段

• 重新分配数据点给簇（或类）
• 重新计算簇（或类）中心

直到聚类的分配不改变。

由于每个阶段都减⼩了⽬标函数 $J$ 的值，因此算法的收敛性得到了保证。

但可能陷入 $J$ 的局部极值。

K-均值示例

Old Faithful Data 数据集

迭代后的代价函数：

J是老忠实间歇喷泉数据的代价函数。

我们故意将聚类中⼼选择了较差的初始值，从⽽算法在收敛之前执⾏了若⼲步，更好的选择是将聚类中⼼选择为由k个随机数据点组成的⼦集。

K均值算法本身经常被用于在EM算法之前初始化高斯混合模型的参数。

K-均值算法的性质

保证在有限次迭代中收敛

每次迭代的训练时间：

1. 将数据点分配到最近的群集中心
   O(KN)
2. 根据分配的点改变聚类中心
   O(N)

K-均值的局限

K-均值 Getting Stuck

一个局部最优

在这里有一个类会更好：

这里两个类会更好：

K均值陷入局部极值

一个不好的局部最优：

目标函数J是非凸的（因此不保证J上的坐标下降收敛到全局最小值）

没有什么办法能阻止k均值陷入局部极小值

我们可以尝试更多随机初始化的点

我们可以尝试非局部拆分和合并操作

• 同时合并相邻的两个簇
• 将一个大的簇分成两个

软分配

在每⼀次迭代中，每个数据点被分配到⼀个唯⼀的聚类中（“硬”分配），某些点可能到两个聚类中心的距离相等。

通过使⽤概率的⽅法，我们得到对数据点聚类的“软”分配，它反映出在最合适聚类分配上的不确定性。

K-均值应用：图像分割和压缩

目标：将图像分割成若干的区域

• 每个区域有⼀个相对相似的视觉外观
• 或者对应于某个物体
• 或物体的⼀部分

每个像素是⼀个3维空间中的⼀个点，三维空间由{红、绿、蓝} 通道的三个亮度值构成

每个值由8比特的精度存储

K均值聚类与K个颜色的调色板一起使用

该方法没有考虑不同像素的空间上的近似性

K-均值用于图像分割

选择2、3和10种颜色对彩色图像进行编码的两个示例

数据压缩

无损数据压缩：能够从压缩的表⽰中精确地重建原始数据

有损数据压缩：接受重建过程中出现的⼀些错误

K-均值应用于有损数据压缩

• 对于N个数据点中的每⼀个，只存储它被分配的聚类种类k，Nlog2 K
• 同时存储了K个聚类中⼼ ${\mu }_k$ 的值，其中K<<N，24K
• 每个数据点都根据它最近的中心 ${\mu }_k$ 确定
• 首先找到最近的 ${\mu }_k$，然后存储标签K而不是原始的数据向量，

这个框架被称为向量量子化（vector quantization），向量 ${\mu }_k$ 被称为编码书向量（code-book vector）

数据压缩完成

• 假设原始图像有N个像素，直接传递整幅图像需要24N⽐特。
• 传递压缩图像所需的⽐特总数为24K + N log2 K
• 当K=2，3以及10时，压缩为原来的比例分别为4%，8%，17%

7.3 ★混合高斯模型与期望最大

高斯模型

单高斯模型

一维高斯分布的概率密度函数如下

$$f(x)=\frac{1}{\sqrt{2\pi }\sigma }\exp \left(-\frac{{\left(x-\mu \right)}^2}{2{\sigma }^2}\right)$$

二维高斯模型

服从二维高斯分布的数据主要集中在一个椭圆内部
服从三维的数据集中在一个椭球内部……

混合高斯模型

为什么要有混合高斯模型?

越靠近椭圆的中心样本出现的概率越大，这是由概率密度函数决定的，

但是这个单高斯分布的椭圆中心的样本量极少，不合理，

求解两个或多个高斯模型，并通过一定的权重将其高斯模型融合成一个模型，即最终的混合高斯模型

高斯混合模型 (GMM)

高斯混合概率分布可以写成高斯分布的线性叠加的形式

一个高斯混合模型能表示成如下分布

$$p(\mathbf{x})=\sum _{k=1}^K{\pi }_k\mathcal{N}(\mathbf{x}|{\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k)$$

其中混合系数满足

$$\begin{gathered} 0\le {\pi }_k\le 1 \\ \sum _{k=1}^K{\pi }_k=1 \end{gathered}$$

某个混合高斯模型融合的高斯模型个数足够多，它们之间的权重设定得足够合理，这个混合模型可以拟合任意分布的样本。

GMM是一个密度估计器
神经网络是通用的函数逼近方法
GMMs 是通用的密度逼近方法（只要有足够的高斯），甚至对角的GMMs都是通用的逼近器

混合高斯模型的边缘分布

一维高斯混合函数的边缘分布

二维高斯混合函数的边缘分布

GMM 和隐变量

引入离散潜在变量 $z$ 来描述高斯混合模型，更深刻地认识这个重要的分布，开始了解期望最⼤化算法。

$K$ 个高斯分布的线性叠加

$$p(\mathbf{x})=\sum _{k=1}^K{\pi }_k\mathcal{N}(\mathbf{x}\mid {\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k)$$

引入一个 $K$ 维的二值随机变量 $z$，用1-of-K表示（one-hot 向量）：使 $Z=z_1,...,z_K$，其中 $z_k\in \{0,1\}$ and ${\sum }_k{z}_k=1$，向量 $Z$ 有 $K$ 个可能的状态。

确定边缘概率分布 $p(\mathbf{z})$

将概率与每个组件 $z_k$ 相关联，$z$ 的边缘概率分布根据混合系数 ${\pi }_k$ 进⾏赋值，即其中 $k$ 满足 $p(z_k=1)={\pi }_k$，$0\le {\pi }_k\le 1$ and ${\sum }_k{\pi }_k=1$

由于 $z$ 使用了“1-of-K”表示方法，因此也可以写成

$$p(\mathbf{z})=\prod _{k=1}^K{\pi }_k^{z_k}$$

当有一个分量时，$p(z_1)={\pi }_1^{z_1}$
当有两个分量时，$p(z_1,z_2)={\pi }_1^{z_1}{\pi }_2^{z_2}$

确定条件概率 $p(\mathbf{x}|\mathbf{z})$

给定z的⼀个特定的值，x的条件概率分布是⼀个高斯分布

$$p(\mathbf{x}\mid z_k=1)=\mathcal{N}(\mathbf{x}\mid {\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k)$$

因此条件概率p(x|z)可以写成如下形式

$$p(\mathbf{x}\mid z)=\prod _{k=1}^K\mathcal{N}(\mathbf{x}\mid {\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k{)}^{z_k}$$

由于指数 $Z_k$，除一个乘积项外其余的都等于1

联合分布 $p(\mathbf{x},\mathbf{z})$

定义隐变量和观测变量的联合分布

$$p(\mathbf{x},\mathbf{z})=p(\mathbf{x}|\mathbf{z})\cdot p(\mathbf{z})$$

其中

• $\mathbf{x}$ 为观测变量
• $\mathbf{z}$ 为隐变量
• $p(\mathbf{z})$ 为边缘分布
• $p(\mathbf{x}|\mathbf{z})$ 为条件分布

x为观测变量，z为潜在变量（值未被观测的变量，潜在的不是显现的,隐含变量）：如父母对子女的成就期望是不可以被直接观察到的。其强度或结构可变。

边缘概率分布 $p(\mathbf{x})$

联合分布 $p(x,z)=p(z)p(x|z)$，因此 $x$ 的边缘概率分布可以通过将联合概率分布对所有可能的 $z$ 求和的方式得到，即

$$\begin{array}{rl}p(x)& =\sum _{z}p(z)p(x|z)\\ & =\sum _z\left(\prod _{k=1}^K{\pi }_k^{z_k}\mathcal{N}(\mathbf{x}|{\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k{)}^{z_k}\right)\\ & =\sum _{k=1}^K{\pi }_k\mathcal{N}(x|{\mu }_k,{\mathbf{\Sigma }}_k)\end{array}$$

$$z_k\in \{0,1\}$$

$x$ 的分布是高斯混合模型的标准形式。

对联合概率分布 $p(x,z)$ 操作，⽽不是对边缘概率分布 $p(x)$ 操作，这会产⽣极⼤的计算上的简化。

$p(x)$ 的边缘分布与 $k$ 个 Gaussian 的线性组合一致。

另一个条件概率 $p(\mathbf{z}|\mathbf{x})$

另一个起重要作用的是给定 $x$ 的条件下，$z$ 的条件概率 $p(z|x)$ (Responsibility)

用 $\gamma (z_k)$ 表示概率 $p(z_k=1|x)$

由贝叶斯定理得到

$$\begin{array}{rl}\gamma (z_k)\equiv p(z_k=1|\mathbf{x})& =\frac{p(z_k=1)p(\mathbf{x}|z_k=1)}{{\sum }_{j=1}^{K}p(z_j=1)p(\mathbf{x}|z_j=1)}\\ & =\frac{{\pi }_k\mathcal{N}(\mathbf{x}|{\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k)}{{\sum }_{j=1}^K{\pi }_j\mathcal{N}(\mathbf{x}|{\mathbf{\mu }}_j,{\mathbf{\Sigma }}_j)}\end{array}$$

我们将 $p(z_k=1)={\pi }_k$ 看成 $z_k=1$ 的先验概率，$\gamma (z_k)=p(z_k=1|x)$ 看成观测到 $x$ 之后后验概率，也可以被看做分量 $k$ 对于“解释”观测值 $x$ 的“责任”（responsibility）贡献或权重。

“责任”(Responsibility) 的描述

GMM 的最大似然

假设我们有⼀个观测的数据集 $\{x_1,...x_N\}$，我们希望使用混合高斯模型来对数据进行建模（$N$ 条数据，维度都为 $D$）

数据集可以表示成 $N\times D$ 的矩阵 $X=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_N\end{array}\right]$，其中第 $n$ 行为 $x_n^T=\left[\begin{array}{cccc}{x}_{n1}& x_{n2}& \cdots & x_{nD}\end{array}\right]$

对应隐含变量会被表示为⼀个 $N\times D$ 的矩阵 $Z=\left[\begin{array}{c}{z}_1\\ z_2\\ ⋮\\ z_N\end{array}\right]$，其中第 $n$ 行为 $z_n^T=\left[\begin{array}{cccc}{z}_{n1}& z_{n2}& \cdots & z_{nK}\end{array}\right]$

目标是表示这个似然函数，从而通过最大化似然函数来估计这三组参数 ${\pi }_k,{\mu }_k,{\Sigma }_k$

GMM 的似然函数

$$\begin{gathered} p(\mathbf{t}\mid X,w,\beta )=\prod _{n=1}^N\mathcal{N}(t_n\mid {\mathbf{w}}^T\varphi ({\mathbf{x}}_n),{\beta }^{-1}) \\ \ln p(\mathbf{t}\mid \mathbf{w},\beta )=\sum _{n=1}^N\ln \mathcal{N}(t_n\mid {\mathbf{w}}^T\varphi ({\mathbf{x}}_n),{\beta }^{-1}) \end{gathered}$$

混合密度函数为

$$p(x)=\sum _{k=1}^K{\pi }_k\mathcal{N}(\mathbf{x}\mid {\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k)$$

因此似然函数为

$$p(X\mid \pi ,\mu ,\Sigma )=\prod _i^N\left\{\sum _{i=1}^K{\pi }_{{}_k}N({\mathbf{x}}_{{}_n}\mid {\mu }_{{}_k},{\Sigma }_{{}_k})\right\}$$

因此对数似然函数为

$$\ln p(X\mid \pi ,\mu ,\Sigma )=\sum _{n=1}^N\ln \left\{\sum _{k=1}^K{\pi }_k\mathcal{N}({\mathbf{x}}_n\mid {\mu }_k,{\Sigma }_k)\right\}$$

这是一个比单一高斯更难的问题

最大化对数似然函数

目标是估计以下三个参数集 ${\pi }_k,{\mu }_k,{\Sigma }_k$。

在保持其他导数不变的情况下，依次求导数，但是没有解析解，这项任务并不简单，因为对 $k$ 的求和出现在对数计算内部，从而对数函数不再直接作用于高斯分布。

虽然基于梯度的优化是可能的。我们考虑更一般的迭代EM算法。

GMM 最大似然估计的一些问题

在最大化似然函数之前，简单地提两个技术问题：

• 病态解，即高斯混合的奇异性问题
• 混合的可区分问题

病态解

病态解：高斯分量会收缩到一个点，混合模型产生奇异性。

考虑一个高斯混合模型：它的分量的协方差矩阵为：${\mathbf{\Sigma }}_k={\sigma }_k^2\mathbf{I}$

若混合模型的第 $j$ 个分量的均值 ${\mu }_j$ 与某个数据点完全相同，即对于某个 $n$ 值，${\mu }_j=x_n$，这个数据点为似然函数贡献一项，形式为：

$$\mathcal{N}({\mathbf{x}}_n\mid {\mathbf{x}}_n,{\sigma }_j^2\mathbf{I})=\frac{1}{(2\pi {)}^{\frac{1}{2}}}\frac{1}{{\sigma }_j^D}$$

如果我们考虑极限 ${\sigma }_j\to 0$，那么我们看到这⼀项趋于⽆穷⼤，因此对数似然函数也会趋于⽆穷⼤。

使⽤合适的启发式⽅法可以避免这个问题：重置均值或协方差。

可区分问题

对于任意给定的最⼤似然解，⼀个由 $K$ 个分量混合⽽成的概率分布总共会有 $K!$ 个等价的解

对应于 $K!$ 种将 $K$ 个参数集合分配到 $K$ 个分量上的⽅式：如 $K=3$，$K!=6$: $123,132,213,231,312,321$

对于参数值空间中任意给定的点，都会有 $K!-1$ 个其他的点给出完全相同的概率分布。

任意等价的解都⼀样好。

标记三个高斯子类的两种方法：

最大似然解

从对数似然函数开始：

$$\ln p(X\mid \pi ,\mu ,\Sigma )=\sum _{n=1}^N\ln \left\{\sum _{k=1}^K{\pi }_k\mathcal{N}({\mathbf{x}}_n\mid {\mu }_k,{\Sigma }_k)\right\}$$

我们期望找到可以最大化这个等式的 ${\mu }_k,{\Sigma }_k,{\pi }_k$

由于求和以高斯形式出现，并且对数不以高斯形式进行运算，所以该任务并不简单。

关于参数 ${\mu }_k,{\Sigma }_k,{\pi }_k$依次求导，并设为0

均值的极大似然解

从对数似然函数开始：

$$\ln p(X\mid \pi ,\mathbf{\mu },\mathbf{\Sigma })=\sum _{n=1}^N\ln \left\{\sum _{k=1}^K{\pi }_k\mathcal{N}({\mathbf{x}}_n\mid {\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k)\right\}$$

关于对均值 ${\mathbf{\mu }}_k$ 求导并将其设为 $0$：

利用高斯的指数形式

并使用公式：$\frac{d}{dx}\ln u=\frac{u^{\prime }}{u}\text{and}\frac{d}{dx}{e}^u=e^u{u}^{\prime }$

可以得到：

利用 ${\mathbf{\Sigma }}_k$ 进行计算（假设矩阵是⾮奇异的）

$${\mathbf{\mu }}_k=\frac{1}{N_k}\sum _{n=1}^N\gamma (z_{nk}){\mathbf{x}}_n$$

第 $k$ 个⾼斯分量的均值 ${\mathbf{\mu }}_k$ 通过对数据集⾥所有的数据点求加权平均的⽅式得到。其中数据点 $x_n$ 的权因⼦由后验概率 $\gamma (z_{nk})$ 给出，⽽ $\gamma (z_{nk})$ 表⽰分量 $k$ 对⽣成 $x_n$ 的责任。

其中，我们定义了：$N_k={\sum }_{n=1}^N\gamma (z_{nk})$

$N_k$ 为分配到聚类 $k$ 的数据点的有效数量。

协方差的极大似然解

设 ${\mathbf{\Sigma }}_k$ 的导数为0

使⽤单⼀⾼斯分布协⽅差矩阵的最⼤似然结果：

$${\mathbf{\Sigma }}_k=\frac{1}{N_k}\sum _{n=1}^N\gamma (z_{nk})({\mathbf{x}}_n-{\mathbf{\mu }}_k)(\mathbf{x}-{\mathbf{\mu }}_k{)}^T$$

这与⼀元⾼斯分布的对应的结果具有相同的函数形式，但是与之前⼀样，每个数据点都有⼀个权值，权值等于对应的后验概率。

其中，我们定义了：$N_k={\sum }_{n=1}^N\gamma (z_{nk})$

$N_k$ 为分配到聚类 $k$ 的数据点的有效数量。

混合系数的最大似然解

关于混合系数 ${\pi }_k$ 最大化 $\ln p(X\mid \pi ,\mu ,\Sigma )$。

要求混合系数的加和等于1。

使⽤拉格朗⽇乘数法，最⼤化下⾯的量：

$$\ln p(X\mid \pi ,\mu ,\Sigma )+\lambda \left(\sum _{k=1}^K{\pi }_k-1\right)$$

设 ${\pi }_k$ 的导数为0，可以得到：

$${\pi }_k=\frac{N_k}{N}$$

最大似然函数表达式总结

用于高斯混合模型的EM

EM算法：一种寻找带有潜在变量的模型的最⼤似然解的⽅法，被称为期望最⼤化算法。

${\mu }_k,{\Sigma }_k,{\pi }_k$ 的结果没有给出混合模型参数的⼀个解析解。因为“责任” $\gamma (z_{nk})$ 以⼀种复杂的⽅式依赖于这些参数。

$$\gamma (z_{nk})=\frac{{\pi }_k\mathcal{N}({\mathbf{x}}_n\mid {\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k)}{{\sum }_{j=1}^K{\pi }_j\mathcal{N}({\mathbf{x}}_n\mid {\mathbf{\mu }}_j,{\mathbf{\Sigma }}_j)}$$

这些结果建议了一种迭代方法来寻找问题的极大似然解。这个迭代过程是EM算法应⽤于⾼斯混合模型的⼀个实例。

用于GMM的非形式化EM描述

1. 为三个参数均值、协⽅差、混合系数选择一个初始值

2. 交替进行E步骤和M步骤

1) E步骤：使⽤参数的当前值计算后验概率

$$\begin{array}{rl}\gamma (z_k)\equiv p(z_k=1|\mathbf{x})& =\frac{p(z_k=1)p(\mathbf{x}|z_k=1)}{{\sum }_{j=1}^{K}p(z_j=1)p(\mathbf{x}|z_j=1)}\\ & =\frac{{\pi }_k\mathcal{N}(\mathbf{x}|{\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k)}{{\sum }_{j=1}^K{\pi }_j\mathcal{N}(\mathbf{x}|{\mathbf{\mu }}_j,{\mathbf{\Sigma }}_j)}\end{array}$$

2) M步骤：重新估计

$$\begin{array}{rl}{\mathbf{\Sigma }}_k& =\frac{1}{N_k}\sum _{n=1}^N\gamma (z_{nk})({\mathbf{x}}_n-{\mathbf{\mu }}_k)(\mathbf{x}-{\mathbf{\mu }}_k{)}^T\\ {\mathbf{\mu }}_k& =\frac{1}{N_k}\sum _{n=1}^N\gamma (z_{nk}){\mathbf{x}}_n\\ {\pi }_k& =\frac{N_k}{N}\\ N_k& =\sum _{n=1}^N\gamma (z_{nk})\end{array}$$

高斯混合模型的EM算法

给定⼀个高斯混合模型，⽬标是关于参数（均值、协⽅差、混合系数）最⼤化似然函数

EM应⽤于⽼忠实间歇喷泉数据集:

高斯混合 vs. K均值算法

高斯混合模型的EM算法就像是K均值算法的一个带有固定先验和协方差的软版本。

K均值算法对数据点的聚类进⾏了“硬”分配，即每个数据点只属于唯⼀的聚类。在K均值算法中，权重为0或1。

⽽EM算法基于后验概率分布，进⾏了⼀个“软”分配。每个中心通过数据的加权方式移动，权重由软分配给定。

EM的实际问题

与K均值算法相⽐，EM算法在达到（近似）收敛之前，经历了更多次的迭代，每次迭代需要更多的计算量。

通常运⾏K均值算法找到高斯混合模型的⼀个合适的初始化值。

协⽅差矩阵可以很⽅便地初始化为通过K均值算法找到的聚类的样本协⽅差。

EM不保证找到对数似然函数的全局最大值。

7.4 一般形式的期望最大

EM算法的另一种观点（潜在变量观点）

这种观点认识到潜在变量z起着重要的作用。

观测数据矩阵 $X=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_N\end{array}\right]$，其中第 $n$ 行为样本向量 $x_n^T=\left[\begin{array}{cccc}{x}_{n1}& x_{n2}& \cdots & x_{nD}\end{array}\right]$

潜在变量矩阵 $Z=\left[\begin{array}{c}{z}_1\\ z_2\\ ⋮\\ z_N\end{array}\right]$，其中第 $n$ 行为 $z_n^T=\left[\begin{array}{cccc}{z}_{n1}& z_{n2}& \cdots & z_{nK}\end{array}\right]$

EM算法的目标是由给定的 $X$ 找到 $P(X)$ 的最大似然解。

在实际应⽤中，没有完整数据集 $\{X,Z\}$，只有不完整的数据 $X$。

所有模型参数的集合被记作 $\theta$

潜在变量的似然函数

对数似然函数的公式：

$$\ln p(\mathbf{X}\mid \theta )=\ln \left\{\sum _{\mathbf{Z}}p(\mathbf{X},\mathbf{Z}\mid \mathbf{\theta })\right\}$$

关键现象：对于潜在变量z的求和位于对数的内部。

即使联合概率分布 $p(X,Z|\theta )$ 属于指数族分布，由于这个求和式的存在，边缘概率分布 $p(X|\theta )$ 通常也不是指数族分布。（取高斯和的对数时不给出简单的二次方）

导致最大似然解的形式更加复杂。

完整数据集

现在假定对于X中的每个观测，我们都有潜在变量Z的对应值。
将 {X, Z} 称为完整（complete）数据集。
称实际的观测数据集X是不完整的（incomplete）。
完整数据集的对数似然函数的形式为ln p(X, Z|θ)。
并且我们假定对这个完整数据的对数似然函数进⾏最⼤化是很容易的。

$p(X,Z|\theta )$ 的期望最大化

我们没有完整数据集{X, Z}，只有不完整的数据X，不能使⽤完整数据的对数似然函数。
反过来考虑在潜在变量Z的后验概率分布下，完整数据对数似然函数的期望。

$$E[\ln p(X,Z\mid \theta )]=\sum _{Z}p(Z\mid X,\theta )\ln p(X,Z\mid \theta )$$

E 步骤和 M 步骤

一般的 EM 算法

给定观测变量X和潜在变量Z上的⼀个联合概率分布p(x, z|θ) ，由参数θ控制，⽬标是关于θ最⼤化似然函数 p(x|θ) 。

缺失变量

EM算法描述了最⼤化⼀个包含离散潜在变量的似然函数。

它也适⽤于未观测的变量对应于数据集⾥的缺失值的情形。

• 取所有变量的联合概率分布，然后对缺失变量进行边缘化
• EM算法可以⽤来最⼤化对应的似然函数

EM算法也适⽤于数据集随机缺失的情形。但是，如果缺失值依赖于未观测的值就不再适用。例如当传感器的测量值超过某个阈值时，传感器就不会成功地返回⼀个值。

重新考察高斯混合模型

将EM算法（潜在变量观点）应⽤于混合高斯模型。

在E步骤中，计算完整数据对数似然函数关于潜在变量后验概率分布的期望，如下式。

$$\mathcal{Q}(\theta ,{\theta }^{旧})=\sum _{\mathbf{Z}}p(\mathbf{Z}\mid X,{\mathbf{\theta }}^{旧})\ln p(\mathbf{X},\mathbf{Z}\mid \mathbf{\theta })$$

在M步骤中，关于 $\theta$ 最大化 $\mathcal{Q}(\theta ,{\theta }^{旧})$，可以得到和之前推导的高斯混合模型参数 $\pi ,\mu ,\Sigma$ 相同的估计。

完整数据(X, Z)的似然函数

$$\begin{gathered} p(\mathbf{z})=\prod _{k=1}^K{\pi }_k^{z_k} \\ p(\mathbf{x}\mid z)=\prod _{k=1}^K\mathcal{N}(\mathbf{x}\mid {\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k{)}^{z_k} \end{gathered}$$

对完整数据(X, Z)进⾏最⼤化，似然函数的形式为

$$p(X,Z\mid \mu ,\Sigma ,\pi )=\prod _{n=1}^N\prod _{k=1}^K{\pi }_k^{z_{nk}}\mathcal{N}(x_n\mid {\mu }_k,{\Sigma }^k{)}^{z_{nk}}$$

对数似然函数是：

$$\ln p(X,\mathbf{Z}|\mathbf{\mu },\mathbf{\Sigma },\mathbf{\pi })=\sum _{n=1}^N\sum _{k=1}^K{z}_{nk}\{\ln {\pi }_k+\ln \mathcal{N}(x_n\mid {\mu }_k,{\Sigma }_k)\}$$

比不完整数据的对数似然函数简单很多：

$$\ln p(X\mid \pi ,\mu ,\Sigma )=\sum _{n=1}^N\ln \left\{\sum _{k=1}^K{\pi }_k\mathcal{N}({\mathbf{x}}_n\mid {\mu }_k,{\Sigma }_k)\right\}$$

完整数据的最大似然函数解可以通过解析解获得。

我们没有潜在变量的值，但是得到了完整数据对数似然函数关于潜在变量后验概率分布的期望。

潜在变量后验概率分布

最终程序：GMM的EM流程

混合伯努利模型 BMM

略

7.5 期望最大的理论基础

EM 算法

给定观测变量 $X$ 和潜在变量 $Z$ 上的⼀个联合概率分布 $p(X,Z|\theta )$, 由参数 $\theta$ 控制, ⽬标是关于 $\theta$ 最⼤化似然函数 $p(X|\theta )$。

第一步：选择初始参数值 ${\theta }^0$ 。
第二步：E步骤：估计 $p(Z|X,{\theta }^t)$。
第三步：求 ${\theta }^{t+1}=\arg \underset{\theta }{\max }Q(\theta ,{\theta }^t)$

其中，$Q(\theta ,{\theta }^t)={\sum }_{Z}p(Z|X,{\theta }^t)\ln p(X,Z|\theta )$

检查对数似然函数或者参数值的收敛性。如果不满⾜收敛准则，那么令 ${\theta }^t\leftarrow {\theta }^{t+1}$，然后回到第二步。

启发式定义的通用 EM 算法

EM是一种通用技术：查找具有潜在变量的概率模型的最大似然解（参数）

EM是启发式定义的，它可以证明最大化似然函数

• 单调增加观察数据的对数似然，直到达到局部最大值
• 证明涉及获得对数似然函数的下界

收敛性证明

边缘不好算，联合好算，转换，且都可以考虑EM

引入了新分布q(Z)，对数似然可以分解为下界和KL散度之和，在E步，求隐变量的后验分布作为q，使得KL散度为0，从而最大化下界；在M步，分布q(Z)保持固定，下界L(q; θ)关于θ进⾏最⼤化，得到了某个新θ值。这会使得下界L增⼤，这会使得对应的对数似然函数更多的增⼤。从而，一轮EM使得对数似然函数增大。在M步骤中，最⼤化L(q; θ)相当于最大化完整数据对数似然函数的期望。

我们的目标是最大化似然函数 $p(X\mid \theta )={\sum }_{Z}p(X,Z\mid \theta )$

最优化 $p(X|\theta )$ 是困难的，但是最优化 $p(X,Z|\theta )$ 是容易的。

$q(Z)$ 为潜在变量 $Z$ 上的一个分布，对于任何的 $q(Z)$ 有分解：

$$\ln p(X\mid \theta )=\mathcal{L}(q,\theta )+\mathrm{KL}(q\parallel p)$$

其中，

E步骤和M步骤

在E步中，下界 $\mathcal{L}(q,\theta )$ 关于 $q(Z)$ 最大化。

因为 $\ln p(X\mid \theta )$ 不依赖于 $q(Z)$ ，因此 $L(q,\theta )$ 的最⼤值出现在KL散度等于0的时候，也就是 的时候。

下界 $\mathcal{L}(q,\theta )$ 为：

其中，常数就是分布q的熵，因此与θ⽆关。

在M步中，最⼤化完整数据对数似然函数的期望。

我们进⾏优化的变量θ只出现在对数运算内部，并且对完整数据的优化要更加简单。

E和M步骤的说明

E步：保持 θ^旧 固定，最大化下界L(q, θ)

把分布q(Z)设置为当前参数值下的后验概率分布，这使得下界移动到对数似然同样的值，此时KL散度为0。

M步：关于θ最大化下界L(q, θ) ，得到更新的θ^新

这使得对数似然随着下界而增加。

在参数空间可视化EM

EM算法通过交替计算当前参数值下的对数似然函数的下界以及最⼤化下界来得到新的参数值。

注意下界是凸函数，有唯一的最大值。

习题：EM算法