C09. 混合模型的 EM 算法

S09. 前言

• 重点
  • 用于混合高斯模型的 EM 算法
• 难点
  • EM 算法的不同视角
• 学习基础
  • $K$ 均值聚类
  • EM 算法
  • 混合高斯模型（S2.3.）
• 学习要点
  • 两类隐变量模型
    • 离散的隐变量模型应用于表示混合概率分布
    • 连续的隐变量模型的应用在（C12）介绍
  • 混合模型与 EM 算法的关系
    • 混合模型可以应用于构建复杂的概率分布，还可以应用于数据聚类
    • 数据聚类不利用概率的解决方案：K 均值算法
    • 数据聚类利用概率的解决方案：混合概率模型，即使用隐变量表示混合概率分布的模型。
      • 离散的隐变量表示数据点分配到混合概率分布的具体成分中
      • 模型寻找最大似然估计的一个一般方法：期望最大化（EM）算法
    • EM 算法在混合概率模型的实际应用
      • 采用非形式化的方式介绍 EM 算法在高斯混合分布中的应用
      • 基于隐变量的角度来形式化分析 EM 算法的应用
    • 给出一个一般形式的 EM 算法

S9.1. $K$ 均值聚类

• $K$ 均值聚类与 EM 算法之间的联系
  • 数据集是由 $D$ 维欧氏空间中的随机变量 $x$ 的 $N$ 次观测组成
  • 目标是将数据集划分为 $K$ 个类别。
    • 聚类内部点之间的距离小于数据点与聚类外部点之间的距离。
    • 二值指示变量 $r_{nk}\in{0,1}$
    • 失真度量 $J=\overset{N}{\underset{n=1}{\sum}}\overset{K}{\underset{k=1}{\sum}}r_{nk}\Vert\mathbf{x}_n-\boldsymbol{\nu}_k\Vert^2$
  • 算法过程
    1. 初始化阶段：设置 $\boldsymbol{\nu}_k$ 的初值
    2. 第一阶段：关于 $r_{nk}$ 最小化 $J$，保持 $\boldsymbol{\nu}_k$ 固定。（相当于 EM 算法中的期望 E 步骤）
    3. 第二阶段：保持 $r_{nk}$ 固定，关于 $\boldsymbol{\nu}_k$ 最小化 $J$ 。（相当于 EM 算法中的最大化 M 步骤）
• $K$ 均值算法的推广：K 中心点算法
  • 引入更加一般的不相似程度的度量 $\mathcal{V}(\mathbf{x},\mathbf{x}’)$
  • 最小化下面的失真度量 $\tilde{J}=\overset{N}{\underset{n=1}{\sum}}\overset{K}{\underset{k=1}{\sum}}r_{nk}\mathcal{V}(\mathbf{x}_n,\boldsymbol{\nu}_k)$
• $K$ 均值聚类应用于图像分割
• $K$ 均值聚类应用于图像压缩
  • 主要是应用于有损数据压缩中

S9.2. 混合高斯

• 混合高斯模型（S2.3.9.）是高斯分量的简单线性叠加，目标是提供一类比单独的高斯分布描述能力更强的概率模型

• 使用离散隐变量来描述混合高斯模型 $p(\mathbf{x}\vert\mathbf{z})=\overset{K}{\underset{k=1}{\prod}}\mathcal{N}(\mathbf{x}\vert\boldsymbol{\nu}_k,\boldsymbol{\Sigma}_k)^{z_k}$

  • $z_k$ 是隐变量，用来描述第 k 个高斯分量是否对描述模型有用
  • $\gamma(z_k)$ 是分量 k 对于 “解释” 观测值 x 的 “责任”(responsibility)

• 最大化混合高斯模型的对数似然函数

  • 存在的问题
    • 最大化混合高斯模型的对数似然函数不是一个具有良好定义的问题，当某个高斯分量 “退化” 到一个具体的数据点时，对数似然函数就会走向于无穷大而无法求得解析解，这是奇异性问题。
    • 对于参数值空间中任意给定的点，都会有 $K!-1$ 个其他的点与之对应，即它们会得出完全相同的概率分布，这是可区分 (identifiability) 问题
  • 解决的办法
    • 基于梯度的优化方法（S5.4.）
    • EM 算法

