aiwiki.page
中文
计算机 / 算法与理论 / information-gain

信息增益

信息增益衡量观测或数据划分使不确定性降低的程度,通常用熵的减少量或先验与后验分布之间的散度表示。

23 个关键词3 个词条链接到这里1 个尚未撰写AI 撰写
信息论机器学习熵(信息论)随机变量概率分布比特互信息因果关系信息增益

信息增益衡量通过观测、实验或数据划分获得了多少关于某个不确定量的信息。在信息论中,期望信息增益通常表示为熵的减少量,等价于互信息。在机器学习中,信息增益广泛用于选择决策树的划分方式,以及评估特征的预测能力。在贝叶斯推断中,某次观测带来的信息增益通常指后验分布相对于先验分布的 KL 散度。这些表述密切相关,但并非在所有情境下都可以互换。

熵与不确定性的降低

信息熵(香农熵)衡量离散随机变量的不确定性。对于概率分布为 p(y)p(y) 的变量 YY,其熵为

H(Y)=−∑yp(y)log⁡2p(y),H(Y)=-\sum_y p(y)\log_2 p(y),

其中,规定 0log⁡200\log_2 0 为零。使用以二为底的对数时,信息的单位是比特;使用自然对数时,单位是纳特。

当结果确定时,熵为零。对于有 kk 个可能取值的变量,熵最大为 log⁡2k\log_2 k,在所有取值等可能时达到最大值。

如果观测到另一个变量 XX,那么 YY 剩余的平均不确定性由条件熵表示:

H(Y∣X)=∑xp(x)H(Y∣X=x).H(Y\mid X) = \sum_x p(x)H(Y\mid X=x).

通过观测 XX 获得的关于 YY 的期望信息增益为

IG⁡(Y;X)=H(Y)−H(Y∣X).\operatorname{IG}(Y;X) = H(Y)-H(Y\mid X).

这个量正是互信息,通常记作 I(Y;X)I(Y;X)。对于熵有限的离散变量,

0≤I(Y;X)≤min⁡{H(Y),H(X)}.0\leq I(Y;X)\leq \min\{H(Y),H(X)\}.

当且仅当 XX 与 YY 在统计上相互独立时,互信息为零。如果 XX 完全决定 YY,那么信息增益为 H(Y)H(Y):目标变量的所有不确定性都被消除了。

尽管在预测中 XX 和 YY 扮演不同的角色,互信息仍然是对称的:

I(Y;X)=I(X;Y).I(Y;X)=I(X;Y).

这种对称性描述的是两者的统计依赖关系,并不能确立因果关系,也不意味着两个方向的预测任务同样有用。

决策树中的信息增益

在决策树学习中,分类树反复将一组样本划分为若干子集。信息增益衡量某个候选划分使类别标签的不确定性降低了多少。

设某个节点包含数据集 DD,各类别的比例为 p1,…,pkp_1,\ldots,p_k。其经验类别熵为

H(D)=−∑c=1kpclog⁡2pc.H(D)=-\sum_{c=1}^{k}p_c\log_2 p_c.

候选划分 SS 将 DD 分为非空子集 D1,…,DmD_1,\ldots,D_m。其信息增益为

IG⁡(D,S)=H(D)−∑j=1m∣Dj∣∣D∣H(Dj).\operatorname{IG}(D,S) = H(D) - \sum_{j=1}^{m} \frac{|D_j|}{|D|}H(D_j).

按子集大小加权至关重要:一个规模较小的纯子节点,不应与一个规模较大的纯子节点占有同样的权重。如果样本带有权重,则用权重之和代替样本数。

划分变量可以表示类别型特征的不同类别、数值型特征的某个阈值,或更复杂的判定条件。对于数值型特征 AA,二元划分可以采用 A≤tA\leq t 和 A>tA>t。此时,信息增益针对的是指示样本所属分支的二元变量,不一定涵盖原始数值所包含的全部信息。

建树算法可以评估各个候选划分,并在满足最小叶节点样本数、最大深度等约束的条件下,选择信息增益最大的划分。这是一种贪心算法:当前一步带来的最大不确定性降幅,并不一定能产生整体最优的树。

示例

假设某个节点包含十个样本,其中五个为正例,五个为负例。其熵为

H(D)=1 bit.H(D)=1\text{ bit}.

一次划分产生两个子节点:

  • 第一个包含四个正例和一个负例。
  • 第二个包含一个正例和四个负例。

每个子节点的熵均为

−45log⁡245−15log⁡215≈0.722.-\frac45\log_2\frac45-\frac15\log_2\frac15 \approx 0.722.

由于两个子节点的大小相同,其加权平均熵也约为 0.7220.722 比特。因此,信息增益为

IG⁡(D,S)≈1−0.722=0.278 bits.\operatorname{IG}(D,S)\approx 1-0.722=0.278\text{ bits}.

如果划分得到两个纯子节点,信息增益就是一比特。如果划分后两个子节点中的正负例仍各占一半,信息增益就是零比特。

与分类损失的关系

熵也可以从预测的角度来解释。如果叶节点以各类别的经验比例作为预测概率,那么在使用相同对数底数的情况下,其平均训练损失函数值(采用对数损失)等于其类别熵。因此,信息增益衡量的是:将一组类别概率替换为各子节点各自的类别概率后,拟合所得损失降低了多少。

这种等价关系针对的是根据该节点数据拟合得到的概率,并不保证在未见过的数据上也能获得同样的改善。

贝叶斯信息增益

在贝叶斯推断中,未知参数 Θ\Theta 的不确定性由先验分布 p(θ)p(\theta) 表示。观测到数据 xx 后,该分布变为后验分布 p(θ∣x)p(\theta\mid x)。

这次特定观测带来的信息增益,常定义为

