Monodyee

这个屌丝很懒，什么也没留下！

热门标签

机器学习笔记：EM算法（期望最大算法）_期望最高求法

作者：Monodyee | 2024-03-21 02:42:49

踩

期望最高求法

1 算法介绍

1.0 EM算法的引入

EM算法主要解决的问题是，具有隐变量的混合模型的参数估计，即其极大似然估计

如果是简单的问题，我们可以直接求出P(x|θ)的时候，我们可以直接用最大似然估计来求出解析解 $\theta_{MLE}=argmax_\theta log P(x|\theta)$

但如果在模型中有了隐变量之后，就不太好求解析解P(x|θ)了，也就无法用最大似然估计来得到最佳的θ

——》这时候就需要EM算法了

1.1 EM算法介绍

EM算法是一个迭代的算法，其会不断地更新θ，直至收敛。

第t轮迭代的公式如下

我们对上式稍作修改，便有了期望形式：

$\theta^{(t+1)}=argmax_\theta \int_z logP(x,z|\theta)\cdot P(z|x,\theta^{(t)})dz=argmax_\theta E_{z|x,\theta^{(t)}}[log P(x,z|\theta)]$

——>EM 算法可以分成两步

————>第一步（E）：求出期望

————>第二步（M）：期望最大化

2 EM算法推导

2.1 第一种推导方法：ELBO+KL散度

根据条件概率的性质，我们有：

$log P(x|\theta)=log\frac{P(x,z|\theta)}{P(x|z,\theta)}$

进一步化简

$log\frac{P(x,z|\theta)}{P(x|z,\theta)}=logP(x,z|\theta)-logP(x|z,\theta)$

令q是任意一个关于z的分布：

$=logP(x,z|\theta)-logq(z)-logP(x|z,\theta)+logq(z)$

$=(logP(x,z|\theta)-logq(z))-(logP(x|z,\theta)-logq(z))$

$=log\frac{P(x,z|\theta)}{q(z)}-log\frac{P(x|z,\theta)}{q(z)}$

也就是 $log P(x|\theta)=log\frac{P(x,z|\theta)}{q(z)}-log\frac{P(x|z,\theta)}{q(z)}$

对等号两边求期望，有：

左边 $=\int_z q(z) log P(x|\theta)dz$

$=log P(x|\theta) \int_z q(z) dz$

$=log P(x|\theta) \cdot 1=log P(x|\theta)$

右边 $=\int_z q(z)[log\frac{P(x,z|\theta)}{q(z)}-log\frac{P(x|z,\theta)}{q(z)}]dz$

$=\int_z q(z)[log\frac{P(x,z|\theta)}{q(z)}]dz-\int_z q(z)[log\frac{P(x|z,\theta)}{q(z)}]dz$

$=\int_z q(z)[log\frac{P(x,z|\theta)}{q(z)}]dz+\int_z q(z)[log\frac{q(z)}{P(x|z,\theta)}]dz$

$=ELBO+KL(q(z)||P(z|x,\theta))$

KL散度见NTU 课程 CE7454:信息论概述_UQI-LIUWJ的博客-CSDN博客
ELBO表示evidence lower bound

因为KL散度始终大于等于0（当KL散度比较的两个分布相同时取等号），所以 $logP(x|\theta)=ELBO+KL(q(z)||P(z|x,\theta)) \ge ELBO$ ，当q(z)和 $P(z|x,\theta^{t})$ 分布相同时取等号。

于是我们令q(z)就是 $P(z|x,\theta^{t})$

所以 $\theta =argmax_\theta logP(x|\theta)$

$=argmax_\theta ELBO$

$=argmax_\theta \int_z P(z|x,\theta^{(t)})[log\frac{P(x,z|\theta)}{P(z|x,\theta^{(t)})}]dz$

$=argmax_\theta \int_z P(z|x,\theta^{(t)})[logP(x,z|\theta)-logP(z|x,\theta^{(t)})]dz$

由于 $\theta^{(t)}$ 和θ无关，所以

$\theta =argmax_\theta \int_z P(z|x,\theta^{(t)})[logP(x,z|\theta)]dz$

不难发现和第一小节的式子是一样的

2.2 第二种推导方法：ELBO+琴声不等式

2.2.1 琴声不等式

对于凸函数f，f[ta+(1-t)b]≥tf(a)+(1-t)f(b)

等号成立条件 a=b

在这里，我们令t为0.5：

$f(\frac{a}{2}+\frac{b}{2})\ge \frac{f(a)}{2}+\frac{f(b)}{2}$

也即f(E)≥E(f)

2,2,2 推导

这里等号成立条件，对所有的z， $\frac{P(x,z|\theta)}{q(z)}$ 均相等，我们令其为C

不难发现 $E_{q(z)}[log\frac{P(x,z|\theta)}{q(z)}]$ 就是2.1中说的ELBO，下面的问题就在于，q(z)此时是否等于 $P(z|x,\theta^{t})$

$\frac{P(x,z|\theta)}{q(z)}=C$

——> $q(z)=\frac{1}{C}P(x,z|\theta)$

等号两边对z求微分 $\int_z q(z)dz=1=\int_z \frac{1}{C}P(x,z|\theta)dz=\frac{1}{C} P(x|\theta)$

【最后一个等号：关于z的全微分，所以把z可以提出来】

所以 $C=P(x|\theta)$ ,将其带入 $\frac{P(x,z|\theta)}{q(z)}=C$

$q(z)=\frac{P(x,z|\theta)}{C}=\frac{P(x,z|\theta)}{P(x|\theta)}=P(z|x,\theta)$

所以用这种方式也能推导出EM的式子

3 EM算法举例：抛硬币问题

3.0 问题的引入：没有隐变量z的情况

假设现在有两枚硬币1和2，,随机抛掷后正面朝上概率分别为P1和P2。

为了估计P1和P2，每次取一枚硬币，连掷5下，记录的结果如下所示：

硬币	结果	统计
1	正正反正反	3正-2反
2	反反正正反	2正-3反
1	正反反反反	1正-4反
2	正反反正正	3正-2反
1	反正正反反	2正-3反

在这种情况下，由于我们知道每一次抛掷的是哪一枚硬币，所以概率很好求

3.1 引入隐变量z

现在我们不知道每轮投掷时使用的是哪一每硬币，那么此时记录的结果如下所示：

硬币结果统计
Unknown 正正反正反 3正-2反
Unknown 反反正正反 2正-3反
Unknown 正反反反反 1正-4反
Unknown 正反反正正 3正-2反
Unknown 反正正反反 2正-3反

那么现在怎么估计P1和P2呢？

硬币	结果	统计
Unknown	正正反正反	3正-2反
Unknown	反反正正反	2正-3反
Unknown	正反反反反	1正-4反
Unknown	正反反正正	3正-2反
Unknown	反正正反反	2正-3反