KL散度及其在统计推断中的应用

介绍

KL散度（Kullback Leibler Divergence）又称相对熵（Relative Entropy），在信息论中用于表示采用概率分布$q$的最优编码来传输真实概率分布为$p$的数据所需要的额外数据量。它的定义式为

$$D(p\vert q)=-\int p(x)\ln\frac{q(x)}{p(x)}dx.$$

由于按照$p$本身进行最优编码并传输所需的数据量最少，即熵（entropy），所以按照另一个概率分布$q$编码的传输一定需要更多的数据量。 结合KL散度的定义可知$D(p \vert\vert q)\ge 0$。KL散度的非负性也可直接由杰森不等式得出：

$$-\int p(x)\ln\frac{q(x)}{p(x)}dx\ge-\ln(\int p(x)\frac{q(x)}{p(x)}dx)=-\ln 1=0.$$

KL散度有时称为“KL距离”，这种叫法是不合适的。一种度量被称为“距离”需要满足以下条件：

1. 非负性：$d(x, y) \ge 0$
2. 自反性： 如果$d(x, y) = 0$，那么$y=x$;
3. 对称性：$d(x,y)=d(y,x)$;
4. 三角不等式：$d(x, y) + d(y, z) \le d(x,z)$

而KL散度只满足非负性和自反性，不满足对称性和三角不等式，因此KL散度不是一种距离。

KL散度原本是信息学中的概念，但它作为一种重要的度量两个概率分布间相差程度的量，在统计学和机器学习中也有广泛的应用。下面分别介绍如何利用KL散度得出EM算法、变分推断和期望传播算法。

EM算法

统计模型有两种变量：随机变量和模型参数$\theta$。其中随机变量包含可以观测到的可见变量$X$和观测不到的隐含变量$W$。 许多统计和机器学习的任务是从给定的数据集$X$中，推断出参数$\theta$的值或者分布。推断有着许多方法，其中 一种是将能够使可见变量的似然最大化的值作为参数，即

$$\theta^* = \arg\max_\theta p(X;\theta).$$

其中$p(X;\theta) = \int p(X,W;\theta)dW$. 至此，推断问题已经被转化为一个优化问题。

一般，求解优化问题常用的方法有：

1. 另耗散关于参数的导数等于$0$，直接解出参数;
2. 梯度下降法，求出导数表达式，逐步迭代。

第一种方法要求参数的最优解可以直接表达为一个解析式，即可以用一个左边是要求的参数、右边是已知量的等式表示。第二种方法要求耗散关于参数的导数可以直接写出解析式，即可以用一个左边是导数、右边是已知量的函数的等式表示。但是，大多数实际问题中这两种都无法满足，有的是等式左右两边同时包含待求解的参数，有的甚至根本写不出表达式。

在这些问题里，有一些是由于含有隐含变量导致的，加入隐含变量问题会变得简单。这样的问题可以用EM算法求解。

EM算法将目标函数，即似然对数进行分解。由概率的性质可知 $\ln p(X;\theta) = \ln p(X,W;\theta) - \ln p(W\vert X;\theta)$

两边对任意一个关于$W$的分布求积分并整理可得

$$\ln p(X;\theta) = \int \ln\frac{ p(X,W;\theta)}{q(W)} q(W)dW - \int \ln \frac{p(W\vert X;\theta)}{q(W)} q(W)dW.$$

注意到等式右边第二项是$q(\cdot)$到$p(\cdot\vert X;\theta)$的KL散度$D(q(\cdot)\vert\vert p(\cdot\vert X;\theta))$。由于KL散度非负，所以右边第一项是似然的下界，称之为ELBO(evidence lower bound)。

由于$\ln p(X;\theta)$中不包含$q$，因此无论我们如何选择$q$或者改变$q$的参数，只要$\theta$不变，$\ln p(X;\theta)$就不会变。因此，当我们固定住$\theta$，通过变化$q$将第二项KL散度最小化，第一项ELBO的值会增大。最小值在$q(W)=p(W\vert X;\theta)$时取到，此时，第二项KL散度为0，第一项ELBO等于$\ln p(X;\theta)$。这一将$q(W)$更新为$p(W\vert X;\theta)$的步骤，被称为E步骤。

