符号说明

• x x x：已观测变量的集合 { x 1 , x 2 , x 3 , . . . , x N } \{x_1,x_2,x_3,...,x_N\} {x1​,x2​,x3​,...,xN​}，长度为 N N N
• z z z：隐变量（未观测变量）
• θ \theta θ：分布参数
• ( x , z ) (x,z) (x,z)：完整数据
• p ( x ∣ θ ) p(x|\theta) p(x∣θ)：似然函数

  KL散度

  • KL散度用于衡量原始分布与近似分布的差异，从公式来看，其计算的是原始分布与近似分布之间的对数差的期望，公式如下

    D K L ( p ∣ ∣ q ) = E [ ln ⁡ p ( x ) − ln ⁡ q ( x ) ] = ∑ i = 1 N p ( x i ) ln ⁡ p ( x i ) q ( x i ) = ∫ x p ( x i ) ln ⁡ p ( x i ) q ( x i ) d x D_{KL}(p||q)=E[\ln p(x)-\ln q(x)]=\sum_{i=1}^Np(x_i)\ln \frac{p(x_i)}{q(x_i)}=\int_x p(x_i) \ln \frac{p(x_i)}{q(x_i)}dx DKL​(p∣∣q)=E[lnp(x)−lnq(x)]=i=1∑N​p(xi​)lnq(xi​)p(xi​)​=∫x​p(xi​)lnq(xi​)p(xi​)​dx

  • KL散度大于等于0

    EM算法

    EM算法原理

    • EM算法常用于估计参数的隐变量，它是一种迭代式的方法，其基本想法是：如果参数 θ \theta θ已知，则可以根据训练数据推断出最优隐变量 z z z的值（ E E E步）；反之，若 z z z已知，则可以方便地对参数 θ \theta θ做极大似然估计（ M M M步）
    • 假设我们要对参数 θ \theta θ做极大似然估计，则需要最大化对数似然

      ln ⁡ p ( x , z ∣ θ ) \ln p(x,z|\theta) lnp(x,z∣θ)，但由于隐变量 z z z是未知的，因此上式无法直接求解，我们可以通过对上式计算关于 z z z的期望来最大化已观测数据x的边缘似然，即最大化

      ln ⁡ p ( x , z ∣ θ ) = ∫ z ln ⁡ p ( x , z ∣ θ ) p ( z ∣ x , θ ) d z \ln p(x,z|\theta)=\int_z \ln p(x,z|\theta)p(z|x,\theta)dz lnp(x,z∣θ)=∫z​lnp(x,z∣θ)p(z∣x,θ)dz

    • 于是，EM算法的原型便是，以初始值 θ 0 \theta^0 θ0为起点，对上式可迭代执行以下步骤直至收敛：
      • 基于第 t t t步的 θ t \theta^t θt推断隐变量 z z z的分布 p ( z ∣ x , θ ) p(z|x,\theta) p(z∣x,θ)
      • 基于已观测变量 x x x和 p ( z ∣ x , θ ) p(z|x,\theta) p(z∣x,θ)对参数 θ \theta θ做极大似然估计得到 θ t + 1 \theta^{t+1} θt+1
      • 由此，我们可以得出EM算法的迭代方程

        θ t + 1 = arg max ⁡ θ ∫ z ln ⁡ p ( x , z ∣ θ t ) p ( z ∣ x , θ t ) d z \theta^{t+1}=\argmax_\theta\int_z \ln p(x,z|\theta^t)p(z|x,\theta^t)dz θt+1=θargmax​∫z​lnp(x,z∣θt)p(z∣x,θt)dz

        变分推断

        问题背景

        • 通常而言，机器学习中需要解决的问题是由观察到的变量 x x x来估计隐变量 z z z的分布以及参数 θ \theta θ，也就是求解 p ( z ∣ x , θ ) p(z|x,\theta) p(z∣x,θ)以及 θ \theta θ

          用公式来表达，变量集合 x x x的联合分布为 p ( x ∣ θ ) = ∏ i = 1 N ∫ z p ( x i , z ∣ θ ) d z p(x|\theta)=\prod_{i=1}^N\int_zp(x_i,z|\theta)dz p(x∣θ)=i=1∏N​∫z​p(xi​,z∣θ)dz

          则其对应的对数似然函数就为

          ln ⁡ p ( x ∣ θ ) = ln ⁡ ∏ i = 1 N p ( x i , z ∣ θ ) = ∑ i = 1 N ln ⁡ [ ∫ z p ( x i , z ∣ θ ) d z ] \ln p(x|\theta)=\ln \prod_{i=1}^Np(x_i,z|\theta)=\sum_{i=1}^N\ln\left[\int_z p(x_i,z|\theta)dz\right] lnp(x∣θ)=lni=1∏N​p(xi​,z∣θ)=i=1∑N​ln[∫z​p(xi​,z∣θ)dz]

        • 而概率模型中的参数估计通常以最大化对数似然函数为手段，对上式应用EM算法得到 θ t + 1 = arg max ⁡ θ ∫ z ln ⁡ p ( x , z ∣ θ t ) p ( z ∣ x , θ t ) d z \theta^{t+1}=\argmax_\theta\int_z \ln p(x,z|\theta^t)p(z|x,\theta^t)dz θt+1=θargmax​∫z​lnp(x,z∣θt)p(z∣x,θt)dz当 p ( z ∣ x , θ t ) p(z|x,\theta^t) p(z∣x,θt)与隐变量 z z z的真实后验分布相等时， ∫ z ln ⁡ p ( x , z ∣ θ t ) p ( z ∣ x , θ t ) d z \int_z \ln p(x,z|\theta^t)p(z|x,\theta^t)dz ∫z​lnp(x,z∣θt)p(z∣x,θt)dz近似于对数似然函数，然而，由于隐变量 z z z是未知的，我们很难得知它的真实分布，因此我们实际使用的 p ( z ∣ x , θ t ) p(z|x,\theta^t) p(z∣x,θt)未必是隐变量 z z z的真实后验分布，而通常只是一个近似分布。

        • 因此，如何推断 z z z的真实后验分布 p ( z ∣ x , θ t ) p(z|x,\theta^t) p(z∣x,θt)成为了一个问题，此时我们便可以借助变分推断。假设我们现在要使用近似分布 q ( z ) q(z) q(z)去逼近真实分布 p ( z ∣ x , θ t ) p(z|x,\theta^t) p(z∣x,θt)，我们可以很容易验证以下关系式

          ln ⁡ p ( x ∣ θ ) = L ( q ) + K L ( q ∣ ∣ p ) \ln p(x|\theta)=L(q)+KL(q||p) lnp(x∣θ)=L(q)+KL(q∣∣p)其中 L ( q ) = ∫ z ln ⁡ p ( x , z ∣ θ ) q ( z ) q ( z ) d z L(q)=\int_z \ln \frac{p(x,z|\theta)}{q(z)}q(z)dz L(q)=∫z​lnq(z)p(x,z∣θ)​q(z)dz， K L ( q ∣ ∣ p ) = ∫ z ln ⁡ q ( z ) p ( z ∣ x , θ ) q ( z ) d z KL(q||p)=\int_z\ln \frac{q(z)}{p(z|x,\theta)}q(z)dz KL(q∣∣p)=∫z​lnp(z∣x,θ)q(z)​q(z)dz

        • 证明如下，通过将对数似然函数进行变换可以得到

          ln ⁡ p ( x ∣ θ ) = ln ⁡ p ( x , z ∣ θ ) − ln ⁡ p ( z ∣ x , θ ) = ln ⁡ p ( x , z ∣ θ ) q ( z ) − ln ⁡ p ( z ∣ x , θ ) q ( z ) \begin{aligned} \ln p(x|\theta) &= \ln p(x,z|\theta)-\ln p(z|x,\theta)\\ &= \ln \frac{p(x,z|\theta)}{q(z)}-\ln \frac{p(z|x,\theta)}{{q(z)}}\\ \end{aligned} lnp(x∣θ)​=lnp(x,z∣θ)−lnp(z∣x,θ)=lnq(z)p(x,z∣θ)​−lnq(z)p(z∣x,θ)​​对等式两边同时乘上 q ( z ) q(z) q(z)可得

          ln ⁡ p ( x ∣ θ ) q ( z ) = ln ⁡ p ( x , z ∣ θ ) q ( z ) q ( z ) − ln ⁡ p ( z ∣ x , θ ) q ( z ) q ( z ) \ln p(x|\theta)q(z) = \ln \frac{p(x,z|\theta)}{q(z)}q(z)-\ln \frac{p(z|x,\theta)}{{q(z)}}q(z) lnp(x∣θ)q(z)=lnq(z)p(x,z∣θ)​q(z)−lnq(z)p(z∣x,θ)​q(z)等式两边同时对 z z z求积分，由于 ln ⁡ p ( x ∣ θ ) \ln p(x|\theta) lnp(x∣θ)与 z z z无关，因此积分后仍得原式，所以有

          ln ⁡ p ( x ∣ θ ) = ∫ z ln ⁡ p ( x , z ∣ θ ) q ( z ) q ( z ) d z − ∫ z ln ⁡ p ( z ∣ x , θ ) q ( z ) q ( z ) d z = ∫ z ln ⁡ p ( x , z ∣ θ ) q ( z ) q ( z ) d z + ∫ z ln ⁡ q ( z ) p ( z ∣ x , θ ) q ( z ) d z \begin{aligned} \ln p(x|\theta) &= \int_z \ln \frac{p(x,z|\theta)}{q(z)}q(z)dz-\int_z\ln \frac{p(z|x,\theta)}{{q(z)}}q(z)dz\\ &= \int_z \ln \frac{p(x,z|\theta)}{q(z)}q(z)dz+\int_z\ln \frac{q(z)}{p(z|x,\theta)}q(z)dz\\ \end{aligned} lnp(x∣θ)​=∫z​lnq(z)p(x,z∣θ)​q(z)dz−∫z​lnq(z)p(z∣x,θ)​q(z)dz=∫z​lnq(z)p(x,z∣θ)​q(z)dz+∫z​lnp(z∣x,θ)q(z)​q(z)dz​令 L ( q ) = ∫ z ln ⁡ p ( x , z ∣ θ ) q ( z ) q ( z ) d z L(q)=\int_z \ln \frac{p(x,z|\theta)}{q(z)}q(z)dz L(q)=∫z​lnq(z)p(x,z∣θ)​q(z)dz， K L ( q ∣ ∣ p ) = ∫ z ln ⁡ q ( z ) p ( z ∣ x , θ ) q ( z ) d z KL(q||p)=\int_z\ln \frac{q(z)}{p(z|x,\theta)}q(z)dz KL(q∣∣p)=∫z​lnp(z∣x,θ)q(z)​q(z)dz，则关系式得证。

        • 观察我们所得到的关系式，假如我们假设近似分布 q ( z ) q(z) q(z)无限接近于 p ( z ∣ x , θ ) p(z|x,\theta) p(z∣x,θ)，那么KL散度便无限趋近于0，此时就有 ln ⁡ p ( x ∣ θ ) ≈ L ( q ) \ln p(x|\theta)\approx L(q) lnp(x∣θ)≈L(q)于是，我们就将最大化对数似然的问题就转化为找到一个q(z)能最大化 L ( q ) L(q) L(q)的问题