上帝算法:EM

现实中的例子

对于NLP中的PLSA模型,$d∈D$表示文档,$w∈V$表示词语,$z$表示隐含的主题。

由于隐变量的存在,

则$P(d_i,w_j)=P(d_i)P(w_j|d_i)=P(d_i)\sum_{k=1,\cdots,K}P(w_j|z_k)P(z_k|d_i)$

这里$z$就是不知道的变量=潜变量=隐变量

样本集分布为$P(D,V)=\prod_{i=1,\cdots,N}\prod_{j=1,\cdots,M}P(d_i,w_j)^{n(w_j,d_i)}$

$n(w,d)$表示$w$在$d$中出现的次数

于是对其求对数最大似然

$L(\theta)=\log P(D,V;\theta)=\sum_{i=1,\cdots,M}\sum_{j=1,\cdots,N}n(w_j,d_i)\log P(d_i,w_j)$

其中$\theta=\{P(w_j|z_k),P(z_k|d_i)\}$

要求$\theta^*=\arg\max L(\theta)$

则令$\frac{\partial L(\theta)}{\partial \theta}=0$以求解

由于隐变量的存在,我们需要对隐变量求边缘化(见第一个式子),于是求解MLE需要对和的对数:$\log P(d_i,w_j)$求导(其中$P(d_i,w_j)$是一个和式)。这样先求和再求导下来表达式一长串,导致求导非常困难,所以才要用近似MLE方法

Expectation Maximization原理

期望最大化,EM算法

思想:通过迭代增大下界的最大对数似然的方式逐步近似极大化$L(\theta)$,每一次迭代$L(\theta)>L(\theta^{i+1})>L(\theta^i)>\cdots$,计算迭代式的最大对数似然(最大化下界,该下界表达式里使得原式中的对和的对数求导被转化为对对数的和求导)非常容易,以此来逐渐接近$L(\theta)$;那么如何构造下界?Jensen不等式!

设$Y$为观测数据(不完全数据),$Z$是未观测数据,$\theta^i$表示第$i$次迭代的模型参数$\theta$

可以理解为$\theta\to Z\to Y$

$L(\theta)=\log P(Y|\theta)=\log \sum_Z P(Y,Z|\theta)$(逆边缘化+贝叶斯公式)

$=\log (\sum_ZP(Z,\theta)P(Y|Z,\theta))$(全概率公式)

那么计算第$i$次迭代后的差

$L(\theta)-L(\theta^i)=\log (\sum_ZP(Z,\theta)P(Y|Z,\theta))-\log P(Y|\theta^i)$

下面拼凑一个$(Z|Y,\theta^i)$出来,拼凑的目的是为了构造出Jensen不等式的形式以创造出一个表示下界的不等式,因为显然$\sum_Z P(Z|Y,\theta^i)=1$

$=\log(\sum_Z P(Z|Y,\theta^i)\frac{P(Z,\theta)P(Y|Z,\theta)}{P(Z|Y,\theta^i)})-\log P(Y|\theta^i)$

由Jensen不等式,$\log \sum_j\lambda_jy_j≥\sum_j\lambda_j\log y_j,\lambda_j≥0,\sum_j\lambda_j=1$

$\therefore L(\theta)-L(\theta^i)≥=\sum_Z P(Z|Y,\theta^i)\log\frac{P(Z,\theta)P(Y|Z,\theta)}{P(Z|Y,\theta^i)}-\log P(Y|\theta^i)$

$\because\sum_Z P(Z|Y,\theta^i)=1$,于是可以在负部凭空构造出此求和以合并两式

$\therefore L(\theta)-L(\theta^i)=\sum_Z P(Z|Y,\theta^i)\log\frac{P(Z,\theta)P(Y|Z,\theta)}{P(Z|Y,\theta^i)}-\sum_ZP(Z|Y,\theta^i)\log P(Y,\theta^i)$

$=\sum_Z [P(Z|Y,\theta^i)\log\frac{P(Z,\theta)P(Y|Z,\theta)}{P(Z|Y,\theta^i)}-P(Z|Y,\theta^i)\log P(Y,\theta^i)]$

$=\sum_Z P(Z|Y,\theta^i)\log\frac{P(Y|Z,\theta)P(Z,\theta))}{P(Z|Y,\theta^i) P(Y|\theta^i)}$

这里通过Jensen不等式同时也将和的对数,转换成了对数的和,$\log$被拿进了$\sum$里面,计算其导数(求最大似然)(对每个参数求偏导)就容易多了

$\Delta =\sum_Z P(Z|Y,\theta^i)\log\frac{P(Y|Z,\theta)P(Z,\theta))}{P(Z|Y,\theta^i) P(Y|\theta^i)}$

令$B(\theta,\theta^i)=L(\theta^i)+ \Delta$

