EM算法原理推导+案例讲解_em-map算法推导

前言

​ EM算法是针对有隐变量的求解极大似然或者最大后验的有效方法。因为我也是正在学习的缘故，所以我将从一个初学者的角度，复现学习过程中遇到的种种问题，本文将从案例出发，对算法原理进行推导证明。

推导

案例引入

​ 以下案例来自李航老师的《机器学习》

​ 假如，我们现在有三枚硬币，A、B、C，它们正面朝上的概率的为$\pi 、q、p$。现在，我们要做的事情是，先抛硬币A，如果硬币A是正面，我们选择硬币B；否则如果硬币A是反面，我们选择硬币C。随后，抛选择到的硬币(B或C)，如果正面朝上，则记作y=1，反面朝上，则记为y=0。

​ 现在，我们假设，我们最终实验10次的结果得到的是

​ 现在，有一个问题。如果我们抛硬币的时候，无法知道从抛硬币A得到了B还是C，仅仅只知道了最终的结果，我们没有没办法求出参数 θ = { π , q , p } \theta=\{\pi,q,p\} θ={π,q,p}呢？

​ 一般遇到这种问题，我们最初的思路是咋样的？是要我们做的实现足够多，就可以使用极大似然估计，求出对应的参数，所以
$$\hat{\theta }=\underset{\theta }{\max }P(Y|\theta )$$
​ 其中，$Y=(y_1,y_2,\cdots ,y_n{)}^T$，代表·n个观测数据，y作为随机变量

​ 对于$P(Y|\theta )$，最大的问题是什么？是我们压根不晓得它是什么概率分布，如果我们知道了他的概率分布，也就知道了这个似然函数是什么。那么就可以计算了。

​ 仔细看这个东西，Y是从哪里得出来的？依题目，其是从B、C的出来的。那么我们是否可以将B、C引入进似然函数中来呢？答案是可以的，我们将他们记作z，称为隐变量，那么似然函数
P ( Y ∣ θ ) = ∑ Z P ( Y , Z ∣ θ ) = ∑ Z P ( Y ∣ Z , θ ) P ( Z ∣ θ )

$$\begin{equation} \begin{aligned} P(Y|\theta)&=\sum\limits_{Z}P(Y,Z|\theta) \\&=\sum\limits_{Z}P(Y|Z,\theta)P(Z|\theta) \end{aligned} \end{equation}$$ P(Y∣θ)​=Z∑​P(Y,Z∣θ)=Z∑​P(Y∣Z,θ)P(Z∣θ)​​​
​ 其中$Z=(z_1,z_2,\cdots ,z_n{)}^T$，代表n个隐藏数据，z作为随机变量。

​ 通过简单的变化，我们就可以表达出来了

​ 首先来看$P(Z|\theta )$，这是什么？注意了，此处我们始终认为$\theta$是一个参数，而不是随机变量，所以严谨一些，其还可以写作$P_{\theta }(Z)$，所以其并不是条件概率，而是一个普通的概率，前面我们说到，Z就是选择B或者C的隐变量，那决定隐变量的取值的概率不就是$\pi$吗？

​ 所以对于正面朝上的概率为$P(z_i|\theta )=\pi$，反面则为$P(z_i|\theta )=1-\pi$。

​ 那再看$P(y_i|z_i,\theta )$，这不就是给定隐变量Z，求出$Y_i$的概率吗？所以
P ( Y ∣ θ ) = ∏ i = 1 n P ( y i ∣ θ ) = ∏ i = 1 n ∑ z i P ( y i , z i ∣ θ ) = ∏ i = 1 n [ π q y i ( 1 − q ) 1 − y i + ( 1 − π ) p y i ( 1 − p ) 1 − y i ]

$$\begin{equation} \begin{aligned} &P(Y|\theta) \\=&\prod\limits_{i=1}^nP(y_i|\theta) \\=&\prod\limits_{i=1}^n\sum\limits_{z_i}P(y_i,z_i|\theta) \\=&\prod\limits_{i=1}^n \left[ \pi{q}^{y_i}(1-q)^{1-y_i}+(1-\pi)p^{y_i}(1-p)^{1-y_i} \right] \end{aligned} \end{equation}$$ ===​P(Y∣θ)i=1∏n​P(yi​∣θ)i=1∏n​zi​∑​P(yi​,zi​∣θ)i=1∏n​[πqyi​(1−q)1−yi​+(1−π)pyi​(1−p)1−yi​]​​​
​ 所以
$$\underset{\theta }{\max }P(Y|\theta )=\underset{\theta }{\max }\prod _{i=1}^n\left[\pi q^{y_i}(1-q{)}^{1-y_i}+(1-\pi )p^{y_i}(1-p{)}^{1-y_i}\right]$$
​ 再说一次， θ = { π , q , p } \theta=\{\pi,q,p\} θ={π,q,p}

​ 要求极大似然，第一眼看上去，想当燃取log求导。但是我们会发现并没有解析解。

​ 那么该如何解决这个问题呢？这就要提到我们的EM算法了。

狭义EM

​ 所谓EM算法，实际上是一种迭代收敛算法。其名字EM拆开，E代表均值，M代表极大值，因此其也叫均值极大算法。

​ EM算法分为两步。

​ ①给定$P(Z|Y,{\theta }^t)\to E_{P(Z|Y,{\theta }^t)}\left[logP(Z,Y|\theta )\right]$

​ ②${\theta }^{t+1}=\underset{\theta }{\max }{E}_{P(Z|Y,{\theta }^t)}\left[logP(Z,Y|\theta )\right]$

​ 注意了，这里的$E_{P(Z|Y,|{\theta }^t)}\left[logP(Z,Y|\theta )\right]$意为$logP(Z,Y|\theta )$对$P(Z|Y,{\theta }^t)$求均值。可以变化为(注意了，式子中，$P(Z|Y,{\theta }^t)$是不在log里面的，仅仅是为了写作的简便，并且假设Z是连续变量，望知悉。下文亦如此)
$$E_{P(Z|Y,{\theta }^t)}\left[logP(Z,Y|\theta )\right]={\int }_{Z}logP(Z.Y|\theta )P(Z|Y,{\theta }^t)dZ$$
​ EM算法就是酱紫，只要不断地循环①、②步，最后就可以收敛。接下来的问题就是，这玩意儿是怎么来的？又为什么这样可以收敛？

问题一：怎么来的？

​ 下面先给出其具体推导
因为： P ( Y ) = P ( Z , Y ) P ( Z ∣ Y ) 所以 : P ( Y ∣ θ ) = P ( Z , Y ∣ θ ) P ( Z ∣ Y , θ ) 所以 : l o g P ( Y ∣ θ ) = l o g P ( Z , Y ∣ θ ) − l o g P ( Z ∣ Y , θ ) 引入关于隐变量的分布 q ( Z ) ，并在等式右边 l o g 里面除以 q ( Z ) 得： l o g P ( Y ∣ θ ) = l o g P ( Z , Y ∣ θ ) q ( Z ) − l o g P ( Z ∣ Y , θ ) q ( Z )

$$\begin{equation} \begin{aligned} 因为：&P(Y)=\frac{P(Z,Y)}{P(Z|Y)} \\所以:&P(Y|\theta)=\frac{P(Z,Y|\theta)}{P(Z|Y,\theta)} \\所以:&logP(Y|\theta)=logP(Z,Y|\theta)-logP(Z|Y,\theta) \\&引入关于隐变量的分布q(Z)，并在等式右边log里面除以q(Z) \\得：&logP(Y|\theta)=log\frac{P(Z,Y|\theta)}{q(Z)}-log\frac{P(Z|Y,\theta)}{q(Z)} \end{aligned} \end{equation}$$ 因为：所以:所以:得：​P(Y)=P(Z∣Y)P(Z,Y)​P(Y∣θ)=P(Z∣Y,θ)P(Z,Y∣θ)​logP(Y∣θ)=logP(Z,Y∣θ)−logP(Z∣Y,θ)引入关于隐变量的分布q(Z)，并在等式右边log里面除以q(Z)logP(Y∣θ)=logq(Z)P(Z,Y∣θ)​−logq(Z)P(Z∣Y,θ)​​​​
​ 对等式左右两边同时对$q(Z)$积分

​ 左边得
$${\int }_{Z}logP(Y|\theta )q(Z)dZ=logP(Y|\theta ){\int }_{Z}q(Z)dZ=logP(Y|\theta )$$
​ 所以最终等式为
l o g P ( Y ∣ θ ) = ∫ Z l o g P ( Z , Y ∣ θ ) q ( Z ) q ( Z ) d Z − ∫ Z l o g P ( Z ∣ Y , θ ) q ( Z ) q ( Z ) d Z = ∫ Z l o g P ( Z , Y ∣ θ ) q ( Z ) q ( Z ) d Z + ∫ Z l o g q ( Z ) P ( Z ∣ Y , θ ) q ( Z ) d Z

$$\begin{equation} \begin{aligned} logP(Y|\theta)&=\int_Zlog\frac{P(Z,Y|\theta)}{q(Z)}q(Z)dZ-\int_Zlog\frac{P(Z|Y,\theta)}{q(Z)}q(Z)dZ \\=&\int_Zlog\frac{P(Z,Y|\theta)}{q(Z)}q(Z)dZ+\int_Zlog\frac{q(Z)}{P(Z|Y,\theta)}q(Z)dZ \end{aligned} \end{equation}$$ logP(Y∣θ)=​=∫Z​logq(Z)P(Z,Y∣θ)​q(Z)dZ−∫Z​logq(Z)P(Z∣Y,θ)​q(Z)dZ∫Z​logq(Z)P(Z,Y∣θ)​q(Z)dZ+∫Z​logP(Z∣Y,θ)q(Z)​q(Z)dZ​​​
​ 仔细看，对于${\int }_{Z}log\frac{q(Z)}{P(Z|Y,\theta )}q(Z)dZ$，这个形式我一般称为两个概率分布的KL散度，意思可以简单理解为是两个概率分布的相似程度，所以
$$KL(q(Z)||P(Z|Y,\theta ))={\int }_{Z}log\frac{q(Z)}{P(Z|Y,\theta )}q(Z)d$$
​ 他表示概率概率分布$q(Z)$和$P(Z|Y.\theta )$的相似程度。它有个特性，KL散度是大于等于0，即$KL(q(Z)||P(Z|Y,\theta ))\ge 0$，当且仅当$q(Z)=P(Z|Y,\theta )$等号成立。

​ 所以
$$logP(Y|\theta )\ge {\int }_{Z}log\frac{P(Z,Y|\theta )}{q(Z)}q(Z)dz$$
​ 当$KL(q(Z)||P(Z|Y,\theta ))=0$时等号成立。

