信息收益的價值可以爲負值嗎？

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時，請確保您只使用當前數據集。