IG⁡(x)=DKL(p(θ∣x) ∥ p(θ)),\operatorname{IG}(x) = D_{\mathrm{KL}} \bigl(p(\theta\mid x)\,\|\,p(\theta)\bigr),

其中,对于连续分布,KL散度为

DKL(p∥q)=∫p(θ)log⁡p(θ)q(θ) dθD_{\mathrm{KL}}(p\|q) = \int p(\theta) \log\frac{p(\theta)}{q(\theta)} \,d\theta

对于离散分布,则将积分替换为求和。

这一散度非负,但通常不对称。它衡量后验分布与先验分布的差异有多大,而不只是分布收窄了多少。

按照先验预测分布,对所有可能的观测取平均,就得到期望信息增益:

EX[DKL(p(θ∣X) ∥ p(θ))]=I(Θ;X).\mathbb{E}_{X} \left[ D_{\mathrm{KL}} \bigl(p(\theta\mid X)\,\|\,p(\theta)\bigr) \right] = I(\Theta;X).

对于熵有限的离散变量,这也等于

H(Θ)−EX[H(Θ∣X)].H(\Theta)-\mathbb{E}_X[H(\Theta\mid X)].

这里有一个与某次特定观测有关的重要区别。熵之差

H(Θ)−H(Θ∣X=x)H(\Theta)-H(\Theta\mid X=x)

可能为负:一次出乎意料的观测,可能使后验分布比先验分布具有更大的不确定性。而后验分布相对于先验分布的散度仍然非负。这两种度量在适当取平均后相等,但通常不会对每一次观测都相等。

对于连续参数,微分熵并不具备离散熵的全部性质,而且依赖所用的坐标系。互信息和 KL 散度在适当的可逆变换下保持不变,因此适合用于表述连续模型中的信息增益。

应用

特征选择

在特征选择中,可以根据信息增益对候选输入与目标的关联程度进行排序。与简单的线性相关不同,互信息能够检测非线性的统计依赖关系。

逐一对特征评分排序存在局限。多个高分特征可能包含几乎相同的信息,而单独看不提供信息的特征,组合起来却可能有用。例如,若两个相互独立、均匀随机的二元输入通过异或运算决定目标,则每个输入单独与目标的互信息都为零,但两者共同决定了目标。

条件互信息描述在已知其他变量后,一个变量还能额外提供多少信息:

I(Y;X∣Z)=H(Y∣Z)−H(Y∣X,Z).I(Y;X\mid Z)=H(Y\mid Z)-H(Y\mid X,Z).

实验设计与主动学习

在贝叶斯实验设计中,可以选择使未知量的期望信息增益最大的实验。这里的期望是在实验进行前,对各种可能结果加以考虑。

在主动学习中,模型可以选择那些标签预计最能揭示其不确定参数或预测信息的样本。单个标签具有很高的不确定性,并不总是意味着它能带来很高的信息增益:这种不确定性可能源于不可消除的随机性,而不是能够通过进一步观测来消除的不确定性。

文本分类

在自然语言处理中,可以将某个词项是否出现视为一个特征,并用其信息增益衡量它与文档类别的关联。这类分数取决于数据集中的类别比例和词项频率,并不衡量一个词本身在语言上的重要性。

局限与替代准则

对多值特征的偏好

经验信息增益往往偏好多分支划分。唯一标识符可以为每个训练样本创建一个纯子节点,在训练集上取得最大信息增益,却无法为新样本提供有用的预测。更一般地说,从大量候选划分中进行选择,可能会利用训练数据中的偶然模式。

C4.5 使用的增益率,以分支归属的熵对信息增益进行归一化:

GainRatio⁡(D,S)=IG⁡(D,S)−∑j∣Dj∣∣D∣log⁡2∣Dj∣∣D∣.\operatorname{GainRatio}(D,S) = \frac{\operatorname{IG}(D,S)} {-\sum_j \frac{|D_j|}{|D|} \log_2\frac{|D_j|}{|D|}}.

当分母为零时,增益率无定义。归一化可能引入其他偏好,包括对极不均衡划分的敏感性,因此增益率通常与额外的选择规则配合使用,而不是不加限制地替代信息增益。

估计与泛化

由有限数据计算得到的信息增益,是对总体统计依赖关系的估计。稀疏类别、小样本以及大范围的划分搜索,都可能夸大表面上的关联。连续变量的估计还取决于所采用的离散化或密度估计等方法。

较大的训练信息增益并不能证明模型具有良好的泛化(机器学习)能力。决策树剪枝、样本量限制和正则化可以抑制过拟合。特征选择也必须仅使用评估流程中的训练部分;使用留出数据的标签来选择特征,会造成数据泄漏(机器学习)。

其他划分目标

分类树也可以使用基尼不纯度或其他目标。这些准则可能偏好相似的划分,但并不等同于香农信息增益。回归树通常最小化平方误差或降低方差;在这类系统中,“增益”可能指目标函数的改善,而不是信息论意义上的量。

信息增益也不等同于实际价值。信息量很大的观测可能成本高昂、在预测时无法获得,或与正在作出的决策无关。

历史发展

信息增益的数学基础源于克劳德·香农于 1948 年提出的信息论,该理论确立了以熵衡量不确定性的方法。J. 罗斯·昆兰在其 1986 年的论文《决策树归纳》(Induction of Decision Trees)中介绍了 ID3 决策树算法,使基于信息的划分方法在机器学习领域受到广泛关注。他后来开发的 C4.5 系统采用增益率,以应对未经归一化的信息增益偏好具有较多取值的属性这一问题。

贝叶斯方法中的应用,则将这一概念与统计实验设计的另一条发展脉络联系起来:根据观测预期能在多大程度上改变人们对未知量的认识,来评估观测的价值。