資訊論中的一些基本知識

原文來自:http://www.cnblogs.com/zhangchaoyang   作者:Orisun

資訊論（Information Theory）是機率論與數理統計的一個分枝。用于資訊處理、資訊熵、通信系統、資料傳輸、率失真理論、密碼學、信噪比、資料壓縮和相關課題。

基本概念

先說明一點：在資訊論裡面對數log預設都是指以2為底數。

自資訊量

聯合自資訊量

條件自資訊量

資訊熵

條件熵

聯合熵

根據鍊式規則，有

可以得出

資訊增益Information Gain

系統原先的熵是H(X)，在條件Y已知的情況下系統的熵（條件熵）為H(X|Y)，資訊增益就是這兩個熵的內插補點。

熵表示系統的不确定度，是以資訊增益越大表示條件Y對于确定系統的貢獻越大。

資訊增益在特征選擇中的應用 

由（7）式可以直接推出詞條w的資訊增益，（7）式中的X代表類别的集合，Y代表w存在和不存在兩種情況

p(ci)是第i類文檔出現的機率；p(w)是在整個訓練集中包含w的文檔占全部文檔的比例；p(ci|w)表示出現w的文檔集合中屬于類别i的文檔所占的比例；表示沒有出現w的文檔集合中屬于類别i的文檔所占的比例。

資訊增益在決策樹中的應用

outlook	temperature	humidity	windy	play
sunny	hot	high	FALSE	no
			TRUE
overcast				yes
rainy	mild
	cool	normal

（7）式中的X表示打球和不打球兩種情況。 

隻看最後一列我們得到打球的機率是9/14，不打球的機率是5/14。是以在沒有任何先驗資訊的情況下，系統的熵（不确定性）為

	2	3						4		6		9	5
							1	TRUR

如果選outlook作為決策樹的根節點，（7）式中的Y為集合{sunny、overcast、rainy}，此時的條件熵為

即選擇outlook作為決策樹的根節點時，資訊增益為0.94-0.693=0.247。

同樣方法計算當選擇temperature、humidity、windy作為根節點時系統的資訊增益，選擇IG值最大的作為最終的根節點。

互資訊Mutual Informantion

 yj對xi的互資訊定義為後驗機率與先驗機率比值的對數。

互資訊越大，表明yj對于确定xi的取值的貢獻度越大。

系統的平均互資訊

 可見平均互資訊就是資訊增益！

互資訊在特征選擇中的應用

詞條w與類别ci的互資訊為

p(w)表示出現w的文檔點總文檔數目的比例，p(w|ci)表示在類别ci中出現w的文檔點總文檔數目的比例。

對整個系統來說，詞條w的互資訊為

最後選互資訊最大的前K個詞條作為特征項。

 交叉熵Cross Entropy

 交叉熵是一種萬能的Monte-Carlo技術，常用于稀有事件的仿真模組化、多峰函數的最優化問題。交叉熵技術已用于解決經典的旅行商問題、背包問題、最短路問題、最大割問題等。這裡給一個文章連結：

A Tutorial on the Cross-Entropy Method

交叉熵算法的推導過程中又牽扯出來一個問題：如何求一個數學期望？常用的方法有這麼幾種：

• 機率方法，比如Crude Monte-Carlo
• 測度變換法change of measure
• 偏微分方程的變量代換法
• Green函數法
• Fourier變換法

在實際中變量X服從的機率分布h往往是不知道的，我們會用g來近似地代替h----這本質上是一種函數估計。有一種度量g和h相近程度的方法叫 Kullback-Leibler距離，又叫交叉熵：

通常選取g和h具有相同的機率分布類型（比如已知h是指數分布，那麼就選g也是指數分布）----參數估計，隻是pdf參數不一樣（實際上h中的參數根本就是未知的）。

基于期望交叉熵的特征項選擇

p(ci|w)表示在出現詞條w時文檔屬于類别ci的機率。

交叉熵反應了文本類别的機率分布與在出現了某個詞條的情況下文本類别的機率分布之間的距離。詞條的交叉熵越大，對文本類别分布影響也就越大。是以選CE最大的K個詞條作為最終的特征項。