机器学习笔记之EM算法(四)广义EM

机器学习笔记之EM算法——广义EM

引言

引言

上一节介绍了引入隐变量的本质，本节将狭义EM算法推广至广义EM算法。

回顾：引如隐变量与EM算法的本质

引入EM算法本质上是基于频率学派的思想，针对概率模型 $P(\mathcal X \mid \theta)$ 中模型参数 $\theta$ 的估计问题。
learning 问题。
找到这个最优模型参数 $\hat \theta$ 的底层逻辑是极大似然估计(Maximum Likelihood Estimate,MLE)：
$\hat \theta = \mathop{\arg\max}\limits_{\theta} \log P(\mathcal X \mid \theta)$
但通常情况是：如果将 $P(\mathcal X \mid \theta)$ 看成概率模型，那么该概率模型产生的真实样本 $\mathcal X$ 过于复杂，导致使用极大似然估计无法有效地求出最优解析解 $\hat \theta$ 。

针对这种情况，我们需要对 $P(\mathcal X \mid \theta)$ 做出一些假设：假设存在概率模型 $P(\mathcal Z)$ ，真实样本 $\mathcal X$ 是以概率模型 $P(\mathcal Z)$ 的条件下产生出来的。数学符号表达即：
$P(\mathcal X \mid \mathcal Z)$
概率图表示为：
请添加图片描述
由于 $P(\mathcal Z)$ 是人为假设的概率分布，从而可以将原始的概率模型 $P(\mathcal X)$ 转化为关于真实样本 $\mathcal X$ ，隐变量 $\mathcal Z$ 的混合概率模型 $P(\mathcal X,\mathcal Z)$ :
$P(\mathcal X,\mathcal Z) = P(\mathcal X \mid \mathcal Z)P(\mathcal Z)$

从而可以通过概率模型 $P(\mathcal Z)$ 作为媒介，将复杂的样本分布 $P(\mathcal X \mid \theta)$ 求解出来：
$P(\mathcal X) = \int_{\mathcal Z} P(\mathcal X,\mathcal Z)d\mathcal Z = \mathbb E_{\mathcal Z}\left[P(\mathcal X,\mathcal Z)\right]$

狭义EM与广义EM

回顾：狭义EM算法

在确立了目标函数： $\log P(\mathcal X \mid \theta)$ 之后，我们将隐变量 $\mathcal Z$ 引入，对目标函数进行展开：
详细的展开过程见传送门,这里就不赘述了。

\begin{aligned} \log P (X ∣ θ) & = \log P (X, Z ∣ θ) - \log P (Z ∣ X, θ) \\ = \log P (X, Z ∣ θ) - \log Q (Z) - [\log P (Z ∣ X, θ) - \log Q (Z)] \\ = \log \frac{P (X, Z ∣ θ)}{Q (Z)} - \log \frac{P (Z ∣ X, θ)}{Q (Z)} \end{aligned}

lo g P (X ∣ θ) = lo g P (X, Z ∣ θ) - lo g P (Z ∣ X, θ) = lo g P (X, Z ∣ θ) - lo g Q (Z) - [lo g P (Z ∣ X, θ) - lo g Q (Z)] = lo g \frac{P ( X , Z ∣ θ )}{Q ( Z )} - lo g \frac{P ( Z ∣ X , θ )}{Q ( Z )}

同时对等式左右两端基于 $\mathcal Q(\mathcal Z)$ 求解期望：
等式左端：

\begin{aligned} E_{Q (Z)} [\log P (X ∣ θ)] & = \int_{Z} Q (Z) \log P (X ∣ θ) d Z \\ = \log P (X ∣ θ) \int_{Z} Q (Z) d Z \\ = \log P (X ∣ θ) \end{aligned}

等式右端：

\begin{aligned} E_{Q (Z)} [\log \frac{P (X, Z ∣ θ)}{Q (Z)} - \log \frac{P (Z ∣ X, θ)}{Q (Z)}] \\ = E_{Q (Z)} [\log \frac{P (X, Z ∣ θ)}{Q (Z)}] - E_{Q (Z)} [\log \frac{P (Z ∣ X, θ)}{Q (Z)}] \\ = \int_{Z} Q (Z) \log \frac{P (X, Z ∣ θ)}{Q (Z)} d Z - \int_{Z} Q (Z) \log \frac{P (Z ∣ X, θ)}{Q (Z)} d Z \end{aligned}

