Expectation Maximization.

在求解概率分布模型$P(x ; \theta)$的参数$\theta$时，通常采用极大似然估计方法；其中$x$被称为观测变量(observable variable)。给定数据后极大化观测变量$x$关于参数$\theta$的对数似然函数：

若概率模型还包含隐变量(latent variable) $z$，则观测变量$x$和隐变量$z$对应的数据总称为完全数据(complete data)，对应的对数似然为：

由于隐变量的不可观测性，上式是intractable的，因为对数函数中包含积分项；需要采用近似算法处理。

期望最大(expectation maximization,EM)算法是用于解决含有隐变量的概率模型的极大似然估计方法，是一种迭代计算的数值方法。

本文目录：

1. 使用条件概率和KL散度推导EM算法
2. 使用边缘分布和Jenson不等式推导EM算法
3. EM算法的几何解释：近似曲线逼近
4. EM算法的收敛性证明
5. 广义EM算法

1. 使用条件概率和KL散度推导EM算法

当概率模型$P(x ; \theta)$含有隐变量$z$时，对其对数似然函数做如下变换：

上式即使已知联合分布$P(x,z ; \theta)$，其条件分布$P(z|x ; \theta)$也是未知的；引入一个新的分布$Q(z)$近似该分布。上式两端对$Q(z)$求期望：

上式中KL散度是一个不小于零的值；ELBO为证据下界(evidence lower bound)，是对数似然函数的一个下界；即：

极大似然估计的原目标函数为：

假设对于第$t$轮计算得到的$\theta^{(t)}$，KL散度可以忽略，即$\text{KL}(Q(z) | | P(z|x ; \theta^{(t)})) ≈ 0$，此时$Q(z) ≈ P(z|x ; \theta^{(t)})$，且目标函数近似替代为：

此时ELBO可以表示为：

注意到上式右端只有第一项包含参数$\theta$，因此最大化ELBO等价于最大化第一项，即：

上式即为期望最大算法的表达式。

2. 使用边缘分布和Jenson不等式推导EM算法

当概率模型$P(x ; \theta)$含有隐变量$z$时，对其对数似然函数做如下变换：

引入一个新的分布$Q(z)$，将上式表示成期望的形式，由于$\log$函数是凹函数(concave)，由Jenson不等式：

上式等号成立当且仅当$\frac{P(x,z ; \theta)}{Q(z)}$为常数$C$，此时$P(x,z ; \theta)=CQ(z)$，两端对$z$取积分得$C=P(x; \theta)$，故$Q(z)=\frac{P(x,z ; \theta)}{P(x; \theta)}=P(z|x ; \theta)$。

极大似然估计的原目标函数为：

假设对于第$t$轮计算得到的$\theta^{(t)}$，Jenson不等式可取等号，即$Q(z)=P(z|x ; \theta^{(t)})$，此时目标函数近似替代为：

注意到上式右端只有第一项包含参数$\theta$，因此最大化目标函数等价于：

3. EM算法的几何解释：近似曲线逼近

EM算法的表达式如下：

EM算法在迭代时分成两步。第一步(E-step)，计算联合分布的对数似然函数$\log P(x,z ; \theta)$关于给定参数$\theta^{(t)}$下的条件分布$P(z|x ; \theta^{(t)})$的期望；第二步(M-step)，计算期望的最大值。参数的初值可以任意选择，但需注意EM算法对初值是敏感的。

上图给出了EM算法的直观解释。对数似然函数表示为曲线$L(\theta)$，该曲线是无法直接求解的。因此在每次迭代$\theta^{(t)}$时寻找对数似然函数的一个下界(即ELBO,表示为$B(\theta,\theta^{(t)})$)，通过极大化该下界来近似极大化对数似然。由于$L(\theta)≥B(\theta,\theta^{(t)})$，保证每次迭代时对数似然都是增加的。

4. EM算法的收敛性证明

下面说明极大似然估计的收敛性等价于期望最大算法的收敛性。原问题的极大似然估计的目标函数为：

注意到$P(x ; \theta)≤1$，因此函数$\log P(x ; \theta)$有上界；只需要证明该函数对于参数$\theta$是单调的，则可说明该目标函数是收敛的。即证：

对目标函数做一些变换：

上式两端对$P(z|x ; \theta^{(t)})$求期望：

若记：

则有：

若证$\log P(x ; \theta^{(t+1)}) ≥ \log P(x ; \theta^{(t)})$，不妨证$Q(\theta^{(t+1)}) ≥ Q(\theta^{(t)})$和$H(\theta^{(t+1)}) ≤ H(\theta^{(t)})$。

⚪ 证明 $Q(\theta^{(t+1)}) ≥ Q(\theta^{(t)})$

由于$Q(\theta)$恰好是期望最大算法的第一步得到的期望值，即：

因此$\theta^{(t+1)}$是使得$Q(\theta)$取得最大值的参数：

⚪ 证明 $H(\theta^{(t+1)}) ≤ H(\theta^{(t)})$

5. 广义EM算法

EM算法的表达式如下：

在迭代中分为两步执行：

上述算法要求条件概率$P(z|x ; \theta^{(t)})$是可求的。若该条件概率不可求，则仍将对数似然函数看作ELBO和KL散度之和：

此时可将$Q(z)$也看做未知量，在迭代求解时与参数$\theta$一起求解。即给定$\hat{\theta}$时，有：

给定$\hat{Q}$时，有：

上述算法被称作广义期望最大(generalized expectation maximization,GEM)算法，也被称作极大-极大(maximization-maximization)算法，算法流程如下：