EM算法

1、必要的前置知识

  1. 最大似然估计(MLE):找出一组参数(模型中的 参数),使得模型产出观察数据的概率最大。
  2. 贝叶斯算法估计:从先验概率和样本分布情况来计算后验概率的一种方式。
  3. 最大后验概率估计(MAP):另一种MLE的感觉,求 $\theta$ 使 $P(x|\theta)P(\theta)$ 的值最大,这也就是要求 $\theta$ 值不仅仅是让似然函数最大,同时要求 $\theta$ 本身出现的先验概率也得比较大。
  4. Jensen不等式:如果函数 $f$ 为凸函数,那么存在公式$f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta) f(y)$,进一步推论得到若 $\theta_1,…\theta_k \geq 0$ 且$\theta_1+\theta_2+…+\theta_k = 1 $,则有 $f(\theta_1 x_1 + … + \theta_k x_k) \leq \theta_1 f(x_1) + … + \theta_k f(x_k)$。

2、EM算法

EM算法(Expectation Maximization Algorithm)最大期望算法,是一种较为常用的算法思路,像之前的 SoftMax 算法就算是 EM 算法的一种,这种算法主要分为以下两个循环操作:

  1. E步骤:估计隐藏变量的概率分布期望函数
  2. M步骤:根据期望函数重新估计分布参数

简单的来说就是写出带参数的表达预测正确的概率公式,然后用一种方法使得这个预测正确的概率最大。其整体的流程如下:

注:这个使预测概率最大化的过程往往会得到一些关键的参数,有时候这个参数就是我们要求得某个事件发生的概率。

  • 初始化分布参数
  • 重复下列操作直至收敛
    • E步骤:估计隐藏变量的概率分布期望函数
    • M步骤:根据期望函数重新估计分布参数(用的是MAP),即重新调整模型参数$\theta$,公式如下

      设数据集中包含着我们不能观测到的隐含数据$z = {z_1, z_2, …,z_m}$

      \[\begin{split} \theta &= arg\ max_\theta\sum_{i=1}^m log(P(x_i;\theta)) \\ &arg\ max_\theta\sum_{i=1}^m log(\sum_{z_i}P(z_i)P(x_i\|z_i;\theta)) \\ &arg\ max_\theta\sum_{i=1}^m log(\sum_{z_i}(P(x_i,z_i;\theta)) \end{split}\]

3、EM算法求解原理

根据上一章中的EM算法总述看来,现在我们整体要做的就是根据对数似然函数,调整参数 $\theta$ 使得对数似然函数向变大的方向前进。按照以往的惯例,我们直接进行求导就好了。然而在这里则行不通,我们可以看到中间存在隐藏数据。为什么说是隐藏的呢,那是因为这个数据是不可观测的,也就是说我们不能在每一步中直接测量到这些数据

不过好消息是我们可以得到这个隐藏函数的分布。于是进行的曲线救国过程的第一步如下: \(\begin{split} l(\theta) &= \sum_{i=1}^m log\sum_z p(x,z;\theta) \\ &= \sum_{i=1}^m log \sum_z Q(z;\theta) * \frac{p(x_i,z;\theta)}{Q(z;\theta)}\ \ \ 步骤1 \\ &= \sum_{i=1}^m log(E_Q(\frac{p(x_i,z;\theta)}{Q(z;\theta)})\ \ \ 步骤2 \\ &\geq \sum_{i=1}^m E_Q(log(\frac{p(x_i,z;\theta)}{Q(z;\theta)})\ \ \ 步骤3 \\ &= \sum_{i=1}^m \sum_z Q(z;\theta) log (\frac{p(x_i,z;\theta)}{Q(z;\theta)})\ \ \ 步骤3 \end{split}\)

首先,我们明确的目标是得到最佳参数 $\theta$ 也就是说,我们企图得到一种可以把似然函数写成纯 $\theta$ 的公式,之后进行通过求偏导的方式来得到我们要求的最佳参数 $\theta$。

步骤一中,我们引入了隐藏数据的分布 $Q(z;\theta) $ , 根据分布函数的性质$\sum_z Q(z;\theta)=1 $ ,所以我们加入这个参数是不会改变原函数的数值,之后根据数学期望的定义将右边式子写成了数学期望的形式,于是得到了步骤二。

在步骤三中,根据根据Jensen不等式,我们可以得到$f(E(x)) \leq E(f(x))$,所以我们将$log$塞到期望函数里面,最终得到了步骤四。

好了到现在为止,我们只是得到了另一个看似依旧不能计算的式子,貌似多此一举的引入了一个叫做 Jensen 不等式的东西,但是这一步是很关键。在未引入Jensen不等式之前,我们只是单纯的添加了一个叫做隐含数据的变量,但是它在式子中并未和别的参数相关,而引入了Jensen不等式之后,这个式子中的隐含数据将和数据集关联就变得可以测量得到了。

所以曲线救国的第二步就是,根据Jensen不等式的取等条件得到 $\frac{p(x,z;\theta)}{Q(z;\theta)} = c$ 的时候等号成立,于是根据如下推导得到当等号成立的时候,得到的关系公式 3.1 。

\[Q(z,\theta) = \frac{p(x,z;\theta)}{c} = \frac{p(x,z;\theta)}{c*\sum_{z_i}p(x,z_i;\theta)} = \frac{p(x,z;\theta)}{p(x;\theta)} = p(z\|x;\theta)\ \ \ 公式3.1\]

之后将公式 3.1 带入之前步骤三的公式中,得到如下公式3.2

\[\sum_{i=1}^m \sum_z p(z\|x_i;\theta) log (\frac{p(x_i,z;\theta)}{p(z\|x_i;\theta)})\ \ 公式3.2\]

又由于给定数据集之后 $p(z|x_i;\theta)$ 的值是固定的,所以可以去掉,而保留前方的 $p(z|x_i;\theta)$ 的原因类似 MAP 模型,要求先验概率也要大。之后便是传统的求能使公式3.2最大的模型参数 $\theta$ 。

至此,我们公式已经推完了,简单的整体分析一下,式子中含有两个变量$z$ 和 $\theta$ ,我们先假定了 $\theta$ 的初始值,显然根据求导等于0能得到 $z$ 的值,之后再根据 $z$ 的值可以反求 $\theta$ 的变化方向。如此往复就是 EM 算法的求解过程。

4、结语

整体而言 EM 算法相比之前的算法引入了一个叫做隐含数据的变量,这个变量我们认为是会对结果发生影响的。整个算法都是在讨论一种,如何将这种我们不清楚的变量和我们预测手法联系在一起,其中用到了 Jensen 不等式来让他们联系在一起,变得可以被计算。以后有时间的话还会补充 GMM 在EM算法中的应用。

  • 本文作者: Author:DeamoV
  • Github:https://github.com/VDeamoV
  • Email:vincent.duan95@outlook.com
  • 本文链接: Artical: EM算法
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!
  • 版权声明: 原创文章如转载,请注明出处