淘宝网站开发店铺什么类别,南阳网站seo推广公司,重庆网站建设科技公司,宿迁交通工程建设有限公司网站EM算法公式推导
EM 算法是一种用来进行含有隐变量的概率生成模型参数估计的迭代算法。
EM算法步骤
EM 算法通过迭代求 L(θ)logP(X∣θ)L(\theta)\log P(X|\theta)L(θ)logP(X∣θ) 的极大似然估计#xff0c;每次迭代包含两部#xff1a;E步#xff0c;求期望#xf…EM算法公式推导
EM 算法是一种用来进行含有隐变量的概率生成模型参数估计的迭代算法。
EM算法步骤
EM 算法通过迭代求 L(θ)logP(X∣θ)L(\theta)\log P(X|\theta)L(θ)logP(X∣θ) 的极大似然估计每次迭代包含两部E步求期望M步求极大化。
算法流程 输入观测变量数据 XXX隐变量数据 ZZZ联合分布 P(X,Z∣θ)P(X,Z|\theta)P(X,Z∣θ) 条件分布P(Z∣X,θ)P(Z|X,\theta)P(Z∣X,θ) 输出模型参数 θ\thetaθ 步骤 选择参数的初值 θ0\theta^{0}θ0 开始迭代 E 步记 θt\theta^{t}θt 为第 ttt 次迭代参数 θ\thetaθ 的估计值在第 i1i1i1 次迭代的 E 步计算 Q(θ,θt)EZ[logP(X,Z∣θ)∣X,θ(t)]∑ZlogP(X,Z∣θ)P(Z∣X,θ(t))\begin{align} Q(\theta,\theta^{t})\mathbb{E}_Z[\log P(X,Z|\theta)|X,\theta^{(t)}]\\ \sum_{Z}\log P(X,Z|\theta)P(Z|X,\theta^{(t)}) \end{align} Q(θ,θt)EZ[logP(X,Z∣θ)∣X,θ(t)]Z∑logP(X,Z∣θ)P(Z∣X,θ(t)) 这里 P(Z∣X,θ(t))P(Z|X,\theta^{(t)})P(Z∣X,θ(t)) 为给定观测数据 XXX 和当前参数估计 θ(t)\theta^{(t)}θ(t) 下隐变量数据 ZZZ 的条件概率分布 M 步求使 Q(θ,θ(t))Q(\theta,\theta^{(t)})Q(θ,θ(t)) 极大化的 θ\thetaθ 确定第 t1t1t1 次迭代的参数估计值 θt1\theta^{t1}θt1 : θ(t1)argmaxθQ(θ,θt)\theta^{(t1)}\arg\max_{\theta}Q(\theta,\theta^{t}) θ(t1)argθmaxQ(θ,θt) 重复 2、3 两步直到收敛。
函数 Q(θ,θ(t))Q(\theta,\theta^{(t)})Q(θ,θ(t)) 是 EM 算法的核心称为 QQQ 函数。
EM算法收敛性证明
EM 迭代算法终归要求的是 logP(X∣θ)\log P(X|\theta)logP(X∣θ) 的极大似然估计因此要证明它的收敛性即要证明 logP(X∣θ(t1))≥logP(X∣θ(t))\log P(X|\theta^{(t1)})\ge \log P(X|\theta^{(t)}) logP(X∣θ(t1))≥logP(X∣θ(t)) 下面开始证明 logP(X∣θ)logP(X,Z∣θ)P(Z∣X,θ)logP(X,Z∣θ)−P(Z∣X,θ)\log P(X|\theta)\log \frac{P(X,Z|\theta)}{P(Z|X,\theta)}\log P(X,Z|\theta)-P(Z|X,\theta) logP(X∣θ)logP(Z∣X,θ)P(X,Z∣θ)logP(X,Z∣θ)−P(Z∣X,θ) 接下来我们同时对等式两边乘 P(Z∣X,θ(t))P(Z|X,\theta^{(t)})P(Z∣X,θ(t)) 在对 ZZZ 求积分 左边∫ZP(Z∣X,θ(t))logP(X,Z∣θ)dZlogP(X,Z∣θ)∫ZP(Z∣X,θ(t))dZlogP(X,Z∣θ)左边\int_Z P(Z|X,\theta^{(t)})\log P(X,Z|\theta)dZ\log P(X,Z|\theta)\int_Z P(Z|X,\theta^{(t)})dZ\log P(X,Z|\theta) 左边∫ZP(Z∣X,θ(t))logP(X,Z∣θ)dZlogP(X,Z∣θ)∫ZP(Z∣X,θ(t))dZlogP(X,Z∣θ) 即左边相当于没变。 右边∫ZP(Z∣X,θ(t))logP(X,Z∣θ)−∫ZP(Z∣X,θ(t))logP(Z∣X,θ)Q(θ,θ(t))−H(θ,θ(t))右边\int_ZP(Z|X,\theta^{(t)})\log P(X,Z|\theta)-\int_ZP(Z|X,\theta^{(t)})\log P(Z|X,\theta)Q(\theta,\theta^{(t)})-H(\theta,\theta^{(t)}) 右边∫ZP(Z∣X,θ(t))logP(X,Z∣θ)−∫ZP(Z∣X,θ(t))logP(Z∣X,θ)Q(θ,θ(t))−H(θ,θ(t)) 分别将上式两项记为 Q(θ,θ(t))Q(\theta,\theta^{(t)})Q(θ,θ(t)) 和 H(θ,θ(t))H(\theta,\theta^{(t)})H(θ,θ(t)) 。我们要证的是 logP(X∣θ(t1))≥logP(X∣θ(t))\log P(X|\theta^{(t1)})\ge \log P(X|\theta^{(t)})logP(X∣θ(t1))≥logP(X∣θ(t)) 这里可以通过证明 logP(X∣θ(t1))−logP(X∣θ(t))Q(θ(t1),θ(t))−Q(θ(t),θ(t))H(θ(t),θ(t))−H(θ(t1),θ(t))≥0\log P(X|\theta^{(t1)})-\log P(X|\theta^{(t)})Q(\theta^{(t1)},\theta^{(t)})-Q(\theta^{(t)},\theta^{(t)})H(\theta^{(t)},\theta^{(t)})-H(\theta^{(t1)},\theta^{(t)})\ge0 logP(X∣θ(t1))−logP(X∣θ(t))Q(θ(t1),θ(t))−Q(θ(t),θ(t))H(θ(t),θ(t))−H(θ(t1),θ(t))≥0 来得到。对于 Q(θ,θ(t))Q(\theta,\theta^{(t)})Q(θ,θ(t)) 明显是通过迭代过程的 argmax\arg\maxargmax 可以保证。因此我们只需证明 H(θ(t),θ(t))−H(θ(t1),θ(t))≥0H(\theta^{(t)},\theta^{(t)})-H(\theta^{(t1)},\theta^{(t)})\ge0H(θ(t),θ(t))−H(θ(t1),θ(t))≥0 H(θ(t),θ(t))−H(θ(t1),θ(t))∫ZP(Z∣X,θ(t))logP(Z∣X,θ(t))−∫ZP(Z∣X,θ(t))logP(Z∣X,θ(t1))∫ZP(Z∣X,θ(t))logP(Z∣X,θ(t))P(Z∣X,θ(t1))KL(P(Z∣X,θ(t))∣∣P(Z∣X,θ(t1)))≥0\begin{align} H(\theta^{(t)},\theta^{(t)})-H(\theta^{(t1)},\theta^{(t)})\int_ZP(Z|X,\theta^{(t)})\log P(Z|X,\theta^{(t)})-\int_ZP(Z|X,\theta^{(t)})\log P(Z|X,\theta^{(t1)})\\ \int_ZP(Z|X,\theta^{(t)})\log \frac{P(Z|X,\theta^{(t)})}{P(Z|X,\theta^{(t1)})}\\ KL(P(Z|X,\theta^{(t)})||P(Z|X,\theta^{(t1)}))\ge0 \end{align} H(θ(t),θ(t))−H(θ(t1),θ(t))∫ZP(Z∣X,θ(t))logP(Z∣X,θ(t))−∫ZP(Z∣X,θ(t))logP(Z∣X,θ(t1))∫ZP(Z∣X,θ(t))logP(Z∣X,θ(t1))P(Z∣X,θ(t))KL(P(Z∣X,θ(t))∣∣P(Z∣X,θ(t1)))≥0 发现最后的形式是 P(Z∣X,θ)(t)P(Z|X,\theta)^{(t)}P(Z∣X,θ)(t) 和 P(Z∣X,θ(t1))P(Z|X,\theta^{(t1)})P(Z∣X,θ(t1)) 的 KL 散度故可以直接得到上式大于等于零收敛性得证。这里也可以由詹森不等式证得。
上面我们是给出最终的公式然后证明它的收敛性即 logP(X∣θ(t1))≥logP(X∣θ(t))\log P(X|\theta^{(t1)})\ge \log P(X|\theta^{(t)})logP(X∣θ(t1))≥logP(X∣θ(t)) 这样来说明 EM 算法确实可以以迭代的形式来最大化 P(X∣θ)P(X|\theta)P(X∣θ) 。但是这个公式是怎么得到的呢下面两小节我们分别从 KL 散度的角度和 Jensen 不等式的角度来推导 EM 算法的导出。
EM算法的导出——KL散度
我们再回顾一下整个算法的设定 观测数据XXX 隐变量ZZZ 完整数据(X,Z)(X,Z)(X,Z) 参数θ\thetaθ MLEθ^MLElogP(X∣θ)\hat{\theta}_{MLE}\log P(X|\theta)θ^MLElogP(X∣θ) EM 公式 θ(t1)argmaxθ∫logP(X,Z∣θ)P(Z∣X,θ(t))dZE步P(Z∣X,θ(t))→EZ∣X,θ(t)[logP(X,Z∣θ)]M步θ(t1)argmaxθEZ∣X,θ(t)[logP(X,Z∣θ)]\theta^{(t1)}\arg\max_{\theta}\int\log P(X,Z|\theta)P(Z|X,\theta^{(t)})dZ\\ E步P(Z|X,\theta^{(t)})\rightarrow \mathbb{E}_{Z|X,\theta^{(t)}}[\log P(X,Z|\theta)]\\ M步\theta^{(t1)}\arg\max_{\theta}\mathbb{E}_{Z|X,\theta^{(t)}}[\log P(X,Z|\theta)] θ(t1)argθmax∫logP(X,Z∣θ)P(Z∣X,θ(t))dZE步P(Z∣X,θ(t))→EZ∣X,θ(t)[logP(X,Z∣θ)]M步θ(t1)argθmaxEZ∣X,θ(t)[logP(X,Z∣θ)]
E 步求对数条件联合概率 logP(X,Z∣θ)\log P(X,Z|\theta)logP(X,Z∣θ) 关于后验 Z∣X,θ(t)Z|X,\theta^{(t)}Z∣X,θ(t) 的期望M 步选择一个新的 θ(t1)\theta^{(t1)}θ(t1) 使得上述期望达到最大。从而迭代地使得 logP(X∣θ)\log P(X|\theta)logP(X∣θ) 达到最大。上面已经证明了这个算法的收敛性。
下面开始推导公式的导出。我们还是从对数似然 logP(X∣θ)\log P(X|\theta)logP(X∣θ) 出发 logP(X∣θ)logP(X,Z∣θ)P(Z∣X,θ)logP(X,Z∣θ)−logP(Z∣X,θ)logP(X,Z∣θ)q(Z)−logP(Z∣X,θ)q(Z)\begin{align} \log P(X|\theta)\log \frac{P(X,Z|\theta)}{P(Z|X,\theta)}\\ \log P(X,Z|\theta)-\log P(Z|X,\theta)\\ \log \frac{P(X,Z|\theta)}{q(Z)}-\frac{\log P(Z|X,\theta)}{q(Z)} \end{align} logP(X∣θ)logP(Z∣X,θ)P(X,Z∣θ)logP(X,Z∣θ)−logP(Z∣X,θ)logq(Z)P(X,Z∣θ)−q(Z)logP(Z∣X,θ) 第一步先从似然引入隐变量 ZZZ 根据联合概率分布的公式进行改写 然后通过对数的性质写开 引入关于 ZZZ 的概率分布 q(Z)q(Z)q(Z) 两个对数里面同时除 q(Z)q(Z)q(Z) 然后两边同时求关于 q(Z)q(Z)q(Z) 的期望
左边∫Zq(Z)logP(X∣θ)dZlogP(X∣θ)∫Zq(Z)dZlogP(X∣θ)×1左边\int_Zq(Z)\log P(X|\theta)dZ\log P(X|\theta)\int_Zq(Z)dZ\log P(X|\theta)\times1 左边∫Zq(Z)logP(X∣θ)dZlogP(X∣θ)∫Zq(Z)dZlogP(X∣θ)×1
左边原来就与 ZZZ 无关相当于对常数求期望不变
右边∫Zq(Z)logP(X,Z∣θ)q(Z)dZ−∫Zq(Z)logP(Z∣X,θ)q(Z)dZELBOKL(q(Z)∣∣P(Z∣X,θ))\begin{align} 右边\int_Zq(Z)\log \frac{P(X,Z|\theta)}{q(Z)}dZ-\int_Zq(Z)\log\frac{ P(Z|X,\theta)}{q(Z)}dZ\\ ELBOKL(q(Z)||P(Z|X,\theta))\\ \end{align} 右边∫Zq(Z)logq(Z)P(X,Z∣θ)dZ−∫Zq(Z)logq(Z)P(Z∣X,θ)dZELBOKL(q(Z)∣∣P(Z∣X,θ)) 右边也求期望后后一项是 q(Z)q(Z)q(Z) 对 P(Z∣X,θ)P(Z|X,\theta)P(Z∣X,θ) 的相对熵也就是 KL 散度。而前一项我们通常称为 ELBO Evidence Lower BOund证据下界。很明显的 KL 散度是恒正的因此前一项 ELBO 是 logP(X∣θ)\log P(X|\theta)logP(X∣θ) 的一个下界。当且仅当后一项相对熵为零即两个分布完全相同 q(Z)P(Z∣X,θ(t))q(Z)P(Z|X,\theta^{(t)})q(Z)P(Z∣X,θ(t)) 时取到等号。 EM 算法的思想就是通过使得 ELBO 取得最大从而使得对数似然 logP(X∣θ)\log P(X|\theta)logP(X∣θ) 也达到最大。即
θ^argmaxθELBOargmaxθ∫Zq(Z)logP(X,Z∣θ)q(Z)dZargmaxθ∫ZP(X,Z∣θ(t))logP(X,Z∣θ)P(X,Z∣θ(t)))dZargmaxθ∫ZP(X,Z∣θ(t))[logP(X,Z∣θ)−logP(X,Z∣θ(t)))]dZargmaxθ∫ZP(X,Z∣θ(t))logP(X,Z∣θ)dZ\begin{align} \hat{\theta}\arg\max_{\theta}ELBO\\ \arg\max_{\theta}\int_Zq(Z)\log \frac{P(X,Z|\theta)}{q(Z)}dZ\\ \arg\max_{\theta}\int_ZP(X,Z|\theta^{(t)})\log \frac{P(X,Z|\theta)}{P(X,Z|\theta^{(t)}))}dZ\\ \arg\max_{\theta}\int_ZP(X,Z|\theta^{(t)})[\log P(X,Z|\theta)-\log P(X,Z|\theta^{(t)}))]dZ\\ \arg\max_{\theta}\int_ZP(X,Z|\theta^{(t)})\log P(X,Z|\theta)dZ\\ \end{align} θ^argθmaxELBOargθmax∫Zq(Z)logq(Z)P(X,Z∣θ)dZargθmax∫ZP(X,Z∣θ(t))logP(X,Z∣θ(t)))P(X,Z∣θ)dZargθmax∫ZP(X,Z∣θ(t))[logP(X,Z∣θ)−logP(X,Z∣θ(t)))]dZargθmax∫ZP(X,Z∣θ(t))logP(X,Z∣θ)dZ
当 q(Z)P(Z∣X,θ(t))q(Z)P(Z|X,\theta^{(t)})q(Z)P(Z∣X,θ(t)) 时取到等号代入进去在经过一次变换后我们发现中括号中后面一项与 θ\thetaθ 无关因此丢掉。注意在迭代算法中 θ(t),θ(t1)\theta^{(t)},\theta^{(t1)}θ(t),θ(t1) 都是常数θ\thetaθ 才是变量最终得到了 EM 的公式
EM算法的导出——Jensen不等式
下面我们再从 Jensen 不等式的角度来进行推导。
先来介绍一下 Jensen 不等式这里只介绍 EM 算法推导需要用到的程度
设 cta(1−t)bcta(1-t)bcta(1−t)b对于一个凸函数 f(x)f(x)f(x) 来说有 f(c)f(ta(1−t)b)≥tf(a)(1−t)f(b)f(c)f(ta(1-t)b)\ge tf(a)(1-t)f(b)f(c)f(ta(1−t)b)≥tf(a)(1−t)f(b) 。
我们如果取 t12t\frac{1}{2}t21 则有 f(12a12b)≥12f(a)12f(b)f(\frac{1}{2}a\frac{1}{2}b)\ge\frac{1}{2}f(a)\frac{1}{2}f(b)f(21a21b)≥21f(a)21f(b) 。即对凸函数来说均值的函数值大于等于函数值的均值。而在概率论中均值就是期望即有 f(E)≥Ef()f(\mathbb{E})\ge\mathbb{E}f()f(E)≥Ef()
下面开始推导 logP(X∣θ)log∫ZP(X,Z∣θ)dZlog∫ZP(X,Z∣θ)q(X)q(Z)dZlogEq(z)[P(X,Z∣θ)q(Z)]≥Eq(z)log[P(X,Z∣θ)q(Z)]\begin{align} \log P(X|\theta)\log\int_ZP(X,Z|\theta)dZ\\ \log\int_Z\frac{P(X,Z|\theta)}{q(X)}q(Z)dZ\\ \log\mathbb{E}_{q(z)}[\frac{P(X,Z|\theta)}{q(Z)}]\\ \ge \mathbb{E}_{q(z)}\log[\frac{P(X,Z|\theta)}{q(Z)}]\\ \end{align} logP(X∣θ)log∫ZP(X,Z∣θ)dZlog∫Zq(X)P(X,Z∣θ)q(Z)dZlogEq(z)[q(Z)P(X,Z∣θ)]≥Eq(z)log[q(Z)P(X,Z∣θ)]
同样是引入隐变量 ZZZ 这次转换为对联合概率分布积分的形式变形上下同乘 q(X)q(X)q(X)我们通常讲积分写成期望的形式log 函数是凸函数这里使用 Jensen 不等式其实这里得到的期望就是 ELBO
这里的等号当且仅当 P(X,Z∣θ)q(Z)\frac{P(X,Z|\theta)}{q(Z)}q(Z)P(X,Z∣θ) 是常数时取到即 P(X,Z∣θ)q(Z)Cq(Z)1CP(X,Z∣θ)∫Zq(Z)dZ∫Z1CP(X,Z∣θ)dZ11C∫ZP(X,Z∣θ)dZ1CP(X∣θ)\frac{P(X,Z|\theta)}{q(Z)}C\\ q(Z)\frac{1}{C}P(X,Z|\theta)\\ \int_Zq(Z)dZ\int_Z\frac{1}{C}P(X,Z|\theta)dZ\\ 1\frac{1}{C}\int_ZP(X,Z|\theta)dZ\frac{1}{C}P(X|\theta) q(Z)P(X,Z∣θ)Cq(Z)C1P(X,Z∣θ)∫Zq(Z)dZ∫ZC1P(X,Z∣θ)dZ1C1∫ZP(X,Z∣θ)dZC1P(X∣θ)
做一个变形等式两边同时对 ZZZ 求积分左边就是 1右边把 ZZZ 积掉得到 CP(X∣θ)CP(X|\theta)CP(X∣θ)代回到原式中
P(X,Z∣θ)q(Z)P(X∣θ)q(Z)P(X,Z∣θ)P(X∣θ)P(Z∣X,θ)\frac{P(X,Z|\theta)}{q(Z)}P(X|\theta)\\ q(Z)\frac{P(X,Z|\theta)}{P(X|\theta)}P(Z|X,\theta) q(Z)P(X,Z∣θ)P(X∣θ)q(Z)P(X∣θ)P(X,Z∣θ)P(Z∣X,θ)
可以看到 q(Z)q(Z)q(Z) 就是后验 P(Z∣X,θ(t))P(Z|X,\theta^{(t)})P(Z∣X,θ(t)) 这与我们在上一小节的结论是一致的再后面就与上一小节一样了不在赘述。
Ref
统计学习方法——李航机器学习白板推导
