信息收益的价值可以为负值吗？

Question

有没有机会让信息获取的价值成为负值？它是根据以下文章中的公式计算的。我无法写出公式，因为它包含了一些硬性符号。

http://citeseerx.ist.psu.edu

谢谢！

Answer 1

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

去想它是通过观察随机变量X取某个值，我们要么不获得或者一些有关信息的另一种方式Ÿ（你不会失去任何）。

---

编辑

让我澄清的决策树（事实上，我脑子里想摆在首位，因为我从一个机器学习背景来）上下文信息增益。

假设给定一组实例和标签（离散类）时给出分类问题。

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

这反过来相当于采摘具有最高信息增益的功能，因为

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的！），我只是认为一个实际的例子可以帮助。

（注意：根据谷歌所有计算）

Answer 2

当然可以。

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

IG（防爆，A）= H（例子） - H（防爆|一）

这种状态变化可以去在任何方向 - 它可以是积极的或消极的。

这是很容易通过例子来看看：

决策树算法是这样的：在一个给定的节点，计算其信息熵（自变量）。

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

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

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

总而言之，决策树算法的核心是确定是否拆分节点的标准 - 这就是它们的结构。这个标准是IG是正面的还是负面的。

Answer 3

对于任何遇到此问题的人，尽管其年龄，我提供这个答案和建议。

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

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

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