熵的概念理解
- Author: 修遠;
- 說明：本文為Datawhale下開源項目《李宏毅機器學習》決策樹的補充內容。作者水平有限，還望學習者批評指正。
- Datawhale
學習目標：
- 學習信息量計算，原理
- 學習信息熵
- 證明0?H(p)?logn0\leqslant H(p)\leqslant logn0?H(p)?logn
- 聯合概率，邊緣概率
- 聯合熵，條件熵，條件熵公式推導
- 互信息，互信息公式推導
- 相對熵，交叉熵
- 回顧LR中的交叉熵
- 計算給定數據集中的香農熵
熵的相關概念
1信息熵
熵 (entropy) 這一詞最初來源于熱力學。1948年，克勞德·愛爾伍德·香農將熱力學中的熵引入信息論，所以也被稱為香農熵 (Shannon entropy)，信息熵 (information entropy)。首先，我們先來理解一下信息這個概念。信息是一個很抽象的概念，百度百科將它定義為：指音訊、消息、通訊系統傳輸和處理的對象，泛指人類社會傳播的一切內容。那信息可以被量化么？可以的！香農提出的“信息熵”概念解決了這一問題。
1.1背景
一條信息的信息量和它的不確定性有著直接的關系。比如說，我們需要搞清楚一件非常非常不確定的事，或者是我們一無所知的事，就需要了解大量的信息。相反，如果我們對某件事已經有了較多的了解，我們就不需要太多的信息就能把它搞清楚。所以，從這個角度，我們可以認為，信息量的度量就等于不確定性的多少。
那么如何量化信息的度量呢？來看一個例子。2010年舉行了世界杯足球賽，大家都很關心誰會是冠軍。假如我錯過了看世界杯，賽后我問一個知道比賽結果的觀眾“哪支球隊是冠軍"？他不愿意直接告訴我，而讓我猜，并且我每猜一次，他要收一元錢才肯告訴我是否猜對了，那么我需要付給他多少錢才能知道誰是冠軍呢？我可以把球隊編上號，從1到 32，然后提問：“冠軍的球隊在1一16號中嗎？"假如他告訴我猜對了，我會接著問：“冠軍在1一8號中嗎？"假如他告訴我猜錯了，我自然知道冠軍隊在9一16號中。這樣只需要五次，我就能知道哪支球隊是冠軍。
所以，誰是世界杯冠軍這條消息的信息量只值5塊錢。
當然，香農不是用錢，而是用“比特" ( Bit )這個概念來度量信息量。一個比特是一位二進制數，計算機中的一個字節是8比特。在上面的例子中，這條消息的信息量是5比特。（如果有朝一日有64支球隊進人決賽階段的比賽，那么“誰是世界杯冠軍"的信息量就是6比特，因為要多猜一次。）讀者可能已經發現，信息量的比特數和所有可能情況的對數函數log有關。（1og232=5，log264=61og_232=5，log_264=61og2?32=5，log2?64=6）
有些讀者此時可能會發現實際上可能不需要猜五次就能猜出誰是冠軍，因為像西班牙、巴西、德國、意大利這樣的球隊得冠軍的可能性比日本、南非、韓國等球隊大得多。因此，第一次猜測時不需要把32支球隊等分成兩個組，而可以把少數幾支最可能的球隊分成一組，把其他隊分成另一組。然后猜冠軍球隊是否在那幾支熱門隊中。重復這樣的過程，根據奪冠概率對剩下的候選球隊分組，直至找到冠軍隊。這樣，也許三次或四次就猜出結果“
因此，當每支球隊奪冠的可能性（概率）不等時， 誰是世界杯冠軍"的信息量比5比特少。香農指出，它的準確信息量應該是
H=?(p(1)logp(1)+...+p(32)logp(32))H=-(p(1)logp(1)+...+p(32)logp(32))H=?(p(1)logp(1)+...+p(32)logp(32))
其中，Pi，P2，一p32分別是這32支球隊奪冠的概率。香農把它稱為“信息熵" (Entropy)，一般用符號H表示，單位是比特。有興趣的讀者可以推算一下當32支球隊奪冠概率相同時，對應的信息熵等于5比特。。對于任意一個隨機變量x（比如得冠軍的球隊），它的熵定義如下：
H(X)=?∑x∈Xnp(x)logp(x)H(X)=-\sum_{x\in X}^{n}p(x)logp(x)H(X)=?x∈X∑n?p(x)logp(x)
若pip_ipi?=0，則定義為0log0=0。上式中的對數以2為底或以e為底(自然對數)，這是熵的單位分別稱做比特(bit)。由定義可知，熵只依賴于X的分布，而與X的取值無關，所以也可將X的熵記作H§，即
H(p)=?∑i=1npilogpiH(p)=-\sum_{i=1}^{n}p_ilogp_iH(p)=?i=1∑n?pi?logpi?
1.2信息熵公式的理解：
1信息量
假如說，一個事件A：你買了一本書，另一個事件B：你將《李宏毅機器學習》的內容全都搞懂了。你買了一本所需的信息量是非常少的，你將《李宏毅機器學習》的內容全都搞懂了這所需要的信息量是非常大的，如何度量這個事件的信息量呢？事件A的信息量表示為H(A)，事件B的信息量表示為H(B)。兩者比較為：H(A)<H(B)H(A)<H(B)H(A)<H(B)。
我們想要在數學公式上跟我們的直覺相統一，假設X是一個事件或者一個信息的時候，它的信息量是跟概率有關的。
我們可以看到發生的幾率越大，所需的信息量就越小，那我們就先假設信息量與概率的關系的為H(X)H(X)H(X)與1p(x)\frac{1}{p(x)}p(x)1?有關系
兩個事件的信息跟每個事件的信息量是什么樣的關系
希望兩者能夠相加起來(有量綱的量)，H(x1,x2)=H(x1)+H(x2)H(x_1,x_2)=H(x_1)+H(x_2)H(x1?,x2?)=H(x1?)+H(x2?)
信息量是大于等于0，肯定不可能是負的 H(X?)0H(X\geqslant) 0H(X?)0
構建一個函數，滿足其上述的關系條件
- H(X)=log1p(x)=?logp(x)H(X)=log\frac{1}{p(x)}=-logp(x)H(X)=logp(x)1?=?logp(x)
- 對數函數的底數為2
- 在信息學中，log的底數一般都為2。但是在機器學習中，底數經常是自然常數e。至于到底用哪一個，一般主要看哪個好用以及哪個好算(例如在下面進行證明的過程中，對數底數為e)
- 該函數符合我們對信息量的直覺
2信息熵
請先在腦海里先記住信息熵是信息量的數學期望
我們想求關于H(X)H(X)H(X)在以p(x)p(x)p(x)分布下的H(X)H(X)H(X)的數學期望
Entropy(X)=?∑xp(x)logH(X)Entropy(X)=-\sum_xp(x)logH(X)Entropy(X)=?x∑?p(x)logH(X)
1.3證明0?H(p)?logn0\leqslant H(p)\leqslant logn0?H(p)?logn：
利用拉格朗日函數證明
-
目標函數
H(p)=?p(1)logp(1)?p(2)logp(2)...?p(n)logp(n)H(p)=-p(1)logp(1)-p(2)logp(2)...- p(n)logp(n)H(p)=?p(1)logp(1)?p(2)logp(2)...?p(n)logp(n)
-
限定條件
p(1)+p(2)+...+p(n)=1p(1)+p(2)+...+p(n)=1p(1)+p(2)+...+p(n)=1
-
構建拉格朗日函數
L(p(1),p(2),...p(n),λ)=?p(1)logp(1)?...?p(n)logp(n)+λ(p(1)+...p(n)?1)L(p(1),p(2),...p(n),\lambda)=-p(1)logp(1)-...-p(n)logp(n)+\lambda(p(1)+...p(n)-1)L(p(1),p(2),...p(n),λ)=?p(1)logp(1)?...?p(n)logp(n)+λ(p(1)+...p(n)?1)
對p(1)偏導等于0
λ?log(e?p(1))=0\lambda-log(e*p(1))=0λ?log(e?p(1))=0
…
對p(n)偏導等于0λ?log(e?p(n))=0\lambda-log(e*p(n))=0λ?log(e?p(n))=0
對其λ\lambdaλ偏導等于0
p(1)+p(2)+...+p(n)?1=0p(1)+p(2)+...+p(n)-1=0p(1)+p(2)+...+p(n)?1=0
求得：
p(1)=p(2)=...=p(n)=1np(1)=p(2)=...=p(n)=\frac{1}{n}p(1)=p(2)=...=p(n)=n1?
代入目標函數得到極值
f(1n,1n,...,1n)=?(1nlog1n+...+1nlog1n)f(\frac{1}{n},\frac{1}{n},...,\frac{1}{n})=-(\frac{1}{n}log\frac{1}{n}+...+\frac{1}{n}log\frac{1}{n})f(n1?,n1?,...,n1?)=?(n1?logn1?+...+n1?logn1?)
=?log(1n)=-log(\frac{1}{n})=?log(n1?)=logn=logn=logn
信息量是對信息的度量，若沒有信息時就為0，不可能出現負數的情況，得證為
0?H(p)?logn0\leqslant H(p)\leqslant logn0?H(p)?logn
2 條件熵(Conditional entropy)
2.1公式理解
設有隨機變量(X,Y)，其聯合概率分布為P(X=xi,Y=yj)=pij,i=1...n,j=1...mP(X=x_i,Y=y_j)=p_{ij},i=1...n,j=1...mP(X=xi?,Y=yj?)=pij?,i=1...n,j=1...m
條件熵H(Y|X)表示在已知隨機變量X的條件下隨機變量Y的不確定性。隨機變量X給定的條件下隨機變量Y的條件熵(conditional entropy)H(Y|X)，定義為X給定條件下Y的條件概率分布的熵對X的數學期望
“相關的”信息能夠消除不確定性
H(Y∣X)=∑I=1mpiH(Y∣X=xi)H(Y|X)=\sum_{I=1}^{m}p_iH(Y|X=x_i)H(Y∣X)=I=1∑m?pi?H(Y∣X=xi?)
這里pip_ipi?=P(X=xix_ixi?)，i=1,2,…n
2.2條件熵的定義式：
(X,Y)(X,Y)(X,Y)發生所包含的熵，減去X單獨發生包含的熵：在X發生的前提下，Y發生“新”帶來的熵
H(X,Y)?H(X)H(X,Y)-H(X)H(X,Y)?H(X)
=?∑x,ylog(x,y)p(x,y)+∑xp(x)logp(x)= -\sum_{x,y}log(x,y)p(x,y)+\sum_xp(x)logp(x)=?∑x,y?log(x,y)p(x,y)+∑x?p(x)logp(x)
=?∑x,ylog(x,y)p(x,y)+∑x(∑yp(x,y))logp(x)=-\sum_{x,y}log(x,y)p(x,y)+\sum_x(\sum_yp(x,y))logp(x)=?∑x,y?log(x,y)p(x,y)+∑x?(∑y?p(x,y))logp(x)
=?∑x,ylog(x,y)p(x,y)+∑x,yp(x,y)logp(x)=-\sum_{x,y}log(x,y)p(x,y)+\sum_{x,y}p(x,y)logp(x)=?∑x,y?log(x,y)p(x,y)+∑x,y?p(x,y)logp(x)
=?∑x,yp(x,y)logp(x,y)p(x)=-\sum_{x,y}p(x,y)log\frac{p(x,y)}{p(x)}=?∑x,y?p(x,y)logp(x)p(x,y)?
=?∑x,yp(x,y)logp(y∣x)=-\sum_{x,y}p(x,y)logp(y|x)=?∑x,y?p(x,y)logp(y∣x)
H(X,Y)?H(X)=?∑x,yp(x,y)logp(y∣x)H(X,Y)-H(X)=-\sum_{x,y}p(x,y)logp(y|x)H(X,Y)?H(X)=?∑x,y?p(x,y)logp(y∣x)
=?∑x∑yp(x,y)logp(y∣x)=-\sum_x\sum_yp(x,y)logp(y|x)=?∑x?∑y?p(x,y)logp(y∣x)
=?∑xp(x)(∑yp(y∣x)logp(y∣x))=-\sum_xp(x)(\sum_yp(y|x)logp(y|x))=?∑x?p(x)(∑y?p(y∣x)logp(y∣x))
=∑xp(x)H(Y∣X=x)=\sum_xp(x)H(Y|X=x)=∑x?p(x)H(Y∣X=x)
3 聯合熵：
對服從聯合分布為p(x,y)p(x,y)p(x,y)的一對離散隨機變量(X,Y)(X,Y)(X,Y)，其聯合熵H(X,Y)H(X,Y)H(X,Y)可表示為
H(X,Y)=?∑x∈X∑y∈Yp(x,y)logp(x,y)H(X,Y)=-\sum_{x\in X}\sum_{y\in Y}p(x,y)logp(x,y)H(X,Y)=?x∈X∑?y∈Y∑?p(x,y)logp(x,y)
4 邊緣概率
當X和Y都是離散型隨機變量時，X和Y的聯合概率分布列了一定義為p(x,y)p(x,y)p(x,y)
-
利用p(x,y)p(x,y)p(x,y)可得XXX的分布列
pX(x)=P(X=x)=∑yp(x,y)p_X(x)=P(X=x)=\sum_{y}p(x,y)pX?(x)=P(X=x)=y∑?p(x,y)
-
利用p(x,y)p(x,y)p(x,y)可得YYY的分布列
pY(y)=P(Y=y)=∑xp(x,y)p_Y(y)=P(Y=y)=\sum_{x}p(x,y)pY?(y)=P(Y=y)=x∑?p(x,y)
5 互信息：
5.1公式理解
兩個隨機變量X，Y的互信息，定義為X，Y的聯合分布和獨立分布乘積的相對熵
- 度量兩個隨機變量的“相關性”
- 互信息就是隨機事件X的不確定性或者說熵H(X)，以及在知道隨機事件Y條件下的不確定性(條件熵)的差異
I(X,Y)=D(P(X,Y)∣∣P(X)P(Y))I(X,Y)=D(P(X,Y)||P(X)P(Y))I(X,Y)=D(P(X,Y)∣∣P(X)P(Y))
I(X,Y)=∑x,yp(x,y)logp(x,y)p(x)p(y)I(X,Y)=\sum_{x,y}p(x,y)log\frac{p(x,y)}{p(x)p(y)}I(X,Y)=x,y∑?p(x,y)logp(x)p(y)p(x,y)?
I(X,Y)=H(X)?H(X∣Y)I(X,Y)=H(X)-H(X|Y)I(X,Y)=H(X)?H(X∣Y)
5.2 互信息的定義式：
I(X,Y)=H(X)+H(Y)?H(X,Y)I(X,Y)=H(X)+H(Y)-H(X,Y)I(X,Y)=H(X)+H(Y)?H(X,Y)
=?∑xp(x)logp(x)+(?∑yp(y)logp(y))?(?∑x,yp(x,y)logp(x,y))=-\sum_xp(x)logp(x)+(-\sum_yp(y)logp(y))-(-\sum_{x,y}p(x,y)logp(x,y))=?∑x?p(x)logp(x)+(?∑y?p(y)logp(y))?(?∑x,y?p(x,y)logp(x,y))
=(?∑x(∑yp(x,y)logp(x))+(?∑y(∑xp(x,y)logp(y)+∑x,yp(x,y)logp(x,y)=(-\sum_x(\sum_yp(x,y)logp(x))+(-\sum_y(\sum_xp(x,y)logp(y)+\sum_{x,y}p(x,y)logp(x,y)=(?∑x?(∑y?p(x,y)logp(x))+(?∑y?(∑x?p(x,y)logp(y)+∑x,y?p(x,y)logp(x,y)
=?∑x,yp(x,y)logp(x)?∑x,yp(x,y)logp(y)+∑x,ylogp(x,y)=-\sum_{x,y}p(x,y)logp(x)-\sum_{x,y}p(x,y)logp(y)+\sum_{x,y}logp(x,y)=?∑x,y?p(x,y)logp(x)?∑x,y?p(x,y)logp(y)+∑x,y?logp(x,y)
=∑x,yp(x,y)(logp(x,y)?logp(x)?logp(y))=\sum_{x,y}p(x,y)(logp(x,y)-logp(x)-logp(y))=∑x,y?p(x,y)(logp(x,y)?logp(x)?logp(y))
=∑x,yp(x,y)logp(x,y)p(x)p(y)=\sum_{x,y}p(x,y)log\frac{p(x,y)}{p(x)p(y)}=∑x,y?p(x,y)logp(x)p(y)p(x,y)?
6 相對熵：
相對熵又稱交叉熵，KL散度等
如果我們對于同一個隨機變量 x 有兩個單獨的概率分布 P(x) 和 Q(x)，我們可以使用 KL 散度（Kullback-Leibler (KL) divergence）來衡量這兩個分布的差異
p(X),q(X)的比值取對數之后，在p(X)的概率分布上求期望
D(p∣∣q)=∑xp(x)logp(x)q(x)=Eplogp(x)q(x)D(p||q)=\sum_{x}p(x)log\frac{p(x)}{q(x)}=E_plog\frac{p(x)}{q(x)}D(p∣∣q)=x∑?p(x)logq(x)p(x)?=Ep?logq(x)p(x)?
說明:相對熵可以度量兩個隨機變量的“距離”
7 交叉熵：
由相對熵公式變形得：
D(p∣∣q)=∑xp(x)logp(x)q(x)D(p||q)=\sum_xp(x)log\frac{p(x)}{q(x)}D(p∣∣q)=∑x?p(x)logq(x)p(x)?
=∑xp(x)logp(x)?∑xp(x)logq(x)=\sum_xp(x)logp(x)-\sum_xp(x)logq(x)=∑x?p(x)logp(x)?∑x?p(x)logq(x)
=?H(p)+(?∑xp(x)logq(x))=-H(p)+(-\sum_xp(x)logq(x))=?H(p)+(?∑x?p(x)logq(x))
等式的前一部分就是p的熵，等式的后一部分，就是交叉熵
H(p,q)=?∑xp(x)logq(x)H(p,q)=-\sum_xp(x)logq(x)H(p,q)=?∑x?p(x)logq(x)
在機器學習中，我們需要評估yyy和y^\hat{y}y^?之間的差距，使用KL散度剛剛好，即D(y∣∣y^)D(y||\hat{y})D(y∣∣y^?)(也就是p(x)p(x)p(x),q(x)q(x)q(x))，由于KL散度中的前一部分$?H(y)4不變，故在優化過程中，只需要關注交叉熵就可以了。所以一般在機器學習中直接用用交叉熵做loss，評估模型。
8 回顧LR中的交叉熵
LR交叉熵公式
$$L(\theta)=\sum_{i=1}{m}[-yilogh_{\theta}(xi)+(1-yi)log(1-h_{\theta}(x^i))]
上式中的yiy^iyi是真實數據，hθ(xi)h_{\theta}(x^i)hθ?(xi)是預測出來的數據分布(模型)，我們一直想要做的是訓練數據上學到的模型與真實數據分布越接近越好，即loss function最小，所以我們需要交叉熵越小越好。
綜上所述，我們一直想要做的就是最小化誤差(訓練數據與模型上的分布的差異)，即最小化相對熵。又因為前一部分-H(y)不變，最小化相對熵也就是最小化交叉熵。
得證，交叉熵可以用來計算模型分布與真實數據分布之間的差異
9計算給定數據集的香農熵：
寫code之前，請查看公式
import numpy as np
def cancShannonEnt(dataSet):''':param dataSet: dataSet:return: shannonEnt'''# 計算公式前，注意數據的格式(array)numEntries = len(dataSet) # 獲取數據的行數labelCounts = { } # 設置字典數據格式，想要存儲的數據格式為：類別：頻數for featVec in dataSet: # 獲取數據集每一行的數據currentLabel = featVec[-1] # 獲取特征向量的最后一列# 檢查字典中key是否存在# 如果key不存在if currentLabel not in labelCounts.keys():# 將當前的標簽存于字典中，并將頻數置為0labelCounts[currentLabel] = 0# 如果key存在，在當前的鍵值上+1labelCounts[currentLabel] +=1# 數據已準備好，計算熵shannonEnt = 0.0 # 初始化信息熵for key in labelCounts: # 遍歷出數據中所的類別pro = float(labelCounts[key]) /numEntries shannonEnt -= pro * np.log2(pro) # 計算信息熵return shannonEnt # 返回信息熵
參考書籍：
- 《數學之美》
- 《機器學習實戰》
總結
- 上一篇： min_25筛详解
- 下一篇： 两种最短路径（测地距离）的算法——Dij