EM

Update

结合两个文章的链接和UBM实例，进行的推导。

J向领导汇报通俗解释版：

我们假设有三个事件，那么对于一个项目，用户点击的概率就是，我们的目的就是估计其中的 $P(A_u = 1)$ 的概率进行排序
注意我们看到的点击和不点击都只是事件，而不是背后的概率。所以不是说点击了， $P(C_u = 1)=1$
我们引入EM算法，去估算，得到这样一个公式，用条件概率去计算事件的概率。
看下图，主要是第一张图，里面讲解了怎么推导。

基本将EM算法和UBM算法搞懂了。

Representation

EM算法是一种迭代算法，用于含有隐变量(hidden variable)的概率模型参数的极大似然估计，记住remember该算法意义，或极大后验概率估计。EM算法的每次迭代由两步组成：E步，求期望(expectation)；M步，求极大( maximization )，所以这一算法称为期望极大算法(expectation maximization algorithm)，简称EM算法。

如果概率模型的变量都是观测变量，那么给定数据之后就可以直接使用极大似然法或者贝叶斯估计模型参数。但是当模型含有隐含变量的时候就不能简单的用这些方法来估计，EM就是一种含有隐含变量的概率模型参数的极大似然估计法。

似然函数是一种关于统计模型中的参数的函数，表示模型参数中的似然性。
注意与最大似然估计中的似然函数是联合概率乘积不同（这是更复杂的似然函数），而这里是简单的似然函数。
概率用于在已知一些参数的情况下，预测接下来的观测所得到的结果，而似然性则是用于在已知某些观测所得到的结果时，对有关事物的性质的参数进行估计。
在已知某个参数B时，事件A会发生的概率写作 $P(A|B)$ ，而当未知参数B时， $L(B|A)$ 表示为已知有事件A发生时，参数B发生的似然性（“概率”）。具体解释为：似然函数 $L(b|A)=P(A|B=b)$ （数值上与条件概率相等）表示为在事件A发生时，参数B=b的似然性。J看上去形式一样，但是意义不一样，记住remember该似然函数定义。对同一个似然函数，如果存在一个参数值，使得它的函数值达到最大的话，那么这个值就是最为“合理”的参数值。
EM算法推导。
面对一个含有隐变量的概率模型，目标是极大化观测数据（不完全数据），即极大化下式（不完全数据Y的对数似然函数）。
$L(θ)=logP(Y|θ)=log\sum_{z}P(Y,Z|θ)=log(\sum_{z}P(Y|Z,\theta)P(Z|\theta))$
极大化的主要困难是上式中含有未观测数据并有包含和（或积分）的对数，EM算法则是通过迭代逐步近似极大化L(θ)的，如果采用梯度下降等方法求导，则隐变量数目上升，无法求解，所以才用迭代法。
事实上，EM算法是通过迭代步近似极大化 $L(\theta)$ 的。假设在第i次迭代后 $\theta$ 的估计值 $\theta^i.$ 。我们希望新估计值能使 $L(\theta)$ 增加，即 $L(\theta)>L(\theta^{(i)})$ ，并逐步达到极大值。为此，考虑两者的差：
$L(\theta)-L(\theta^{(i)})=log(\sum_zP(Y|Z,\theta)P(Z|\theta))-logP(Y|\theta^{(i)})$
由此式推得到： $B(\theta, \theta^{(i)})=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)})}\\L(\theta)\ge B(\theta, \theta^{(i)})$
B函数是目标式的一个下界，只要其变大，那么目标式子也变大。
从而推得式子： $\theta^{(i+1)}=argmax_{\theta}B(\theta, \theta^{(i)})$
分析B函数，得到等价式子： $\theta^{(i+1)}=argmax_{\theta}Q(\theta, \theta^{(i)})$
总结：EM算法的一次迭代，即求Q函数及其最大化，EM算法是通过不断求解下界的极大化逼近求解对数似然函数极大化的算法。下图中相交处是 $\theta^{(i)}$ ，即表示B函数是一个下界。而之后找 $\theta^{(i+1)}$ 使得B函数极大化，Q函数也会极大化，从而导致不完全数据Y的对数似然函数也最大化。
EM算法。
输入：观测数据 $Y$ ，隐变量数据 $Z$ ，联合分布 $P(Y,Z|\theta)$ ，条件分布 $P(Z|Y,\theta)$ ；
输出：模型参数 $\theta$ 。
1. 选择参数的初值 $\theta^{(0)}$ ，开始迭代；
2. E步：记 $\theta^{(0)}$ 为第 $i$ 次迭代参数 $\theta$ 的估计值，在第 $i+1$ 次迭代的E步，计算
  $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)})$
  这里， $P(Z|Y, \theta^{(i)})$ 是在给定观测数据Y和当前的参数估计 $\theta^{(i)}$ 下隐变量数据Z的条件概率分布；
3. 求使 $Q(\theta, \theta^{(i)})$ 极大化的 $\theta$ ，确定第 $i+1$ 次迭代的参数的估计值 $\theta^{(i+1)}$
  $\theta^{(i+1)} = \arg \max_{\theta} Q(\theta, \theta^{(i)})$
4. 重复第(2)步和第(3)步，直到收敛。
  其中的函数 $Q(\theta, \theta^{(i)})$ 是EM算法的核心。称为Q函数。
  Q函数：完全数据的对数似然函数 $\log P(Y, Z | \theta)$ 关于在给定观测数据Y和当前参数 $\theta^{(i)}$ 下对未观测数据Z的条件概率分布 $P(Z|Y, \theta^{i})$ 的期望:
  $Q(\theta, \theta^{(i)}) = E_Z[\log P(Y, Z|\theta) | Y, \theta^{(i)}]\\= \sum_Z P(Z | Y, \theta^{(i)}) \log P(Y, Z | \theta)$
  算法说明：
5. 参数的初值可以任意选择。但需注意EM算法对初值是敏感的。常用的办法是选取几个不同的初值进行迭代，然后对得到的各个估计值加以比较，从中选择最好的。
  2.E步求 $Q(\theta, \theta^{(i)})$ 。Q函数式中Z是未观测数据，Y是观测数据。注意， $Q(\theta, \theta^{(i)})$ 的第1个变量 $\theta$ 表示要极大化的参数，第2个变量 $\theta^{(i)}$ 表示参数的当前估计值。每次迭代实际在求Q函数及其极大。
6. M步求 $Q(\theta, \theta^{(i)})$ 的极大化，得到 $\theta^{(i+1)}$ ，完成一次迭代 $\theta^{(i)}\rightarrow\theta^{(i+1)}$ 。后面将证明每次迭代使似然函数增大或达到局部极值。
7. 给出停止迭代的条件，一般是 $\theta$ 或是Q函数更新的差值小于某一较小的正数。
EM算法推导在非监督学习中的应用。
比如在k-means中，隐变量是每个样例的最佳类别，先随便制定一个类C给它，计算各自距离（E步），然后让P(x,y)最大（k-means中是最小化平方误差），再将质心重新指派给样例（M步），不断重复，一直到没有更好的。

Reference

Previousunsupervised learning NextEM with CM

Last updated 5 years ago

Was this helpful?