信息量

信息量 是对 事件包含的信息 的度量。对于事件 $x_i$,其信息量 $h(x)$ 应该是多少?我们应该解决以下几个关键问题。

  1. 事件的信息量由什么决定?

    时间的信息量由该事件发生的概率决定。越小概率的事情发生了,则信息量越大(例如川建国当选总统);而越大概率的事情发生了,则信息量越小(例如太阳从东边升起)。

  2. 怎么表示信息量?

    随概率增大的减小的函数形式很多,但我们应该考虑到事件信息量的一个规律:对于独立事件 $x_1$ 与 $x_2$,这两个事件同时发生的信息量应该等于 $x_1$ 的信息量与 $x_2$ 的信息量的和,即 $h(x_1, x_2) = h(x_1) + h(x_2)$,因此很自然地引入对数 log 来表示事件信息量。

由此,我们可以定义事件 $x$ 的信息量 $h(x)$ 为

$$ h(x) = - \log_2 p(x) $$

此处的负号是为了保证信息量为正,底数为 2 是遵循信息论传统,实际上可以用别的底数,下面省略底数 2。

信息熵

信息量(Information Entropy)衡量的是具体事件 $x$ 所包含的信息,而 信息熵 则衡量了所有 可能的事件的信息量的期望

假设随机事件 $x_i$ 发生的概率为 $p(x_i)$,那么信息熵 $H(X)$ 为: $$ H(X) = -\sum _{i=1}^n p(x_i) \log p(x_i) $$

条件熵

所谓 条件熵(Conditional Entropy)指的是基于条件 $X$ 的 $Y$ 的信息熵,即假设已知条件 $X$ 的概率分布,求此情况下 $Y$ 的信息熵。信息熵的表示为 $H(Y|X)$,计算如下: $$ \begin{aligned} H(Y|X) &= \sum_x p(x) H(Y|X=x) \\ &= - \sum_x p(x) \sum_y p(y|x) \log p(y|x) \\ &= - \sum_x \sum_y p(x, y) \log p(y|x) \end{aligned} $$

举个例子,假设 $X$ 包括 2 种事件 $x_1$、$x_2$,$Y$ 包括 2 种事件 $y_1$、$y_2$,且有

$$ \begin{aligned} p(y_1) &= 1 / 2 \\ p(y_2) &= 1 / 2 \\ p(x_1) &= 1 / 3 \\ p(y_1 | x_1) &= 1 / 4 \\ p(y_2 | x_1) &= 3 / 4 \\ p(x_2) &= 2 / 3 \\ p(y_1 | x_2) &= 3 / 8 \\ p(y_2 | x_2) &= 5 / 8 \\ \end{aligned} $$

那么 $Y$ 的信息熵 $H(Y)$ 为:

$$ H(Y) = - \frac{1}{2} \log \frac{1}{2} - \frac{1}{2} \log \frac{1}{2} $$

在条件 $X$ 下的 $Y$ 条件熵 $H(Y|X)$ 为:

$$ H(Y|X) = \frac{1}{3} [- \frac{1}{4}\log\frac{1}{4} - \frac{3}{4}\log\frac{3}{4}] + \frac{2}{3} [- \frac{3}{8}\log\frac{3}{8} - \frac{5}{8}\log\frac{5}{8}] $$

信息增益

信息增益

信息增益(Information Gain)即在新的一个条件下,信息量(复杂度)减少的量。

对于事件分布 $Y$,其信息熵为 $H(X)$,若已知另一事件分布 $X$,则条件 $X$ 下的 $Y$ 条件熵为 $H(Y|X)$,那么 $X$ 为 $Y$ 所带来的的信息增益为:

$$ IG(Y,X) = H(Y) - H(Y|X) $$

信息增益有什么用呢?举个现实的例子,在《非诚勿扰》中,假设某女嘉宾对某男嘉宾的牵手概率为 50%(事件 $Y$ 分布),随后可以问男嘉宾以下两个问题中的一个:

  1. 如果问是否有房(事件 $X1$),是与否的概率分别为 10%、90%(事件 $X1$ 分布),若得知有房则牵手概率上升为 70%,没房则下降为 40%。
  2. 如果问是否经常出差(事件 $X2$),是与否的概率分别为 30%、70%(事件 $X2$ 分布),若得知经常出差则牵手概率下降为 40%,否则上升为 60%。

