KL散度（Kullback-Leibler Divergence）

November 17, 2015 zr9558 4 Comments

在信息论和概率论里面，Kullback-Leibler 散度（简称KL散度，KL divergence）是两个概率分布 $P$ 和 $Q$ 的一个非对称的度量公式。这个概念是由 Solomon Kullback 和 Richard Leibler 在 1951 年引入的。从概率分布 $Q$ 到概率分布 $P$ 的 KL 散度用 $D_{KL}(P||Q)$ 来表示。尽管从直觉上看 KL 散度是一个度量或者是一个距离，但是它却不满足度量或者距离的定义。例如，从 $Q$ 到 $P$ 的 KL 散度就不一定等于从 $P$ 到 $Q$ 的 KL 散度。

KL 散度的数学定义：

对于离散空间的两个概率分布 $P$ 和 $Q$ 而言，从 $Q$ 到 $P$ 的KL散度被定义为

$D_{KL}(P||Q)=\sum_{i}P(i)\log_{2}(P(i)/Q(i)).$

换句话说，它是两个概率分布 $P$ 和 $Q$ 的对数差的期望，这里的期望是以概率 $P$ 来描述的。KL散度有定义当且 $Q(i)=0 \implies P(i)=0$ 对于所有的 $i$ 都成立。如果 $P(i)=0,$ 那么可以假设KL散度的第 $i$ 项是零，因为 $\lim_{x\rightarrow 0^{+}}x\log_{2}x=0.$

对于连续空间 $X$ 的两个概率分布 $P$ 和 $Q$ 而言，从 $Q$ 到 $P$ 的 KL 散度被定义为：

$D_{KL}(P||Q)=\int_{X}p(x)\log_{2}(p(x)/q(x))dx,$

这里的 $p$ 和 $q$ 是概率分布 $P$ 和 $Q$ 的概率密度。

KL 散度的基本性质：

（1）KL 散度总是非负的，并且只有 $P(x)=Q(x)$ 几乎处处成立的时候，才会有

$D_{KL}(P||Q)=0.$

证明：利用Jensen’s Inequality。

$D_{KL}(P||Q)=-E_{P}(\log_{2}(q(x)/p(x)))$

$\geq -log_{2}(E_{p}(q(x)/p(x)))=-log_{2}(\int_{X}q(x)dx)=0.$

（2）如果 $P_{1}, P_{2}$ 是独立分布，并且联合分布是 $P(x,y)=P_{1}(x)P_{2}(y),$ $Q_{1},Q_{2}$ 是独立分布并且联合分布是 $Q(x,y)=Q_{1}(x)Q_{2}(y),$ 那么

$D_{KL}(P||Q)=D_{KL}(P_{1}||Q_{1})$ + $D_{KL}(P_{2}||Q_{2}).$

（3）如果定义分布 $P$ 和 $Q$ 的交叉墒是

$H(P,Q)=-\int_{X}p(x)\log_{2}q(x)dx,$

分布 $P$ 的熵是

$H(P)=-\int_{X}p(x)\log_{2}p(x)dx,$

那么 $D_{KL}(P||Q)=H(P,Q)-H(P).$

（4）KL 散度是两个概率分布 $P$ 和 $Q$ 差别的非对称性的度量。 KL 散度是用来度量使用基于 $Q$ 的编码来编码来自 $P$ 的样本平均所需的额外的位元数。典型情况下， $P$ 表示数据的真实分布， $Q$ 表示数据的理论分布，模型分布，或 $P$ 的近似分布。

（5）从KL散度的定义可以得出

$D_{KL}(P||Q)\neq D_{KL}(Q||P),$

所以 KL 散度不满足距离的对称性。当然，如果需要把它弄成对称的，可以定义

$DS_{KL}(P,Q)=(D_{KL}(P||Q)$ + $D_{KL}(Q||P))/2.$

简单例子：

比如有四个类别，一个方法 P 得到四个类别的概率分别是0.1，0.2，0.3，0.4。另一种方法 Q（或者说是事实情况）是得到四个类别的概率分别是0.4，0.3，0.2，0.1,那么这两个分布的 KL 散度就是

$D_{KL}(P||Q)$

$=0.1*\log_{2}(0.1/0.4)$ + $0.2*\log_{2}(0.2/0.3)$ + $0.3*\log_{2}(0.3/0.2)$ + $0.4*\log_{2}(0.4/0.1).$

案例分析：

