NLP学习笔记34-EM算法-白红宇

NLP学习笔记34-EM算法

阅读量：138 次

发布时间：2019-02-26

本文共 2170 字，大约阅读时间需要 7 分钟。

一序

本文属于贪心NLP训练营学习笔记系列。从隐变量到EM算法。

二数据表示

传统的数据表示，如图片、文本等是人能直观理解。但是不一定是好的表示，可能有冗余的特征，有噪音等。

是不是转换为低维的空间会更好？

很多算法包括机器学习都是为了寻找一个更好的表示方法。

三隐变量模型

隐变量生成的例子：

Complete Case and Incomplete Case

Complete Case ：用最大似然MLE来求解 $\large \theta$

Incomplete Case：使用EM算法

Complete Case ：

$\large l(\theta ,D)=log p(x,z|\theta )=logp(z|\theta _z)+log(x|z,\theta _x)$

Incomplete Case:z没有观测到，不能直接最大化，不能写成上面那种

$\large l(\theta ,D)=log \sum_{z}^{ } p(x,z|\theta )= log \sum_{z}^{ } p (z|\theta _z)p(x|z,\theta _x)$

-w674

要考虑所有z的可能，这里用的累加实际上就是边缘概率。比较复杂，所以要引入EM算法来进行求解，只能不断地建立ll的下界（E-step），再优化下界（M-step），依次迭代，直至算法收敛到局部最优解。这就是EM算法的核心思想。

EM算法通过引入隐含变量,使用MLE（极大似然估计）进行迭代求解参数。通常引入隐含变量后会有两个参数，EM算法首先会固定其中的第一个参数，然后使用MLE计算第二个变量值；接着通过固定第二个变量，再使用MLE估测第一个变量值，依次迭代，直至收敛到局部最优解。

E-Step：通过observed data和现有模型估计参数估计值 missing data；

M-Step：假设missing data已知的情况下，最大化似然函数。

四推导EM

下面用MLE的方式来推导EM，先根据损失函数 $\large L(\theta )=logp(x|\theta )$ 写出目标函数： $\large argmaxL(\theta )=argmaxlogp(x|\theta )$

假设第n 次迭代后得到了 $\large \theta _n$ 是已知的。那么我们希望下一步找到的新参数 $\large \theta$ 与 $\large \theta _n$ 差距越大越好.（这里的 $\large \theta$ 就是求 $\large \theta _{n+1}$ ）

$\large argmax_\theta (L(\theta )-L(\theta _n))=logp(x|\theta )-logp(x|\theta _n)$

然后把隐变量考虑进来：

= $\large log\sum_{z}^{ } p(x,z|\theta )-log(p(x|\theta _n)) \\=log\sum_{z}^{ } p(x|z,\theta )p(z|\theta )-log(p(x|\theta _n)) \\=log\sum_{z}^{ } p(x|z,\theta )p(z|\theta ) \frac{p(z|x,\theta _n) }{p(z|x,\theta _n) }-log(p(x|\theta _n)) \\=log\sum_{z}^{ } p(z|x,\theta_n)\frac{p(x|z,\theta )p(z|\theta ) }{p(z|x,\theta _n) }-log(p(x|\theta _n))$ 式子a

补充数学背景知识：Jensen不等式(jensen’s inequality),只介绍不证明，我一开始这里没听懂，因为我数学基础太差，老师说大一就学过这个。

若对于任意点集 $\large \{x_i \}$ ，若 $\large \lambda _i\geq0$ 且 $\large \sum_{i}^{ } \lambda _i=1$ ，使用数学归纳法，可以证明凸函数 f (x) 满足：

$\large f(\sum_{i=1}^{M} \lambda _ix_i )\leq \sum_{i=1}^{M} \lambda _i f(x_i)$

如果是凹函数，则不等号方向反向。为了加深印象，我从pdf截个图。插一句，Google 会找到”jensen’s inequality EM“算法的很多课件，都是国外知名大学的PDF，非常值得推荐。

根据Jensen不等式,

$\large log\sum_{ i=1}^{n} \lambda _ix_i \geq \sum_{ i=1}^{n} \lambda _i logx_i$ (因为log函数凹函数，二阶导数为 $\large -\frac{1}{ x^2}<0$ ,所以使用Jensen不等式时，应用第二条准则：f(E[X])>=E[f(x)])

