熵，交叉熵，KL散度的了解

文章目錄

• • 可視化機率分布
  • 編碼 Code
  • 可變長度-編碼（Variable-Length Code）
  • 編碼空間（The Space of Codewords）
  • 優化編碼（Optimal Encodings）
  • 交叉熵（Cross-Entropy）
  • 多變量的熵（Entropy and Multiple Variable）
  • 互資訊（Mutual Information）

參考部落格： https://colah.github.io/posts/2015-09-Visual-Information/#fn1

什麼是熵，什麼是資訊熵？在機器學習中一直都很難了解，最近讀了一篇部落格，它用可視化的方法幫助我們更好的了解什麼是資訊熵。

可視化機率分布

首先舉個例子，這個例子在後文中也會用到。假設我在重慶，有時候它會下雨，但是大多數時候是晴天，下雨的機率大概是25%，晴天的機率是75%。簡單的用圖表示如下：

然後大部分時間，我穿的是短袖，機率為62%，有時候穿雨衣，機率為38%。

假如穿衣服和天氣是互相獨立的，那麼我們可以很好的将這兩個變量分布用一個圖可視化出來。

圖中橫軸表示穿什麼衣服的機率，豎軸表示天氣的機率。正方形内部被整齊的劃分為4塊，這4塊都是互相獨立的，即穿什麼衣服和什麼天氣是沒有關系的。

但是現實生活中不是這樣的，這兩個條件是互相影響的，比如說上圖中的4個子塊會因為兩個變量之間的互相影響導緻有的子塊機率變小（下雨導緻穿短袖的機率變低）；有的子塊機率變大（下雨導緻穿雨衣的機率變大）。是以我們實際得到的這些子塊有的是膨脹的，有的是縮小的，可視化出來如下圖：

既然兩個變量是互相影響的，那麼此時，我們考慮引入條件機率，假設天氣已知，此時穿衣服的條件機率為：

• p ( 穿 雨 衣 ∣ 下 雨 ) = 75 % p(穿雨衣|下雨)=75\% p(穿雨衣∣下雨)=75%
• p ( 穿 短 袖 ∣ 下 雨 ) = 25 % p(穿短袖|下雨)=25\% p(穿短袖∣下雨)=25%
• p ( 穿 雨 衣 ∣ 晴 天 ) = 25 % p(穿雨衣|晴天)=25\% p(穿雨衣∣晴天)=25%
• p ( 穿 短 袖 ∣ 晴 天 ) = 75 % p(穿短袖|晴天)=75\% p(穿短袖∣晴天)=75%

則上圖可以轉換為（規則化）

由條件機率公式 p ( x , y ) = p ( x ) ∗ p ( y ∣ x ) p(x,y)=p(x)*p(y|x) p(x,y)=p(x)∗p(y∣x)，我們可以得到，

• p ( 穿 雨 衣 , 下 雨 ) = p ( 下 雨 ) ∗ p ( 穿 雨 衣 ∣ 下 雨 ) = 25 % ∗ 75 % = 0.1875 ≈ 19 % p(穿雨衣,下雨)=p(下雨)*p(穿雨衣|下雨)=25\%*75\%=0.1875\approx19\% p(穿雨衣,下雨)=p(下雨)∗p(穿雨衣∣下雨)=25%∗75%=0.1875≈19%
• p ( 穿 短 袖 , 下 雨 ) = p ( 下 雨 ) ∗ p ( 穿 短 袖 ∣ 下 雨 ) = 25 % ∗ 25 % = 0.0625 ≈ 6 % p(穿短袖,下雨)=p(下雨)*p(穿短袖|下雨)=25\%*25\%=0.0625\approx6\% p(穿短袖,下雨)=p(下雨)∗p(穿短袖∣下雨)=25%∗25%=0.0625≈6%
• p ( 穿 雨 衣 , 晴 天 ) = p ( 晴 天 ) ∗ p ( 穿 雨 衣 ∣ 晴 天 ) = 75 % ∗ 25 % = 0.1875 ≈ 19 % p(穿雨衣,晴天)=p(晴天)*p(穿雨衣|晴天)=75\%*25\%=0.1875\approx19\% p(穿雨衣,晴天)=p(晴天)∗p(穿雨衣∣晴天)=75%∗25%=0.1875≈19%
• p ( 穿 短 袖 , 晴 天 ) = p ( 晴 天 ) ∗ p ( 穿 短 袖 ∣ 晴 天 ) = 75 % ∗ 75 % = 0.5625 ≈ 56 % p(穿短袖,晴天)=p(晴天)*p(穿短袖|晴天)=75\%*75\%=0.5625\approx56\% p(穿短袖,晴天)=p(晴天)∗p(穿短袖∣晴天)=75%∗75%=0.5625≈56%

