離散變量x的熵H(x)=E(I(x))=-$sumlimits_{x}{p(x)lnp(x)}$

 

連續(xù)變量x的微分熵H(x)=E(I(x))=-$int{p(x)lnp(x)dx} $

 

條件熵H(y|x)=-$intint{p(x,y)lnp(y|x)dydx}$

 

兩個變量X和 Y 的聯(lián)合熵定義為：

H(X,Y)=-$intint{p(x,y)lnp(x,y)dxdy}$
H(x,y)=H(y|x)+H(x)
若x，y獨立，H(x,y)=H(x)+H(y),此時對x的了解不能增進(jìn)對y的了解。
 

交叉熵Cross Entropy

H(p;q)=-$int{p(x)lnq(x)dx}$ 

很少見，通常使用KL距離

Kullback-Leibler divergence:KL（p||q）=-$int{p(x)lnq(x)dx}-(-int{p(x)lnp(x)dx})$=H(p)+H(p;q)=-$int{p(x)ln{frac{q(x)}{p(x)}}dx}$

p=q時，KL(p||q)=0,H(p;q)=H(p)

交叉熵與kl距離相差一個H(p)

當(dāng)p未知而q已知時，通過改變KL中的p、q的位置，可以減少未知量，便于計算相似度。

 交叉熵是一種萬能的Monte-Carlo技術(shù)，常用于稀有事件的仿真建模、多峰函數(shù)的最優(yōu)化問題。交叉熵技術(shù)已用于解決經(jīng)典的旅行商問題、背包問題、最短路問題、大割問題等。這里給一個文章鏈接：A Tutorial on the Cross-Entropy Method

交叉熵算法的推導(dǎo)過程中又牽扯出來一個問題：如何求一個數(shù)學(xué)期望？常用的方法有這么幾種：

概率方法，比如Crude Monte-Carlo
測度變換法change of measure
偏微分方程的變量代換法
Green函數(shù)法
Fourier變換法
在實際中變量X服從的概率分布h往往是不知道的，我們會用g來近似地代替h----這本質(zhì)上是一種函數(shù)估計。有一種度量g和h相近程度的方法叫 Kullback-Leibler距離，又叫交叉熵,通常選取g和h具有相同的概率分布類型（比如已知h是指數(shù)分布，那么就選g也是指數(shù)分布）----參數(shù)估計，只是pdf參數(shù)不一樣（實際上h中的參數(shù)根本就是未知的）。

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

 

CE(w)=$sumlimits_{i}p(c_{i}|w)logfrac{p(c_{i}|w}{p(c_{i}}$

p(ci|w)表示在出現(xiàn)詞條w時文檔屬于類別ci的概率。

交叉熵反應(yīng)了文本類別的概率分布與在出現(xiàn)了某個詞條的情況下文本類別的概率分布之間的距離。詞條的交叉熵越大，對文本類別分布影響也就越大。所以選CE大的K個詞條作為最終的特征項。

 

 

 

 

互信息Mutual Informantion

 yj對xi的互信息定義為后驗概率與先驗概率比值的對數(shù)。

 

I(x,y)=log$frac{p(x|y)}{p(x)}=I(x)-I(x|y)$

互信息越大，表明y對于確定x的取值的貢獻(xiàn)度越大。

系統(tǒng)的平均互信息

I(X,Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)

 可見平均互信息就是信息增益！

I(X,Y)=KL(p(x,y)||p(x)p(y))=-$intint{p(x,y)ln(frac{p(x)p(y)}{p(x,y)})dxdy}$

 

互信息在特征選擇中的應(yīng)用

詞條w與類別ci的互信息為

MI(w,c)=log$frac{p(w|c)}{p(w)}$

p(w)表示出現(xiàn)w的文檔點總文檔數(shù)目的比例，p(w|ci)表示在類別ci中出現(xiàn)w的文檔點總文檔數(shù)目的比例。

對整個系統(tǒng)來說，詞條w的互信息為

 

$MI_{avg}(w,c)=sumlimits_{i}p(c)logfrac{p(w|c)}{p(w)}$

最后選互信息大的前K個詞條作為特征項。