则$L(\theta)≥B(\theta,\theta^i)$,即$B(\theta,\theta^i)$为$L(\theta)$的一个下界。那么极大化$B(\theta,\theta^i)$下界自然也等同于极大化$L(\theta)$

$\therefore \theta^{i+1}=\arg \max_\theta B(\theta,\theta^i)≤\arg\max L(\theta)$

同时注意到$L(\theta^i)=B(\theta^i,\theta^i)$,很显然,如果$\theta=\theta^i$,即通过迭代$i$次之后模型参数已经完全一样,那自然是极大对数似然=近似极大对数似然

$\therefore \theta^{i+1}=\arg \max_\theta(L(\theta^i)+\sum_Z P(Z|Y,\theta^i)\log\frac{P(Y|Z,\theta)P(Z,\theta))}{P(Z|Y,\theta^i) P(Y|\theta^i)})$

该式子中$P(Z|Y,\theta^i) P(Y|\theta^i)和L(\theta)$与极大化$\theta$没有关系,所以可以直接忽略(注意$\log$外的$P(Z|Y,\theta^i)$不忽略,因为有它方便计算),$P(Z|Y,\theta^i)$是一个可以求得的潜变量后验概率

且$\because P(Y,Z|\theta)=P(Y|Z,\theta)P(Z,\theta))$

$\therefore \theta^{i+1}=\arg\max_\theta(\sum_Z P(Z|Y,\theta^i)\log P(Y,Z|\theta))$,

记为$\arg\max_\theta Q(\theta,\theta^i)$

$Q(\theta,\theta^i)=\sum_Z P(Z|Y,\theta^i)\log P(Y,Z|\theta)=\mathbb E_Z[\log P(Y,Z|\theta)|Y,\theta^i]$

$\theta^i$是要迭代的参数,初始为$\theta^0$

即:完全数据的对数似然在后验潜变量上的期望,此式子为EM算法的核心

敛散性

定理一:设$P(Y|\theta)$为观测数据的似然函数,$\theta^i(i=1,2,\cdots)$为EM算法得到的参数估计序列,$P(Y|\theta^i)(i=1,2,\cdots)$为对应的似然函数序列,则$P(Y|\theta^i)$是单调递增的,即

(也就是说每一次迭代的预测必然比上一次迭代更好,这是EM算法的核心之一,从道理上能理解,这里数学证明)

定理二:设$L(\theta)=\log P(Y|\theta)$为观测数据的对数似然函数,$\theta^i(i=1,2,\cdots)$为EM算法得到的参数估计序列,$L(\theta^i)(i=1,2,\cdots)$为对数函数似然序列

  1. 如果$P(Y|\theta)$有上界,则$L(\theta^i)=\log P(Y|\theta^i)$收敛到某一值(单调有界定理)
  2. 在函数$Q(\theta,\hat\theta)$与$L(\theta)$满足一定条件下,由EM算法得到的参数估计序列$\theta^i$的收敛值$\theta^*$是$L(\theta)$的稳定点

证略

显然EM算法不能保证找到全局最优值,只能收敛到稳定点,也因此初值选择非常重要

Expectation Maximization Algorithm

于是根据原理推导出来的公式可以给出EM算法:

对于观测变量数据$Y$,隐变量数据$Z$,联合分布$P(Y,Z|\theta)$,条件分布$P(Z|Y,\theta)$,选择初值$\theta^0$开始迭代

E-step:在第$i+1$步的时候,计算在第$i$次迭代的参数估计值$\theta^i$的$Q$函数:

M-step:

迭代直到$||\theta^{i+1}-\theta^i||或||Q(\theta^{i+1},\theta^i)-Q(\theta^{i},\theta^i)||$足够小

后记

边缘化:实际上就是求出边缘概率以消去变量 $p(x)=\int_{-∞}^{+∞}p(y)dy$,那么$y$就被消去了,通过边缘化可以获得我们想要的任何属性(推理)

概率论中的条件期望:$\mathbb E_Z[P(X)|C]=\int_ZP(X)P(Z|C)dZ$

在推导中常犯的一个马虎错误:看清楚积分的作用域,比如$\sum_xf(x)g(x)$,如果$\sum_x f(x)=1$,别直接就给求和了= =,后面还有一个带积分变量$x$的函数呢!

求极大值可以用求0导数法也可以用拉格朗日乘数法将边界条件限制(经常需要如此!)进去

算Q可以借助期望运算的性质来减小运算量

EM算法实在是非常的美妙,很多人称其为“上帝的算法”;更多扩展可以看知乎上的这篇文章:EM算法存在的意义是什么?,包含了诠释EM算法的九层境界

为什么要构造下界?是因为我们想要消去和的对数这种很难计算的东西使用了Jensen不等式,而Jensen不等式的副作用就是产生了不等式,所以才会想着通过迭代容易计算的下界的方法来逼近