​ 所以，要$\underset{\theta }{\max }logP(Y|\theta )$，当$q(Z)=P(Z|Y,{\theta }^t)$，$KL(q(Z)||P(Z|Y,{\theta }^t))=0$，注意了，此时的$P(Z|Y,\theta )$里面的${\theta }^t$是上一轮的$\theta$，为啥我要用上一轮的？因为EM是一个迭代式算法。并且这样后面可以进行收敛性证明
max ⁡ θ l o g P ( Y ∣ θ ) = max ⁡ θ ∫ Z l o g P ( Z , Y ∣ θ ) P ( Z ∣ Y , θ t ) P ( Z ∣ Y , θ t ) d Z = max ⁡ θ ∫ Z [ l o g P ( Z , Y ∣ θ ) − l o g P ( Z ∣ Y , θ t ) ] P ( Z ∣ Y , θ t ) d Z = max ⁡ θ ∫ Z l o g P ( Z , Y ∣ θ ) P ( Z ∣ Y , θ t ) d Z − ∫ Z l o g P ( Z ∣ Y , θ t ) P ( Z ∣ Y , θ t ) d Z 因为后面一部分的 θ t 是确定的，所以 = max ⁡ θ ∫ Z l o g P ( Z , Y ∣ θ ) P ( Z ∣ Y , θ t ) d Z = θ t + 1

$$\begin{equation} \begin{aligned} \max\limits_{\theta}logP(Y|\theta)&=\max\limits_{\theta}\int_Zlog\frac{P(Z,Y|\theta)}{P(Z|Y,\theta^t)}P(Z|Y,\theta^t)dZ \\&=\max\limits_{\theta}\int_Z\left[logP(Z,Y|\theta)-logP(Z|Y,\theta^t)\right]P(Z|Y,\theta^t)dZ \\&=\max\limits_{\theta}\int_ZlogP(Z,Y|\theta)P(Z|Y,\theta^t)dZ-\int_ZlogP(Z|Y,\theta^t)P(Z|Y,\theta^t)dZ \\&因为后面一部分的\theta^t是确定的，所以 \\&=\max\limits_{\theta}\int_ZlogP(Z,Y|\theta)P(Z|Y,\theta^t)dZ \\&={\theta^{t+1}} \end{aligned} \end{equation}$$ θmax​logP(Y∣θ)​=θmax​∫Z​logP(Z∣Y,θt)P(Z,Y∣θ)​P(Z∣Y,θt)dZ=θmax​∫Z​[logP(Z,Y∣θ)−logP(Z∣Y,θt)]P(Z∣Y,θt)dZ=θmax​∫Z​logP(Z,Y∣θ)P(Z∣Y,θt)dZ−∫Z​logP(Z∣Y,θt)P(Z∣Y,θt)dZ因为后面一部分的θt是确定的，所以=θmax​∫Z​logP(Z,Y∣θ)P(Z∣Y,θt)dZ=θt+1​​​
​ 所以就推出来了。

问题二：收敛性证明

​ 对于我们的损失函数，我们只需要证明
l o g P ( Y ∣ θ t ) ≤ l o g P ( Y ∣ θ t + 1 )

$$\begin{equation} \begin{aligned} logP(Y|\theta^t)\le{logP(Y|\theta^{t+1})} \end{aligned} \end{equation}$$ logP(Y∣θt)≤logP(Y∣θt+1)​​​
​ 所以
$$logP(Y|\theta )=logP(Y,Z|\theta )-logP(Z|Y,\theta )$$
​ 等式左右两边对$P(Z|Y，{\theta }^t)$求积分。左边
$${\int }_{Z}logP(Y|\theta )P(Z|Y,{\theta }^t)dZ=logP(Y|\theta ){\int }_{Z}P(Z|Y,{\theta }^t)=logP(Y|\theta )$$
​ 所以
$$logP(Y|\theta )={\int }_{Z}P(Y,Z|\theta )P(Z|Y，{\theta }^t)dZ-{\int }_{Z}logP(Z|Y,\theta )P(Z|Y，{\theta }^t)dZ$$
​ 定义Q函数和H函数
$$\begin{gathered} Q(\theta ,{\theta }^t)={\int }_{Z}P(Y,Z|\theta )P(Z|Y，{\theta }^t)dZ \\ H(\theta ,{\theta }^t)=-{\int }_{Z}logP(Z|Y,\theta )P(Z|Y，{\theta }^t)dZ \end{gathered}$$
​ 看这个Q函数，这不就是我们上面提到EM算法吗？我们上面是这样说到的
$${\theta }^{t+1}=\underset{\theta }{\max }{E}_{P(Z|Y,|{\theta }^t)}\left[logP(Z,Y|\theta )\right]=\underset{\theta }{\max }{\int }_{Z}logP(Z.Y|\theta )P(Z|Y,{\theta }^t)dZ$$
​ 所以有
$${\int }_{Z}logP(Z.Y|{\theta }^{t+1})P(Z|Y,{\theta }^t)dZ\ge {\int }_{Z}logP(Z.Y|\theta )P(Z|Y,{\theta }^t)dZ$$
​ 所以
$$Q({\theta }^{t+1},{\theta }^t)\ge Q(\theta ,{\theta }^t)$$
​ 所以，不论$\theta$取什么，始终成立，所以也有
$$Q({\theta }^{t+1},{\theta }^t)\ge Q({\theta }^t,{\theta }^t)$$
​ 对于$H(\theta ,{\theta }^t)$，只需要同样证明
$$H({\theta }^{t+1},{\theta }^t)\ge H({\theta }^t,{\theta }^t)$$
​ 所以
$$\begin{array}{c}\begin{array}{rl}& H({\theta }^{t+1},{\theta }^t)-H({\theta }^t,{\theta }^t)\ge 0\\ =& -{\int }_{Z}logP(Z|Y,{\theta }^{t+1})P(Z|Y，{\theta }^t)dZ+{\int }_{Z}logP(Z|Y,{\theta }^t)P(Z|Y，{\theta }^t)dZ\ge 0\\ =& {\int }_{Z}P(Z|Y,{\theta }^t)\left[log\frac{P(Z|Y,{\theta }^t)}{P(Z|Y,{\theta }^{t+1})}\right]dZ\\ =& KL\left(P(Z|Y,{\theta }^t)||P(Z|Y,{\theta }^{t+1})\right)\end{array}\end{array}$$
​ 同样的KL散度，根据性质恒大于等于0.

