EM算法笔记

1. 前言

这一节来学习EM算法,想学习EM算法需要先了解极大似然估计(使似然函数取得最大值时参数估计)。在统计学习方法中说道,EM就是含有隐变量的概率模型参数的极大似然估计法。

EM与极大似然估计一样,都是对参数进行计算的一种算法;

隐变量不是未知的,未知是你不知道它存在,而隐变量是你知道它存在,只是不知道它的值;

已知观测值,想根据观测值去计算显量的分布,这之间还有一个未知的隐变量

这样,隐变量(分布) 与 显量(分布)之间构成了“鸡生蛋、蛋生鸡”的问题,知道隐变量可以求显量,同样知道显量也可以求隐变量。

而我们要做的就是求解这2个变量分布的参数,若果没有隐变量,可以直接采用极大似然估计的方法求取这些参数,但隐变量的存在使我们没法直接求取。

那如何求取呢,思路是不妨先假设显量分布的参数,然后计算隐变量;再由隐变量,去计算显量,直到收敛。这种思路其实是一种聚类的思路。

2. 示例

随机选取n位志愿者,测量他们的身高:若样本中存在男性与女性,身高分别服从N(μ1, σ1)和N(μ2, σ2)的分布,试估计μ1, σ1,μ2, σ2。

男女生身高分布中,隐变量是男女的性别,显量是身高

假设男生的概率是p1,女生的概率是p2,建立分布模型如下:h = p1 * N(μ1, σ1) + p2 * N(μ2, σ2)

这个采用的模型就是高斯混合模型GMM,这个后边介绍。

Train Set:x1,x2,x3...xn

  1. 假设

    μ1 = 1.75,σ1 = 50,p1 = 0.5

    μ2 = 1.63,σ2 = 30,p2 = 0.5

  2. 求解在观测数据下,求解每个样本隐量的概率

    如x1 = 1.84

    先带入到 N(μ1, σ1) 中,计算一个概率q1;

    在带入到 N(μ2, σ2) 中,计算一个概率q2;

    p1(男) = p1× q1 / (p1×q1 + p2 × q2)

    p1(女) = p2 × q2 / (p1×q1 + p2 × q2)

    这里p1(男) = 0.8,p1(女) = 0.2;

    然后遍历所有样本,求取

    p2(男), p2(女)

    ...

    pn(男), pn(女)

  3. 使用隐变量的概率,处理样本,再求解显量的分布

    x1 = 1.84

    x1 * p1(男) = 1.472

    x1 * p1(女) = 0.368

    直观意思是,1.84中,1.472是男性;0.368中是女性

    同理,对所有xi 都进行计算

    x2 * p2(男) = 0.5

    x2 * p2(女) = 1.08

    ...

    xn * pn(男) = 0.9

    xn * pn(女) = 0.8

    然后把所有男的都拿出来,应该符合高斯分布;把所有女的拿出来,也应该符合高斯分布。

    拿这些数据,再去求μ, σ

  4. 然后反复进行 2-3步骤,直到收敛。

做法归纳:

  1. 假设分布的参数,
  2. 然后去求各样本解隐变量的概率;
  3. 接着再由该隐变量的参数,去处理样本,从而修正分布的参数;
  4. 重复过程直到收敛

3. 推导

参考

3.1 似然函数

第二步中,对每个样本的每个可能的类别z,求联合概率分布之和;

联合概率取其中一个的积分,得到的就是边缘概率

3.2 引入Qi(z)

对于每个样本i,我们用Qi(z) 表示样本i隐含变量z的某种分布,且Qi(z)满足

这个不等式是Jensen不等式,表述如下:

如果f是凹函数,X是随机变量,则E[f(x)] <= f(E(x)),当f是严格凸函数时,等号不成立,凸函数反之。

等号成立的条件是X = E[X]。

log函数是凹函数,log由于Qi(z)是概率分布,里边可以看做求期望,

Jensen不等式有不同的版本,其实就是凹凸函数的定义,见这篇文章

3.3 Qi(z)的计算

根据Jensen不等式,当X = E[X]时,等式成立,L(θ)与J(z, Q)相等。这里的X指的是关于z的变量:

E[x]是一个常量,这里假设为c,表述为:

接着:

到这里,求出Qi(z) 的分布,其实就是p(z|xi; θ)这个条件概率分布,也被称为后验概率分布。

这个条件概率,就是在θi与样本xi下,隐变量zi的概率;也就是示例中,根据假设的μ、σ,在样本xi(183cm)下,求其隐变量男女生概率的那步。

3.4 坐标上升理解EM

不等式表述为:L(θ) = J(z, Q),且在Qi(z) = p(z|xi; θ)时,取得等号。EM算法可描述为

首先固定θ,调整Q(z),使得J(z, Q)上升与L(θ)在此θ处相等;

然后固定Q(z),调整θ,使J(z, Q)达到最大值(θt => θt+1);

然后再固定θ,调整Q(z),一直到收敛L(θ)到最大的θ处。

这里,对EM算法收敛性直观认识一下,从这个图中,可以直观的看出,由于每次更新θ,都获取了J的最大值,而L>=J,故L一定是单调递增的,也就是极大似然函数时单调递增,而且我们通过逼近,一定会的得到它。

3.5 小结

EM算法整体框架

  1. 先求隐变量在样本与显量参数下的条件概率分布
  2. 再带入下限函数,求解使下限函数取得最大值时的显量概率分布

更进步,对于θ的似然估计,可以将分子Qi(z)去掉,因为最后求的是θ,而将它拿出后,会是常数。

4. 另一种推导

以上推导,能很直管的认识EM算法,但对于EM中前后两步的关系表达的并不清除,下边看看《统计学习方法》中的表述。

4.1 似然函数

这一步是相同的

4.2 推导Qi

ps:画红线的2步反过来看就可以看懂了,其实就是

这里的不等式用到就是Jensen不等式, 。函数B是L(θ)的下界,且

为了使L(θ)取最大位置,下一个θi+1应该在极值处取得,这个过程如下(省去对θ而言的常数项)。

于是就得到了Qi,E步是得到Q,M步是取极值。

4.3 小结

这个过程是从M步开始,知道推导除了Q,而这个Q也可看成一个期望,是对联合分布的条件期望。

与前一种对比看,前一种在E步得出隐变量的条件概率分布即可,这一种进一步做了期望的计算,两者在M步上是相同的。

5. 混合高斯分布GMM

随机变量X是有K个高斯分布混合而成,取各个高斯分布的概率为p1, p2, ...pk,第i个高斯分布的均值是μi,方差是σi。若观测到随机变量X的一系列样本x1, x2, ...xn,试估计 p, μ, σ(加粗代表向量意思)。

也就是示例中的模型,这个过程就是将高斯分布带到EM算法中的一个示例,在取max时,采用梯度下降的方式,分别对μ、σ求偏导,然后取值得到。推导的过程这里不写了,将结果写下来。

想象每个样本一列排放;E步是将每个样本横向切分成隐变量的分布;M步是纵向对每个显量在各切片上的分布进行计算。(这个过程像极了切馅子的过程_)。

6. 尾声

引申阅读

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×