【机器学习】EM算法(Expectation-Maximization算法)详解

EM算法(Expectation-Maximization算法)是一种用于处理不完全数据或带有隐藏变量的统计模型的优化算法。为了更好地理解它,可以将其类比为一个反复猜测和改进的过程。

0.举个简单的例子

假设你是一名厨师,有两种巧克力酱:黑巧克力和白巧克力。你拿到了一批混合巧克力酱的样本,但你不知道每一勺巧克力酱里包含多少黑巧克力和白巧克力。你的目标是估计出这两种巧克力酱的比例。

  1. 初始猜测
    你先随便猜测黑巧克力和白巧克力的比例,比如50%黑巧克力和50%白巧克力。

  2. E步
    根据你的初始猜测,你估计每一勺混合巧克力酱里有多少是黑巧克力,多少是白巧克力。

  3. M步
    根据你在E步的估计,重新计算黑巧克力和白巧克力的比例,更新你的猜测。

  4. 迭代
    你不断重复上述步骤,每次根据新的比例估计混合巧克力酱的成分,再根据新的估计调整比例。经过几轮迭代后,你会发现你的比例猜测越来越准确,最终得到一个比较接近实际的比例。

总结

EM算法就是在不断猜测和改进的过程中,逐步优化模型参数,使其更好地解释数据。在处理带有隐藏变量或不完全数据的问题时,它是一个非常有效的工具。

1.预备知识

1.1 Jensen不等式

Jensen不等式是一种在凸函数和凹函数理论中具有重要作用的不等式。它表明,对于一个凸函数,函数值的期望大于等于期望的函数值。相反,对于凹函数,函数值的期望小于等于期望的函数值。

Jensen不等式的形式

对于凸函数

f f f是一个定义在实数集上的凸函数, X X X 是一个随机变量,那么:

f ( E [ X ] ) ≤ E [ f ( X ) ] f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)] f(E[X])E[f(X)]

对于凹函数

如果 f f f是凹函数,则不等式的方向相反:

f ( E [ X ] ) ≥ E [ f ( X ) ] f(\mathbb{E}[X]) \geq \mathbb{E}[f(X)] f(E[X])E[f(X)]

凸函数的定义

一个函数 f f f被称为凸函数,如果对于任意的 x 1 , x 2 x_1, x_2 x1,x2 λ ∈ [ 0 , 1 ] \lambda \in [0, 1] λ[0,1],有:

f ( λ x 1 + ( 1 − λ ) x 2 ) ≤ λ f ( x 1 ) + ( 1 − λ ) f ( x 2 ) f(\lambda x_1 + (1-\lambda) x_2) \leq \lambda f(x_1) + (1-\lambda) f(x_2) f(λx1+(1λ)x2)λf(x1)+(1λ)f(x2)

这意味着在其定义域内,连接函数图上任意两点的线段都在函数图像之上。

Jensen不等式的直观理解

Jensen不等式可以通过一个简单的几何图形来理解。对于一个凸函数,函数图像在连接任意两点的线段的上方,这使得函数在这些点上的值的加权平均(期望)总是大于或等于在这些点加权平均值(期望)处的函数值。

应用示例

示例1:对数函数的应用

假设我们有一组正数 x 1 , x 2 , … , x n x_1, x_2, \ldots, x_n x1,x2,,xn,并且我们定义 f ( x ) = log ⁡ ( x ) f(x) = \log(x) f(x)=log(x)作为凹函数。那么,Jensen不等式给出:

log ⁡ ( 1 n ∑ i = 1 n x i ) ≥ 1 n ∑ i = 1 n log ⁡ ( x i ) \log\left(\frac{1}{n} \sum_{i=1}^n x_i\right) \geq \frac{1}{n} \sum_{i=1}^n \log(x_i) log(n1i=1nxi)n1i=1nlog(xi)

这表明几何平均数小于或等于算术平均数的对数。

示例2:EM算法中的应用

在EM算法中,我们通过Jensen不等式来处理对数似然函数的最大化问题。考虑对数似然函数:

log ⁡ p ( X ∣ θ ) = log ⁡ ∑ Z p ( X , Z ∣ θ ) \log p(\mathbf{X} | \theta) = \log \sum_{\mathbf{Z}} p(\mathbf{X}, \mathbf{Z} | \theta) logp(Xθ)=logZp(X,Zθ)

由于对数函数是凹函数,利用Jensen不等式可以得到:

