0%

信息熵总结

前言

学习决策树时会接触到一些信息熵,条件熵和信息增益的知识,此外还有互信息,相对熵,交叉熵和互信息,KL散度等等乱七八糟的知识和名字,我本人已经记得大脑混乱了,还没有全部记住,所以在这里记录一下.

信息熵

信息的度量,信息的不确定程度,是乱七八糟熵的基础。吴军大大的数学之美中用了猜球队冠军的方式引出了信息熵的概念。我觉得这种方法印象很深刻,所以在这里提出一下。如果有32支球队,使用二分查找法去猜哪支球队是冠军,如:冠军在1-16号球队内。这样一共需要猜5次就可以找到结果,也就是$log32=5$。但是某些球队的获胜率大一些,所以它的准确信息量的表示应该如下:

$H(X) = - \sum_{x\in X}P(x)logP(x)$

香农称它为信息熵,表示信息的不确定程度。不确定性越大,信息熵也就越大。图1中的$P(x)$表示随机变量$x$的概率,信息熵$H(X)$的取值范围:$0<=H(X)<=logn$,其中$n$是随机变量$X$取值的种类数。

条件熵

有两个随机变量$X$和$Y$,在已知$Y$的情况下,求$X$的信息熵称之为条件熵:

$H(X|Y) = -\sum_{x\in X,y\in Y}P(x,y)logP(x|y)$

其中$P(x|y)$是已知$y$求$x$的条件概率,$P(x,y)$是联合概率。

联合熵

联合熵可以表示为两个事件$X$、$Y$的熵的并集:

$H(X,Y) = -\sum_{i=1}^n \sum_{j=1}^n P(x_i,y_i)logP(x_i,y_i)$
$= \sum_{i=1}^n \sum_{j=1}^n P(x_i,y_i)log{1\over P(x_i,y_i )}$

它的取值范围是:$max(H(x),H(y)) <= H(x,y) <= H(x)+H(y)$

信息增益

表示在确定某条件Y后,随机变量$X$的信息不确定性减少的程度,也称为互信息($Mutual Information$).

$I(X;Y) = H(X) - H(X|Y)$

它的取值是$0$到$min(H(X),H(Y))$之间的数值,取值为$0$时表示两个事件$X$和$Y$完全不相关。在决策树算法中$ID3$算法就是使用信息增益来划分特征的。在某个特征条件下,求数据的信息增益,信息增益大的特征说明对数据划分帮助很大。优先选择该特征进行决策树的划分,这就是$ID3$算法。

信息增益比(率)

信息增益比是信息增益的进化版,用于解决信息增益对属性选择取值较多的问题。信息增益率为信息增益与该特征的信息熵之比。在决策树中算法中,$C4.5$算法就是使用信息增益比来划分特征。公式如下:

$g_R(D,A) = {g(D,A)\over H(D)} $

信息熵,条件熵和互信息的关系:

基尼系数(Gini)

在决策树的$CART$(分类回归树)中有两类树,一是回归树,划分特征使用的是平方误差最小化的方法。二是分类树,采用的就是$Gini$系数最小化进行划分数据集。

$Gini(P) = \sum_{k=1}^K p_k(1-p_k) = 1 - \sum_{k=1}^K p_k^2$

其中$k$为$label$的种类数。基尼指数越大,信息的不确定性越大,这与信息熵相同。($CART$树是如何使用$Gini$指数的这里就不详细介绍了,以后会在决策树中详细介绍的。)

相对熵(KL散度)

用来描述两个概率分布$P$、$Q$之间的差异,数学之美中介绍是用来衡量两个取值为正数函数的相似性:

$KL(P||Q)= \sum_{i=1}^n P(x_i)log{P(x_i)\over Q(x_i)}$

如果两个函数(分布)完全相同,那么它们的相对熵为0。同理如果相对熵越大,说明它们之间的差异越大,反之相对熵越小,说明它们之间的差异越小。需要注意的是相对熵不是对称的,也就是:

$KL(P||Q)\neq KL(Q||P)$

但是这样计算很不方便,所以香农和杰森(不是郭达斯坦森)提出了一个新的对称的相对熵公式:

$JS(P||Q) = {1\over 2}[KL(P||Q) + KL(Q||P)]$

上面的相对熵公式可以用于计算两个文本的相似度。吴军大大在《数学之美》中介绍,$Google$的问答系统就是用这个公式计算答案相似性的(现在还是不是就不清楚了)。

交叉熵(Cross-Entropy)

我们知道通常深度学习模型最后一般都会使用交叉熵作为模型的损失函数。那是为什么呢?首先我们先将相对熵$KL$公式进行变换($log$中除法可以拆分为两个$log$相减):

$D_{KL}(P||Q) = \sum_{i=1}^n P(x_i)log(P(x_i)) - \sum_{i=1}^n P(x_i)log(Q(x_i))$
$= -H(P(x)) + [-\sum_{i=1}^n P(x_i)log(Q(x_i))]$

其中前一部分的$-H(P(x))$是$P$的信息熵,后一部分就是我们所说的交叉熵。

$H(P,Q) = -\sum_{i=1}^n P(x_i)log(Q(x_i))$

损失函数是计算模型预测值和数据真实值之间的相关性,所以可以使用相对熵($KL$散度)计算。根据上述公式可以看出:$-H(P(x))$是不变的,所以我们可以通过计算后一部分的交叉熵来求得$Loss$。所以通常会使用交叉熵来作为$Loss$函数。同理交叉熵越小,预测值和真实值之间相似度越高,模型越好。

LR的损失函数就是交叉熵。

困惑度(Perplexity,PPL)

在$NLP$中,通常使用困惑度作为衡量语言模型好坏的指标。

$PP(S) = P(w_1w_2\dots w_n)^{-{1\over N}}$
$= \sqrt[N]{1\over{P(w_1w_2\dots w_n)}}$
$= \sqrt[N]{\prod_{i=1}^n {1\over P(w_i|w_1w_2\dots w_{i-1})}}$

其中$S$为句子,$N$是句子中单词的个数,$P(w_i)$代表第$i$个单词的概率。所以$PPL$越小$P(w_i)$的概率越高,则这句话$S$属于自然语言的概率也就越高。