EM算法(Expectation-Maximization算法)是一种用于处理不完全数据或带有隐藏变量的统计模型的优化算法。为了更好地理解它,可以将其类比为一个反复猜测和改进的过程。
0.举个简单的例子
假设你是一名厨师,有两种巧克力酱:黑巧克力和白巧克力。你拿到了一批混合巧克力酱的样本,但你不知道每一勺巧克力酱里包含多少黑巧克力和白巧克力。你的目标是估计出这两种巧克力酱的比例。
初始猜测:
你先随便猜测黑巧克力和白巧克力的比例,比如50%黑巧克力和50%白巧克力。E步:
根据你的初始猜测,你估计每一勺混合巧克力酱里有多少是黑巧克力,多少是白巧克力。M步:
根据你在E步的估计,重新计算黑巧克力和白巧克力的比例,更新你的猜测。迭代:
你不断重复上述步骤,每次根据新的比例估计混合巧克力酱的成分,再根据新的估计调整比例。经过几轮迭代后,你会发现你的比例猜测越来越准确,最终得到一个比较接近实际的比例。
总结
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=1∑nxi)≥n1i=1∑nlog(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∣θ)=logZ∑p(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∣θ)≥Z∑q(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(P∥Q)=x∑P(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∣θ)=logZ∑p(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∣θ)≥Z∑q(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,θ)=Z∑q(Z)logp(X,Z∣θ)−Z∑q(Z)logq(Z)
EM算法的步骤解释
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(Z∣X,θ(t))。因此,ELBO达到最大值,因为这使得 q ( Z ) q(\mathbf{Z}) q(Z) 充分接近于 p ( Z ∣ X , θ ) p(\mathbf{Z} | \mathbf{X}, \theta) p(Z∣X,θ)。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(Z∣X,θ)。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(Z∣X,θ(t))。这一步的目的是估计在给定观测数据 X \mathbf{X} X 和当前参数 θ ( t ) \theta^{(t)} θ(t) 下,隐藏变量 Z \mathbf{Z} Z 的概率分布。
具体操作如下:
计算后验分布:
根据贝叶斯定理,我们计算隐藏变量的后验分布: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(Z∣X,θ(t))=p(X∣θ(t))p(X,Z∣θ(t))
由于 p ( X ∣ θ ( t ) ) p(\mathbf{X} | \theta^{(t)}) p(X∣θ(t))是一个常数,对后验分布进行归一化即可。
期望计算:
计算包含隐藏变量的对数似然的期望: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))=EZ∣X,θ(t)[logp(X,Z∣θ)]=Z∑p(Z∣X,θ(t))logp(X,Z∣θ)
这个期望是E步的主要计算内容,用于后续M步的参数更新。
M步(Maximization Step)
目标:最大化期望对数似然函数,更新参数 θ \theta θ。
在M步中,我们最大化在E步中计算得到的期望对数似然函数 Q ( θ , θ ( t ) ) Q(\theta, \theta^{(t)}) Q(θ,θ(t)),从而更新模型参数 θ \theta θ。具体操作如下:
- 最大化期望对数似然函数:
找到参数 θ \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))
这个步骤通过优化技术实现,比如梯度上升法。
- 更新参数:
将参数更新为新的值 θ ( 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,表示数据点属于哪个高斯分布。
- 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(Xi∣Zi,θ(t))p(Zi∣θ(t))
这一步利用当前参数 θ ( t ) \theta^{(t)} θ(t)计算每个数据点的后验概率。
- 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θmaxi∑j∑q(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算法不断提高对数似然函数的值,最终收敛到一个局部最优解。