信息增益的值可以是负数吗？

Question

信息增益的值可以是负数吗？

machine-learninginformation-theory

23

信息增益的值有可能是负数吗？

- julie

3个回答

4

首先，答案是否定的。最坏的情况是没有变化或信息增益为零。如果需要证明，请像Amro所指出的那样在MathOverFlow上查找完整的证明。

现在给出建议。如果您只对决策树进行第一层分析，似乎显而易见它永远不会为负数。然而，当我使用信息增益构建我的第一棵树时，到了第三个分支，我发现自己的增益为负数。这似乎不可行或无用，因此我匆忙检查了我的计算。计算是正确的。我错了的部分是基础公式的第一部分。我正在使用上一级的答案作为起始熵，但这是错误的，因为它包含其他数据集的信息。您需要确保对于您的起始熵，您确定该分支的熵独立计算！这意味着您的“起始熵”实际上可能比前一级别更高。

换句话说，在计算信息增益时，请确保仅使用当前数据集。

- Lon

-3

当然可以。

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

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

这种状态变化可以朝任何方向进行，可以是正的也可以是负的。

通过例子很容易理解：

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

您可以这样想：信息熵对于分类/离散变量就像方差对于连续变量一样。当然，方差只是标准差的平方。例如，如果我们根据各种标准将数据集任意分成两组来预测价格，并且我们将数据集分为A组和B组，其中A组的价格为（50、60和70），而B组的价格为（50、55、60），则B组的方差最小，即它们彼此靠近。当然，方差不能为负（因为在将每个点与均值的距离相加后，会将其平方），但方差之间的差异肯定可以为负。

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

无论如何，在计算给定节点的信息熵之后，您需要在每个变量的每个值上拆分该节点的数据（如果您在根节点，则是整个数据集），然后针对每个拆分，计算两个组的IE，并取加权平均IE。接下来，选择结果为最低加权平均IE的拆分，并将其与节点IE进行比较（显然只是单个组）。如果该拆分的加权平均IE低于节点IE，则拆分该节点的数据（形成一个分支），否则停止，即该节点无法进一步拆分--您已经到达底部。

总之，决策树算法的核心是确定是否要分裂节点的标准——这就是它们构建的方式。这个标准是信息增益（IG）是正还是负。

- doug

4

你的说法不正确，信息增益永远是非负数。这与互信息是相同的，即 I(X;Y)>=0。详情请见：http://en.wikipedia.org/wiki/Mutual_information#Relation_to_other_quantities。 - Amro

我几乎从不在没有证据的情况下被说服。无论如何，我的观点并不重要，但我认为IG确实具有正面和负面价值的实际应用是决定性的。（第三种可能是IG的定义在不同学科中有多种变化，这并不是第一次。OP的问题对上下文保持沉默。） - doug

我添加了更多的解释，并提供了一个实际的决策树示例。 - Amro

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Amro · Accepted Answer

IG(Y|X) = H(Y) - H(Y|X) >= 0，因为最坏情况下X和Y是独立的，所以H(Y) >= H(Y|X)，这意味着通过观察随机变量X的某些值，我们要么获得一些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找吧！），我只是觉得一个实际的例子可能有帮助。

（注：所有计算均根据Google进行）