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条数据哪条是男生的数据,哪条是女生的数据.

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

  • 当我们知道了每个人是男生还是女生,我们可以很容易利用极大似然对男女各自的身高的分布进行估计。
  • 反过来,当我们知道了男女身高的分布参数我们才能知道每一个人更有可能是男生还是女生。例如我们已知男生的身高分布为 N(\mu_1 = 172, \sigma^2_1=5^2) , 女生的身高分布为 N(\mu_2 = 162, \sigma^2_2=5^2) , 一个学生的身高为180,我们可以推断出这个学生为男生的可能性更大。

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

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

  • 先求男生和女生的分布
  • 而后根据男生女生分布估计模型参数
  • 根据优化后的模型估计男女生分布
  • 根据优化后的男生和女生的分布再去估计模型参数
  • …如此反复直到满意为止

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

琴生不等式

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

有下列不等式成立:

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 之后,我们的目标变成了找到合适的 \thetaz 让对数似然函数极大:

\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 吗?那我们自然而然会想到分别对未知的 \thetaz 分别求偏导,这样做可行吗?

理论上是可行的,然而如果对分别对未知的 \thetaz 分别求偏导,由于 logP(x^{(i)}|\theta)P(x^{(i)}, z|\theta) 边缘概率,转化为 logP(x^{(i)}|\theta) 求导后形式会非常复杂(可以想象下 log(f_1(x)+ f_2(x)+…复合函数的求导) ,所以很难求解得到 \thetaz 。那么我们想一下可不可以将加号从 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.png

模型参数\theta的不同取值可使函数g(\theta, z)找到极值点,而不同的Q_i(z)的取值可使g(\theta, z)移动:
image.png
如果能调整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.png
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
评论加载中...

发表评论