带你理解EM算法

很多时候，我们都要最大化似然度来求得一个参数 $θ$ 的最优值。但是，很多时候，当我们的模型中存在隐变量的时候（比如，一个词所属的主题，聚类问题中样本的类别, etc.），我们的似然度是很难求的。下面是该似然度的式子，其中z表示不可观测的变量，x表示可观测的变量，由于z是不可观测的，所以，要求似然度，我们必须要对z求和或求积分(连续的时候求积分，离散的时候求和)。

L (θ) = \sum_{i = 1}^{N} \log p (x_{i} | θ) = \sum_{i = 1}^{N} \log [\sum_{z_{i}} p (x_{i}, z_{i} | θ)]

可以看到上面的这个式子，如果不存在隐变量的话，那么那个log是直接作用与p的，如果p恰好是指数族分布，那么这个似然度就非常好求，但是有隐变量的时候，log被一个

\sum_{z}

给截断的，这就使得这个式子变得很难优化。

这个问题的关键在于， $\log p (x_{i} | θ)$ 很难优化，但是 $p (x_{i}, z_{i} | θ)$ 却很好优化,比如说聚类的时候，你提前知道所有样本的类别了，那你计算每个类别的中心距离就太简单了，但是要优化 $p (x_{i}, z_{i} | θ)$ 的前提是，你要看得到隐变量的取值才行啊，然而隐变量是看不到的。EM算法通过一个巧妙的构造，让 $p (x_{i}, z_{i} | θ)$ 和似然度 $p (x_{i} | θ)$ 的下界联系起来，这是我们只要优化下界就能代替优化似然度本身。

接下来我们看一下对于单个样本 $p (x_{i})$ 似然度的下界是什么东西。在这里我们引入了 $z_{i}$ 的分布 $q_{i} (z_{i})$

\begin{aligned} \log p (x_{i} | θ) & = \log p (x_{i}, z_{i}) - \log p (z_{i} | x_{i}) \\ = \log (\frac{p (x_{i}, z_{i})}{q_{i} (z_{i})}) - \log (\frac{p (z_{i} | x_{i})}{q_{i} (z_{i})}) \\ = \log p (x_{i}, z_{i}) - \log q_{i} (z_{i}) - \log (\frac{p (z_{i} | x_{i})}{q_{i} (z_{i})}) \\ = \int q_{i} (z_{i}) \log p (x_{i}, z_{i}) d z - \int q_{i} (z_{i}) \log q (z_{i}) d z - \int q_{i} (z_{i}) \log (\frac{p (z_{i} | x_{i})}{q_{i} (z_{i})}) d z (两 边 同 时 对 z 求 期 望) \\ = \underset{E L O B_{i}}{\underset{⏟}{E_{z_{i}} (\log p (x_{i}, z_{i})) - H (q_{i})}} + K L (q_{i} (z_{i}) | | p (z_{i} | x_{i})) \end{aligned}

我们知道

K L (q (z_{i}) | | p (z_{i} | x_{i})) ⩾ 0

，所以这个似然度一定有

\log p (x_{i}) ⩾ E_{z_{i}} (\log p (x_{i}, z_{i})) - H (q_{i})

可以看到对数似然度被分解成了两部分，一个是evidence lower bound(ELOB)，似然度的下界，另一个是KL距离，不管q是什么分布，这两部分加起来肯定是一样的。
带你理解EM算法

图中的L是我们的ELOB。

也就是说，只要我们令KL距离为0，此时 $q (z) = p (z | x)$ ，那么ELOB就等于似然度的值了。这就意味着我们最大化 $θ$ 的时候，不再需要对 $\log p (x | θ)$ 做，只需要找到 $θ$ 使得这个ELOB最大不就相当于在“最大化我们的似然度”吗。而最大化这个ELOB太简单了，在这里 $H (q)$ 是q的熵，与 $θ$ 无关只与分布q有关，所以不用管。于是我们把 $q (z) = p (z | x)$ 代入到ELOB中得到

\begin{aligned} E L O B_{i} & = E_{z_{i}} (\log p (x_{i}, z_{i})) + c o n s t \\ = \int q_{i} (z_{i}) \log p (x_{i}, z_{i}) d z + c o n s t \\ = \int p (z_{i} | x_{i}) \log p (x_{i}, z_{i}) d z + c o n s t \\ = \sum_{z_{i}} p (z_{i} | x_{i}) \log p (x_{i}, z_{i}) + c o n s t (如 果 z 是 离 散 的) \end{aligned}

EM算法，示意图，E步，把KL设为0，蓝色的线往上移，使得ELOB=似然度，M步，最大化ELOB，使得似然度增大，红色的线往上移，然后我们不断重复直到收敛。

考虑所有样本，正式的EM框架：

E步：把 $q_{i} (z_{i}) = p (z_{i} | x_{i})$ 代入到下界中，再把常数项剔除，

Q (θ, θ^{t - 1}) = \sum_{i = 1}^{N} \sum_{z_{i}} p (z_{i} | x_{i}, θ^{t - 1}) \log p (x_{i}, z_{i}, θ) = \sum_{i = 1}^{N} E [\log p (x_{i}, z_{i} | θ) | x_{i}, θ^{t - 1}]

M步：最大化下界ELOB

θ^{t} = \arg max_{θ} Q (θ, θ^{t - 1})

M步2：我们还可以做MAP估计，只需要在Q加上参数的对数先验就可以轻松完成，E步没有任何变化

θ^{t} = \arg max_{θ} Q (θ, θ^{t - 1}) + \log p (θ)

在MAP估计的时候，不仅需要考虑下界的最大化，还需要考虑先验对参数的影响。

作为分享主义者(sharism)，本人所有互联网发布的图文均遵从CC版权，转载请保留作者信息并注明作者a358463121专栏:http://blog.csdn.net/a358463121，如果涉及源代码请注明GitHub地址：https://github.com/358463121/。商业使用请联系作者。

相关推荐