19

有没有机会让信息增益的价值为负？

4

3 回答 3

45

IG(Y|X) = H(Y) - H(Y|X) >= 0，因为H(Y) >= H(Y|X)最坏的情况是 X 和 Y 是独立的，因此H(Y|X)=H(Y)

另一种思考方式是，通过观察随机变量 X 取一些值，我们要么没有获得关于 Y 的信息，要么获得了一些关于 Y 的信息（你不会丢失任何信息）。

编辑

让我在决策树的背景下澄清信息增益（实际上，当我来自机器学习背景时，我首先想到了这一点）。

假设一个分类问题，我们有一组实例和标签（离散类）。

选择在树的每个节点处拆分哪个属性的想法是选择将类属性拆分为两个最纯粹的可能实例组（即最低熵）的特征。

这反过来相当于选择具有最高信息增益的特征，因为

InfoGain = entropyBeforeSplit - entropyAfterSplit

其中拆分后的熵是每个分支的熵的总和，由该分支下的实例数加权。

现在不存在类值的可能拆分，这将生成比拆分前更纯度（更高熵）的案例。

以这个二进制分类问题的简单示例为例。在某个节点，我们有 5 个正实例和 4 个负实例（总共 9 个）。因此熵（分裂前）为：

H([4,5]) = -4/9*lg(4/9) -5/9*lg(5/9) = 0.99107606

现在让我们考虑一些分裂的情况。最好的情况是当前属性完美地分割了实例（即一个分支全为正，另一个全为负）：

    [4+,5-]
     /   \        H([4,0],[0,5]) =  4/9*( -4/4*lg(4/4) ) + 5/9*( -5/5*lg(5/5) )
    /     \                      =  0           // zero entropy, perfect split
[4+,0-]  [0+,5-]

然后

IG = H([4,5]) - H([4,0],[0,5]) = H([4,5])       // highest possible in this case

想象第二个属性是最坏的情况，其中一个创建的分支没有得到任何实例：而是所有实例都向下到另一个分支（例如，如果属性在实例之间是恒定的，则可能发生，因此无用）：

    [4+,5-]
     /   \        H([4,5],[0,0]) =  9/9 * H([4,5]) + 0
    /     \                      =  H([4,5])    // the entropy as before split
[4+,5-]  [0+,0-]

和

IG = H([4,5]) - H([4,5],[0,0]) = 0              // lowest possible in this case

现在介于这两种情况之间，您会看到任意数量的情况，例如：

    [4+,5-]
     /   \        H([3,2],[1,3]) =  5/9 * ( -3/5*lg(3/5) -2/5*lg(2/5) )
    /     \                       + 4/9 * ( -1/4*lg(1/1) -3/4*lg(3/4) )
[3+,2-]  [1+,3-]

和

IG = H([4,5]) - H([3,2],[1,3]) = [...] = 0.31331323

因此，无论您如何拆分这 9 个实例，您总能获得积极的信息增益。我意识到这不是数学证明（请转到 MathOverflow！），我只是认为一个实际的例子可以提供帮助。

（注：所有计算依据谷歌）

于 2010-07-20T18:33:45.617 回答
3

首先，答案是否定的，不能是否定的。绝对最坏的可能性是没有变化，或者 IG 为零。如果您想要证明，请像 Amro 指出的那样在 MathOverFlow 上查找完整证明。

现在寻求建议。如果你只做决策树的第一层，很明显它永远不会出现负面结果。然而，当我使用信息增益构建我的第一棵树时，我发现我的第三个分支获得了负增益。这似乎没有用或不可能，所以我争先恐后地检查我的数学。数学很好。我错的部分是基本公式的第一部分。我使用上面级别的答案作为我的起始熵，但这是错误的，因为它包含来自其他数据集的信息。您需要确保为您的起始熵单独确定该分支的熵！ 这意味着您的“起始熵”实际上可能高于它之前的水平。

换句话说，在计算 IG 时，请确保您只使用当前数据集。

于 2017-03-14T21:25:16.603 回答
-3

当然可以。

信息增益只是信息熵从一种状态到另一种状态的变化：

IG(Ex, a) = H(Ex) - H(Ex | a)

这种状态变化可以朝任何一个方向发展——可以是正面的，也可以是负面的。

这很容易通过示例看出：

决策树算法的工作原理如下：在给定节点处，您计算其信息熵（对于自变量）。

你可以这样想：信息熵是分类/离散变量，正如方差是连续变量）。当然，方差只是标准差的平方。例如，如果我们正在寻找基于各种标准的价格预测，并且我们将我们的数据集任意分为两组，其中 A 组的价格是（50、60 和 70），B 组的价格是是 (50, 55, 60)，B 组的方差最小——即它们靠得很近。当然方差不能是负数（因为在将每个点与均值的距离相加后，将其平方），但方差的差异肯定可以。

要了解这与信息熵/信息增益有何关系，假设我们不是在预测价格，而是在预测其他东西，例如我们网站的访问者将成为注册用户还是高级订阅者，或者两者都不是。这里的独立变量是离散的，不像价格那样连续，因此您无法以有意义的方式计算方差。信息熵是用来代替的。（如果你怀疑方差和 IE 之间的类比，你应该知道大多数决策树算法能够同时处理离散和连续变量，在后一种情况下，算法将使用方差作为分裂标准，而不是使用 IG。 )

无论如何，在计算给定节点的信息熵之后，然后在每个变量的每个值上拆分该节点上的数据（如果您在根节点，这是整个数据集），然后对于每个拆分，计算两组的IE，并取加权平均IE。接下来采用导致最低加权平均 IE 的拆分，并将其与节点 IE（显然只是一个组）进行比较。如果拆分的加权平均 IE低于节点 IE，则在该节点处拆分数据（形成一个分支），如果不是，则停止，即该节点不能进一步拆分 - 你是在底部。

总之，决策树算法的核心是确定是否拆分节点的标准——这就是它们的构造方式。该标准是 IG 是积极的还是消极的。

于 2010-07-20T21:47:52.713 回答