log ⁡ p ( X ∣ θ ) ≥ ∑ Z q ( Z ) log ⁡ p ( X , Z ∣ θ ) q ( Z ) \log p(\mathbf{X} | \theta) \geq \sum_{\mathbf{Z}} q(\mathbf{Z}) \log \frac{p(\mathbf{X}, \mathbf{Z} | \theta)}{q(\mathbf{Z})} logp(Xθ)Zq(Z)logq(Z)p(X,Zθ)

这为我们提供了一个下界,使得我们可以在每一步迭代中最大化这个下界(即ELBO),从而间接最大化对数似然函数。

总结

Jensen不等式是一个强有力的工具,在许多领域中都有广泛的应用,包括概率论、统计学和信息论。在EM算法中,Jensen不等式的应用使得我们能够处理复杂的似然函数,迭代地优化模型参数,从而更好地解释数据。

1.2 KL散度

EM算法和KL散度(Kullback-Leibler Divergence)之间有密切的关系。在EM算法中,KL散度用于解释为什么该算法在每次迭代中都会增加似然函数,并最终收敛到一个局部最大值。以下是对这两者关系的详细解释。

KL散度简介

KL散度是用于衡量两个概率分布之间差异的非对称度量。对于两个概率分布 P P P Q Q Q,其定义为:
D K L ( P ∥ Q ) = ∑ x P ( x ) log ⁡ P ( x ) Q ( x ) D_{KL}(P \| Q) = \sum_x P(x) \log \frac{P(x)}{Q(x)} DKL(PQ)=xP(x)logQ(x)P(x)

KL散度度量了分布 Q Q Q从分布 P P P 期望值的偏离程度。它总是非负的,并且当且仅当 P = Q P = Q P=Q时为零。

EM算法中的KL散度

在EM算法中,我们试图最大化不完全数据的对数似然函数 log ⁡ p ( X ∣ θ ) \log p(\mathbf{X} | \theta) logp(Xθ)。由于直接优化这个对数似然函数是困难的,EM算法通过引入一个关于隐藏变量的概率分布 q ( Z ) q(\mathbf{Z}) q(Z),转而优化一个更易处理的目标函数。这就涉及到了KL散度。

Jensen不等式和变分推断

考虑观测数据 X \mathbf{X} X和隐藏数据 Z \mathbf{Z} Z的联合分布 p ( X , Z ∣ θ ) p(\mathbf{X}, \mathbf{Z} | \theta) p(X,Zθ),我们有:

log ⁡ p ( X ∣ θ ) = log ⁡ ∑ Z p ( X , Z ∣ θ ) \log p(\mathbf{X} | \theta) = \log \sum_{\mathbf{Z}} p(\mathbf{X}, \mathbf{Z} | \theta) logp(Xθ)=logZp(X,Zθ)

由于对数函数的凹性,利用Jensen不等式,可以得到:

log ⁡ p ( X ∣ θ ) ≥ ∑ Z q ( Z ) log ⁡ p ( X , Z ∣ θ ) q ( Z ) \log p(\mathbf{X} | \theta) \geq \sum_{\mathbf{Z}} q(\mathbf{Z}) \log \frac{p(\mathbf{X}, \mathbf{Z} | \theta)}{q(\mathbf{Z})} logp(Xθ)Zq(Z)logq(Z)p(X,Zθ)

右边的表达式被称为下界(Evidence Lower Bound, ELBO),其形式为:

L ( q , θ ) = E q ( Z ) [ log ⁡ p ( X , Z ∣ θ ) ] − E q ( Z ) [ log ⁡ q ( Z ) ] \mathcal{L}(q, \theta) = \mathbb{E}_{q(\mathbf{Z})} [\log p(\mathbf{X}, \mathbf{Z} | \theta)] - \mathbb{E}_{q(\mathbf{Z})} [\log q(\mathbf{Z})] L(q,θ)=Eq(Z)[logp(X,Zθ)]Eq(Z)[logq(Z)]

这可以拆分成两部分:

L ( q , θ ) = ∑ Z q ( Z ) log ⁡ p ( X , Z ∣ θ ) − ∑ Z q ( Z ) log ⁡ q ( Z ) \mathcal{L}(q, \theta) = \sum_{\mathbf{Z}} q(\mathbf{Z}) \log p(\mathbf{X}, \mathbf{Z} | \theta) - \sum_{\mathbf{Z}} q(\mathbf{Z}) \log q(\mathbf{Z}) L(q,θ)=Zq(Z)logp(X,Zθ)Zq(Z)logq(Z)

