盒马唠机器学习之EM算法
EM算法是一种迭代的算法,1977年由Dempster等人提出,用于含有隐变量(Hidden Variable)的概率模型参数的极大似然估计,或极大后验概率估计。它的计算方法中每一次迭代都分两步,其中一个为期望步(E步),另一个为极大步(M步),所以算法被称为EM算法(Expectation Maximization Algorithm)。其基本思想是:首先根据己经给出的观测数据,估计出模型参数的值;然后再依据上一步估计出的参数值估计缺失数据的值,再根据估计出的缺失数据加上之前己经观测到的数据重新再对参数值进行估计,然后反复迭代,直至最后收敛,迭代结束。
极大似然估计
在介绍EM算法之前,我们先来介绍极大似然估计,通过极大似然估计的例子引出EM算法。
一个栗子: 假设你在校园里随便找了100学生。然后统计抽样得到的100个学生的身高。假设他们的身高是服从正态分布的。但是这个分布的均值μ和方差σ2我们不知道,这两个参数就是我们要估计的。记作θ=[μ,σ]T。
欲求在抽样X时,最优的μ和σ2参数估计,虽然模型的原型已知,但不同的参数对应着不同的学生成绩分布,其中一种最简单有效的参数估计方法就是估计的参数在目前抽样的数据上表现最好,即使得f(X|μ,σ2)的联合概率最大,即什么样的参数μ和σ2能恰好符合观测样本分布的规则。
估计:
假设:样本集X={x1,x2,…,xN}, N=100。概率密度:p(xi|μ,σ2)抽到学生i(的身高)的概率。μ和σ2是服从分布的参数。独立同分布:同时抽到这100个男生的概率就是他们各自概率的乘积 。
在实际计算中,对数函数是一个严格递增的函数,对数似然函数取代似然函数后,计算要简单很多,而且直接的似然函数计算中涉及大量浮点概率的乘法,容易导致计算机浮点计算精不够而出现机器0值,更普遍的如公式(3)去求值。余下的问题,就是求l(μ,σ2|X)的极大值的过程,即参数的一阶偏导为0的极值点,在此不详述了,直接给出式子。
但是如果现在这100个人中,不光有男生,还有女生(里面就有2个类别和2种参数),其中男生和女生的身高都服从高斯分布,但是参数不同(均值,方差)。而且抽取得到的每个样本都不知道是从哪个分布抽取的。那么我们应该怎么求男生和女生对应的身高的高斯分布的参数是多少呢?那就引出了EM算法了。
EM算法推导
设有样本集{x(1),…,x(m)},包含m个独立的样本。其中每个样本i对应的类别z(i)是未知的,所以很难用极大似然求解。
带有隐变量似然函数:
右式分子分母同时乘 Q(z):
为嘛这么干呢?说白了就是要凑Jensen不等式( 其中Q(z)是Z的分布函数)。先简单的介绍下Jensen不等式。
设f是定义域为实数的函数,如果对于所有的实数x。如果对于所有的实数x,f(x)的二次导数大于等于0,那么f是凸函数。如果f是凸函数,X是随机变量,那么:E[f(X)]>=f(E[X])。Jensen不等式应用于凹函数时,不等号方向反向。
实线f是凸函数,X有0.5的概率是a,有0.5的概率是b则X的期望值就是a和b的中值了。
由于
是
的期望。
其中
应用Jensen不等式可得
则原式得:
下界比较好求,所以我们要优化这个下界来使得似然函数最大。
其中Q(z)是z的分布函数:
由上式可得C就是p(xi,z)对z求和。
EM算法流程 :
初始化分布参数θ,重复E、M步骤直到收敛。
E步骤:根据参数θ初始值或上一次迭代所得参数值来计算出隐性变量的后验概率(即隐性变量的期望),作为隐性变量的现估计值: