机器学习3. EM算法与变分推断(Variational Inference)

参考文献

1. PRML

EM算法

核心思想（以混合高斯为例）：样本$x$x是由多个混合高斯组成，若我们知道每个数据$x_i$xi​来自于哪个混合高斯（如第$k$k个），那么我们对所有属于类$k$k的$x_{ik}$xik​使用极大似然估计就可以求得相应的参数。但是现在我们不知道样本$x_{ik}$xik​中到底属于哪个$k$k，我们可以先根据当前的参数$\theta$θ估计一个样本的类别向量$z_{ik}$zik​（E步），使得在这个类别向量下我的总似然最大，然后我在这个类别向量的条件下用以前的极大似然方法估计我新的参数（M步）。重复迭代直至收敛。

• Jession 不等式

  • 对凸函数$f(x)$f(x)来说，有下式成立（凹函数反向）
    $E[f(x)] \geq f(E[x])$E[f(x)]≥f(E[x])
  • 等号成立条件：
    $x$x是常数

• 原始问题似然函数推导：
  $l(\theta)=\sum_i log(P(x_i;\theta))$l(θ)=∑i​log(P(xi​;θ)) 对数似然定义
  $=\sum_i log(\sum_{z_i} P(x_i,z_i;\theta))$=∑i​log(∑zi​​P(xi​,zi​;θ)) 将隐变量展开
  $=\sum_{i}log(\sum_{z_i}Q(z_i)\frac{P(x_i,z_i,\theta)}{Q(z_i)})$=∑i​log(∑zi​​Q(zi​)Q(zi​)P(xi​,zi​,θ)​) ，其中${Q(z_i)}$Q(zi​)是$z_i$zi​的分布（类似一个multinational的分布）

  • 若直接对上式进行极大似然估计，那么由于对数内侧求和符号的存在，所求偏导比较复杂。
  • 观察对数项，其实是$\frac{P(x_i,z_i,\theta)}{Q(z_i)}$Q(zi​)P(xi​,zi​,θ)​对$Q$Q分布的一个数学期望，又因为对数函数是凹函数，由jession不等式可得下界：
    $\sum_{i}log(\sum_{z_i}Q(z_i)\frac{P(x_i,z_i,\theta)}{Q(z_i)}) =\sum_{i}log(E_Q[\frac{P(x_i,z_i,\theta)}{Q(z_i)}])$∑i​log(∑zi​​Q(zi​)Q(zi​)P(xi​,zi​,θ)​)=∑i​log(EQ​[Q(zi​)P(xi​,zi​,θ)​])
    $\geq \sum_{i}E_Q[log(\frac{P(x_i,z_i,\theta)}{Q(z_i)})]$≥∑i​EQ​[log(Q(zi​)P(xi​,zi​,θ)​)] (Jession 不等式)
    $=\sum_i\sum_{z_i}Q(z_i)log(\frac{P(x_i,z_i,\theta))}{Q(z_i)})$=∑i​∑zi​​Q(zi​)log(Q(zi​)P(xi​,zi​,θ))​)
  • 此时便可以用极大似然估计参数了。现在推导等式成立条件：
    $\frac{P(x_i,z_i,\theta))}{Q(z_i)}$Q(zi​)P(xi​,zi​,θ))​等于一常数$c$c，根据数学分布的定义对$z_i$zi​求和可得：
    $Q(z_i) = \frac{P(x_i,z_i,\theta)}{\sum_{z_i}P(x_i,z_i,\theta)}$Q(zi​)=∑zi​​P(xi​,zi​,θ)P(xi​,zi​,θ)​
    $=\frac{P(x_i,z_i,\theta)}{P(x_i,\theta)} =P(z_i|x_i,\theta)$=P(xi​,θ)P(xi​,zi​,θ)​=P(zi​∣xi​,θ)（求和消去了隐变量z，后一个等号是条件概率公式）
  • 上式我们推得了$Q(z_i)$Q(zi​)是什么分布的时候（z关于x的条件概率分布），不等式等号成立。然后我们可以：
    • 基于这个分布$Q(z_i)$Q(zi​)，我们得到了原似然的一个“紧”的下界（不等号成立），我们对这个似然使用极大似然估计（求和号都在对数号前边，方便估计），得到新的最优化参数$\theta_{t+1}$θt+1​
    • 用新的参数$\theta_{t+1}$θt+1​重新计算此时分布$Q(z_i)$Q(zi​)，重复上述过程。（迭代直至收敛）。

• 引用一下别人的图片。
  

变分推断/变分贝叶斯

在贝叶斯框架下，万物基于概率，万物也都有先验信息。贝叶斯学派认为，由于观测数据的到来（似然函数），修正了我们先前对事物的认知（先验的认知）。从而得到了修正后的认知（后验）。
贝叶斯公式：
$P(B_i|A) = \frac{P(B_i)P(A|B_i)}{\sum_j {P(B_j)P(A|B_j)}} \tag {2.1}$P(Bi​∣A)=∑j​P(Bj​)P(A∣Bj​)P(Bi​)P(A∣Bi​)​(2.1)
其中分母为归一化因子，$P(B_i)$P(Bi​)是先验信息，$P(B_i|A)$P(Bi​∣A)是后验，$P(A|B_i)$P(A∣Bi​)是似然。

• 但是实际上后验信息很难计算，所以我们想换一种方法近似得到后验信息。
  变分推断核心思想：假设真正的后验分布是$p$p，给定较为简单的分布$q$q，我们希望用$q$q分布去逼近$p$p分布。这样虽然我们不能直接计算$p$p分布，但也能得到一个差不多近似的$q$q分布。

• 衡量分部之间的距离–>KL Divergence
  任意两分布$p$p和$q$q的KL距离定义如下：
  $D(P||Q)=\sum P(x)log\frac{P(x)}{Q(x)} \tag {2.2}$D(P∣∣Q)=∑P(x)logQ(x)P(x)​(2.2)
  当两个分布相同时，KL为0，除此之外均大于0。
  KL散度是非对称的度量。

• Variational Inference中假设各隐变量独立(Mean Field，平均场理论)，即
  $P(Z)=P(Z_1)P(Z_2)...P(Z_n) \tag {2.3}$P(Z)=P(Z1​)P(Z2​)...P(Zn​)(2.3)