称第一项为证据下界(Evidence Lower Bound,ELBO)

\int_{\mathcal Z}\mathcal Q(\mathcal Z) \log \frac{P(\mathcal X,\mathcal Z \mid \theta)}{\mathcal Q(\mathcal Z)}d \mathcal Z

第二项(带负号)为表示 $\mathcal Q(\mathcal Z)$ 和 $P(\mathcal Z \mid \mathcal X,\theta)$ 的 $\mathcal K\mathcal L$ 散度：

\int_{\mathcal Z}\mathcal Q(\mathcal Z) \log \frac{P(\mathcal Z \mid \mathcal X,\theta)}{\mathcal Q(\mathcal Z)}d \mathcal Z = \mathcal K\mathcal L\left[\mathcal Q(\mathcal Z) || P(\mathcal Z \mid \mathcal X,\theta)\right]

核心部分：至此， $\log P(\mathcal X \mid \theta)$ 分解成了两项：ELBO和 $\mathcal K\mathcal L$ 散度两项。

首先观察ELBO：将ELBO看成关于隐变量概率分布 $\mathcal Q(\mathcal Z)$ 和概率模型参数 $\theta$ 的函数：
$\mathcal L\left[\mathcal Q(\mathcal Z),\theta\right] = \int_{\mathcal Z}\mathcal Q(\mathcal Z) \log \frac{P(\mathcal X,\mathcal Z \mid \theta)}{\mathcal Q(\mathcal Z)}d \mathcal Z$
观察 $\mathcal K\mathcal L$ 散度，由于 $\mathcal K\mathcal L$ 散度自身性质：大于等于0恒成立
$\mathcal K\mathcal L\left[\mathcal Q(\mathcal Z) || P(\mathcal Z \mid \mathcal X,\theta)\right] \geq 0$
并且在 $\mathcal Q(\mathcal Z) = P(\mathcal Z \mid \mathcal X,\theta)$ 时， $\mathcal K\mathcal L$ 散度取得最小值0。因此，则有：
$\log P(\mathcal X \mid \theta) \geq \mathcal L[\mathcal Q(\mathcal Z),\theta]$

从而引出狭义EM的朴素想法：

$\mathcal Q(\mathcal Z) = P(\mathcal Z \mid \mathcal X,\theta)$ ；
在步骤1条件下，通过调整模型参数 $\theta$ ，使得 $\mathcal L[\mathcal Q(\mathcal Z),\theta]$ 最大；
$\hat \theta = \mathop{\arg\max}\limits_{\theta} \mathcal L[\mathcal Q(\mathcal Z)]$

狭义EM算法的问题

继续观察狭义EM的朴素想法，主要问题出现在步骤1：核心问题出现在： $P(\mathcal Z \mid \mathcal X,\theta)$ 可能无法求解。

$P(\mathcal Z \mid \mathcal X,\theta)$ 是否可以求解取决于生成模型的复杂程度，核心在于我们定义的隐变量 $\mathcal Z$ 它的复杂程度：

例如高斯混合模型(Gaussian Mixture Model,GMM)，它对于隐变量 $\mathcal Z$ 的概率分布是 离散的分类分布(Categorical Distribution)；
例如隐马尔可夫模型(Hidden Markov Model,HMM)，它对于隐变量 $\mathcal Z$ 的概率分布 受齐次马尔可夫假设的约束；

因此，这些模型它们定义的隐变量 $\mathcal Z$ 的概率分布是结构化的、简单的，因而可以直接 求解 $P(\mathcal Z \mid \mathcal X,\theta)$ ，最终使用狭义EM进行求解；
但是，更多模型隐变量 $\mathcal Z$ 的概率分布是复杂的，使得 $P(\mathcal Z \mid \mathcal X,\theta)$ 无法求解，因而无法使用狭义EM算法求解。从而衍生出其他求解概率分布方法，如近似推断(主要有变分推断、马尔可夫链蒙特卡洛方法等)

广义EM想要表达的朴素思想：
既然无法求解 $P(\mathcal Z \mid \mathcal X,\theta)$ ，就在当前迭代步骤中求解一个和 $P(\mathcal Z \mid \mathcal X,\theta)$ 最接近的概率分布 $\hat {\mathcal Q(\mathcal Z)}$ 来替代 $P(\mathcal Z \mid \mathcal X,\theta)$ 。

具体迭代过程如下。基于第 $t + 1$ 步迭代，有：