那么,女嘉宾应该问什么问题更好?

如果问问题一,那么信息增益为:

$$ \begin{aligned} IG(Y,X1) &= H(Y) - H(Y|X1) \\ &= H(Y) - \frac{1}{10} [- \frac{7}{10}\log\frac{7}{10} - \frac{3}{10}\log\frac{3}{10}] + \frac{9}{10} [- \frac{4}{10}\log\frac{4}{10} - \frac{6}{10}\log\frac{6}{10}] \\ &\approx H(Y) - 0.961985 \end{aligned} $$

如果问问题二,那么信息增益为:

$$ \begin{aligned} IG(Y,X2) &= H(Y) - H(Y|X2) \\ &= H(Y) - \frac{3}{10} [- \frac{4}{10}\log\frac{4}{10} - \frac{6}{10}\log\frac{6}{10}] + \frac{7}{10} [- \frac{6}{10}\log\frac{6}{10} - \frac{4}{10}\log\frac{4}{10}] \\ &\approx H(Y) - 0.970951 \end{aligned} $$

因为信息增益 $IG(Y,X1) > IG(Y,X2)$,第一个问题的信息增益更大,所以应该问第一个问题。

注意:信息增益 被用作决策树 ID3 算法选择分裂属性的依据(贪心)。

互信息

首先,互信息(Mutual Information)的计算方式跟 信息增益 一样,它衡量的是联合分布 $p(X,Y)$ 和分解的边缘分布的乘积 $p(X)p(Y)$ 的相似程度,并且是 对称 的。

很多时候我们不专门区分它们的区别(例如在决策树选择特征时),如果硬要说他们之间的区别的话,在说到 互信息 的时候,两个随机变量地位相同(一个系统内的两个子系统);而提到 信息增益 的时候,是把一个变量看成减小另一个变量不确定度的手段(一个系统的两个状态)。

可以参考 知乎:信息增益和互信息有什么联系和区别?

信息增益率

信息增益有个很大的缺点,就是倾向于 可取值的数目较多的属性。举个极端的例子,如果把样本的唯一编号作为事件 $X$,那么该特征一定是使得信息增益 $IG(Y, X) = H(Y) - H(Y|X)$ 最大的选择,经此一役所有样本的 $y$ 都确定了。

因此,信息增益率(Information Gain Ratio)被提出来,其与信息增益相比,在于加多了一个分母 $IV(X)$(IV,Instrisic Information,属性的内在信息)。IV 表示了属性自身的「不确定性」,如果其不确定性非常大,那么倾向于不取该属性。其计算方式为 $$ IV(X) = -\sum_x p(x) \log (p(x)) $$ 举例来说,如果属性 $X$ 的可能性有 $p(x_1)=0.2$、$p(x_2)=0.8$,那么其 IV 为 $-(0.2 \log 0.2 + 0.8 \log 0.8)$。

而信息增益率则为: $$ \begin{aligned} IGR(Y, X) &= \frac{IG(Y, X)}{IV(X)} \\ &= \frac{H(X) - H(Y|X)}{IV(X)} \end{aligned} $$

注意:信息增益率 被用作决策树 C4.5 算法选择分裂属性的依据。具体来说,C4.5 算法从候选的属性中找出 信息增益 高于平均水平的属性(先保证 该特征具有较高的信息增益),再从中选择 信息增益率 最高的(再保证 不会出现选择了编号特征这种极端的情况)。

补充:ID3、C4.5、CART 简单区别

  • ID3:选择 信息收益 最大的特征。
  • C4.5:选择 信息增益 高于平均水平的属性,再选择 信息增益率 最高的特征
  • CART:选择 基尼系数 最高的特征,基尼系数 表示从数据集中随机抽取两个样本,其类别标记不一致的概率。

参考