​ 因为
$$\begin{gathered} P(Y|{\theta }^{t+1})=Q({\theta }^{t+1},{\theta }^t)+H({\theta }^{t+1},{\theta }^t); \\ P(Y|{\theta }^t)=Q({\theta }^t,{\theta }^t)+H({\theta }^t,{\theta }^t); \end{gathered}$$
​ 所以得证
$$P(Y|{\theta }^{t+1})\ge P(Y|{\theta }^t)$$
​ 所以呢？既然算法本身可行，那直接用来解前面的问题就可以了嘛

案例求解

​ 在求解之前，为了防止出现误解，我们先对之前的所有的量都重定义一下，先先来定义一下观测变量y
Y = ( y 1 y 2 ⋮ y n ) Y=

$$\begin{pmatrix} y_1 \\ y_2 \\\vdots \\ y_n \end{pmatrix}$$ Y= ​y1​y2​⋮yn​​ ​
​ 这里的Y表示其包含了所有数据，前面提到过，而$y_i$代表第i个数据。这些数据也被称为观测数据。也就是案例中我们观测到的数据（0或1）

​ 除此之外，还有一个隐变量z，这些隐变量，实际上就是上文中提到的每次选出一个观测变量y，都会有一个对应的隐数据Z，也就是投掷硬币A得出的结果。定义隐变量z
Z = ( z 1 z 2 ⋮ z n ) Z=

$$\begin{pmatrix} z_1 \\ z_2 \\\vdots \\ z_n \end{pmatrix}$$ Z= ​z1​z2​⋮zn​​ ​
​ $z_i$代表第i次实验得到的隐藏数据。

​ 而隐变量和观测变量的对应数据的结合也被称为完整数据
( Y , Z ) = ( ( y 1 , z 1 ) ( y 2 , z 2 ) ⋮ ( y n , z n ) ) (Y,Z)=

$$\begin{pmatrix} (y_1,z_1) \\ (y_2,z_2) \\\vdots \\ (y_n,z_n) \end{pmatrix}$$ (Y,Z)= ​(y1​,z1​)(y2​,z2​)⋮(yn​,zn​)​ ​
​ 而对于硬币A，B，C正面的概率，为了方便表达我们做出以下定义

​ $C1$用作标记，下文中记作$Ck$，方便后面写并且${\pi }_1+{\pi }_2=1$，即$\sum _{k=1}^2=1$

​ 而对于B，C

​ 现在，我们回顾一下我们的目标
$$\underset{\theta }{\max }P(Y|\theta )$$
​ 要使用EM对其求解，我们就要求出（Z是离散变量，故用$\sum$）
E P ( Z ∣ Y , θ t ) [ l o g P ( Z , Y ∣ θ ) ] = ∑ Z l o g P ( Z , Y ∣ θ ) P ( Z ∣ Y , θ t ) = ∑ Z l o g ∏ i = i n P ( z i , y i ∣ θ ) ∏ i = 1 P ( z i ∣ y i , θ t )

$$\begin{equation} \begin{aligned} &{E_{P(Z|Y,\theta^{t})}\left[logP(Z,Y|\theta)\right]} \\=&\sum\limits_{Z}logP(Z,Y|\theta)P(Z|Y,\theta^t) \\=&\sum\limits_{Z}log\prod_{i=i}^nP(z_i,y_i|\theta)\prod\limits_{i=1}P(z_i|y_i,\theta^t) \end{aligned} \end{equation}$$ ==​EP(Z∣Y,θt)​[logP(Z,Y∣θ)]Z∑​logP(Z,Y∣θ)P(Z∣Y,θt)Z∑​logi=i∏n​P(zi​,yi​∣θ)i=1∏​P(zi​∣yi​,θt)​​​
​ 在一般的算法模型中，一般情况下我们都会消去连乘号，因为其计算量相对复杂，并且求导的难度也大。

所以
∑ Z l o g ∏ i = i n P ( z i , y i ∣ θ ) ∏ i = 1 P ( z i ∣ y i , θ t ) = ∑ Z ∑ i = 1 n l o g P ( z i , y i ∣ θ ) ∏ i = 1 P ( z i ∣ y i , θ t ) = ∑ Z [ l o g P ( z 1 , y 1 ∣ θ ) + l o g P ( z 2 , y 2 ∣ θ ) + ⋯ + l o g P ( z n , y n ∣ θ ) ] ∏ i = 1 P ( z i ∣ y i , θ t ) = ∑ z 1 , z 2 ⋯   , z n [ l o g P ( z 1 , y 1 ∣ θ ) + l o g P ( z 2 , y 2 ∣ θ ) + ⋯ + l o g P ( z n , y n ∣ θ ) ] ∏ i = 1 P ( z i ∣ y i , θ t ) = ∑ z 1 , z 2 ⋯   , z n l o g P ( z 1 , y 1 ∣ θ ) ∏ i = 1 P ( z i ∣ y i , θ t ) + ∑ z 1 , z 2 ⋯   , z n l o g P ( z 2 , y 2 ∣ θ ) ∏ i = 1 P ( z i ∣ y i , θ t ) + ⋯ + ∑ z 1 , z 2 ⋯   , z n l o g P ( z n , y n ∣ θ ) ∏ i = 1 P ( z i ∣ y i , θ t )