已知第 $t$ 步的最优参数结果 $\theta^{(t)}$ ，则有： $\log P(\mathcal X \mid \theta^{(t)})$ 是确定的。
这意味着 ELBO + KL-Divergence 的结果是固定的，因此求解最小化的KL-Divergence等价于求解最大化的ELBO;
在步骤1的条件下，求解第 $t$ 步最接近 $P(\mathcal Z \mid \mathcal X,\theta^{(t)})$ 的概率分布 $\hat {\mathcal Q}^{(t+1)}(\mathcal Z)$ 作为第 $t + 1$ 步的最优后验概率分布。数学语言表示如下：
此时的 $\theta^{(t)}$ 是已知量，看做常数;虽然依然不知道 $P(\mathcal Z \mid \mathcal X,\theta^{(t)})$ 的具体结果，但不影响我们求解 $\mathcal K\mathcal L[\mathcal Q(\mathcal Z) || P(\mathcal Z \mid \mathcal X,\theta^{(t)})]$
$\begin{aligned} {\hat{Q}}^{(t + 1)} (Z) & = \underset{Q (Z)}{\arg min} K L [Q (Z) | | P (Z ∣ X, θ^{(t)})] \\ = \underset{Q (Z)}{\arg max} L [Q (Z), θ^{(t)}] \end{aligned}$
基于步骤2中产生的最优概率分布 $\hat {\mathcal Q}^{(t+1)}(\mathcal Z)$ ，继续使用狭义EM算法，将 $t + 1$ 步迭代的最优模型参数 $\theta^{(t+1)}$ 求解出来：
$\theta^{(t+1)} = \mathop{\arg\max}\limits_{\theta} \mathcal L[\hat {\mathcal Q}^{(t+1)}(\mathcal Z),\theta]$

