什么是熵(entropy)?

信息量的度量——熵(entropy)
熵的概念最早起源于物理学,用于度量一个热力学系统的无序程度。在信息论里面,熵是对不确定性的测量。
有一种概念对物理和化学有极其重要的作用,它帮助我们解释物理现象的发生而不是通过其他方式。冰为什么融化?岩浆为什么冷却?奶油为什么会融入在咖啡中?这个概念就是熵。

我们经常说的“信息量太大了”,其中的”信息量“到底如何度量?
Claude Elwood Shannon 借鉴了热力学的概念,把信息中排除了冗余后的平均信息量称为“信息熵”。
这个概念现在看着很简单易懂,但是开创性地提出这样的概念不是容易的事情。

1 Entropy 熵

熵(entropy)可以度量随机变量的不确定性,设X是一个取有限值得离散随机变量,其概率分布为

\(P(X=x_i)=p_i, \quad i=1,2,\cdots,n\)

则随机变量X的熵定义为

\(H(X)=-\sum\limits_{i=1}^{n}{p_i}\log{p_i}\)

其中,如果对数以2为底,则熵的单位可以称作bit,由于熵只与X的分布有关,与X的具体取值无关,因此也可以表示为

\(H(p)=-\sum\limits_{i=1}^{n}{p_i}\log{p_i}\)

2 Information gain 信息增益

  • Conditional entropy 条件熵

设有随机变量(X,Y),其联合概率分布为

\(P(X=x_i, Y=y_j)=p_{ij}, \quad i=1,2,\cdots,n ; \quad j=1,2,\cdots,m\)

条件熵H(Y|X)可以表示在随机变量X已知的情况下随机变量Y的不确定性. 随机变量X给定的条件下随机变量Y的条件熵(conditional entropy)H(Y|X),定义为X给定条件下Y的条件概率分布的熵对X的数学期望

\(H(Y|X)=\sum\limits_{i=1}^{n}p_iH(Y|X=x_i)\)

其中, \(p_i=P(X=x_i),\quad i=1,2,\cdots,n.\)

当熵和条件熵忠的概率由数据估计(特别是极大似然估计)得到时,所对应的熵与条件熵分别称为经验熵(empirical entropy)和经验条件熵(empirical conditional entropy). 此时,如果有0概率,令0log0=00log⁡0=0.

  • Information gain 信息增益

信息增益(information gain)表示得知特征X的信息而使得得知类Y的信息的不确定性减少的程度.

特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差,即

\(g(D,A)=H(D)-H(D|A)\)

熵H(Y)与条件熵H(Y|X)之差也常被称为互信息(mutual information). 决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

3 Information gain ratio 信息增益比

在实际训练模型时,以信息增益作为划分训练数据集的特征,会偏向于选择取值较多的特征. 因此,也常常使用信息增益比来作为准则.

特征A对训练数据集D的信息增益比gR(D,A)定义为其信息增益g(D,A)与训练数据集D关于特征A的值的熵HA(D)之比,即

\(g_R(D,A)=\frac{g(D,A)}{H_A(D)}\)

其中,\(H_A(D)=-\sum\limits_{i=1}^{n}{\frac{|D_i|}{|D|}\log_2{\frac{|D_i|}{|D|}}}\),n是特征A取值的个数.

1.1 熵的引入
    事实上,熵的英文原文为entropy,最初由德国物理学家鲁道夫·克劳修斯提出,其表达式为:

    它表示一个系系统在不受外部干扰时,其内部最稳定的状态。后来一中国学者翻译entropy时,考虑到entropy是能量Q跟温度T的商,且跟火有关,便把entropy形象的翻译成“熵”。

    我们知道,任何粒子的常态都是随机运动,也就是”无序运动”,如果让粒子呈现”有序化”,必须耗费能量。所以,温度(热能)可以被看作”有序化”的一种度量,而”熵”可以看作是”无序化”的度量。

    如果没有外部能量输入,封闭系统趋向越来越混乱(熵越来越大)。比如,如果房间无人打扫,不可能越来越干净(有序化),只可能越来越乱(无序化)。而要让一个系统变得更有序,必须有外部能量的输入。

    1948年,香农Claude E. Shannon引入信息(熵),将其定义为离散随机事件的出现概率。一个系统越是有序,信息熵就越低;反之,一个系统越是混乱,信息熵就越高。所以说,信息熵可以被认为是系统有序化程度的一个度量。
    若无特别指出,下文中所有提到的熵均为信息熵。

1.2 熵的定义
    下面分别给出熵、联合熵、条件熵、相对熵、互信息的定义。
    熵:如果一个随机变量X的可能取值为X = {x1, x2,…, xk},其概率分布为P(X = xi) = pi(i = 1,2, …, n),则随机变量X的熵定义为:

    把最前面的负号放到最后,便成了:

    上面两个熵的公式,无论用哪个都行,而且两者等价,一个意思(这两个公式在下文中都会用到)。
    联合熵:两个随机变量X,Y的联合分布,可以形成联合熵Joint Entropy,用H(X,Y)表示。
    条件熵:在随机变量X发生的前提下,随机变量Y发生所新带来的熵定义为Y的条件熵,用H(Y|X)表示,用来衡量在已知随机变量X的条件下随机变量Y的不确定性。

    且有此式子成立:H(Y|X) = H(X,Y) – H(X),整个式子表示(X,Y)发生所包含的熵减去X单独发生包含的熵。至于怎么得来的请看推导:

   简单解释下上面的推导过程。整个式子共6行,其中

第二行推到第三行的依据是边缘分布p(x)等于联合分布p(x,y)的和;
第三行推到第四行的依据是把公因子logp(x)乘进去,然后把x,y写在一起;
第四行推到第五行的依据是:因为两个sigma都有p(x,y),故提取公因子p(x,y)放到外边,然后把里边的-(log p(x,y) – log p(x))写成- log (p(x,y)/p(x) ) ;
第五行推到第六行的依据是:条件概率的定义p(x,y) = p(x) * p(y|x),故p(x,y) / p(x) =  p(y|x)。
    相对熵:又称互熵,交叉熵,鉴别信息,Kullback熵,Kullback-Leible散度等。设p(x)、q(x)是X中取值的两个概率分布,则p对q的相对熵是:

    在一定程度上,相对熵可以度量两个随机变量的“距离”,且有D(p||q) ≠D(q||p)。另外,值得一提的是,D(p||q)是必然大于等于0的。

    互信息:两个随机变量X,Y的互信息定义为X,Y的联合分布和各自独立分布乘积的相对熵,用I(X,Y)表示:

    且有I(X,Y)=D(P(X,Y) || P(X)P(Y))。下面,咱们来计算下H(Y)-I(X,Y)的结果,如下:

    通过上面的计算过程,我们发现竟然有H(Y)-I(X,Y) = H(Y|X)。故通过条件熵的定义,有:H(Y|X) = H(X,Y) – H(X),而根据互信息定义展开得到H(Y|X) = H(Y) – I(X,Y),把前者跟后者结合起来,便有I(X,Y)= H(X) + H(Y) – H(X,Y),此结论被多数文献作为互信息的定义。

发表评论

电子邮件地址不会被公开。 必填项已用*标注