EM算法_em算法可以求解非线性问题吗-程序员宅基地

技术标签: 算法  机器学习  em算法  

正文

   今天来分享EM算法,几个月前,通过阅读各种文献终于对EM算法有了较为清晰的认识,一直就想写篇博客总结一些,可惜拖延症拖延至今(QAQ)。
   期望最大算法(EM算法)是一种从不完全数据或有数据丢失的数据集(存在隐含变量)中求解概率模型参数的最大似然估计方法。先大体知道这么回事,理解了整篇文章再回来品读这句话。

必备知识

jenson不等式

   jenson不等式以丹麦数学家(Johan Jensen)命名。它给出积分的凸函数值和凸函数的积分值间的关系。jenson不等式的具体内容是啥呢?
   若f(x)在(a,b)之间是凸函数,那么:

f(_i=1kθ_ix_i)_i=1kθ_if(x_i)

   其中\(\theta_1,\theta_2,…,\theta_k\geq0,\sum_{i=1}^k\theta_i=1\)
   对于连续函数:
   若 \(p(x)>0 \quad on \quad S\subseteq dom f, \int_Sp(x)dx=1\)
   则:
f(_Sp(x)dx)_Sf(x)p(x)dx

   Jensen不等式是关于凸性(convexity)的不等式。凸性是一个很好的性质,在最优化问题里面,线性和非线性不是本质的区别,只有凸性才是。如果最优化的函数是凸的,那么局部最优就意味着全局最优,否则无法推得全局最优。有很多不等式都可以用Jensen不等式证得,从而可以把他们的本质归结为凸性。例如,均值不等式:
_i=1nx_in(_i=1nx_i)1n

   本质上可以归结为对数函数log(x)的凸性。

聚类

   首先让我们回忆一下k-means算法。
   k-means算法,也叫k-平均或者k-均值算法,是一种广泛使用的聚类算法,其经常作为很多聚类算法的基础。
   假设输入样本为 \(S=x_1,x_2,…,x_m\)
   那么算法步骤为:
* 选择初始的k个簇中心: \(\mu_1,\mu_2,…\mu_k\)
* 将每个样本x标记为距离簇中心最近的簇:

label_i=argmin_1ji||x_iu_j||

* 更新簇中心:
μ_j=1|c_j|_ic_jx_i

* 重复最后两个步骤,指导满足终止条件。
   终止条件有很多,可以使用 迭代次数簇中心变化率最小平方误差MSE
   现在来思考一下,经典的 k-means算法可以很方便的将未标记的样本分成多个集合,但并不能给出一个样本属于某一个集合的后验概率,当然咱们可以使用一些类似SVM中的方式得到类似于概率的数值。

最大似然估计

   最大似然估计属于统计学的内容,其常常用来估计样本的分布,找出与样本分布最接近的概率分布模型,它是一种非参数估计。其简单有效的估计方式使得其在应用中占据重要地位。
   假如小红有一枚硬币,她抛了十次,结果分别是,正反反正反反反反正反
   假设p为每次抛硬币结果为正的概率,则出现上面结果的概率为:

P=p(1p)(1p)p(1p)(1p)(1p)(1p)p(1p)=p3(1p)7

   重点来了,最大似然概率的思想就是最大化似然概率,什么是似然概率,似然概率就是出现当前样本的概率,也就是上面的概率P,那么怎么最大化上面的概率P呢?小时候学的微积分派上用场了:一阶导为0求极点…。可以求得上式的最优解为: p=0.3
   上面的整个思路历程就是最大似然估计的全过程。
   将上面的例子更泛化一点,投N次硬币,得到结果,其中n次朝上,N-n次朝下。
   假定朝上概率为p,则似然函数为:
P=pn(1p)Nn

   因为对数函数是严格单增,为了方便计算,通常将似然函数变为对数似然函数计算:
P=log(pn(1p)Nn)=nlog(p)+(Nn)log(1p)

求最大:
npNn1p=0p=nN

   更进一步的,给定一组样本\(x_1,x_2,…,x_n\),已知他们来自于高斯分布\(N(\mu,\sigma)\),试估计\(\mu,\sigma\)
   写出似然函数:
   已知高斯分布的概率密度函数为:
f(x)=12πσe(x_iμ)22σ2

   则似然函数为:
L(x)=_i=1n12πσe(xμ)22σ2

   对数似然:
