EM算法（Expectation-Maximization），即期望-最大化算法。目标是估计某个概率分布函数中的参数θ\thetaθ，使得在事件xxx发生的期望值Ex(log⁡P(x∣θ))E_{x}(\log P(x|\theta))Ex​(logP(x∣θ))最大化。通常该问题可以通过最大似然估计的方法求解，但在许多情况下，数据的分布十分复杂，我们必须要引入一个隐变量zzz，假设xxx是由zzz产生的，而zzz的分布是可以自己假设的，从而减少了分布模型的复杂度。下面来简单的推导一下EM算法的过程，以帮助自己理解和记忆。
  首先，我们有对数似然函数L(θ)=log⁡P(x∣θ)L(\theta) = \log P(x|\theta)L(θ)=logP(x∣θ)引入隐变量zzz，可得到log⁡P(x∣θ)=log⁡P(x,z∣θ)−log⁡P(z∣x,θ)\log P(x|\theta)=\log P(x,z|\theta)-\log P(z|x,\theta)logP(x∣θ)=logP(x,z∣θ)−logP(z∣x,θ)证明过程如下，根据贝叶斯公式P(A∣B)=P(AB)P(B)P(A|B)=\frac{P(AB)}{P(B)}P(A∣B)=P(B)P(AB)​可得P(x,z∣θ)=P(x,z,θ)P(θ)⇒P(θ)=P(x,z,θ)P(x,z∣θ))P(x,z|\theta)=\frac{P(x,z,\theta)}{P(\theta)}\Rightarrow P(\theta)=\frac{P(x,z,\theta)}{P(x,z|\theta))}P(x,z∣θ)=P(θ)P(x,z,θ)​⇒P(θ)=P(x,z∣θ))P(x,z,θ)​P(z∣x,θ)=P(x,z,θ)P(x,θ)⇒P(x,θ)=P(x,z,θ)P(z∣x,θ))P(z|x,\theta)=\frac{P(x,z,\theta)}{P(x, \theta)}\Rightarrow P(x, \theta)=\frac{P(x,z,\theta)}{P(z|x,\theta))}P(z∣x,θ)=P(x,θ)P(x,z,θ)​⇒P(x,θ)=P(z∣x,θ))P(x,z,θ)​P(x∣θ)=P(x,θ)P(θ)=P(x,z∣θ)P(z∣x,θ)P(x|\theta)=\frac{P(x,\theta)}{P(\theta)}=\frac{P(x,z|\theta)}{P(z|x,\theta)}P(x∣θ)=P(θ)P(x,θ)​=P(z∣x,θ)P(x,z∣θ)​两边取对数可得log⁡P(x∣θ)=log⁡P(x,z∣θ)P(z∣x,θ)=log⁡P(x,z∣θ)−log⁡P(z∣x,θ)\log P(x|\theta)=\log \frac{P(x,z|\theta)}{P(z|x,\theta)}=\log P(x,z|\theta)-\log P(z|x,\theta)logP(x∣θ)=logP(z∣x,θ)P(x,z∣θ)​=logP(x,z∣θ)−logP(z∣x,θ)做一个恒等变换log⁡P(x∣θ)=log⁡P(x,z∣θ)−log⁡P(z)−[log⁡P(z∣x,θ)−log⁡P(z)]\log P(x|\theta)=\log P(x,z|\theta)-\log P(z)-[\log P(z|x,\theta)-\log P(z)]logP(x∣θ)=logP(x,z∣θ)−logP(z)−[logP(z∣x,θ)−logP(z)]log⁡P(x∣θ)=log⁡P(x,z∣θ)P(z)−log⁡P(z∣x,θ)P(z)\log P(x|\theta)=\log \frac{P(x,z|\theta)}{P(z)}-\log \frac{P(z|x, \theta)}{P(z)}logP(x∣θ)=logP(z)P(x,z∣θ)​−logP(z)P(z∣x,θ)​两边分别乘以P(z)P(z)P(z)并对zzz取积分可得∫zP(z)log⁡P(x∣θ)dz=∫zP(z)log⁡P(x,z∣θ)P(z)dz−∫zP(z)log⁡P(z∣x,θ)P(z)dz\int_zP(z)\log P(x|\theta)dz=\int_zP(z)\log \frac{P(x,z|\theta)}{P(z)}dz-\int_zP(z)\log \frac{P(z|x, \theta)}{P(z)}dz∫z​P(z)logP(x∣θ)dz=∫z​P(z)logP(z)P(x,z∣θ)​dz−∫z​P(z)logP(z)P(z∣x,θ)​dz由于P(x∣θ)P(x|\theta)P(x∣θ)是与zzz无关的函数，因此等号左边为∫zP(z)log⁡P(x∣θ)dz=log⁡P(x∣θ)∫zP(z)dz=log⁡P(x∣θ)\int_zP(z)\log P(x|\theta)dz=\log P(x|\theta)\int_zP(z)dz=\log P(x|\theta)∫z​P(z)logP(x∣θ)dz=logP(x∣θ)∫z​P(z)dz=logP(x∣θ)等号右边化简可得∫zP(z)log⁡P(x,z∣θ)P(z)dz−∫zP(z)log⁡P(z∣x,θ)P(z)dz=∫zP(z)log⁡P(x,z∣θ)P(z)dz−[∫zP(z)log⁡P(z∣x,θ)−P(z)log⁡P(z)dz]=∫zP(z)log⁡P(x,z∣θ)P(z)dz+[∫zP(z)log⁡P(z)−P(z)log⁡P(z∣x,θ)dz]=∫zP(z)log⁡P(x,z∣θ)P(z)dz+∫zP(z)log⁡P(z)P(z∣x,θ)dz=∫zP(z)log⁡P(x,z∣θ)P(z)dz+DKL(P(z)∥P(z∣x,θ))\int_zP(z)\log \frac{P(x,z|\theta)}{P(z)}dz-\int_zP(z)\log \frac{P(z|x, \theta)}{P(z)}dz\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \\ \\=\int_zP(z)\log \frac{P(x,z|\theta)}{P(z)}dz-[\int_zP(z)\log P(z|x,\theta)-P(z)\log P(z)dz]\\ \\=\int_zP(z)\log \frac{P(x,z|\theta)}{P(z)}dz+[\int_zP(z)\log P(z)-P(z)\log P(z|x,\theta)dz]\\ \\ =\int_zP(z)\log \frac{P(x,z|\theta)}{P(z)}dz+\int_zP(z)\log \frac{P(z)}{P(z|x, \theta)}dz\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \\ \\ =\int_zP(z)\log \frac{P(x,z|\theta)}{P(z)}dz+D_{KL}(P(z)\|P(z|x,\theta))\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \:∫z​P(z)logP(z)P(x,z∣θ)​dz−∫z​P(z)logP(z)P(z∣x,θ)​dz=∫z​P(z)logP(z)P(x,z∣θ)​dz−[∫z​P(z)logP(z∣x,θ)−P(z)logP(z)dz]=∫z​P(z)logP(z)P(x,z∣θ)​dz+[∫z​P(z)logP(z)−P(z)logP(z∣x,θ)dz]=∫z​P(z)logP(z)P(x,z∣θ)​dz+∫z​P(z)logP(z∣x,θ)P(z)​dz=∫z​P(z)logP(z)P(x,z∣θ)​dz+DKL​(P(z)∥P(z∣x,θ))其中DKL(P(z)∥P(z∣x,θ))≥0D_{KL}(P(z)\|P(z|x,\theta))\geq 0DKL​(P(z)∥P(z∣x,θ))≥0表示KL散度，因此可得log⁡P(x∣θ)≥∫zP(z)log⁡P(x,z∣θ)P(z)dz\log P(x|\theta)\geq \int_zP(z)\log \frac{P(x,z|\theta)}{P(z)}dzlogP(x∣θ)≥∫z​P(z)logP(z)P(x,z∣θ)​dz我们称不等号的右侧式子为ELBO(evidence lower bound)，当且仅当DKL(P(z)∥P(z∣x,θ))=0D_{KL}(P(z)\|P(z|x,\theta))= 0DKL​(P(z)∥P(z∣x,θ))=0时等号成立，即P(z)=P(z∣x,θ)P(z)=P(z|x,\theta)P(z)=P(z∣x,θ)P(z∣x,θ)P(z|x,\theta)P(z∣x,θ)表示zzz的后验概率，我们可以令第iii次迭代时，zzz的后验概率为P(z)=P(z∣x,θ(i))P(z)=P(z|x,\theta^{(i)})P(z)=P(z∣x,θ(i))则ELBO=∫zP(z)log⁡P(x,z∣θ)P(z)dz=∫zP(z∣x,θ(i))log⁡P(x,z∣θ)P(z∣x,θ(i))dzELBO=\int_zP(z)\log \frac{P(x,z|\theta)}{P(z)}dz\: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \: \\=\int_zP(z|x,\theta^{(i)})\log \frac{P(x,z|\theta)}{P(z|x,\theta^{(i)})}dzELBO=∫z​P(z)logP(z)P(x,z∣θ)​dz=∫z​P(z∣x,θ(i))logP(z∣x,θ(i))P(x,z∣θ)​dz计算在参数θ(i)\theta^{(i)}θ(i)的条件下，期望值Ez∣x,θ(i)[log⁡P(x,z∣θ)]=ELBOE_{z|x,\theta^{(i)}}[\log P(x,z|\theta)]=ELBOEz∣x,θ(i)​[logP(x,z∣θ)]=ELBO的过程就是EM算法中的E步，核心在于计算zzz的后验概率P(z∣x,θ)P(z|x,\theta)P(z∣x,θ)。M步则是寻找更优的模型参数θ\thetaθ以最大化对数似然函数log⁡P(x∣θ)\log P(x|\theta)logP(x∣θ)，其等价于最大化ELBO，即θ(i+1)=arg max⁡θlog⁡P(x∣θ)=arg max⁡θELBO=arg max⁡θ∫zP(z∣x,θ(i))log⁡P(x,z∣θ)P(z∣x,θ(i))dz=arg max⁡θ∫z[P(z∣x,θ(i))log⁡P(x,z∣θ)−P(z∣x,θ(i))log⁡P(z∣x,θ(i))]dz=arg max⁡θ∫zP(z∣x,θ(i))log⁡P(x,z∣θ)dz\theta^{(i+1)}=\argmax_{\theta}\log P(x|\theta)\: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \\ \\=\argmax_{\theta}ELBO\: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \:\: \\ \\=\argmax_{\theta}\int_zP(z|x,\theta^{(i)})\log \frac{P(x,z|\theta)}{P(z|x,\theta^{(i)})}dz\: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \:\: \: \:\: \: \\ \\=\argmax_{\theta}\int_z[P(z|x,\theta^{(i)})\log P(x,z|\theta)-P(z|x,\theta^{(i)})\log P(z|x,\theta^{(i)})]dz\\ \\=\argmax_{\theta}\int_zP(z|x,\theta^{(i)})\log P(x,z|\theta)dz\: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \:\: \: \: \: \: \: \: \: \: \: \:\: \: \: \: \: \:\: \: \:\: \:\:\: \:\:\: \:θ(i+1)=θargmax​logP(x∣θ)=θargmax​ELBO=θargmax​∫z​P(z∣x,θ(i))logP(z∣x,θ(i))P(x,z∣θ)​dz=θargmax​∫z​[P(z∣x,θ(i))logP(x,z∣θ)−P(z∣x,θ(i))logP(z∣x,θ(i))]dz=θargmax​∫z​P(z∣x,θ(i))logP(x,z∣θ)dz上式最后一步推导，是因为P(z∣x,θ(i))log⁡P(z∣x,θ(i))P(z|x,\theta^{(i)})\log P(z|x,\theta^{(i)})P(z∣x,θ(i))logP(z∣x,θ(i))是与θ\thetaθ无关的常数项，因此可以可以直接忽略。EM算法就是，通过先固定参数θ\thetaθ调整后验概率P(z)P(z)P(z)，然后再固定P(z)P(z)P(z)，调整θ\thetaθ使得期望达到最大。重复迭代E和M步，直至收敛。