Created by potrace 1.13, written by Peter Selinger 2001-2015

EM算法

EM算法可以理解为极大似然估计的加强版.为了引出EM算法我们先从极大似然估计的一个例子说起.

极大似然估计

假设我们需要调查我们学校学生的身高分布。我们先假设学校所有学生的身高服从正态分布 N \left( \mu , \sigma ^ { 2 } \right) ,这个分布的均值 \mu 和方差 \sigma^2 未知，如果我们估计出这两个参数，那我们就得到了最终的结果。那么怎样估计这两个参数呢？

学校的学生这么多，我们不可能挨个统计吧？这时候我们需要用到概率统计的思想，也就是抽样，根据样本估算总体。随后我们随机抽到了 200 个人的身高数据 X={x_1,x_2,…,x_N} .

现在问题来了,怎样根据这些样本数据估算参数 \mu 和 \sigma^2 呢？

先来研究一下另一个问题,这个学校里哪些身高出现的概率最大?

答案是这200个人的身高出现的概率最大,因为概率最大的事件，最可能发生.进而就可以反推出使这200个学生的身高概率是最大的模型参数,这就是极大似然估计.

这200个学生的身高发生的概率为:

P ( X | \mu , \sigma ) = \prod _ { i = 1 } ^ { m } P \left( x _ { i } | \mu , \sigma \right)

\mu 和 \sigma^2 使其最大化时的值:

\mu , \sigma = \arg\max P ( X | \mu , \sigma )

我们只需要对所有参数求偏导,然后让这些偏导数为 0，假设有 n 个参数，就有 n 个方程组成的方程组，那么方程组的解就是似然函数的极值点了，从而得到对应的参数了。

EM算法的理解

新的需求,我们需要将男生和女生的模型分开，即男生 \in N(\mu_1, \sigma_1^2) ，女生 \in N(\mu_2, \sigma_2^2) ,但是我们并不清楚这200条数据哪条是男生的数据,哪条是女生的数据.

这个时候，对于每一个样本或者你抽取到的人，就有两个问题需要估计了，一是这个人是男的还是女的，二是男生和女生对应的身高的正态分布的参数是多少。这两个问题是相互依赖的:

我们先优化一个问题,在利用这个问题优化另一个问题,这样就可以将两者都逐步优化.有个形象的比喻,比如说食堂的大师傅炒了一份菜，要等分成两份给两个人吃，显然没有必要拿来天平一点的精确的去称分量，最简单的办法是先随意的把菜分到两个碗中，然后观察是否一样多，把比较多的那一份取出一点放到另一个碗中，这个过程一直迭代地执行下去，直到大家看不出两个碗所容纳的菜有什么分量上的不同为止。

这里用EM算法求模型参数也是一样的道理:

以上就是EM算法的理解,为了推导出EM算法的公式,下面先来介绍一些基础知识.

琴生不等式

如果函数 f(x) 是凸函数,即 f''(x) \geq 0

image

有下列不等式成立:

E(f(X)) \geq f(EX)

这个不等式称为琴生不等式.

推广到凹函数,如果 f''(x) \leq 0 ,那么不等式的方向相反:

E(f(X)) \leq f(EX)

不等式取等号的条件X为常数,想象一下上图如果X为常数的时候横轴这个维度只有一个值,即:
a = b = E(X)
此时:
E(f(X)) = f(EX)

期望

对于离散型随机变量 X 的概率分布为 p_i = p\{X=x_i\} ，数学期望 E(X) 为：

E(X) = \sum \limits _i x_ip_i

p_i 是权值，满足两个条件 1 \ge p_i \ge 0 ， \sum \limits _i p_i = 1 。

若连续型随机变量 X 的概率密度函数为 f(x) ，则数学期望 E(X) 为：

E(X) = \int _ {-\infty} ^{+\infty} xf(x) dx

设 Y = g(X) ， 若 X 是离散型随机变量，则：

E(Y) = \sum \limits _i g(x_i)p_i

若 X 是连续型随机变量，则：

E(X) = \int _ {-\infty} ^{+\infty} g(x)f(x) dx

EM算法的推导

对于 m 个相互独立的样本 x=(x^{(1)},x^{(2)},...x^{(m)}) ，对应的隐含数据 z=(z^{(1)},z^{(2)},...z^{(m)}) ，此时 (x,z) 即为完全数据，样本的模型参数为 \theta , 则观察数据 x^{(i)} 的概率为 P(x^{(i)}|\theta) ，完全数据 (x^{(i)},z) 的似然函数为 P(x^{(i)},z|\theta) 。

假如没有隐含变量 z ，我们仅需要找到合适的 \theta 极大化对数似然函数即可：

\theta =arg \max \limits_{\theta}L(\theta) = arg \max \limits_{\theta}\sum\limits_{i=1}^m logP(x^{(i)}|\theta)

增加隐含变量 z 之后，我们的目标变成了找到合适的 \theta 和 z 让对数似然函数极大：

\theta, z = arg \max \limits_{\theta,z}L(\theta, z) = arg \max \limits_{\theta,z}\sum\limits_{i=1}^m log\sum\limits_{z}P(x^{(i)}， z|\theta)

不就是多了一个隐变量 z 吗？那我们自然而然会想到分别对未知的 \theta 和 z 分别求偏导，这样做可行吗？