$$\begin{equation} \begin{aligned} &\sum\limits_{Z}log\prod_{i=i}^nP(z_i,y_i|\theta)\prod\limits_{i=1}P(z_i|y_i,\theta^t) \\=&\sum_{Z}\sum\limits_{i=1}^nlogP(z_i,y_i|\theta)\prod\limits_{i=1}P(z_i|y_i,\theta^t) \\=&\sum\limits_{Z}\left[logP(z_1,y_1|\theta)+logP(z_2,y_2|\theta)+\cdots+logP(z_n,y_n|\theta)\right]\prod\limits_{i=1}P(z_i|y_i,\theta^t) \\=&\sum\limits_{z_1,z_2\cdots,z_n}\left[logP(z_1,y_1|\theta)+logP(z_2,y_2|\theta)+\cdots+logP(z_n,y_n|\theta)\right]\prod\limits_{i=1}P(z_i|y_i,\theta^t) \\=&\sum\limits_{z_1,z_2\cdots,z_n}logP(z_1,y_1|\theta)\prod\limits_{i=1}P(z_i|y_i,\theta^t)+\sum\limits_{z_1,z_2\cdots,z_n}logP(z_2,y_2|\theta)\prod\limits_{i=1}P(z_i|y_i,\theta^t)+\cdots+\\&\sum\limits_{z_1,z_2\cdots,z_n}logP(z_n,y_n|\theta)\prod\limits_{i=1}P(z_i|y_i,\theta^t) \end{aligned} \end{equation}$$ ====​Z∑​logi=i∏n​P(zi​,yi​∣θ)i=1∏​P(zi​∣yi​,θt)Z∑​i=1∑n​logP(zi​,yi​∣θ)i=1∏​P(zi​∣yi​,θt)Z∑​[logP(z1​,y1​∣θ)+logP(z2​,y2​∣θ)+⋯+logP(zn​,yn​∣θ)]i=1∏​P(zi​∣yi​,θt)z1​,z2​⋯,zn​∑​[logP(z1​,y1​∣θ)+logP(z2​,y2​∣θ)+⋯+logP(zn​,yn​∣θ)]i=1∏​P(zi​∣yi​,θt)z1​,z2​⋯,zn​∑​logP(z1​,y1​∣θ)i=1∏​P(zi​∣yi​,θt)+z1​,z2​⋯,zn​∑​logP(z2​,y2​∣θ)i=1∏​P(zi​∣yi​,θt)+⋯+z1​,z2​⋯,zn​∑​logP(zn​,yn​∣θ)i=1∏​P(zi​∣yi​,θt)​​​
​ 我们先看第一项
$$\begin{array}{c}\begin{array}{rl}& \sum _{z_1,z_2\cdots ,z_n}logP(z_1,y_1|\theta )\prod _{i=1}P(z_i|y_i,{\theta }^t)\\ =& \sum _{z_1,z_2\cdots ,z_n}logP(z_1,y_1|\theta )P(z_1|y_1,{\theta }^t)\prod _{i=2}P(z_i|y_i,{\theta }^t)\\ =& \sum _{z_1}logP(z_1,y_1|\theta )P(z_1|y_1,{\theta }^t)\sum _{z_2\cdots ,z_n}\prod _{i=2}P(z_i|y_i,{\theta }^t)\\ & 因为\sum _{z_2\cdots ,z_n}\prod _{i=2}P(z_i|y_i,{\theta }^t)积分为1\\ =& \sum _{z_1}logP(z_1,y_1|\theta )P(z_1|y_1,{\theta }^t)\end{array}\end{array}$$

​ 所以所有项相加就得
E P ( Z ∣ Y , θ t ) [ l o g P ( Z , Y ∣ θ ) ] = ∑ i = 1 n ∑ z i l o g P ( z i , y i ∣ θ ) P ( z i ∣ y i , θ t ) = ∑ i = 1 n ∑ k = 1 2 l o g P ( z i = C k , y i ∣ θ ) P ( z i = C k ∣ y i , θ t ) = ∑ k = 1 2 ∑ i = 1 n l o g P ( z i = C k , y i ∣ θ ) P ( z i = C k ∣ y i , θ t )

$$\begin{equation} \begin{aligned} &{E_{P(Z|Y,\theta^{t})}\left[logP(Z,Y|\theta)\right]} \\=&\sum\limits_{i=1}^n\sum\limits_{z_i}logP(z_i,y_i|\theta)P(z_i|y_i,\theta^t) \\=&\sum\limits_{i=1}^n\sum\limits_{k=1}^2logP(z_i=Ck,y_i|\theta)P(z_i=Ck|y_i,\theta^t) \\=&\sum\limits_{k=1}^2\sum\limits_{i=1}^nlogP(z_i=Ck,y_i|\theta)P(z_i=Ck|y_i,\theta^t) \end{aligned} \end{equation}$$ ===​EP(Z∣Y,θt)​[logP(Z,Y∣θ)]i=1∑n​zi​∑​logP(zi​,yi​∣θ)P(zi​∣yi​,θt)i=1∑n​k=1∑2​logP(zi​=Ck,yi​∣θ)P(zi​=Ck∣yi​,θt)k=1∑2​i=1∑n​logP(zi​=Ck,yi​∣θ)P(zi​=Ck∣yi​,θt)​​​
​ 因此，式子最终变成了连加，接下来只要求出对应的概率即可