• 我们前边说想找一个好优化的分布$q$q去近似真正的后验$p$p， 现在我们从似然函数出发，推导VI的形式。
  $ln(p(X)) = ln(p(X,Z) - ln(p(Z|X))$ln(p(X))=ln(p(X,Z)−ln(p(Z∣X))【条件概率公式，Z是所有的隐变量】
  $= ln(\frac{p(X,Z)}{q(Z)})-ln(\frac{p(Z|X)}{q(Z)})$=ln(q(Z)p(X,Z)​)−ln(q(Z)p(Z∣X)​) 【等号右侧同时引入z的分布q】
  $= ln(p(X,Z) -ln(q(Z))-ln(\frac{p(Z|X)}{q(Z)})$=ln(p(X,Z)−ln(q(Z))−ln(q(Z)p(Z∣X)​)
  等式两侧对$q(Z)$q(Z)积分：

  • 左=$\int ln(p(X))q(Z)dZ=ln(p(X))\int q(Z)dZ=ln(p(X))$∫ln(p(X))q(Z)dZ=ln(p(X))∫q(Z)dZ=ln(p(X)) 【q(Z)自己是一个分布，求和为1，所以左边不变。】
  • 右=$ln(p(X)) = \int q(Z)ln(p(X,Z)) dZ- \int q(Z) ln q(Z)dZ- \int q(Z) ln(\frac{p(Z|X)}{ln(q(Z)})dZ$ln(p(X))=∫q(Z)ln(p(X,Z))dZ−∫q(Z)lnq(Z)dZ−∫q(Z)ln(ln(q(Z)p(Z∣X)​)dZ
    我们注意到最后一项就是$q$q和$p$p的负KL距离，我们定义前两项叫做ELBO(Evidence Lower BOund),那么：
  • 右=$ELBO+KL(q,p)$ELBO+KL(q,p)
    注意希望p分布和q分布尽量接近，也就是他们的KL距离越小，这等价于最大化ELBO。
    
    记$L(q)=ELBO= \int q(Z)ln(p(X,Z)) dZ- \int q(Z) ln q(Z)dZ$L(q)=ELBO=∫q(Z)ln(p(X,Z))dZ−∫q(Z)lnq(Z)dZ
    $= \int\prod_{i=1} ^M q_i({Z_i})ln(p(X,Z)) dZ- \int \prod_{i=1} ^M q_i({Z_i}) ln \prod_{i=1} ^M q_i({Z_i})dZ$=∫∏i=1M​qi​(Zi​)ln(p(X,Z))dZ−∫∏i=1M​qi​(Zi​)ln∏i=1M​qi​(Zi​)dZ 【由均值场定理对Z展开】
    • 考虑第一项：
      $=\int_{z_1}\int_{z_2}..\int_{z_M}\prod_{i=1} ^M q_i({Z_i})ln(p(X,Z)) dz_1 dz_2...dz_M$=∫z1​​∫z2​​..∫zM​​∏i=1M​qi​(Zi​)ln(p(X,Z))dz1​dz2​...dzM​ 【将积分号展开】
      $=\int_{z_j} q_j(Z_j) (\int_{z_{i \neq j}} ...\int \prod_{i \neq j}^M q_i(Z_i) lnp(X,Z) \prod_{i \neq j}^M d_{Z_i})d_{Z_j}$=∫zj​​qj​(Zj​)(∫zi̸​=j​​...∫∏i̸​=jM​qi​(Zi​)lnp(X,Z)∏i̸​=jM​dZi​​)dZj​​
      $=\int_{z_j} q_j(Z_j) E_{i \neq j}[ ln(p(X,Z))]d_{Z_j}$=∫zj​​qj​(Zj​)Ei̸​=j​[ln(p(X,Z))]dZj​​ 【将$z_j$zj​提出来，剩下的所有项放后边得到一个数学期望】
    • 考虑第二项：
      • 引理：N重积分（一项求和一项对变量连乘可分解为N个一重积分，证明就是展开后无关项都会积分掉。）
        $\int_{x_1} \int_{x_2}(f(x_1) + f(x_2)) p(x_1, x_2) dx_1 dx_2$∫x1​​∫x2​​(f(x1​)+f(x2​))p(x1​,x2​)dx1​dx2​
        $= \int_{x_1} f(x_1) dx_1 + \int_{x_2} f(x_2) dx_2$=∫x1​​f(x1​)dx1​+∫x2​​f(x2​)dx2​
      • 由引理可得第二项为：
        $\int \prod_{i=1} ^M q_i({Z_i}) ln \prod_{i=1} ^M q_i({Z_i})dZ$∫∏i=1M​qi​(Zi​)ln∏i=1M​qi​(Zi​)dZ
        $=\int \prod_{i=1} ^M q_i({Z_i}) \sum_{i=1} ^M ln q_i({Z_i})dZ$=∫∏i=1M​qi​(Zi​)∑i=1M​lnqi​(Zi​)dZ 【对数与连乘操作化简】
        $=\sum_{i=1} ^M\int q_i({Z_i}) ln q_i({Z_i})dZ$=∑i=1M​∫qi​(Zi​)lnqi​(Zi​)dZ 【注意这里求和还是关注了所有项，若只关注某一项，则去掉求和号，下标改为对应的下标】

  所以，对某一项$q_j$qj​：
  $L(q_j) =\int_{Z_j} q_j(Z_j) E_{i \neq j} ln(p(X,Z))d_{Z_j} - \int_{Z_j} q_j(Z_j) ln(q_j(Z_j))dZ_j+ const$L(qj​)=∫Zj​​qj​(Zj​)Ei̸​=j​ln(p(X,Z))dZj​​−∫Zj​​qj​(Zj​)ln(qj​(Zj​))dZj​+const
  胜利就在前方，对上式化简可得一KL散度,记$ln tmp = E_{i \neq j} ln(p(X,Z))$lntmp=Ei̸​=j​ln(p(X,Z))：
  $L(q_j) =\int_{Z_j} q_j(Z_j) ln tmp - \int_{Z_j} q_j(Z_j) ln(q_j(Z_j))dZ_j+ const$L(qj​)=∫Zj​​qj​(Zj​)lntmp−∫Zj​​qj​(Zj​)ln(qj​(Zj​))dZj​+const 【变量替换】
  $L(q_j) =\int_{Z_j} q_j(Z_j) [ln tmp - ln(q_j(Z_j)]dZ_j+ const$L(qj​)=∫Zj​​qj​(Zj​)[lntmp−ln(qj​(Zj​)]dZj​+const【提取公因式】
  $L(q_j) =\int_{Z_j} q_j(Z_j) [ln \frac{tmp}{q_j(Z_j)}]dZ_j -+ const$L(qj​)=∫Zj​​qj​(Zj​)[lnqj​(Zj​)tmp​]dZj​−+const 【对数化简】
  $L(q_j) =-\int_{Z_j} q_j(Z_j) [ln \frac{q_j(Z_j)}{tmp}]dZ_j -+ const$L(qj​)=−∫Zj​​qj​(Zj​)[lntmpqj​(Zj​)​]dZj​−+const 【化简为KL散度】
  令上式这个KL散度最小，则整体最大。KL散度在取等号时最小：
  $q_j(Z_j)=tmp$qj​(Zj​)=tmp 【取对数】
  $ln q_j^*(Z_j)=lntmp= E_{i \neq j} ln(p(X,Z))$lnqj∗​(Zj​)=lntmp=Ei̸​=j​ln(p(X,Z))

结论：
- 某个隐变量的后验分布等于其他隐变量和数据x的联合似然的均值。这样更新后的q可以最大化ELBO从而最小化KL距离。从而近似我们的真实后验p。

补充：

• 在实际使用中，我们先写出ELBO，挑出要更新的参数项（包括先验和似然项），化简这个复杂的表达式，凑成后验分布的形式，由共轭分布的性质推导后验分布的参数即可。