• 用于混合高斯模型的 EM 算法（推导算法公式，了解算法思想）

  • 期望最大化（Expectation-Maximization，EM）算法：是寻找带有隐变量模型的最大似然解的方法。
  • 公式中的 $z_{nk}$ 表示 $\mathbf{x}_n$ 数据点对描述第 $k$ 个概率分量的贡献；或者第 $k$ 个概率分量对解释 $\mathbf{x}_n$ 数据点的贡献。
  • EM 算法的过程
    1. 初始化均值、协方差、混合系数；
    2. 在期望 (E) 步骤，使用参数的当前值计算公式给出的后验概率（也被称为 “责任”）
    3. 在最大化 (M) 步骤，利用计算出的概率重新估计均值、协方差和混合系数。
    4. 当对数似然函数的变化量或者参数的变化量低于某个阈值时，算法收敛。

• EM 算法的形式化分析及其他应用

  • EM 算法估计模型的 MAP（最大后验概率）解
  • EM 算法估计数据集随机缺失的问题的解
    • 数据集随机缺失的混合高斯模型
  • EM 算法与 $K$ 均值的联系
    • $K$ 均值算法对数据点的聚类进行了 “硬” 分配，即每个数据点只属于唯一的聚类；
      • $K$ 均值算法没有估计聚类的协方差，只是估计了聚类的均值。
      • 带有广义的协方差矩阵的硬分配版本的混合高斯模型叫做椭圆 $K$ 均值算法
    • EM 算法对数据点的聚类进行了 “软” 分配，即基于后验概率分布来确定数据点最应该分在哪个聚类中。
    • 在极限的情况下，最大化完整数据对数似然函数的期望等价于最小化公式给出的 $K$ 均值的失真度量 $J$

• 用于混合 Bernoulli 分布模型的 EM 算法

  （推导公式，理解 EM 算法的构建过程）

  • 由 Bernoulli 分布描述的离散二值变量的混合，也叫隐类别分析。是考虑离散变量上的 Markov 模型的基础。
  • 与混合高斯模型不同的是不存在似然函数趋于无穷大的奇异性
  • 混合 Bernoulli 分布模型可以推广到 $M>2$ 个状态的离散变量多项式分布的情况。

• 用于贝叶斯线性回归的 EM 算法

  • 贝叶斯线性回归的证据近似问题（S3.5.2.）
    1. 初始化参数 $\alpha$ 和 $\beta$
    2. E 步骤，计算 $\text{w}$ 的后验概率分布，找到完整数据对数似然函数的期望；
    3. M 步骤，关于参数 $\alpha$ 和 $\beta$ 最大化期望，从而重新估计参数 $\alpha$ 和 $\beta$。

S9.4. EM 算法的通用形式

（先推导公式，再依赖具体案例深入理解 EM 算法，后面有广泛的应用。这节看懂了，才代表真正理解 EM 算法了）

• EM 算法可以看成参数空间中的运算 (P312 F9.14)
  1. 选择某个初始的参数值
  2. E 步骤中，基于固定的参数值，计算隐变量上的后验概率分布，得到了更小的下界
  3. M 步骤，下界被最大化，得到新的参数值
• EM 算法的扩展
  • 广义 EM 算法 (Generalized EM Algorithm)：
    • 改变 E 步骤中完全的最优化为局部最优化
    • 解决 M 步骤中无法计算的问题
      • 在 M 步骤中使用非线性优化策略（例如：共轭梯度算法）
      • 期望条件最大化算法 (Expectation Conditional Maximization Algorithm,ECM)：在每个 M 步骤中进行若干具有限制条件的最优化。
    • 增量形式的 EM 算法，收敛速度更快

S09. 小结

混合模型是模型推导的模型基础，EM 算法是模型计算的算法基础。