《数值方法：原理、算法及应用》第18课：期望最大化算法

创作时间:

作者:

@小白创作中心

《数值方法：原理、算法及应用》第18课：期望最大化算法

引用

来源

https://www.bilibili.com/read/cv34287917/

期望最大化（EM）算法是机器学习和统计学中一种重要的参数估计方法，广泛应用于高斯混合模型、隐马尔可夫模型等含有隐变量的模型。本文通过详细的理论推导和生动的实例解释，帮助读者深入理解EM算法的基本原理和应用。

混合高斯模型

混合高斯模型的似然函数是基于多个高斯分布的加权和来构建的。假设我们有一个混合高斯模型，其中包含K个高斯分布。每个高斯分布都有自己的均值$\mu_k$、协方差矩阵$\Sigma_k$以及混合系数$\pi_k$（表示第k个高斯分布在混合模型中的权重）。给定一个数据集$X = {x_1, x_2, ..., x_N}$，混合高斯模型的似然函数可以写为：

其中：

$\Theta$是模型参数。
$p(x_i|\mu_k, \Sigma_k)$是第k个高斯分布在$x_i$处的概率密度函数。

分点解释：

混合系数：$\pi_k$表示第k个高个高斯分布在混合模型中的权重，满足$\sum_{k=1}^{K} \pi_k = 1$。
高斯分布：每个高斯分布由均值$\mu_k$和协方差矩阵$\Sigma_k$定义，其概率密度函数为$p(x_i|\mu_k, \Sigma_k) = \frac{1}{(2\pi)^{d/2}|\Sigma_k|^{1/2}} \exp\left(-\frac{1}{2}(x_i-\mu_k)^T\Sigma_k^{-1}(x_i-\mu_k)\right)$。
似然函数：对于数据集中的每个点$x_i$，其出现在混合模型中的概率是各个高斯分布在该点概率的加权和。因此，整个数据集的似然函数是所有数据点概率的乘积。

对数似然函数：为了简化计算，通常会取对数似然函数：

$$\log L(\Theta|X) = \sum_{i=1}^{N} \log \left( \sum_{k=1}^{K} \pi_k p(x_i|\mu_k, \Sigma_k) \right)$$

对数似然函数在优化和求解模型参数时更为方便。通过最大化对数似然函数，我们可以找到最优的模型参数$\Theta$。在实际应用中，混合高斯模型的参数通常通过期望最大化（EM）算法等优化方法进行估计。

EM算法的基本思想

EM算法的基本思想是通过迭代的方式，不断地根据已有的观测数据来估计模型的参数，然后再根据这些参数来估计缺失的数据，如此反复进行，直到模型的参数收敛为止。

举例解释

假设我们有一堆身高数据，其中包含了男生和女生的身高，但是我们并不知道每个数据是男生的身高还是女生的身高（这就是一个隐变量）。我们的目标是想要分别估算出男生和女生的平均身高。男生和女生的身高分布可能不同，但我们假设它们各自服从某种分布（例如，正态分布），其均值（即平均身高）是我们想要估计的参数。

在这个问题中，我们可以将问题表述为一个优化问题，其中未知数是每个数据点属于男生或女生的概率，记作$\gamma_{ik}$，表示第 i 个数据点属于类别 k（男生或女生）的概率。同时，我们把男生身高分布的均值和方差分别记作 $\mu_m$ 和 $\sigma_m^2$，女生身高分布的均值和方差分别记作 $\mu_f$ 和 $\sigma_f^2$。

目标函数可以设计为最大化数据的似然性，即最大化所有数据点在其所属类别（男生或女生）分布下的概率乘积。在统计学中，这通常通过最大化似然函数来实现，但因为我们是在处理一个包含隐变量（即数据点的性别）的问题，所以实际上我们会最大化期望似然函数。

然而，从优化的角度来说，最大化一个函数等同于最小化其负值。因此，我们可以将目标函数定义为负的期望似然函数，这样问题就变成了最小化该目标函数。

目标函数可以表示为：

$$\mathcal{L} = -\sum_{i=1}^{N} \sum_{k=1}^{2} \gamma_{ik} \left[ \log \pi_k + \log \mathcal{N}(x_i; \mu_k, \sigma_k^2) \right]$$

其中：

N 是数据点的总数。
$x_i$ 是第 i 个数据点的身高。
$\gamma_{ik}$ 是第 i 个数据点属于类别 k（男生或女生）的概率，这是一个需要优化的未知数。
$\mu_k$ 和 $\sigma_k$ 分别是类别 k（男生或女生）身高分布的均值和标准差，这些也是需要优化的参数。但在EM算法的M步中，我们通常会先固定这些参数来优化 $\gamma$，然后再固定$\gamma$来优化这些参数。

我们的目标是找到最优的$\gamma_{ik}$，使得上述目标函数 $\mathcal{L}$ 最小化。这通常通过EM算法迭代进行，每次迭代包括E步（期望步）和M步（最大化步），直至收敛。

需要注意的是，这里的方差$\sigma_k^2$必须是正数，均值$\mu_k$必须在身高的合理范围内，而概率$\gamma_{ik}$必须在0和1之间，并且对于每个数据点 i，其属于所有类别的概率之和必须为1，即$\sum_{k=1}^{2} \gamma_{ik} = 1$。这些约束条件在优化过程中必须得到满足。

在这个数学问题中，我们面对的是一个典型的混合模型问题，其中隐变量是每个数据点的性别。通过EM算法，我们可以利用观测到的身高数据（不完全数据）来估计男生和女生的平均身高，即使性别标签（完全数据的另一部分）是未知的。算法通过迭代地在期望步骤（E步）计算隐变量的期望值（即身高数据点属于男生或女生的概率），并在最大化步骤（M步）中利用这些期望值来更新平均身高的估计值，最终收敛到稳定的参数估计。

初始化：我们首先随机给男生和女生的平均身高赋一个初值。
期望步（E步）：根据当前的平均身高估计值，我们可以计算出每个身高数据是男生身高的概率和是女生身高的概率。比如，如果某个身高数据更接近当前男生的平均身高估计值，那么我们就认为这个数据更有可能是男生的身高。在EM算法中，$\gamma_{ik}$ 表示第 $i$ 个数据点属于第 $k$ 个分布（例如，第 $k$ 个高斯分布）的责任度或隶属度。具体来说，在E步骤中，我们根据当前的模型参数（均值、方差和混合系数）来计算每个数据点属于各个分布的概率。这个概率是根据贝叶斯定理来计算的，它考虑了先验概率（混合系数 $\pi_k$）和似然（数据点在第 $k$ 个高斯分布下的概率密度）。因此，$\gamma_{ik}$ 的更新公式通常如下：

$$\gamma_{ik} = \frac{\pi_k \mathcal{N}(x_i; \mu_k, \Sigma_k)}{\sum_{j=1}^{K} \pi_j \mathcal{N}(x_i; \mu_j, \Sigma_j)}$$

这里，$\mathcal{N}(x_i; \mu_k, \Sigma_k)$ 表示第 $i$ 个数据点在第 $k$ 个高斯分布下的概率密度。