​ 先看$P(y)$，省略掉$\theta$，因为他是参数，不是随机变量，因此对任意一个$y_i$，有
P ( y i ) = ∑ z i P ( y i , z i ) = ∑ z i P ( y i ∣ z i ) P ( z i ) = ∑ k = 1 K P ( y i ∣ z i = C k ) P ( z i = C k ) = ∑ k = 1 K p k y i ( 1 − p k ) 1 − y i π k

$$\begin{equation} \begin{aligned} P(y_i)=&\sum\limits_{z_i}P(y_i,z_i) \\=&\sum\limits_{z_i}P(y_i|z_i)P(z_i) \\=&\sum\limits_{k=1}^KP(y_i|z_i=Ck)P(z_i=Ck) \\=&\sum\limits_{k=1}^Kp_k^{y_i}(1-p_k)^{1-y_i}\pi_k \end{aligned} \end{equation}$$ P(yi​)====​zi​∑​P(yi​,zi​)zi​∑​P(yi​∣zi​)P(zi​)k=1∑K​P(yi​∣zi​=Ck)P(zi​=Ck)k=1∑K​pkyi​​(1−pk​)1−yi​πk​​​​
​ 再看$P(y,z)$
$$\begin{array}{c}\begin{array}{rl}P(y_i,z_i=Ck)=& P(y_i|z_i=Ck)P(z_i=Ck)\\ =& p_k^{y_i}(1-p_k{)}^{1-y_i}{\pi }_k\end{array}\end{array}$$
​ 对于$P(z|y)$
$$\begin{array}{c}\begin{array}{rl}P(z_i=Ck|y_i)=& \frac{P(z_i=Ck,y_i)}{P(y_i)}\\ =& \frac{p_k^{y_i}(1-p_k{)}^{1-y_i}{\pi }_k}{\sum _{k=1}^K{p}_k^{y_i}(1-p_k{)}^{1-y_i}{\pi }_k}\end{array}\end{array}$$
​ 请注意分子和分母的$k$，分子的$k$是输入的值，而分母的$k$是求和符滴。

​ 所以最终结果为
E P ( Z ∣ Y , θ t ) [ l o g P ( Z , Y ∣ θ ) ] = ∑ k = 1 2 ∑ i = 1 n l o g P ( z i = C k , y i ∣ θ ) P ( z i = C k ∣ y i , θ t ) = ∑ k = 1 2 ∑ i = 1 n l o g [ p k y i ( 1 − p k ) 1 − y i π k ] P ( z i = C k ∣ y i , θ t ) = ∑ k = 1 2 ∑ i = 1 n [ l o g π k + y i l o g p k + ( 1 − y k ) l o g ( 1 − p k ) ] P ( z i = C k ∣ y i , θ t )

$$\begin{equation} \begin{aligned} &{E_{P(Z|Y,\theta^{t})}\left[logP(Z,Y|\theta)\right]} \\=&\sum\limits_{k=1}^2\sum\limits_{i=1}^nlogP(z_i=Ck,y_i|\theta)P(z_i=Ck|y_i,\theta^t) \\=&\sum\limits_{k=1}^2\sum\limits_{i=1}^nlog \left[ p_k^{y_i}(1-p_k)^{1-y_i}\pi_k \right]P(z_i=Ck|y_i,\theta^t) \\=&\sum\limits_{k=1}^2\sum\limits_{i=1}^n\left[log \pi_k+y_ilogp_k+(1-y_k)log(1-p_k) \right]P(z_i=Ck|y_i,\theta^t) \end{aligned} \end{equation}$$ ===​EP(Z∣Y,θt)​[logP(Z,Y∣θ)]k=1∑2​i=1∑n​logP(zi​=Ck,yi​∣θ)P(zi​=Ck∣yi​,θt)k=1∑2​i=1∑n​log[pkyi​​(1−pk​)1−yi​πk​]P(zi​=Ck∣yi​,θt)k=1∑2​i=1∑n​[logπk​+yi​logpk​+(1−yk​)log(1−pk​)]P(zi​=Ck∣yi​,θt)​​​
​ 要求${\theta }^{t+1}=\underset{\theta }{\max }{E}_{P(Z|Y,{\theta }^t)}\left[logP(Z,Y|\theta )\right]$

​ 就要对其关于$\theta$求导，因为 θ = { π , p } \theta=\left\{\pi,p\right\} θ={π,p}，因为他们又分为几个分量，比如 π = { π 1 , π 2 } \pi=\left\{\pi_1,\pi_2\right\} π={π1​,π2​},式子中又仅存在${\pi }_k$，故对${\pi }_k$求导。但是还有一个约束条件，就是前面提到的$\sum _{k=1}^2{\pi }_k=1$，因此这是一个带约束的优化问题。