在进行E步骤后，我们可以通过优化参数$\theta$将第一项ELBO最大化。ELBO中不包含对隐含变量的积分，根据假设，优化ELBO是简单的。 优化过程使得ELBO变大，参数$\theta$得到了更新变为$\theta’$。由于$q$此时仍然是旧参数下的后验分布$p(W\vert X;\theta)$，与此时的$p(W\vert X;\theta)$不同，所以第二项KL散度由0增大。可见，在优化ELBO的过程中，等式右边两项都增大，故等式左边$\ln p(X;\theta)$增大。这一优化ELBO更新$\theta$的步骤称为M步骤。

在M步骤中，第二项KL散度不为0，可以再进行一次E步骤。依此类推，不断地进行E步骤和M步骤的迭代，就可以不断增大目标函数。当经过某次M步骤后，第二项KL散度为0时，说明目标函数已经无法继续增大，此时的$\theta$就是最优参数，并且$q(W)$是隐含变量的后验分布。

EM算法的步骤：

1. 随机初始化$\theta$和$q(W)$
2. 迭代以下两个步骤直至收敛
   • E步骤：使$q(W)=p(W\vert X;\theta)$;
   • M步骤：优化ELBO项，更新$\theta$.

变分推断

变分推断(variational inference)和EM算法有许多类似，也有本质上的不同。相似点在于二者所解决的模型都隐含变量，二者都将似然分解为ELBO项和KL散度之和并利用KL散度的性质来求解；不同点在于，EM算法是求得的是极大似然解，得到的是参数的点估计，变分推断求得的参数的后验概率分布，且EM的解是精确的，不存在近似，而变分推断求得的是近似解。

在变分推断中，对数似然为

$$\ln(p(X))=\ln \int p(X, W)dW$$

与EM算法中不同的是，表达式中没有参数$\theta$。变分推断中，$\theta$被看成一种随机变量，包含在$W$中。由于$W$被积掉，似然是一个定值，我们的目标不再是最大化似然，而是根据贝叶斯公式求后验分布$p(W\vert X)$

$$p(W\vert X) = \frac{p(X,W)}{p(X)}$$

上式右边分母中往往涉及到无法写出表达式的积分，没有办法直接求出精确的后验分布。变分推断采用某种容易求解的分布$q(W)$来近似后验分布$p(W\vert X)$。两个分布直间的近似的程度自然而然地使用KL散度度量。我们把问题转化为

$$\min_q D(q(W) \vert\vert p(W \vert X))$$

注意到变分推断中使用的是$K(q \vert\vert p)$，原因在于对于选定$q$进行积分比对$p$进行积分简单。与EM算法中类似，上式可以表示为

$$\min_q D(q(W)\vert\vert p(W\vert X))=\ln p(X) - \int \ln\frac{p(X,W)}{q(W)}q(W)dW$$

上式中右边是似然对数减去ELBO，似然对数在这个问题中是一个定值，因此原问题等价于

$$\max_q \int \ln\frac{p(X,W)}{q(W)}q(W)dW.$$

变分通过选取特定形式的$q$简化上面的优化问题。其中有一类重要的近似叫做Mean Field。假设隐含变量集合$W$由$w_1,w_2,\cdots,w_m$构成，mean field设定近似分布满足以下形式

$$q(W)=\prod_j q(w_j)$$

即各个隐含变量彼此相互独立。对这种形式的变分分布，目标函数可以转化为几个更简单的子问题。 在每个子问题中，保持其他隐含变量的分布不变，只更新某一个隐含变量的分布。例如在优化$w_j$时，子优化问题为

$$\max_{q(w_j)} \int E_{i\neq j}[\ln p(X,W)]q(w_j)dw_j -\int q(w_j)\ln q(w_j) dw_j.$$

最大化该式，更新$w_j$的分布$q(w_j)$