回到前面的式子，我们上面我们构造了一个类似 $\large \lambda _i$ 的这么一个项： $\large p(z|x,\theta _n)$ ,因为 $\large \sum_{z}^{ }p(z|x,\theta _n)=1$ ,所以：

$\large L(\theta )-L(\theta _n)\geq \sum_{z}^{ }p(z|x,\theta _n ) log\frac{p(x|z,\theta )p(z|\theta ) }{p(z|x,\theta _n) }-log(p(x|\theta _n)$

= $\large \sum_{z}^{ }p(z|x,\theta _n ) log\frac{p(x|z,\theta )p(z|\theta ) }{p(z|x,\theta _n) (p(x|\theta _n)}$ （这里就是 $\large \sum_{z}^{ }p(z|x,\theta _n)=1$ ，然后 $\large log(M)-log(N)=log(\frac{M}{N} )$ ）

记做 $\large \Delta (\theta | \theta _n)$ ，即：

$\large L(\theta ) -L(\theta _n) \geq \Delta (\theta |\theta _n ) \\->L(\theta ) \geq L(\theta _n)+\Delta (\theta |\theta _n )$

这样我们就找到了 $\large L(\theta)$ 的下界，求最大值的时候，我们可以不断最大化下界，从而使得 $\large L(\theta)$ 最大化。

这里比较抽象，老师没有展开讲，这个课件画个图辅助理解。有两个问题：

1. 什么时候下界与 $\large L(\theta)$ 在此点 $\large \theta$ 处相等？

2.为什么一定会收敛？

证明：一种收敛方法是 $\large L(\theta)$ 不再变化，还有一种就是变化幅度很小,即根据 $\large L(\theta _{n+1})-L(\theta _{n})$ 的值来决定。

$\large argmax_\theta (L(\theta )) = argmax( L(\theta _n)+\Delta (\theta |\theta _n))$

= $\large argmax_\theta (L( \theta _n) + \sum_{z}^{ }p(z|x,\theta _n ) log\frac{p(x|z,\theta )p(z|\theta ) }{p(z|x,\theta _n) (p(x|\theta _n)})$

这里把和求极值的目标 $\large \theta$ 无关的去掉。

= $\large argmax _\theta ( \sum_{z}^{ }p(z|x,\theta _n ) log p(x|z,\theta )p(z|\theta ))$

= $\large argmax _\theta ( \sum_{z}^{ }p(z|x,\theta _n ) log p(x,z|\theta ))$

根据概率公式： $\large p(AB)=p(A,B)=p(A|B)P(B)$
扩展一下： $\large p(AB|C)=p(A,B|C)=p(A|B,C)P(B|C)$
$\large p(A,B|C)$ 表示C发生的条件下，AB发生的概率
$\large p(A|B,C)$ 表示事件B，事件C都发生的条件下，A发生的概率
所以： $\large p(x|z,\theta)p(z|\theta)=p(x,z|\theta)$

我们观察下，这个式子，前一项是一个z的期望值。数学期望记不清了，看看下图

所以,结合上面的式子，： $\large argmax_\theta [ E_{z|x,\theta _n} logp(x,z|\theta )]$

以上就是EM算法的形式，它分两个步骤：

求期望：E-step，求z的期望值，就是求 $\large E_{z|x,\theta _n}$ 在 $\large {log}p(x,z|\theta)$ 的条件下的期望。

求极值：M-step，最大化 $\large {log}p(x,z|\theta)$ ，这个时候z是已知的。相当于Complete Case，使用MLE去求。

pdf还有种写法：

EM小结

E-step是求z

M-step是求 $\large \theta$

1、EM算法不是全局最优解，是局部最优解。通常我们使用不同的初始化，多重复几次，以获得较好效果。

2、EM算是严格递增的，所以EM一定会收敛converge。

五 K-means

老师说，简单提一下em的一个例子k-means,有谁不知道嘛？我真的不知道啊。

1、先标记两个点，图2

2、根据这两个点计算距离，分类.图3.

3、根据分类，重新计算分类的中心点。图4.回到步骤2，直到完成收敛（点颜色不变）。

K-means cost function

K均值算法中，有两个未知的东西：

1 变量 $\large r_{nk}$ ，代表一个点属于哪个分类，当 $\large r_{nk}$ =1时，代表 $\large x_n$ 属于第k个分类，当 $\large r_{nk}$ =0不属于。那么每个样本 $\large x_n$ 的 $\large r_{n1},r_{n2},r_{n3}...,r_{nk}$