l(x)iμ)2=log(L(x))=_i=1n12πσe(xμ)22σ2=(_i=1n12πσ)+(_i=1ne(xμ)22σ2)=n2log(2πσ2)12σ2_i=1n(x

   最大化似然函数,分别对\(\mu和\sigma\)求偏导求极值得:

μ=1nix_iσ2=1ni(x_iμ)2

   可以发现咱们使用最大似然估计得到\(\mu和\sigma\)的值很符合直观想象:样本的均值就是高斯分布的均值,样本的方差就是高斯分布的方差。

提出问题

   然而我们遇到的问题的随机变量有的时候是无法直接观察到的。比如:有N个人,其中有男性有女性,他们的身高分别服从\(N(\mu_1,\sigma_1)\)和\(N(\mu_2,\sigma_2)\)分布,要估计\(\mu_1,\sigma_1,\mu_2,\sigma_2\)。
   我们如果知道哪些是男性哪些是女性就好了,只需要分别对他们使用上面的最大似然估计。但是遗憾的是我们并不知道,因此我们需要使用EM算法。想一想这个问题,我们也可以先对数据进行聚类,得到男性和女性两类,再分别建模。待我们学完EM算法,我们会发现其实两种方法的思想是相似的。最后我们会分析一下k-means和EM算法的关系。
   上面的问题包含两个高斯模型,因此这类问题又称为高斯混合模型(GMM),高斯混合模型是EM算法解决问题的一个基本问题。

GMM的直观解法

   随机变量X是由K个高斯分布混合而成,取各个高斯分布的概率为\(\pi_1,\pi_2,…,\pi_K\),第i个高斯分布的均值为\(\mu_i\),方差为\(\sum_i\)。随机变量X的一组样本为\(x_1,x_2,…,x_n\),估计参数\(\pi,\mu,\sum\)。
   按上面的步骤计算,先写出似然函数:

L(x)=_i=1n_k=1Kπ_kN(x_i|μ_i,_k)

   取对数:

l(x)=_i=1nlog(_k=1Kπ_kN(x_i|μ_i,_k))

   显然上面的式子无法直接用求导的方式找最大值,为了解决这个问题,我们将问题分为两步:
* 估计数据来自哪一部分
   对于每个样本\(x_i\),它由第k个高斯分布生成的概率为:
γ(i,k)=π_kN(x_i|μ_k,_k)_j=1Kπ_jN(x_i|μ_j,Σ_j)

   注意上面的式子中的\(\mu和\sigma\)也是待估计的值,因此采用采样迭代法:首先先验的给出\(\mu和\sigma\),然后计算\(\gamma\),再通过计算出的\(\gamma\)计算\(\mu和\sigma\),重复达到收敛即可。
   这里的\(\gamma(i,k)\)也可以看做第k个高斯分布在生成数据\(x_i\)时所做的贡献。
   上面已经粗略的说了计算的步骤,那么\(\mu和\sigma\)怎么由\(\gamma\)计算呢?
* 估计每个高斯分布的参数
   对于每个高斯分布\(N_k\)而言,可以看做由它生成了\({\gamma(i,k)x_i|i=1,2,…,n}\)这些点。由于是高斯分布,所以直接使用前面讨论过的结果即可:
μ=1nix_iσ2=1ni(x_iμ)2

   得到:
N_k=_i=1Nγ(i,k)μk=1N_k_i=1N_kγ(i,k)x_i_k=1N_k_i=1M_kγ(i,k)(x_iμ_k)(x_iμ_k)Tπ_k=N_kN=1N_i=1Nγ(i,k)

   重复上面的两步,达到收敛条件(各参数无明显变化等)即可。这就是EM算法的直观过程。

EM算法

   假设有数据集\({x_1,x_2,…,x_n}\)包含m个独立样本,希望从中找到该组数据的模型\(p(x,z)\)的参数。
   写出对数似然:

l(θ)=i=1nlog(p(x_i,θ))=i=1nlog(zp(x,z;θ))

   z是隐随机变量,不方便直接找到参数估计。因此使用一个求最大值时常用的一个策略:计算\(l(\theta)\)的下界,求这个下界的最大值;重复这个过程,直到收敛到局部最大值。先求到的下界有可能比较宽松,不断重复,使得精度提升,使得求到的下界更紧,从而最终接近真实结果。
em_tuidao
   令\(Q_i\)是z的某一个分布,\(Q_i\geq0\),使用jenson不等式:
l(θ)=_i=1nlog_zp(x,z;θ)=_i=1nlog_z_ip(x_i,z_i;θ)=_i=1nlog_z_iQ_i(z_i)p(x_i,z_i;θ)Q_i(z_i)_i=1n_z_iQ_i(z_i)logp(x_i,z_i;θ)Q_i(z_i)

em_jenson
   为了取等号,使得:
p(x_i,z_i;θ)Q_i(z_i)=c

   由此:
Q_i(z_i)p(x_i,z_i;θ)_zQ_i(z_i)=1

Q_i(z_i)=p(x_i,z_i;θ)_zp(x_i,z_i;θ)=p(x_i,z_i;θ)p(x_i;θ)=p(z_i;x_i,θ)

   如此我们就得到EM算法的整体框架:
* E-step 对于每个i,令\(Q_i(z_i)=p(z_i;x_i,\theta)\)
* M-step 求\(\theta=argmax_{\theta}\sum_i\sum_{z_i}Q_i(z_i)log\frac{p(x_i,z_i;\theta)}{Q_i(z_i)}\)
   重复进行上述两个步骤直至收敛。
   至于EM算法的收敛性证明,我就不说了,直接上从网上找的一段证明:
em_proof

使用EM算法解决GMM问题

   还记得咱们刚开始推到的GMM问题的解决方法吗?咱们当时是通过计算每一个高斯分布在每一个数据中占的比例估计每一个高斯分布的样本数据,然后再估计高斯分布的参数。现在咱们使用上面推导的EM算法解决一些这个问题。
   随机变量X是由K个高斯分布混合而成,取各个高斯分布的概率为\(\varphi_1,\varphi_2,…,\varphi_K\),第i个高斯分布的均值为\(,u_i\),方差为\(\sum_i\)。若观测到随机变量X的一系列样本\(x_1,x_2,…,x_n\),试估计参数\(\phi,\mu,\sum\)。
* E-step \(Q_i(z_i=j)=P(z_i=j|x_i;\phi,\mu,\sum)\)
* M-step 将多项式分布和高斯分布的参数带入:

_i=1n_z_iQ_i(z_i)logp(x_i,z_i;ϕ,μ,)Q_i(z_i)=_i=1n_j=1KQ_i(z_i=j)logp(x_i|z_i;ϕ,μ,)p(z_i=j;ϕ)Q_i(z_i=j)=_i=1n_j=1KQ_i(z_i=j)log1(2π)n/2|Σ_j|1/2exp(12(x_iμj)TΣ_j1(x_iμj))ϕ_jQ_i(z_i=j)

   对均值求导:
_μ_l_i=1n_j=1KQ_i(z_i=j)log1(2π)n/2|Σ_j|1/2exp(12(x_iμj)TΣ_j1(x_iμj))ϕ_jQ_i(z_i=j)=_μ_l_i=1n_j=1KQ_i(z_i=j)12(x_iμ_j)Σ_j1(x_iμ_j)=12_i=1n_j=1KQ_i(z_i=j)_μ_l(x_iTΣ_l1x_ix_iTΣ_j1μjμTΣ_j1x_i+μTΣ_j1μ_j)=12_i=1nQ_i(z_i=l)(x_iTΣ_l1x_iTΣ_l1+2μ_lTΣ_l1)=_i=1nQ_i(z_i=l)(x_iTΣ_l1μ_lTΣ_l1)

   令等式为0,得到均值为:
μ_l=_i=1nQ_i(z_i=l)x_i_i=1nQ_i(z_i=l)

   同理可以求得方差:

Σ_j=_i=1nQ_i(z_i=j)(x_iμ_j)(x_iμ_j)T_i=1nQ_i(z_i=j)

   现在来估计多项式分布\(\phi\)的分布:

_i=1n_j=1KQ_i(z_i=j)log1(2π)n/2|Σ_j|1/2exp(12(x_iμi)TΣ_j1(x_iμj))ϕ_jQ_i(z_i=j)

   因为咱们是要估计\(\phi\),因此先删除无关的常数项,化简为:

_i=1n_j=1KQ_i(z_i=j)logϕ_j

   概率的归一性,建立拉格朗日方程:

L(ϕ)=_i=1n_j=1KQ_i(z_i=j)logϕ_j+β(_j=1Kϕ_j1)

   有log函数在,求解到的\(\varphi_i\)一定是正的,因此不用考虑\(\varphi_i\)这个条件。
   求偏导,赋为0,得:

ϕ_jL(ϕ)=_inQ_i(z_i=j)ϕ_j+β

_j=1Kϕ_j=1

β=_i=1nQ_i(z_i=j)ϕ_j1=_i=1nQ_i(z_i=j)ϕ_j(_j=1Kϕ_j)=_i=1n_j=1KQ_i(z_i=j)=_i=1n1=n

   由此:

ϕ_j=1n_i=1nQ_i(z_i=j)

   这样就得到了结果:

μ_l=_i=1nQ_i(z_i=l)x_i_i=1nQ_i(z_i=l)Σ_j=_i=1nQ_i(z_i=j)(x_iμ_j)(x_iμ_j)T_i=1nQ_i(z_i=j)ϕ_j=1n_i=1nQ_i(z_i=j)

   直观的看我们用EM算法求到的结果和前面的直观解法得到的结果不太一样,但是他们其实是一样的。(仔细想想!!!)

EM算法的另一种理解

   其实EM算法可以看做坐标上升。所谓坐标上升就是每次通过更新函数中的一维,通过多次的迭代以达到优化函数的目的。

J(Q,θ)=_i_z_iQ_i(z_i)logp(x_i,z_i;θ)Q_i(z_i)

   上面的J就是前面咱们推到出的EM算法的目标函数。E-step就是在Q维上最大化J,M-step就是在\(\theta\)上最大化J。

k-means和EM算法的关系

   可以发现EM算法的过程跟k-means算法的过程非常相似,都是先确定一个,更新另一个,再重新更新第一个,反复进行到收敛。实际上,k-means就是EM算法的一个实现。在k-means中先是假定隐含变量类别并将某一类别赋给每一个样例,这个过程就是E-step,M-step通过确定好的类别对其每个类的参数进行优化(这里就是更新类中心并重新分配类别)。

   总的来说,EM算法就是使用极大似然估计的方法,通过坐标上升的优化方法对隐变量和显变量的联合分布就行求最值的过程。

   好了,EM学完了,不得不说,EM算法中包含的东西真多啊!下一个准备学习的是—->LDA

参考链接

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/u010843612/article/details/78243186

智能推荐

Apache Apollo MQTT服务器配置与调试_apollo mqtt 关闭用户名-程序员宅基地

文章浏览阅读2.5k次。1、下载并安装一个大神的博客:MQTT再学习 -- 搭建MQTT服务器及测试2、直接启动Apache Apollo服务器的命令./apollo create xxx./xxx/bin/apollo-broker run3、后台运行apollo-broker-service installapollo-broker-service start|restart|stop|u..._apollo mqtt 关闭用户名

【二】数据结构之List_list<list<r>>-程序员宅基地

文章浏览阅读8.4k次。【二】数据结构之List数据结构中,线性表无独有偶,除了Vector还有另外一种ADT,就是我们要讨论的List,与向量Vector有所不同,列表List不在是系统连续的内存空间,也就是说不是基于数组来实现的了,尽管在物理上不是线性的,但是抽象层次上,List在逻辑上依旧是现行表,因此List优化了Vector插入,删除操作的劣势,但是在查找方面却不如Vector的二分查找来的快。 List有哪些_list>

Java多线程(六)Lock的使用 (ReentrantLock;ReentrantReadWriteLock) 7.30_private lock lock = new reentrantlock();-程序员宅基地

文章浏览阅读167次。ReentrantLock类:JDK1.5中增加了ReentrantLock类,可以实现线程之间的同步互斥;还具有嗅探锁定,多路分支通知等功能;使用ReentrantLock实现同步:public class MyThread extends Thread{ private Service service; public MyThread(Service service) { ..._private lock lock = new reentrantlock();

迁移学习全面理解_数据域和标签域都存在差异的迁移学习-程序员宅基地

文章浏览阅读6.9k次,点赞7次,收藏51次。目录目标和本质分类迁移学习全面概述:从基本概念到相关研究什么是迁移学习?什么使得迁移学习与众不同呢?迁移学习的定义迁移学习的场景迁移学习的应用从模拟中学习适应到新的域跨语言迁移知识迁移学习的方法使用预训练的 CNN 特征理解卷积神经网络学习图像的隐含结构学习域不变的表征让表征更加相似混淆域相关的研究领域半监督学习更..._数据域和标签域都存在差异的迁移学习

Ubuntu 20.04下PyCharm配置QtDesigner,PyUIC和Pyrcc_ubuntu20.04 下 pycharm 配置qtdesigner pyuic 和 pyrcc-程序员宅基地

文章浏览阅读3k次,点赞6次,收藏31次。配置前准备首先安装qt5工具:sudo apt-get install qt5-default qttools5-dev-tools安装pyqt5:sudo pip3 install pyqt5配置QtDesigner打开PyCharm,依次点击File–>Settings–>Tools–>External Tools.点击右边界面上的 “ + ”,弹出 Create Tool 对话框。Name 根据你自己的喜好填写,我这里填写的是QtDesignerProgram 填_ubuntu20.04 下 pycharm 配置qtdesigner pyuic 和 pyrcc

【MySQL】本地创建MySQL数据库详解-程序员宅基地

文章浏览阅读1.1k次,点赞25次,收藏25次。(方法一)点开【开始】菜单>>在搜索框中输入“cmd”>>在搜索结果中,右击【命令提示符】程序>>点击选择“以管理员身份运行”>>进入到MySQL安装的bin目录下。>>随便输入密码,回车>>进入到MySQL安装的data目录下,打开以“err”结尾的文件>>搜索password查找初始密码。右键点击“此电脑”>>属性>>高级系统设置>>环境变量>>编辑Path变量,添加MySQL安装目录下的bin文件路径。(方法二)进入到MySQL安装的bin目录下。在解压好的文件夹中创建my.ini文件。_本地创建mysql数据库

随便推点

数据库模糊匹配通配符的简单举例_模糊查询一个字符和多个字符用什么代替-程序员宅基地

文章浏览阅读2.3k次。使用SQL通配符可以替代一个或多个字符,即模糊查询。SQL通配符必须与 LIKE 运算符一起使用。在 SQL 中,可使用以下通配符如下:1、% 替代一个或多个字符 2、_ 仅替代一个字符 3、[charlist] 字符列中的任何单一字符 4、[^charlist]或者[!charlist] 不在字符列中的任何单一字符_模糊查询一个字符和多个字符用什么代替

嵌入式Linux学习之旅(6)— 使用正点原子的Linux内核启动系统_4.1.15-g49efdaa-程序员宅基地

文章浏览阅读1.7k次。Linux内核在i.mx6ull的编译运行编译Linux Kernel需要使用lzop库,所以需要安装,否则编译内核会失败!!!sudo apt-get install lzop一、Linux Kernel的编译在Ubuntu 中创建~/imx6ull/project/alientek_linux目录存放Linux Kernel源码,将正点原子已经移植好的源码linux-imx-4.1..._4.1.15-g49efdaa

认证方式-程序员宅基地

文章浏览阅读109次。Claims-based分开认证和授权,如用QQ账户登录系统。.net 下实现ClaimsIdentityClaimsPrincipalWindows使用windows认证:<authentication mode="Windows" />相关模块:WindowsAuthenticationModule  //Authenticat..._"

计算机十大算法应用 知乎,2019 智源·知乎看山杯算法大赛收官:7 支团队脱颖而出,单人队荣摘桂冠!...-程序员宅基地

文章浏览阅读152次。雷锋网 AI 开发者按:1 月 10 日,北京智源人工智能研究院联合知乎、数据评测平台 biendata 举办的「2019 智源·知乎看山杯专家发现算法大赛」正式收官。大赛颁奖仪式暨算法交流会在清华大学 FIT 大楼多功能厅举行,北京智源人工智能研究院副院长、清华大学计算机系副主任、教授唐杰,知乎技术副总裁李大任出席了该仪式,并为获奖选手颁发了获奖证书。清华大学计算机系长聘副教授、智源学者刘知远,..._知乎刘看山杯数据

最好的降噪蓝牙耳机有哪些?目前最好的降噪蓝牙耳机推荐_目前降噪效果最好的蓝牙耳机-程序员宅基地

文章浏览阅读108次。耳机应该是除了手机之外陪伴你最久的一样电子产品吧?别看它个头不大,作用可不小,如果你已经想入手一款蓝牙耳机,又不知道该怎么选,看这里,我来告诉你,哪一款最适合你。一、南卡A2降噪蓝牙耳机价格:399充电方式:无线充电续航时间:6H+30H蓝牙音频格式:AAC-SBCNank南卡听名字不熟悉不要紧,重点看品质。南卡A2整个耳机仅4.1克,无限充电方便小巧,蓝牙5.2信号传输稳定,解析能力高,三频均衡,无论是接打电话、听音乐,都能表现出超高水准,尤其配有13mm超大动圈,高通3040芯片_目前降噪效果最好的蓝牙耳机

【图像分割】医学图像分割多目标分割(多分类)实践-程序员宅基地

文章浏览阅读2.4w次,点赞77次,收藏467次。文章目录1. 数据集2. 数据预处理3. 代码部分3.1 训练集和验证集划分3.2 数据加载和处理3.3 One-hot 工具函数3.4 网络模型3.5 模型权重初始化3.6 损失函数3.7 模型评价指标3.8 训练3.9 模型验证3.10 实验结果1. 数据集来自ISICDM 2019 临床数据分析挑战赛的基于磁共振成像的膀胱内外壁分割与肿瘤检测数据集。(原始数据)(ground truth)灰度值:灰色128为膀胱内外壁,白色255为肿瘤。任务是要同时分割出膀胱内外壁和肿瘤部分,加上背景_多目标分割

推荐文章

热门文章

相关标签