$$q(w_j)=\frac{\exp\{E_{i\neq j}[\ln p(X,W)]\}}{\exp\{\int E_{i\neq j}[\ln p(X,W)]dw_j\}}$$

此时得到新的变分分布$q(W)$会使得目标式函数也变大。之后，再依次更新其他隐含变量的变分分布。如此迭代，直到收敛，目标不在变大。 最后，我们需要求的$p(W \vert X)$便可以由$q(W)$近似。

变分推断算法如下：

1. 随机初始化各个隐含变量的分布$q(w_j), j=1,2,\cdots,m$;
2. 迭代直至收敛
   • 对越每个隐含变量$w_j$，在其他变量的分布不变的情况下，优化其分布使得ELBO最大

期望传播

变分推断通过最小化$D(q(W)\vert\vert p(W \vert X))$寻找$p(W\vert X)$的近似分布$q(W)$。如果最小化的是$D(p(W \vert X)\vert\vert q(W) )$则得到另外一种近似推断的方法：期望传播算法。

在期望传播算法中，限制$q(W)$为指数族分布，使用另导数为0的方法最小化KL散度，可以得到 $E_q[s(W)]=E_p[s(W)]$

其中$s(W)$表示充分统计量。$E_q[s(W)]$ 可以通过参数表示，将使用$q$的参数表示的$E_q[s(W)]$与$E_p[s(W)]$进行匹配，我们可以直接得出近似分布$q$的参数。

在期望传播算法中，使用因子形式表示概率分布更加方便。设模型的联合分布可以表示为

$$p(X,W)=\prod_i f_i(W)$$

由贝叶斯公式可得出后验概率可表示为

$$p(W\vert\vert X) = \frac{1}{p(X)}\prod_i f_i(W)$$

其中$p(X)=\int \prod_i f_i(W) dW$是一个常量。 令

$$q(W)=\frac{1}{Z}\prod_i \hat f _i (W)$$

其中$Z=\int \prod_i \hat f _i (W)dW$。 KL散度则可表示为

$$D(p(W \vert X)\vert\vert q(W) )=D(\frac{1}{p(X)}\prod_i f_i(W)\vert\vert \frac{1}{Z}\prod_i \hat f _i (W))$$

该式涉及到对$p(W \vert X)$的积分较难。因此，期望传播采取在其他因子不变的情况下，每次只更新一个因子$\hat f _j (W)$策略。将$q(W)$更新为最小化

$$D(\frac{1}{Z_j}f_j(W)q^{-j}(W)\vert\vert q(W))$$

的形式，再得到

$$\hat f_j=K\frac{q(W)}{q^{-j}(W)}$$

其中

$$q^{-j}(W)=\prod_{i!=j} \hat f _i (W)$$ $$Z_j = \int \frac{1}{Z_j}f_j(W)q^{-j}(W) dW$$ $$K = \int \hat f_j(W)q^{-j}(W) dW$$

在更新一个因子后，再用同样的方法更新其他因子，不断迭代，使得近似分布$q(W)$逐渐接近$p(W\vert X)$。但是，期望传播算法不能保证算法会收敛。

期望传播算法：

1. 随机初始化因子$\hat f_i (W), i=1,2,\dots$
2. 循环更新，直至收敛
   1. 计算$q^{-j}(W)=q(W)/\hat f_i(W)$和$Z_j$
   2. 更新$q(W)$最小化$D(\frac{1}{Z_j}f_j(W)q^{-j}(W)\vert\vert q(W))$
   3. 计算$\hat f_j(W)$

总结

KL散度可以度量分布之间的差异，在统计推断中具有非常重要的地位。EM算法、变分推断和期望传播算法都利用了KL散度的性质。 EM算法在E步骤中利用KL散度寻找出隐含变量用于迭代的中间值，在M步骤中更新参数，通过E步骤M步骤的反复迭代，达到最大化似然的目的。 变分推断和期望传播算法分别使用两种形式的KL散度来度量近似分布与真实后验分布的差异，并通过反复地更新部分隐含变量的近似分布来不断地减小差异，最后达到真实的后验分布被很好地近似的目的。