Notes for (conditional/cross-)Entropy, Mutual-information, ...


整理下 entropy 的一些東西, 不然久沒看老是忘記.

  • Entropy of a r.v. X: H(X)
  • Conditional Entropy of Y given X: H(Y|X)
  • Cross(Relative) Entropy of two pdf, p and q: D(pq)
  • Mutual Information of two r.v.s: I(X;Y)

文章會明確定義每一項, 然後在推導它們之間關係的同時會解釋其物理意義.

最後其實就可以整理成類似集合關係的圖 (wiki)


Entropy

H(X)=xXp(x)log1p(x)

一個 r.v. X 假設配給他的 pdf 為 p, 則可以算出相對應的 entropy H(X), 所以我們其實可以看成是 H(p).
可以知道當 p 是 uniform distribution 時 entropy 達到最大 (後面再證明). 同時該定義可以很容易看出 H(X)0.

直觀解釋:

  1. 因為 uniform distribution 時最大 (最無法確定哪一個 outcome 最有可能), 另一個極端為 X 為 constant (r.v. 只有一個 outcome) 所以我們可以理解為 entropy 為量測一個 r.v. X不確定性
  2. 如果要對每一個 outcome 決定要用多少 bit 來代表, 我們希望平均花的 bits 數能最小, 直觀上機率愈大的 outcome 用愈小的 bits 來表達. 因此 outcome xi 我們用 log1p(xi) 這麼多 bits 表示, 則 entropy 代表了 encode 所有 outcome 所需要的平均 bits 數, 則這個數是最小的. (這可以從下面的 cross entropy 得到證明)
  3. 我們可以用 entropy 來表示該 r.v. 所包含的資訊量. 因為比 entropy 更多的資訊量都是 reduandant 的 (由上一點可看出)

為了方便我們會交叉使用 資訊量 或是 encode 的最小平均 bits 數 來表示 entropy 的物理意義.


Cross(Relative) Entropy

為量測兩個 pdfs, p(x) and q(x) 之間的 “divergence”, 也稱為 KL divergence. 注意 divergence 不需滿足三角不等式也不需滿足對稱性, 因此不是一個 “metric”. 但也足夠當成是某種”距離”來看待 (不是指數學上的 norm)

D(pq)=xp(x)logp(x)q(x)

Jensen’s inequality 可以推得 D(pq)0, 另外 D(pq)=0 iff p=q

D(pq)=xp(x)logq(x)p(x)by Jensen's inequality: logxp(x)q(x)p(x)=0

重寫一下 (2):
0D(pq)=xp(x)log1q(x)H(p)

這說明了對於 outcome xi (true distribution 為 p(x)) 我們用 log1q(xi) 這麼多 bits 表示是浪費的. 所以證明了上面 Entropy 第二種解釋.

直觀解釋:

  • D(pq) 表示使用錯誤的 distribution q 來 encode 要多花的平均 bits 數量

Conditional Entropy

H(Y|X)=xXp(x)H(Y|x=X)=xp(x)yp(y|x)log1p(y|x)

H(Y|x=X) 解釋為 given x encode Y 的最小平均 bits 數 (就是 entropy 只是又重複說了一次), 但是每一個 x 有自己的機率, 因此對 x 再取一次平均.

  • case 1:
    如果 Y 完全可以由 X 決定, 因此一旦給定 x, Y 就是一個 constant, 所以 H(Y|x=X)=0. 再對 X 算期望值仍然是 0.

  • case 2:
    如果 X and Y independent.

    (7)=xp(x)yp(y)log1p(y)=xp(x)H(Y)=H(Y)

    得到結論 H(Y|X)=H(Y)

Case 1 and 2 說明了 X and Y 在完全依賴和完全無關時 H(Y|X) 分別為 0 and H(Y). 直覺上我們可以認為 0H(Y|X)H(Y), 因為剛好是兩個極端情形. 但直覺是不夠的, 我們證明一下.

使用定義, 我們可以很容易推導出

I(X;Y)H(Y)H(Y|X)=x,yp(x,y)logp(x,y)p(x)p(y)=D(p(x,y)p(x)p(y))0

我們這裡先偷跑出了 mutual information I(X;Y) 的定義, 下面會再詳細講.

直觀解釋:
H(Y|X) 表示給了 X 的資訊後, Y 剩下的資訊量. 其中 0H(Y|X)H(Y)


Chain Rule for Entropy

我們在把 (7) 做個運算:

H(Y|X)=(7)=xp(x)yp(y|x)logp(y|x)=x,yp(x,y)logp(x,y)p(x)=x,yp(x,y)logp(x,y)+x,yp(x,y)logp(x)=H(X,Y)H(X)

直觀解釋:
給定 XY 剩下的資訊量 (H(Y|X)) 就等於 X,Y 整體的資訊量扣掉單獨 X 部分的資訊量


Mutual Information

(9) 已經先給出了定義, 我們這裡重複一次:

I(X;Y)x,yp(x,y)logp(x,y)p(x)p(y)=D(p(x,y)p(x)p(y))(用 entropy 定義得到) =H(Y)H(Y|X)(用 entropy 定義得到) =H(X)H(X|Y)

在用 Chain Rule for Entropy: H(Y)=H(X,Y)H(X|Y) 代進 (16) 得到

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

我知道這麼多式子一定眼花了….好在完全可以用集合的 Venn diagram 表示!


所有式子的直觀表達


Reference

  1. wiki mutual information
  2. Dr. Yao Xie, ECE587, Information Theory, Duke University 本篇內容只是 lecture 1 ~ 4 的範圍