類似的，假設穿着已知，給定天氣的條件機率如下：

• p ( 下 雨 ∣ 穿 雨 衣 ) = 50 % p(下雨|穿雨衣)=50\% p(下雨∣穿雨衣)=50%
• p ( 下 雨 ∣ 穿 短 袖 ) = 25 % p(下雨|穿短袖)=25\% p(下雨∣穿短袖)=25%
• p ( 晴 天 ∣ 穿 雨 衣 ) = 8 % p(晴天|穿雨衣)=8\% p(晴天∣穿雨衣)=8%
• p ( 晴 天 ∣ 穿 短 袖 ) = 92 % p(晴天|穿短袖)=92\% p(晴天∣穿短袖)=92%

則可以用另一個方式可視化上述的聯合分布

編碼 Code

在簡單介紹了一個可視化機率的例子之後，我們将利用它進一步研究資訊熵。資訊熵從文字的編碼（Code）講起，現在假設你（Bob）要與你美國的朋友（Alice）通信，因為你是一個狗（dog）的愛好者，是以在你發給Alice的信件中dog的詞彙出現頻率較高；Alice是貓（cat）的愛好者，是以在她給你的信件中cat出現的頻率較高。假設Bob的詞向量詞頻分布為 p ( x ) p(x) p(x)，Alice的詞頻分布為 q ( x ) q(x) q(x)，則他們的分布如下(僅針對動物的詞頻)：

他們的詞向量相同，不同的僅僅是詞頻的分布。現在Bob使用如下的編碼格式進行發送，将每個單詞用0-1來編碼。

在發送的時候，将每個字元根據上述編碼進行替換即可：

可變長度-編碼（Variable-Length Code）

使用上述編碼政策，我們平均需要2比特長度，對于每個字元：

A v e r a g e ( L o l d ) = ∑ x ∈ X p ( x ) L ( x ) = 1 2 × 2 + 1 4 × 2 + 1 8 × 2 + 1 8 × 2 = 2 b i t Average(L_{old})=\sum_{x\in X}p(x)L(x)=\frac{1}{2}\times 2+\frac{1}{4}\times 2+\frac{1}{8}\times 2+\frac{1}{8}\times 2=2 bit Average(Lold​)=x∈X∑​p(x)L(x)=21​×2+41​×2+81​×2+81​×2=2bit

注意到上述編碼并沒有考慮詞頻的不同，而是統一用兩個字元來編碼，如果再多一個單詞的話，則平均需要3個bit。學習過哈夫曼樹的同學對于帶權最短路徑會想到，可以通過建構哈夫曼編碼縮短上述的平均編碼長度 A v e r a g e ( L o l d ) Average(L_{old}) Average(Lold​)。新的編碼政策如下：

在下圖中，我們使用橫軸表示編碼長度 L ( x ) L(x) L(x)，縱軸表示詞頻分布 p ( x ) p(x) p(x)。則對比新舊的平均編碼如下（矩形的面積）：

新的平均編碼長度如下：

A v e r a g e ( L n e w ) = ∑ x ∈ X p ( x ) L ( x ) = 1 2 × 1 + 1 4 × 2 + 1 8 × 3 + 1 8 × 3 = 1.75 b i t Average(L_{new})=\sum_{x\in X}p(x)L(x)=\frac{1}{2}\times 1+\frac{1}{4}\times 2+\frac{1}{8}\times 3+\frac{1}{8}\times 3=1.75 bit Average(Lnew​)=x∈X∑​p(x)L(x)=21​×1+41​×2+81​×3+81​×3=1.75bit

通過分析會發現，針對上述的詞頻分布，平均至少需要 1.75 1.75 1.75 bit，無論我們如何優化，都不可能小于這個值，這裡可以将它了解為平均編碼長度的一個下限。這個下限就是該分布的熵。

編碼空間（The Space of Codewords）

針對老版本的編碼，一個 b i t bit bit可以編碼的字元數為 2 1 2^{1} 21； n 個 b i t n個bit n個bit可以編碼的長度為 2 n 2^{n} 2n個字元；但是在哈夫曼編碼中，可變長的編碼的空間是多少呢？ 答案是 2 n − 1 2^{n-1} 2n−1 ，因為它需要另外 1 b i t 1 bit 1bit來保證字首碼的不同。

