EM算法

琴生不等式(Jensen's Inequality)

凸函数：对函数\(f\)和其定义域内任意的\(x\)，均有\(f''(x) \geq 0\)，则我们称该函数为凸函数；当函数的输入为一个向量\((x_1,x_2,...,x_n)\)时，我们称当该函数的海塞矩阵\(H\)为半正定矩阵时，该函数为凸函数

琴生不等式：对凸函数\(f\)，我们有 \[ E[f(x)] \geq f(E[x]) \] 等号当且仅当\(x\)取值概率为1时成立；当\(f\)为凹函数时，我们有： \[ E[f(x)] \leq f(E[x]) \] 同理，等号当且仅当\(x\)取值概率为1时成立

EM算法

输入：观测变量数据\(Y\)，隐变量\(Z\)，联合分布\(p(y,z|\theta)\)，条件分布\(p(z|y,\theta)\)

输出：模型参数\(\theta\)

算法步骤：

• 选择参数初值\(\theta_0\)，开始迭代
• E-step(Expectation)：记\(\theta^{(i)}\)为第i次迭代参数\(\theta\)的估计值，在第i + 1次迭代的E步，计算

\[ \begin{align*} Q(\theta,\,\theta^{(i)}) &= E_Z[log\,p(y,z|\theta)\,|\,y,\theta^{(i)}] \\ &= \sum_{Z}log\,p(y,z|\theta)p(z|y,\theta^{(i)}) \end{align*} \]

• M-step(Maximization)：求使得\(Q(\theta,\,\theta^{(i)})\)极大化的\(\theta\)，确定第i + 1次迭代的参数的估计值\(\theta^{(i + 1)}\)

\[ \theta^{(i + 1)} = arg\,\mathop{max}_\theta \,Q(\theta,\theta^{(i)}) \]

• 重复第2步和第3步，直到收敛

几点说明：

• 模型参数\(\theta\)可任意选取，但是EM算法对初值是敏感的
• Q函数式中\(Z\)式未观测数据，\(Y\)是观测数据。注意，\(Q(\theta,\theta^{(i)})\)的第一个变元表示要极大化的参数，第二个边缘表示参数当前的估计值。每次迭代实际在求Q函数及其极大值
• 停止迭代的条件：

\[ ||\theta^{(i + 1)} - \theta^{(i)}|| < \epsilon \;\;或\;\; ||Q(\theta^{(i + 1)},\theta^{(i)}) - Q(\theta^{(i )},\theta^{(i)})|| < \epsilon \]

EM算法的介绍与推导

EM算法介绍

在给定样本估计参数且参数为单个参数时，我们知道可用极大似然估计来估计参数；但此时我们存在一个隐变量，这时我们无法通过极大似然估计来求出解析解，于是我们通过EM算法来解决显/隐变量相互依赖的关系，通过赋初值迭代优化直到收敛的方式来解决参数的估计问题

EM算法的思路是使用启发式的迭代方法，由于我们没办法直接求出模型分布参数，我们可以先猜想隐含参数(E-step)，然后基于观测数据和隐含参数来极大化似然函数，求解参数(M-step)，然后不断循环迭代此过程，直到参数收敛即得到结果

EM算法推导

我们要最大化似然函数，故参数满足： \[ \theta = arg\,\mathop{max}_{\theta}\,\sum_{i = 1}^{n}\,log\,p(y^{(i)}|\theta) \] 添加隐变量\(z\)后，问题变为： \[ \theta = arg\,\mathop{max}_{\theta,z}\,\sum_{i = 1}^{n}log\sum_{z^{(i)}}p(y^{(i)},z^{(i)} |\theta) \] 对朴素的最大似然估计来说，此时的不同在于多了一个隐变量\(z\)，那么最朴素的想法是对\(\theta\)求偏导来得到极大似然估计的参数结果，但是对上式求导得到的边缘密度形式会非常复杂，很难求解。于是我们想到用琴生不等式将log内部的求和符号提出，于是有： \[ \begin{align*} \sum_{i = 1}^{n}log\sum_{z^{(i)}}p(y^{(i)},z^{(i)} |\theta) &= \sum_{i = 1}^{n}log\sum_{z^{(i)}}Q_i(z^{(i)})\frac{p(y^{(i)},z^{(i)}|\theta)}{Q_i(z^{(i)})} \\ &\geq \sum_{i = 1}^{n}\sum_{z^{(i)}}Q_i(z^{(i)})log\frac{p(y^{(i)},z^{(i)}|\theta)}{Q_{i}(z^{(i)})} \end{align*} \] 上式引入了一个新的分布\(Q_i(z^{(i)})\)，满足 \[ \sum_{z}Q_i(z) = 1,\;0\leq Q_i(z) \leq 1 \] 由于使用了琴生不等式，我们给出了极大似然函数的一个下界，我们对此下界不断进行优化，当这个值收敛时说明取到了区域极值(这也是为什么可能与取的初值有关)

需要注意的是，我们在应用琴生不等式时需要保证不等式的等号成立，而等号成立条件为取值概率为1，即： \[ \frac{p(y^{(i)},z^{(i)}|\theta)}{Q_i(z^{(i)})} = c \] 其中c是一个常数，我们进行累和可知： \[ \sum_{z}p(y^{(i)},z^{(i)}|\theta) = c\sum_{z}Q_i(z^{(i)}) \] 由于右式累和的结果为1，所以有： \[ \sum_{z}p(y^{(i)},z^{(i)}|\theta) = c\\ Q_i(z^{(i)}) = \frac{p(y^{(i)},z^{(i)}|\theta)}{c} = \frac{p(y^{(i)},z^{(i)}|\theta)}{\sum_z p(y^{(i)},z^{(i)}|\theta)} = \frac{p(y^{(i)},z^{(i)}|\theta)}{p(y^{(i)}|\theta)} = p(z^{(i)}|y^{(i)},\theta) \] 所以我们要优化的函数为 \[ \sum_{i = 1}^{n}\sum_{z^{(i)}}Q_i(z^{(i)})log\frac{p(y^{(i)},z^{(i)}|\theta)}{Q_{i}(z^{(i)})} \] 注意到： \[ \sum_{i = 1}^{n}\sum_{z^{(i)}}Q_i(z^{(i)})log\,{Q_{i}(z^{(i)})} \] 为常数，所以最后参数\(\theta\)的优化为： \[ \theta = arg\,\mathop{max}_{\theta}\sum_{i = 1}^{n}\sum_{z^{(i)}}p(z^{(i)}|y^{(i)},\theta)log\,{p(y^{(i)},z^{(i)}|\theta)} \]

EM算法的收敛性

收敛性证明

我们有： \[ log\,p(y|\theta) = log\,p(y,z|\theta) - log\,p(z|y,\theta) \] 两边同时求期望得： \[ E_{z|y,\theta^{(t)}}[log\,p(y|\theta)] = E_{z|y,\theta^{(t)}}[log\,p(y,z|\theta)] - E_{z|y,\theta^{(t)}}[log\,p(z|x,\theta)] \] 等式左侧与\(Z\)无关，故取期望值不变

等式右侧第一项即为\(Q(\theta,\theta^{(t)})\)，由我们对EM算法的推导可知： \[ Q(\theta^{(t + 1)},\theta^{(t)}) \geq Q(\theta^{(t)},\theta^{(t)}) \] 然后我们来看第二项，由上所述，我们有\(Q(\theta^{(t + 1)},\theta^{(t)}) \geq Q(\theta^{(t)},\theta^{(t)})\)，那么只需要保证： \[ E_{z|y,\theta^{(t)}}[log\,p(z|y,\theta^{(t + 1)})] \leq E_{z|y,\theta^{(t)}}[log\,p(z|y,\theta^{(t)})] \] 注意到上式是\(z\)和\(y\)的DL散度定义，故显然成立

所以说明EM算法是收敛的，但收敛值为局部最佳，且与初值的选取有关