在实际的工作中，我们通常会有某个网页或者app被用户点击或者播放的数据，同时，我们会拥有用户画像（personas），此刻我们关心的问题就是如何计算网页里面的某个新闻或者app里面的某个专辑受到不同维度的用户画像的喜好程度。比如，如何判断该新闻是受到各个年龄层的用户的喜爱还是只是受到某个年龄层的用户的喜爱？如何判断某个电台节目是受到大众的喜爱还是更加受到男性或者女性的喜爱？此时，怎么计算物品被用户的喜欢程度就成为了一个重要的关键。

通常的方案就是，比方说：某个电台专辑被66.7%的男性用户播放过，被33.3%的女性用户播放过，那么该物品是不是真的就是更加受到男性用户的青睐呢？答案是否定的。如果使用这款app的用户的男女比例恰好是1：1，那么根据以上数据，该电台专辑显然更加受到男性用户的喜爱。但是，实际的情况，使用这款app的用户的男女比例不完全是1：1。如果男性用户：女性用户=2：1的话，如果某个电台专辑被66.7%的男性用户播放过，被33.3%的女性用户播放过，那么说明该专辑深受男女喜欢，两者对该专辑的喜好程度是一样的。因为基础的男女比例是2：1，该专辑被男女播放的比例是2：1，所以，该专辑对男女的喜爱程度恰好是1：1。

那么如何计算该专辑的喜好程度呢？首先我们会使用KL散度来描述这件事情。

数据挖掘与机器学习

机器学习的基本模型—入门知识

November 13, 2015 zr9558 1 Comment

机器学习的各种算法在于如何使用特定函数与已知的数据集相匹配，从而达到训练和测试的目的。本篇文章对一些近似的模型做一些相应的介绍。

线性模型

一维输入变量

假设学习对象 $f$ 函数的输入是一组实数，那么对该函数进行近似的时候，最简单的方案就是 $f_{\theta}(x)=\theta\cdot x$ 。在这里， $\theta$ 是这个函数的斜率，也就是这个函数 $f_{\theta}(x)$ 的参数。机器学习就是通过对这个参数的学习，完成函数的近似计算。这个模型对于 $\theta$ 而言是一个线性函数，操作起来十分方便，但是对于实际的情况来说，该模型过于简单，没有太大的使用价值。由于上面这个模型过于简单，那么在实际应用中，会对上述的模型进行必要的扩展，使得函数 $f_{\theta}(x)$ 变成参数的线性模型，这样这个模型就可以用来表示非线性的输入和输出了。可以把 $\theta\cdot x$ 扩展成如下形式：

$f_{\theta}(x)=\sum_{j=1}^{b}\theta_{j}\cdot\phi_{j}(x).$

在这个式子中， $\phi_{j}(x)$ 是基函数向量 $\phi(x)=(\phi_{1}(x),\cdot\cdot\cdot,\phi_{b}(x))^{T}$ 的第 $j$ 个分量， $\theta_{j}$ 是 $\theta=(\theta_{1},\cdot\cdot\cdot,\theta_{b}))^{T}$ 的第 $j$ 个分量， $b$ 是基函数 $\phi(x)$ 的维数。根据上面 $f_{\theta}(x)$ 的定义，可以得到该函数是参数向量 $\theta$ 的线性函数。也就是说对于 $b$ 维参数 $\theta,\theta^{'}$ 和 $\alpha\in \mathbb{R}$ ，满足

$f_{\theta+\theta^{'}}(x)=f_{\theta}(x)+f_{\theta^{'}}(x),$

$f_{\alpha \theta}(x)=\alpha f_{\theta}(x).$

那么这个时候如何选择基函数 $\phi(x)$ 就成为了一个关键所在。

数学分析里面有一个经典定理叫做Weierstrass定理，陈述如下：

Weierstrass第一逼近定理：假设是闭区间上的连续函数，对于任意的，则存在多项式使得对于所有的，有。

根据Weierstrass第一逼近定理，对于任何一个闭区间上面的连续函数，都可以用多项式去逼近。所以联系到机器学习，就可以把基函数 $\phi(x)$ 的分量设置为多项式，换句话说

$\phi_{j}(x)=x^{j-1}$

$\phi(x)=(1,x,x^{2},\cdot\cdot\cdot, x^{b-1})^{T}.$

那么上述的 $\theta$ 的线性函数却是关于自变量 $x$ 的非线性函数，而且 $f_{\theta}(x)=\sum_{j=1}^{b}\theta_{j}\cdot x^{j-1}$ 可以逼近关于 $x$ 的闭区间上任何一个连续函数。

与Weierstrass逼近定理类似，用Fourier级数也可以逼近Lipchitz连续函数。所以也可以选择基函数

$\phi_{0}(x)=1,\phi_{2j-1}(x)=\sin(jx),\phi_{2j}(x)=\cos(jx),$ 其中 $j\geq 1.$

简单来说就是令 $b=2m+1,$ $\phi(x)=(1,\sin(x),\cos(x),\cdot\cdot\cdot,\sin(mx),\cos(mx))^{T}.$ 根据这些模型， $f_{\theta}(x)$ 就可以表示复杂的非线性模型了。

高维输入变量

对于高维的变量 $\textbf{x}=(x^{(1)},\cdot\cdot\cdot,x^{(d)}),$ 函数依旧可以扩展成如下模式：

$f_{\theta}(\textbf{x})=\sum_{j=1}^{b}\theta_{j}\cdot\phi_{j}(\textbf{x})={\theta}^{T}\phi(\textbf{x}).$

对于多维的输入向量 $\textbf{x}$ ，可以用一维的基函数来构造多维基函数的乘法模型和加法模型。

乘法模型指的是把一维的基函数作为因子，通过使其相乘而获得多维基函数的方法。表达式如下：

$f_{\theta}(x)=\sum_{j_{1}=1}^{b^{'}}\cdot\cdot\cdot\sum_{j_{d}=1}^{b^{'}}\theta_{j_{1},\cdot\cdot\cdot,j_{d}}\phi_{j_{1}}(x^{(1)})\cdot\cdot\cdot \phi_{j_{d}}(x^{(d)}).$

在上面的式子中， $b^{'}$ 是各个维数的参数个数。对于这个模型而言，它的表现力十分丰富，但是不足之处在于所有的参数个数是 $(b^{'})^{d},$ 是一个非常巨大的数字，导致的维数灾难，所以在实际运用中，不主张用这个模型。