整理：广义EM的E部和M部分别表示如下：
${ Q ^ ( t + 1 ) ( Z ) = arg ⁡ max ⁡ Q ( Z ) ∫ Z Q ( Z ) log ⁡ P ( X , Z ∣ θ ( t ) ) Q ( Z ) d Z θ ( t + 1 ) = arg ⁡ max ⁡ θ ∫ Z Q ^ ( t + 1 ) ( Z ) log ⁡ P ( X , Z ∣ θ ) Q ^ ( t + 1 ) ( Z ) d Z$

{\begin{cases} {\hat{Q}}^{(t + 1)} (Z) = \underset{Q (Z)}{\arg max} \int_{Z} Q (Z) \log \frac{P (X, Z ∣ θ^{(t)})}{Q (Z)} d Z \\ θ^{(t + 1)} = \underset{θ}{\arg max} \int_{Z} {\hat{Q}}^{(t + 1)} (Z) \log \frac{P (X, Z ∣ θ)}{{\hat{Q}}^{(t + 1)} (Z)} d Z \end{cases}

⎩ ⎨ ⎧ \hat{Q}^{(t + 1)} (Z) = Q (Z) ar g max \int_{Z} Q (Z) lo g \frac{P ( X , Z ∣ θ ^{(t)} )}{Q ( Z )} d Z θ^{(t + 1)} = θ ar g max \int_{Z} \hat{Q}^{(t + 1)} (Z) lo g \frac{P ( X , Z ∣ θ )}{Q ^ ^{(t + 1)} ( Z )} d Z

我们和狭义EM做一个对比：

核心区别在于E部：狭义EM默认 $P(\mathcal Z \mid \mathcal X,\theta)$ 可求解，并令 $\mathcal Q(\mathcal Z) = P(\mathcal Z \mid \mathcal X,\theta)$ 作为条件；而广义EM在 $P(\mathcal Z \mid \mathcal X,\theta)$ 无法求解的情况下，先求出 $P(\mathcal Z \mid \mathcal X,\theta)$ 的近似解 $\hat {\mathcal Q(\mathcal Z)}$ ，并令 $\mathcal Q(\mathcal Z) = \hat {\mathcal Q(\mathcal Z)}$ 。

实际上从狭义和广义的M部求解公式中观察出区别。

将广义EM算法的M部公式展开：
$\begin{aligned} θ^{(t + 1)} & = \underset{θ}{\arg max} \int_{Z} {\hat{Q}}^{(t + 1)} (Z) \log \frac{P (X, Z ∣ θ)}{{\hat{Q}}^{(t + 1)} (Z)} d Z \\ = \underset{θ}{\arg max} {E_{{\hat{Q}}^{(t + 1)} (Z)} [\frac{\log P (X, Z ∣ θ)}{{\hat{Q}}^{(t + 1)} (Z)}]} \\ = \underset{θ}{\arg max} {E_{{\hat{Q}}^{(t + 1)} (Z)} [\log P (X, Z ∣ θ)] - E_{{\hat{Q}}^{(t + 1)} (Z)} [\log {\hat{Q}}^{(t + 1)} (Z)]} \end{aligned}$
观察大括号内第二项，它就是关于 $\hat {\mathcal Q}^{(t+1)}(\mathcal Z)$ 分布的信息熵：
$\begin{aligned} E_{{\hat{Q}}^{(t + 1)} (Z)} [\log {\hat{Q}}^{(t + 1)} (Z)] & = \int_{Z} {\hat{Q}}^{(t + 1)} (Z) \log [{\hat{Q}}^{(t + 1)} (Z)] d Z \\ = H [{\hat{Q}}^{(t + 1)} (Z)] \end{aligned}$

因此，关于M部，广义EM比狭义EM多了一项：
无论是狭义EM中的 $P(\mathcal Z \mid \mathcal X,\theta^{(t)})$ 还是广义EM中的 $\hat {\mathcal Q}^{(t+1)}(\mathcal Z)$ ,均视为当前迭代步骤关于隐变量后验概率的最优解，统一用· $\hat {\mathcal Q}(\mathcal Z)$ 表示。
${ arg ⁡ max ⁡ θ { E Q ^ ( Z ) [ log ⁡ P ( X , Z ∣ θ ) ] } arg ⁡ max ⁡ θ { E Q ^ ( Z ) [ log ⁡ P ( X , Z ∣ θ ) ] + H [ Q ^ ( Z ) ] }$

{\begin{cases} \underset{θ}{\arg max} {E_{\hat{Q} (Z)} [\log P (X, Z ∣ θ)]} \\ \underset{θ}{\arg max} {E_{\hat{Q} (Z)} [\log P (X, Z ∣ θ)] + H [\hat{Q} (Z)]} \end{cases}

⎩ ⎨ ⎧​θargmax​{EQ^​(Z)​[logP(X,Z∣θ)]}θargmax​{EQ^​(Z)​[logP(X,Z∣θ)]+H[Q^​(Z)]}​

如果

\hat {\mathcal Q}(\mathcal Z)

未知，广义EM的M部需要多求解一项；但如果

\hat {\mathcal Q}(\mathcal Z)

是已知项，那么

\mathcal H [\hat {\mathcal Q}(\mathcal Z)]

相当于常数，和

\theta

无关。从而将上式进行如下变换：

\mathop{\arg\max}\limits_{\theta} \left\{\mathbb E_{\hat {\mathcal Q}(\mathcal Z)}[\log P(\mathcal X,\mathcal Z \mid \theta)] + \mathcal H [\hat {\mathcal Q}(\mathcal Z)]\right\} = \mathop{\arg\max}\limits_{\theta} \left\{\mathbb E_{\hat {\mathcal Q}(\mathcal Z)}[\log P(\mathcal X,\mathcal Z \mid \theta)]\right\}

因此，可以得出这样一个结论：狭义EM可看作后验概率 $P(\mathcal Z \mid \mathcal X,\theta)$ 已知条件下的广义EM，狭义EM是广义EM的一种特殊情况。

实际上，上式实际上对一个情况加深了印象：广义EM中对于 $P(\mathcal Z \mid \mathcal X,\theta)$ 的近似解： $\hat {\mathcal Q}^{(t+1)}(\mathcal Z)$ 即便是近似解，但该解与 $\theta$ 有明确的关联关系。

相关参考：
机器学习-EM算法5(广义EM)

相关阅读:
深度干货！一篇Paper带您读懂HTAP | StoneDB学术分享会第①期
【计算机毕设之基于Java的用户行为分析图书销售智能推荐系统-哔哩哔哩】 https://b23.tv/OVxIJs6
kubernetes集群编排——k8s存储
【蓝桥杯软件赛零基础备赛20周】第3周——填空题
生产脚本1
项目进展（五）-修复PCB电路板，学习32位ADC芯片ADS1285
centos安装flink，通过windows访问webui
门店数字化转型| 美容院管理系统
Oracle 锁表，如何解锁
GoldenGate中使用 exp/imp 进行初始化

原文地址：https://blog.csdn.net/qq_34758157/article/details/126752655