EM算法的步骤解释

  1. E步(期望步)
    在这一步,我们选择使得KL散度最小的 q ( Z ) q(\mathbf{Z}) q(Z),即 q ( Z ) = p ( Z ∣ X , θ ( t ) ) q(\mathbf{Z}) = p(\mathbf{Z} | \mathbf{X}, \theta^{(t)}) q(Z)=p(ZX,θ(t))。因此,ELBO达到最大值,因为这使得 q ( Z ) q(\mathbf{Z}) q(Z) 充分接近于 p ( Z ∣ X , θ ) p(\mathbf{Z} | \mathbf{X}, \theta) p(ZX,θ)

  2. M步(最大化步)
    通过固定 q ( Z ) q(\mathbf{Z}) q(Z),我们最大化ELBO L ( q , θ ) \mathcal{L}(q, \theta) L(q,θ),从而更新参数 θ \theta θ

KL散度在EM算法中的作用

在EM算法的每个迭代步骤中,E步通过最小化KL散度使得当前估计的隐藏变量分布 q ( Z ) q(\mathbf{Z}) q(Z)接近真实的后验分布 p ( Z ∣ X , θ ) p(\mathbf{Z} | \mathbf{X}, \theta) p(ZX,θ)。M步通过最大化期望对数似然来更新参数,从而使得模型的对数似然函数不断增加。由于KL散度的非负性,这种迭代方式保证了似然函数不会减少,最终收敛到局部最优解。

直观理解

你可以将EM算法想象成一种“猜测-改进”过程:

  • E步:根据当前参数,猜测隐藏变量的分布,使得猜测尽可能符合观测数据和当前模型(即最小化KL散度)。
  • M步:根据最新的猜测,调整模型参数,使得模型更好地解释所有数据(即最大化对数似然)。

结论

通过上述步骤,EM算法利用KL散度的性质,在每次迭代中不断改进模型参数,使得模型逐渐趋于最优。这种方法在处理带有隐藏变量或不完全数据的问题时,特别有效。

2.EM算法详解

EM算法(Expectation-Maximization)用于含有隐藏变量的概率模型参数估计。让我们详细解释这两步的具体操作和它们在算法中的作用。

EM算法步骤详细解释

EM算法通过不断迭代两个步骤(E步和M步),来优化模型参数,使得对数似然函数最大化。

E步(Expectation Step)

目标:计算隐藏变量的期望值。

在E步中,我们利用当前参数 θ ( t ) \theta^{(t)} θ(t)计算隐藏变量的后验分布 q ( Z ) q(\mathbf{Z}) q(Z),即 q ( Z ) = p ( Z ∣ X , θ ( t ) ) q(\mathbf{Z}) = p(\mathbf{Z} | \mathbf{X}, \theta^{(t)}) q(Z)=p(ZX,θ(t))。这一步的目的是估计在给定观测数据 X \mathbf{X} X 和当前参数 θ ( t ) \theta^{(t)} θ(t) 下,隐藏变量 Z \mathbf{Z} Z 的概率分布。

具体操作如下:

  1. 计算后验分布
    根据贝叶斯定理,我们计算隐藏变量的后验分布:

    q ( Z ) = p ( Z ∣ X , θ ( t ) ) = p ( X , Z ∣ θ ( t ) ) p ( X ∣ θ ( t ) ) q(\mathbf{Z}) = p(\mathbf{Z} | \mathbf{X}, \theta^{(t)}) = \frac{p(\mathbf{X}, \mathbf{Z} | \theta^{(t)})}{p(\mathbf{X} | \theta^{(t)})} q(Z)=p(ZX,θ(t))=p(Xθ(t))p(X,Zθ(t))

    由于 p ( X ∣ θ ( t ) ) p(\mathbf{X} | \theta^{(t)}) p(Xθ(t))是一个常数,对后验分布进行归一化即可。

  2. 期望计算
    计算包含隐藏变量的对数似然的期望:

    Q ( θ , θ ( t ) ) = E Z ∣ X , θ ( t ) [ log ⁡ p ( X , Z ∣ θ ) ] = ∑ Z p ( Z ∣ X , θ ( t ) ) log ⁡ p ( X , Z ∣ θ ) Q(\theta, \theta^{(t)}) = \mathbb{E}_{\mathbf{Z} | \mathbf{X}, \theta^{(t)}}[\log p(\mathbf{X}, \mathbf{Z} | \theta)] = \sum_{\mathbf{Z}} p(\mathbf{Z} | \mathbf{X}, \theta^{(t)}) \log p(\mathbf{X}, \mathbf{Z} | \theta) Q(θ,θ(t))=EZX,θ(t)[logp(X,Zθ)]=Zp(ZX,θ(t))logp(X,Zθ)

    这个期望是E步的主要计算内容,用于后续M步的参数更新。