理论上是可行的，然而如果对分别对未知的 \theta 和 z 分别求偏导，由于 logP(x^{(i)}|\theta) 是 P(x^{(i)}， z|\theta) 边缘概率，转化为 logP(x^{(i)}|\theta) 求导后形式会非常复杂（可以想象下 log(f_1(x)+ f_2(x)+… 复合函数的求导) ，所以很难求解得到 \theta 和 z 。那么我们想一下可不可以将加号从 log 中提取出来呢？我们对这个式子进行缩放如下：

\begin{align} \sum\limits_{i=1}^m log\sum\limits_{z}P(x^{(i)}， z|\theta) & = \sum\limits_{i=1}^m log\sum\limits_{z}Q_i(z)\frac{P(x^{(i)}， z|\theta)}{Q_i(z)} \\ & \geq \sum\limits_{i=1}^m \sum\limits_{z}Q_i(z)log\frac{P(x^{(i)}， z|\theta)}{Q_i(z)} \end{align}

上式式用到了 Jensen 不等式 (对数函数是凹函数),相当于:

f(E(\frac{P(x^{(i)}， z|\theta)}{Q_i(z)})) \geq E(f(\frac{P(x^{(i)}， z|\theta)}{Q_i(z)}))

上式我实际上是我们构建了 L(\theta, z) 的下界，实际上这个下界是 log\frac{P(x^{(i)}， z|\theta)}{Q_i(z)} 的期望。

image

模型参数 \theta 的不同取值可使函数 g(\theta, z) 找到极值点,而不同的 Q_i(z) 的取值可使 g(\theta, z) 移动:

image

如果能调整 Q_i(z) 使得 g(\theta, z) 的极值与 L(\theta, z) 的极值相等,那么求 L(\theta, z) 的极大值,就可以转换为求 g(\theta, z) 的极大值.调整 Q_i(z) 使得不等式变成等式是E步做的事情,极大化 g(\theta, z) 是M步做的事情.

由琴生不等式可知，等式成立的条件是随机变量是常数，则有：

\frac{P(x^{(i)}， z|\theta)}{Q_i(z)} =c

其中 c 为常数，对于任意 i，我们得到：

{P(x^{(i)}， z|\theta)} =c{Q_i(z)}

方程两边同时累加和：

\sum\limits_{z} {P(x^{(i)}， z|\theta)} = c\sum\limits_{z} {Q_i(z)}

由于 \sum\limits_{z}Q_i(z) =1 。 从上面两式，我们可以得到：

\sum\limits_{z} {P(x^{(i)}， z|\theta)} = c

Q_i(z) = \frac{P(x^{(i)}， z|\theta)}{c} = \frac{P(x^{(i)}， z|\theta)}{\sum\limits_{z}P(x^{(i)}， z|\theta)} = \frac{P(x^{(i)}， z|\theta)}{P(x^{(i)}|\theta)} = P( z|x^{(i)}，\theta)

从上式可以发现 Q(z) 是已知样本和模型参数下的隐变量分布。也就是说当 Q_i(z) = P( z|x^{(i)}，\theta)) 时,不等式可以取等号.

事实上,我们并不能一次性使 g(\theta,z) 与 L(\theta,z) 完全重合,如下图,每一次使 g(\theta,z) = L(\theta,z) 的 \theta 是上一次迭代 g(\theta,z) 的最高点.

image

E步计算:

Q_i(z) = P( z|x^{(i)}，\theta))

M步极大化:

arg \max \limits_{\theta} \sum\limits_{i=1}^m \sum\limits_{z}Q_i(z)log\frac{P(x^{(i)}， z|\theta)}{Q_i(z)}

去掉对于极大化 \theta 而言是常数的 Q_i(z) ，上式可写为：

arg \max \limits_{\theta} \sum\limits_{i=1}^m \sum\limits_{z}Q_i(z)log{P(x^{(i)}， z|\theta)}

李航老师的<统计学习方法中>第158页,对于 Q 函数的定义有些不同:

完全数据的对数似然函数 \log P(Y,Z|\theta) 关于在给定观测数据 Y 和当前参数 \theta^{(i)} 下对未观测数据 Z 的条件概率分布 P(Z|Y,\theta^{(i)}) 的数学期望称为 Q 函数.

即:

\begin{align*}Q(\theta,\theta^{(i)}) &= E_Z[\log P(Y,Z|\theta)|Y,\theta^{(i)}]\\&=\sum\limits_{z}P(Z|Y,\theta^{(i)})log{P(Y,Z|\theta)} \end{align*}

其中 Y 是观测变量, Z 是隐变量.

<统计学习方法中>E步计算Q函数,M步极大化Q函数,这与我们的推导结果是相同的.

另外,由于:

P(Z|Y,\overline{\lambda}) = \frac{P(Z,Y|\overline{\lambda})}{P(Y|\overline{\lambda})}

这里的 P(Y|\overline{\lambda}) 对于 Z 的概率没有影响,相当于常数,所以有时使用EM算法会这样定义Q函数:

Q(\theta,\theta^{(i)}) = \sum\limits_{z}P(Z,Y|\theta^{(i)})log{P(Y,Z|\theta)}

参考:
https://zhuanlan.zhihu.com/p/36331115
周志华<机器学习>
李航<统计学习方法>

posted @ 2018-09-04 10:16:31
评论加载中...
发表评论