字首碼：在可變長的編碼中，如果字首碼相同，是會引起歧義的，比如假設0 和 01 都在可變長的編碼中都編碼不同的字元，此時，當接收方解碼的時候，它不知道是應該解碼為{0和1}還是{01}為整體。換句話說，每個字元的編碼都不應該是其它字元的字首碼。假設我們想編碼4個字元(看作完全二叉樹)，需要2個bit，為了保證字首碼不同，在兩個分支上加1bit，保證字首碼不同。

為了縮小平均的編碼長度，引入了可變長度的編碼，但由于字首碼的原因，會損失掉一部分編碼空間。例如假設我們使用了01編碼一個字元，那麼010,011…等等都不能再編碼其它字元，如下圖：

圖中是3個bit編碼的空間，因為擁有了一個2bit的編碼(01)，我們損失了 1 4 \frac{1}{4} 41​的編碼空間，同時這種損失也意味着其它字元需要更長的字元來編碼。而且可以看到，越短的編碼，它損失的空間越大，但是越短的編碼，意味着越少的花費。此時有兩個沖突需要平衡：短編碼花費少，但是損失了其它短編碼的編碼空間，使得其它字元需要更長的編碼，其它字元則需要更多的花費。我們需要找到一種最優的編碼來解決這個問題。

優化編碼（Optimal Encodings）

單獨考慮一個字元的編碼。假設我們選擇了1個長度的編碼0，那麼有0開頭的任意長度的編碼将不能使用，損失的空間是 1 2 \frac{1}{2} 21​；若繼續選擇長度為2的編碼10，則損失的空間為 1 4 \frac{1}{4} 41​。随着編碼長度 L L L的增加，損失呈指數型降低。如下圖：

注意到一個字元如果用短的編碼，它會減少資訊長度，但是編碼損失較高，比較

我們知道平均編碼長度為 A v e r a g e ( L o l d ) = ∑ x ∈ X p ( x ) L ( x ) Average(L_{old})=\sum_{x\in X}p(x)L(x) Average(Lold​)=∑x∈X​p(x)L(x)，可以用如下矩形的面積表示：

那怎麼求解 L ( x ) L(x) L(x)呢? 如下圖， 因為是指數分布，函數圖像為 y = 2 − x y=2^{-x} y=2−x,已知 y = p ( a ) = c o s t = 1 2 L y=p(a)=cost=\frac{1}{2^{L}} y=p(a)=cost=2L1​, x = − l o g 2 y = − l o g 2 p ( a ) x=-log_{2}^{y}=-log_{2}^{p(a)} x=−log2y​=−log2p(a)​; 即 L ( x ) = l o g ( 1 p ( x ) ) = l o g ( 1 c o s t ) L(x)=log{(\frac{1}{p(x)})}=log{(\frac{1}{cost})} L(x)=log(p(x)1​)=log(cost1​)。這裡 y = p ( a ) = c o s t y=p(a)=cost y=p(a)=cost還可以這樣了解，就是一個字元出現的機率越高，那麼它的不确定性就越低，提供的資訊就越少，是以和損失是正比的。

資訊熵計算公式如下： H ( p ) = ∑ x p ( x ) l o g 2 ( 1 p ( x ) ) H(p)=\sum_{x}p{(x)}log_{2} \left(\frac{1}{p(x)}\right) H(p)=x∑​p(x)log2​(p(x)1​)

交叉熵（Cross-Entropy）

交叉熵： 使用機率分布A進行最佳編碼，使用分布B進行解碼的平均長度。公式定義如下： H p ( q ) = ∑ x q ( x ) l o g 2 ( 1 p ( x ) ) H_{p}(q)=\sum_{x}q(x)log_{2} \left(\frac{1}{p(x)}\right) Hp​(q)=x∑​q(x)log2​(p(x)1​)

回顧Bob和Alice，他們的詞向量一樣，隻是說的頻率不一樣，Bob的是 p ( x ) p(x) p(x), Alice的是 q ( x ) q(x) q(x)，則交叉熵可以用如下的圖表示：

Bob和Alice都各有自己的最優編碼，是以可以組合出2種熵和交叉熵(右下角編碼器，括号内解碼器)，如下：