​ 故构造拉格朗日函数
$$L(\theta ,\lambda )=\sum _{k=1}^K\sum _{i=1}^n\left[log{\pi }_k+y_{i}log{p}_k+(1-y_k)log(1-p_k)\right]P(z_i=Ck|y_i,{\theta }^t)+\lambda \left[\sum _{k=1}^2{\pi }_k-1\right]$$
​ 对${\pi }_k$求导
∂ L ( θ , λ ) ∂ π k = ∑ i = 1 n 1 π k P ( z i = C k ∣ y i , θ t ) + λ = 0 等式左右乘以 π k 得 ∑ i = 1 n P ( z i = C k ∣ y i , θ t ) + λ π k = 0

$$\begin{equation} \begin{aligned} &\frac{\partial{L(\theta,\lambda)}}{\partial{\pi_k}} \\=&\sum\limits_{i=1}^n\frac{1}{\pi_k}P(z_i=Ck|y_i,\theta^t)+\lambda=0 \\&等式左右乘以\pi_k得 \\&\sum\limits_{i=1}^nP(z_i=Ck|y_i,\theta^t)+\lambda{\pi_k}=0 \end{aligned} \end{equation}$$ =​∂πk​∂L(θ,λ)​i=1∑n​πk​1​P(zi​=Ck∣yi​,θt)+λ=0等式左右乘以πk​得i=1∑n​P(zi​=Ck∣yi​,θt)+λπk​=0​​​
​ 我们知道，对于${\pi }_k$里面的$k$，在本文中可以取到${\pi }_1$和${\pi }_2$，所以依据$\sum _{i=1}^{n}P(z_i=Ck|y_i,{\theta }^t)+\lambda {\pi }_k=0$，有
$$\begin{gathered} \sum _{i=1}^{n}P(z_i=C1|y_i,{\theta }^t)+\lambda {\pi }_1=0 \\ \sum _{i=1}^{n}P(z_i=C2|y_i,{\theta }^t)+\lambda {\pi }_2=0 \end{gathered}$$
​ 也即
$$\sum _{i=1}^{n}P(z_i=C1|y_i,{\theta }^t)+\lambda {\pi }_1+\sum _{i=1}^{n}P(z_i=C2|y_i,{\theta }^t)+\lambda {\pi }_2=0$$
​ 即
$$\begin{array}{c}\begin{array}{rl}& \sum _{k=1}^2\left[\sum _{i=1}^{n}P(z_i=Ck|y_i,{\theta }^t)+\lambda {\pi }_k\right]=0\\ & 即\sum _{k=1}^2\sum _{i=1}^{n}P(z_i=Ck|y_i,{\theta }^t)+\sum _{k=1}^2\lambda {\pi }_k=0\\ & \sum _{i=1}^n\sum _{k=1}^{2}P(z_i=Ck|y_i,{\theta }^t)+\lambda \sum _{k=1}^2{\pi }_k=0\\ & 因为\sum _{k=1}^{2}P(z_i=Ck|y_i,{\theta }^t)=\sum _{z_i}P(z_i|y_i,{\theta }^t)=1\\ & 所以\sum _{i=1}^{n}1+\lambda =0\to n+\lambda =0\to \lambda =-n\end{array}\end{array}$$
​ 将所得结果回代$\sum _{i=1}^{n}P(z_i=Ck|y_i,{\theta }^t)+\lambda {\pi }_k=0$
$$\sum _{i=1}^{n}P(z_i=Ck|y_i,{\theta }^t)-n{\pi }_k=0$$
​ 移向整理得
$${\pi }_k=\frac{1}{n}\sum _{i=1}^{n}P(z_i=Ck|y_i,{\theta }^t)$$
​ 再让原来的拉格朗日函数对$p_k$求导
$$\begin{array}{c}\begin{array}{rl}& \frac{\partial L(\theta ,\lambda )}{\partial p_k}\\ =& \sum _{i=1}^n\left[\left(\frac{y_i}{p_k}-\frac{1-y_i}{1-p_k}\right)P(z_i=Ck|y_i,{\theta }^t)\right]=0\\ 即& \sum _{i=1}^n\left[\left(\frac{y_i(1-p_k)}{p_k(1-p_k)}-\frac{(1-y_i)p_k}{(1-p_k)p_k}\right)P(z_i=Ck|y_i,{\theta }^t)\right]=0\\ & \sum _{i=1}^n\left[\frac{y_i-p_k}{p_k(1-p_k)}P(z_i=Ck|y_i,{\theta }^t)\right]=0\\ 即& \frac{1}{p_k(1-p_k)}\sum _{i=1}^n\left[(y_i-p_k)P(z_i=Ck|y_i,{\theta }^t)\right]=0\\ & \sum _{i=1}^n\left[(y_i-p_k)P(z_i=Ck|y_i,{\theta }^t)\right]=0\\ & \sum _{i=1}^n{y}_{i}P(z_i=Ck|y_i,{\theta }^t)-\sum _{i=1}^n{p}_{k}P(z_i=Ck|y_i,{\theta }^t)=0\\ 即& \sum _{i=1}^n{y}_{i}P(z_i=Ck|y_i,{\theta }^t)-p_k\sum _{i=1}^{n}P(z_i=Ck|y_i,{\theta }^t)=0\\ 移项得：& p_k=\frac{\sum _{i=1}^n{y}_{i}P(z_i=Ck|y_i,{\theta }^t)}{\sum _{i=1}^{n}P(z_i=Ck|y_i,{\theta }^t)}\end{array}\end{array}$$
​ 前面我们推过
$$\begin{array}{c}\begin{array}{rl}P(z_i=Ck|y_i)=& \frac{p_k^{y_i}(1-p_k{)}^{1-y_i}{\pi }_k}{\sum _{k=1}^K{p}_k^{y_i}(1-p_k{)}^{1-y_i}{\pi }_k}\end{array}\end{array}$$
​ 总结得到以下结果
$$\begin{gathered} {\pi }_k=\frac{1}{n}\sum _{i=1}^{n}P(z_i=Ck|y_i,{\theta }^t); \\ {p}_k=\frac{\sum _{i=1}^n{y}_{i}P(z_i=Ck|y_i,{\theta }^t)}{\sum _{i=1}^{n}P(z_i=Ck|y_i,{\theta }^t)} \end{gathered}$$
​ 其中$P(z_i=Ck|y_i,{\theta }^t)$代表用上一轮的参数求出的概率

