EM原理及应用举例

1、EM 原理及应用举例陈朝虹硕 (1)班201220109072作业要求EM算法1、 原理？为何可行？2、 运用的地方，优缺点3、 与 ML的关系？4、 一个具体的模型应用问题映射代码迭代轨迹遇到什么问题EM 算法原理给定的训练样本是使得 p(x,z)最大。 p(x,z)，样例间独立，我们想找到每个样例隐含的类别的最大似然估计如下：z，能第一步是对极大似然取对数，第二步是对每个样例的每个可能类别z 求联合分布概率和。但是直接求一般比较困难， 因为有隐藏变量z 存在，但是一般确定了z 后，求解就容易了。EM 是一种解决存在隐含变量优化问题的有效方法。竟然不能直接最大化，我们可以不断地建立的下界（

2、E 步），然后优化下界（M步）。这句话比较抽象，看下面的。对于每一个样例i ，让表示该样例隐含变量z 的某种分布，满足的条件是。（如果z 是连续性的，那么是概率密度函数，需要将求和符号换做积分符号）。（ 1）到（ 2）比较直接，就是分子分母同乘以一个相等的函数。（2）到（ 3）利用了 Jensen 不等式。可以求得：至此， 我们推出了在固定其他参数后，的计算公式就是后验概率，解决了如何选择的问题。这一步就是E 步，建立的下界。接下来的M步，就是在给定后，调整，去极大化的下界（在固定后，下界还可以调整的更大）。那么一般的EM算法的步骤如下：循环重复直到收敛：（ E 步）对于每一个 i ，计算（

3、M步）计算那么究竟怎么确保 EM收敛？假定 和 是 EM第 t 次和证明了 ，也就是说极大似然估计单调增加，估计的最大值。下面来证明，选定 后，我们得到 E 步t+1 次迭代后的结果。 如果我们那么最终我们会到达最大似然这一步保证了在给定时， Jensen 不等式中的等式成立，也就是然后进行 M步，固定，并将视作变量，对上面的求导后，得到，这样经过一些推导会有以下式子成立：解释第（ 4）步，得到而没有使等式成立，等式成立只有是在固定时，只是最大化，并按 E 步得到，也就是时才能成立。的下界，况且根据我们前面得到的下式，对于所有的和都成立因此（第（ 5）步利用了 M步的定义，5）成立，（ 6）是

4、之前的等式结果。M步就是将调整到，使得下界最大化。这样就证明了会单调增加。一种收敛方法是不再变化，还有一种就是变化幅度很小。运用的地方，优缺点运用的地方：1 参数估计2 聚类，如果估计的参数可以表明类别的话，聚类问题也就可以归结为参数估计问题。优缺点直观地理解EM算法，它也可被看作为一个逐次逼近算法：事先并不知道模型的参数，可以随机的选择一套参数或者事先粗略地给定某个初始参数 0 ，确定出对应于这组参数的最可能的状态， 计算每个训练样本的可能结果的概率，在当前的状态下再由样本对参数修正，重新估计参数 ，并在新的参数下重新确定模型的状态，这样，通过多次的迭代，循环直至某个收敛条件满足为止，就可以

5、使得模型的参数逐渐逼近真实参数。EM算法的主要目的是提供一个简单的迭代算法计算后验密度函数，它的最大优点是简单和稳定，但容易陷入局部最优，运算的结果于参数初始值的选择有较大关系。与 ML 的关系？ML是最大似然估计，ML估计出参数的前提是有完整的样本数据，本（即不完整数据集）上进行参数估计。EM的 M步骤里，采用了大化来更新参数值。而 EM则可以在含有隐藏样ML的思想，即似然函数最一个具体的模型应用考虑一个投掷硬币的实验：有两枚特制的硬币A 和 B，这两枚硬币和普通的硬币不一样。A和 B 投掷出正面的概率分别记为? A 和 ?B。我们现在独立地做6 次试验： 随机的从这两枚硬币中抽取1 枚，投

6、掷 10次，统计出现正面的次数。那么我们就得到了如表格1 的实验结果：试验代号正面次数硬币13B29A38A44B57A62B在这个实验中，我们记录两组随机变量X = (3,9,8,4,7,2); Z =(Z1,Z 2,Z 3,Z 4,Z 5) ，其中，Zi 表示第 i 次试验选择的硬币，Zi =(1,2)，分别表示选择的是A 还是 B。我们的目标是通过这个实验来估计? = ( ? A; ? B) 的数值。这个实验中的参数估计就是有完整数据的参数估计，这个是因为我们不仅仅知道每次试验中投掷出正面的次数，我们还知道每次试验中投掷的是硬币A还是B。一个很简单也很直接的估计? 的方法如下 <其

7、实是最大似然估计的结果>，问题：如果不知道表格中的第三列，即标量Z 为未知变量，估计?A 和 ? B？代码：% 有 A， B两枚硬币，抛出正面的概率分别为theta1， theta2，未知% 共 6次试验；每次试验，选择一枚硬币（A或 B），抛 10 次，统计出现正面的次数分别为2,9,8,4,7,3%【对应的硬币为隐藏的变量：B，A，A，B，A，B，根据最大似然得到的结果为0.8,0.3】% 估计两枚硬币抛出正面的概率x=2,9,8,4,7,3;theta=0.9,0.4;%设定初始值P=zeros(6,2);%联合概率密度函数，P(xi,zi|theta)Q=zeros(6,2);%

8、每一次试验中，选到的硬币是A或 B的概率，Qi(zi)=p(zi|xi,theta)iter=0;N=30;show=zeros(N,2);%保存迭代结果whileiter<Niter=iter+1;fori=1:6forj=1:2P(i,j)=NCHOOSEK(10,x(i)*(theta(j)x(i)*(1-theta(j)(10-x(i);%计算概率分布Pendforj=1:2Q(i,j)=P(i,j)/sum(P(i,:);end%计算 Qend%-迭代计算theta(1),theta(2)-tempUP=0;tempDOWN=0;fori=1:6tempUP=tempUP+ x

9、(i)*Q(i,1);tempDOWN=tempDOWN+10*Q(i,1);endtheta(1)=tempUP/tempDOWN;tempUP=0;tempDOWN=0;fori=1:6tempUP=tempUP+ x(i)*Q(i,2);tempDOWN=tempDOWN+10*Q(i,2);endtheta(2)=tempUP/tempDOWN;show(iter,:)=theta;end ;%保存本次迭代结果结果：show =0.81660.35700.80160.31740.79820.30830.79740.30670.79730.3064在第 5 次迭代时，就几乎达到稳定0.79720.30640.79720.30640.79720.30640.79720.30640.79720.30640.79720.30640.79720.30640.79720.30640.79720.30640.79720.30640.79720.30640.79720.30640.79720