• Bob使用Bob的編碼 （ H p ( p ) = 1.75 b i t s H_{p}(p)=1.75 bits Hp​(p)=1.75bits ）
• Bob使用Alice的編碼 （ H q ( p ) = 2.375 b i t s H_{q}(p)=2.375 bits Hq​(p)=2.375bits ）
• Alice使用Bob的編碼 （ H p ( q ) = 2.25 b i t s H_{p}(q)=2.25 bits Hp​(q)=2.25bits ）
• Alice使用Alice的編碼（ H q ( q ) = 1.75 b i t s H_{q}(q)=1.75 bits Hq​(q)=1.75bits ）

注意到交叉熵不是對稱的， H q ( p ) ≠ H p ( q ) H_{q}(p)\neq H_{p}(q) Hq​(p)̸​=Hp​(q)，它衡量的是兩個分布的不同。兩個分布越接近，他們的交叉熵越小。當兩個分布不同的時候，多出來的部分我們稱之為Kullback–Leibler divergence (KL散度)，定義如下（注意解碼器一緻）：

D q ( p ) = H q ( p ) − H ( p ) D_{q}(p)=H_{q}(p)-H(p) Dq​(p)=Hq​(p)−H(p) D p ( q ) = H p ( q ) − H ( q ) D_{p}(q)=H_{p}(q)-H(q) Dp​(q)=Hp​(q)−H(q)

圖示如下：

多變量的熵（Entropy and Multiple Variable）

會議之前穿衣服和天氣的例子，它是一個多變量的分布，如圖：

可以看出這個聯合分布中一共包含4塊内容，每塊内容的機率也是知道的，知道了每塊的機率，有上述熵的定義，我們可以求得它的編碼長度，可視化如下：

我們稱該聯合分布的平均最短編碼為 X X X和 Y Y Y的聯合熵，定義如下：

H ( X , Y ) = ∑ x , y p ( x , y ) l o g 2 ( 1 p ( x , y ) ) H(X,Y)=\sum_{x,y}p(x,y)log_{2}\left(\frac{1}{p(x,y)}\right) H(X,Y)=x,y∑​p(x,y)log2​(p(x,y)1​)

如果我們不把機率扁平化，采用三維的方式來可視化，那麼熵就是下圖中的體積。

假設現在我已經從天氣預報中得知了天氣狀況，那麼現在我還需要提供多少穿衣資訊呢？【 p ( x , y ) ≤ p ( x ∣ y ) p(x,y)\leq p(x|y) p(x,y)≤p(x∣y)，因為後者乘了一個小于等于1的數 p ( y ) p(y) p(y); 也就是說 p ( x ∣ y ) p(x|y) p(x∣y)機率更大，提供了更少的不确定性(隻需提供更少的資訊)， L ( x , y ) = log ⁡ 2 ( 1 p ( x ∣ y ) ) L(x,y)=\log_{2}\left(\frac{1}{p(x|y)}\right) L(x,y)=log2​(p(x∣y)1​) 越小】

從編碼的角度講，因為天氣已知，我穿衣服的機率變了，也就是說 p ( x , y ) p(x,y) p(x,y) 變成了 p ( x ∣ y ) p(x|y) p(x∣y)，我們需要重新設立一套更短編碼，解碼的機率是不變的，是以條件熵 就定義出來了，如下：

H ( X ∣ Y ) = ∑ x , y p ( x , y ) l o g 2 ( 1 p ( x ∣ y ) ) H(X|Y)=\sum_{x,y}p(x,y)log_{2}\left(\frac{1}{p(x|y)}\right) H(X∣Y)=x,y∑​p(x,y)log2​(p(x∣y)1​)

互資訊（Mutual Information）

在上一節中，我們發現兩個變量之間如果不獨立，是存在一定的影響的。假設每個變量都包含了一定量的資訊，用一個矩形條表示，那麼聯合機率 H ( X , Y ) H(X,Y) H(X,Y) 包含的總資訊應該是 H ( X ) H(X) H(X) 和 H ( Y ) H(Y) H(Y) 的并集。如下圖：

那缺掉的部分是什麼呢？如圖：

從圖中可以看出 H ( X , Y ) = H ( Y ) + H ( X ∣ Y ) H(X,Y)=H(Y)+H(X|Y) H(X,Y)=H(Y)+H(X∣Y)，它表示 變量 X X X 和 Y Y Y 包含的資訊是由變量 Y Y Y 包含的資訊 加上 在變量 X X X 但不在 Y Y Y 中的資訊 。如圖：

通過進一步對變量 X X X 和 Y Y Y 中包含的資訊進行分析，可以得到如下圖：

持續更新。。。