​ 我们所要求的，是${\pi }_1,p_1,p_2$。

​ 首先，因为是迭代算法，所以我们随机初始化${\pi }_1^t=0.5,p_1^t=0.5,p_2^t=0.5$

​ 先求出$P(z_i=Ck|y_i,\theta )$，比如求$P(z_i=C1|y_i,\theta )$，里面所有的量我们都是知道的，求出来之后，就可以根据上面推导出来的公式求出${\pi }_1^{t+1},p_1^{t+1},p_2^{t+1}=$。假如
$$\begin{gathered} P(z_i=C1|y_i)=\frac{p_1^{y_i}(1-p_1{)}^{1-y_i}{\pi }_1}{\sum _{k=1}^K{p}_k^{y_i}(1-p_k{)}^{1-y_i}{\pi }_k}这里的参数都是{\theta }^t \\ {\pi }_1^{t+1}=\frac{1}{n}\sum _{i=1}^{n}P(z_i=C1|y_i,{\theta }^t); \\ {p}_1^{t+1}=\frac{\sum _{i=1}^n{y}_{i}P(z_i=C1|y_i,{\theta }^t)}{\sum _{i=1}^{n}P(z_i=Ck|y_i,{\theta }^t)} \\ {p}_2^{t+1}=\frac{\sum _{i=1}^n{y}_{i}P(z_i=C2|y_i,{\theta }^t)}{\sum _{i=1}^{n}P(z_i=Ck|y_i,{\theta }^t)} \end{gathered}$$
​ 其中$P(z_i=C2|y_i,{\theta }^t)=1-P(z_i=C1|y_i,{\theta }^t)$，以上的这些量，我们都是知道的，都是可以直接算出来的，因此只需要不断迭代更新即可。

​ 然后不断地循环这个步骤，直到模型收敛，模型什么时候收敛呢？就是当${\theta }^{t+1}\approx {\theta }^t$，代表收敛，我们就不必迭代更新了。

广义EM

​ 实际上，在很多情况情况下，我们并不知道$P(Z|Y,{\theta }^t)$是什么，或者即便是知道了，也干脆就求不出$P(Z|Y,{\theta }^t)$

​ 前面我们提到，$q(Z)=P(Z|Y,{\theta }^t)$，既然求不出$P(Z|Y,{\theta }^t)$，那就尝试求出$q(Z)$

​ 前面我们提到
l o g P ( Y ∣ θ ) = ∫ Z l o g P ( Z , Y ∣ θ ) q ( Z ) q ( Z ) d Z + ∫ Z l o g q ( Z ) P ( Z ∣ Y , θ ) q ( Z ) d Z

$$\begin{equation} \begin{aligned} logP(Y|\theta)=&\int_Zlog\frac{P(Z,Y|\theta)}{q(Z)}q(Z)dZ+\int_Zlog\frac{q(Z)}{P(Z|Y,\theta)}q(Z)dZ \end{aligned} \end{equation}$$ logP(Y∣θ)=​∫Z​logq(Z)P(Z,Y∣θ)​q(Z)dZ+∫Z​logP(Z∣Y,θ)q(Z)​q(Z)dZ​​​
​ 可以$q(Z)$是什么呢？Z是隐变量，我们肯定也得不出，但是否也可以像是迭代求$\theta$一样，迭代求出$q(Z)$？可以的。先来看求解步骤

​ 分为两步

​ ①固定θ，$q(Z{)}^{q+1}=\underset{q}{\max }{\int }_{Z}log\frac{P(Z,Y|\theta )}{q(Z)}q(Z)dZ$

​ ②固定q，${\theta }^{t+1}=\underset{\theta }{\max }{\int }_{Z}log\frac{P(Z,Y|\theta )}{q(Z)}q(Z)dZ$

​ 为何第一步是是这样呢？我们来看$logP(Y|\theta )$，我们希望$q(Z)=P(Z|Y,{\theta }^t)$，那么也就是要是他们的KL散度最小。第一步是固定$\theta$，那么对于$logP(Y|\theta )$的值就是固定的。而我们的目标，就是要使得$q(Z),P(Z|Y,{\theta }^t)$这两个分布越相近越好。因此
$$\underset{q(Z)}{\min }{\int }_{Z}log\frac{q(Z)}{P(Z|Y,\theta )}q(Z)dZ$$
​ 又因为$logP(Y|\theta )$，所以最小化这个KL散度，相当于
$$\underset{q(Z)}{\max }{\int }_{Z}log\frac{P(Z,Y|\theta )}{q(Z)}q(Z)dZ$$
​ 因此。实际上这个广义EM的第一步就是找出一个与$P(Z|Y,{\theta }^t)$最相近的$q(Z)$，找到了之后实际上就是又回到了狭义EM的那一个步骤。

结束

以上便是EM算法的推导和案例讲解，我也正是在学习的，如有问题，还望点点您的小手指给我指出，阿里嘎多