Expectation–maximization Algorithm

##Introduction

EM(Expectation-Maximization)与Gradient Boosting类似，其实是一种算法框架。当算法模型中存在隐藏变量，并且无法把隐藏变量积分掉(i.e., 不能转化成closed-form)时，EM采取迂回策略求解。

##A Simply Comprehensible Inference

似然函数\( p(x;\theta) \)化作包含隐藏变量的形式\( \sum\limits_{z} p(x,z;\theta) \)后，可以做如下分解。其中，\( \theta \)是模型参数，\( q(z) \)是隐藏变量\( z \)的分布函数。

$$\ln p(x;\theta) = \mathcal{L}(q;\theta) + KL(q \parallel p)$$

右式的两部分分别定义如下。

$$\mathcal{L} (q;\theta) = \sum\limits_{z} q(z) \ln \{ \frac{p(x,z;\theta)}{q(z)} \}$$ $$KL(q \parallel p) = - \sum\limits_{z} q(z) \ln \{ \frac{p(z|x;\theta)}{q(z)} \}$$

由于\( KL(q \parallel p) \geq 0 \)，因此 \( \mathcal{L} (q;\theta) \)是对数似然\( \ln p(x;\theta) \)的下界。为了抬高下界，可以令\( KL(q \parallel p) = 0 \)，即用\( z \)在数据集\( x \)和模型参数\( \theta^{(i)} \)(表示第\( i \)次迭代中\( \theta \)的估计值，\( \theta^{(0)} \)是初始参数值)已知情况下的后验概率来估计\( q(z) \)。这就是E-step，后验概率通常可以用贝叶斯公式展开求解。E-step:

$$q(z) = p(z|x; \theta^{(i)})$$

在抬高下界的约束下，我们再去最大化\( \mathcal{L} (q;\theta) \)(此时只有\( \theta \)是变量)。这就是M-step，即估计新的\( \theta^{(i+1)} \)来最大化对数似然\( \ln p(x;\theta) \)(此时\( \ln p(x;\theta) = \mathcal{L} (q;\theta) \))的期望。M-step:

$$\theta^{(i+1)} = \underset{\theta}{\operatorname{arg\,max}}\ \mathcal{L} (L) (q; \theta)$$

循环迭代，通过不断推高对数似然的下界，来最大化它。

##A More General Inference

事实上，E-step(expectation)是指计算对数似然的期望表达式，M-step(maximization)是指估计新的参数\( \theta \)来最大化对数似然的期望表达式值。因此，E-step可以直接表示成用后验概率来估计\( q(z) \)时，对数似然的期望形式(期望就是乘上分布函数求积分)。E-step:

$$Q(\theta|\theta^{(i)}) = \operatorname{E}_{z \sim p(z|x;\theta^{(i)})}\left[ \ln p(x,z;\theta) \right] = \sum\limits_{z} p(z|x;\theta^{(i)}) \ln p(x,z;\theta) = \mathcal{L} (q;\theta) - H(p(z|x;\theta^{(i)}))$$

观察发现，这个期望表达式就是\( \mathcal(L) (q;\theta) \)的分子部分，而负熵则是分母部分。由于熵与参数变量\( \theta \)无关，在M-step中对参数求梯度时它是常数，梯度为0；所以与上一节中的描述形式其实是一致的。

M-step就是最大化上面的期望表达式值，采用拉格朗日乘数法估计\( \theta \)(有时还会包含一些约束条件)。对\( \theta \)中的某具体参数求梯度时，其他参数即为常数，表达式会大大简化。M-step:

$$\theta^{(i+1)} = \underset{\theta}{\operatorname{arg\,max}} \ Q(\theta|\theta^{(i)}) \$$

注意，极大似然估计时，基于样本独立同分布的假设，要将每个样本的对数似然相加。

$$\theta^{(i+1)} = \underset{\theta}{\operatorname{arg\,max}} \sum\limits_{t} \sum\limits_{z} p(z^{(t)}|x;\theta^{(i)}) \ln p(x^{(t)},z^{(t)};\theta)$$