加法模型指的是把一维的基函数作为因子，通过相加而活得高维基函数的方法。表达式如下：

$f_{\theta}(x)=\sum_{k=1}^{d}\sum_{j=1}^{b^{'}}\theta_{k,j}\phi_{j}(x^{(k)}).$

加法模型中所有参数的个数是 $b^{'}d,$ 它是一个关于维数 $d$ 的线性函数，复杂度没有乘法模型大，但是表现力和乘法模型比起来则差很多。

核模型

在线性模型中，多项式或三角函数等基函数的选择都是与训练样本无关的，核模型则与之相反，会在进行基函数构造的时候使用输入样本 $\{\mathbf{x}_{i}\}_{i=1}^{n}.$ 在核模型中，会使用核函数

$K(\mathbf{x},\mathbf{c})=\exp(-||\mathbf{x}-\mathbf{c}||_{2}^{2}/(2h^{2})),$

其中 $||\cdot||_{2}$ 指的是欧几里德2-范数， $h$ 表示核函数的带宽， $\mathbf{c}$ 指的是核函数的均值。从核函数的定义可以可以延伸出模型

$f_{\theta}(\mathbf{x})=\sum_{j=1}^{n}\theta_{j}\cdot K(\mathbf{x},\mathbf{x}_{j}).$

在这个模型中，关于 $\theta$ 而言仍然满足线性关系。换句话说，对于 $\theta,\theta^{'}\in\mathbb{R}^{n},$ 有 $f_{\theta+\theta^{'}}(x)=f_{\theta}(x)+f_{\theta^{'}}(x)$ 和 $f_{\alpha\theta}(x)=\alpha f_{\theta}(x).$ 对于核函数来说，无论输入的是一维变量还是高维变量，核函数都可以容易的进行扩展。

层级模型

对参数来说是非线性的模型，都称为非线性模型。下面要介绍的就是非线性模型中的层级模型，它在很多领域都有应用。假设模型是

$f_{\theta}(\mathbf{x})=\sum_{j=1}^{b}\alpha_{j}\cdot\phi(\mathbf{x};\mathbf{\beta}_{j}).$

上式中， $\phi(\mathbf{x};\mathbf{\beta})$ 是关于参数向量 $\mathbf{\beta}$ 的基函数，层级模型是基于参数向量 $\mathbf{\alpha}=(\alpha_{1},\cdot\cdot\cdot,\alpha_{b})^{T}$ 的线性形式。同时也包含参数向量 $\{\beta_{j}\}_{j=1}^{b},$ 所以层级模型是基于参数向量 $\mathbf{\theta}=(\mathbf{\alpha}^{T},\mathbf{\beta}_{1}^{T},\cdot\cdot\cdot,\mathbf{\beta}_{b}^{T})^{T}$ 的非线性形式。基函数通常采用S型函数