M步(Maximization Step)

目标:最大化期望对数似然函数,更新参数 θ \theta θ

在M步中,我们最大化在E步中计算得到的期望对数似然函数 Q ( θ , θ ( t ) ) Q(\theta, \theta^{(t)}) Q(θ,θ(t)),从而更新模型参数 θ \theta θ。具体操作如下:

  1. 最大化期望对数似然函数
    找到参数 θ \theta θ 使得 Q ( θ , θ ( t ) ) Q(\theta, \theta^{(t)}) Q(θ,θ(t))最大:

θ ( t + 1 ) = arg ⁡ max ⁡ θ Q ( θ , θ ( t ) ) \theta^{(t+1)} = \arg\max_{\theta} Q(\theta, \theta^{(t)}) θ(t+1)=argθmaxQ(θ,θ(t))

这个步骤通过优化技术实现,比如梯度上升法。

  1. 更新参数
    将参数更新为新的值 θ ( t + 1 ) \theta^{(t+1)} θ(t+1),并用于下一次迭代的E步计算。

示例解释

假设我们有一个包含两个高斯分布的混合模型(GMM),并且我们观测到了数据 X \mathbf{X} X。模型中有两个隐藏变量 Z 1 \mathbf{Z}_1 Z1 Z 2 \mathbf{Z}_2 Z2,表示数据点属于哪个高斯分布。

  1. E步
    在E步中,我们计算每个数据点属于每个高斯分布的概率(后验概率):

q ( Z i ) = p ( X i ∣ Z i , θ ( t ) ) p ( Z i ∣ θ ( t ) ) p ( X i ∣ θ ( t ) ) q(\mathbf{Z}_i) = \frac{p(\mathbf{X}_i | \mathbf{Z}_i, \theta^{(t)}) p(\mathbf{Z}_i | \theta^{(t)})}{p(\mathbf{X}_i | \theta^{(t)})} q(Zi)=p(Xiθ(t))p(XiZi,θ(t))p(Ziθ(t))

这一步利用当前参数 θ ( t ) \theta^{(t)} θ(t)计算每个数据点的后验概率。

  1. M步
    在M步中,我们利用E步计算的后验概率,重新估计模型参数(均值、方差和混合系数),使得期望对数似然函数最大化:

θ ( t + 1 ) = arg ⁡ max ⁡ θ ∑ i ∑ j q ( Z i , j ) log ⁡ p ( X i , Z i , j ∣ θ ) \theta^{(t+1)} = \arg\max_{\theta} \sum_{i} \sum_{j} q(\mathbf{Z}_{i,j}) \log p(\mathbf{X}_i, \mathbf{Z}_{i,j} | \theta) θ(t+1)=argθmaxijq(Zi,j)logp(Xi,Zi,jθ)

通过最大化期望对数似然,我们得到新的参数 θ ( t + 1 ) \theta^{(t+1)} θ(t+1)

总结

  • E步:根据当前参数 θ ( t ) \theta^{(t)} θ(t),计算隐藏变量的后验分布 q ( Z ) q(\mathbf{Z}) q(Z)
  • M步:利用后验分布 q ( Z ) q(\mathbf{Z}) q(Z),最大化期望对数似然函数 Q ( θ , θ ( t ) ) Q(\theta, \theta^{(t)}) Q(θ,θ(t)),更新参数 θ \theta θ

通过反复迭代这两个步骤,EM算法不断提高对数似然函数的值,最终收敛到一个局部最优解。

相关推荐

  1. 机器学习-聚类算法详解

    2024-07-20 15:38:01       68 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-20 15:38:01       171 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-20 15:38:01       189 阅读
  3. 在Django里面运行非项目文件

    2024-07-20 15:38:01       157 阅读
  4. Python语言-面向对象

    2024-07-20 15:38:01       170 阅读

热门阅读

  1. 单机 Redission 存在的问题以及怎么解决

    2024-07-20 15:38:01       32 阅读
  2. 力扣(LeetCode)——70. 爬楼梯

    2024-07-20 15:38:01       31 阅读
  3. 如何使用fiddler 查看手机端数据包

    2024-07-20 15:38:01       37 阅读
  4. AI艺术创作:掌握Midjourney和DALL-E的技巧与策略

    2024-07-20 15:38:01       35 阅读
  5. 快速创建 vue 项目并添加 Dockerfile 文件

    2024-07-20 15:38:01       29 阅读
  6. C语言(7.4)

    2024-07-20 15:38:01       35 阅读
  7. 怎么降低美国服务器硬盘故障率?

    2024-07-20 15:38:01       37 阅读