Entropy Decomposition Rule by Probability Tree

Ramon Yeung 在他最近所著的 The First Course of Information Theory 提到一個關於Entropy與代數群的關係 , 雖然這層關係主要是對應在非典型的Shannon Type的信息不等式 , 但足以讓學數學的我們大開眼界 , 說真的 , 我打從開始接觸信息理論 , 就不曾在提起過抽象代數 , 但......凡是一個偉大理論都是有好幾個面相 , 就差在你能不能看出這箇中奧妙 , 這就讓我想起 , 楊鎮麟在年輕時就有獨到的眼光看出勞倫茲轉換與對稱群的關係 , 而獲得他老師費米的讚賞 , 這種獨到的眼光我相信除了要有十足深厚的數學功力還要添加幾分的運氣與天真 , 於是我也嘗試從信息理論的基礎Entropy及Mutual Information兩個物理量 , 看能不能想出具有我個人風格的觀點 , 只是 , 老話一句 , 羅馬不是一夕建成 , 偉大數學觀點我是沒有 , 倒是還簡單的推出兩個我個人覺得在證明上蠻好用的算式工具-Cancellation Rule 消去法 , 以及意外發現用Probability Tree建立的 entropy decomposition rule , 跟各位分享分享 :

1. Cancellation Rule in Entropy

Entropy的Chain Rule是大家相當熟悉的 , 那消去律又是什麼 ??
Data processing inquality 提供給我們一個可以直觀判斷的Mutual Information 不等式 , 我想將這種直觀的想法提出兩個疑問?? (註: H(X\Y) is conditional entropy )

<1> 已知 H(X\Y)=H(X\Z) 則在什麼條件下 H(Y) 會等於 H(Z)嗎??(消去X)
<2> 已知 I(X;Y)=I(X;Z) 則在什麼條件下 H(Y) 會等於 H(Z)嗎??(消去X)

第一個問題對應上圖的Multi-Access Model 以及 第二個問題則是Broadcast Model ,
這兩個Model有個字的恆等關係 , 敘述如下 :

1. (Multi-Access Model) 若 H(X\Y) = H(X\Z) if and only if I(X ; Y)=I(X;Z)
2. (Broadcast Model) 若 H(Y\X) = H(Z\X) if and only if H(X,Y)=H(X,Z)

由上面這兩個恆等關係 , 我得到消去律的完整Rule , 並同時回答我上面兩個提問

1. (Multi-Access Model) H(X\Y) = H(X\Z) 且 H(X , Y) ﹦H(X , Z) 則 H(Y)=H(Z)
2. (Broadcast Model) H(Y\X)=H(Z\X) 且 I(X ; Y) = I(X ; Z) 則 H(Y)=H(Z)

其實這個消去律並沒有了不起的學問 , 堆導過程其實也只要套用Information Theory的幾個基本fomula , 但.....這其實這是一個不輸給Data Processing Inquality的好用工具 , 尤其在驗證每個Channel Capacity 或是Sourceing Coding的Minimum Rate的 achieveable region 中 Converse的部份 , 那些令人眼花撩亂的不等式還摻雜一堆隨機變數 , 你就會發現有了消去律 , 你的證明動作常常就是 "消 消 消" , 一消在消 , 欲罷不能............



2. Entropy Decomposition Rule

什麼是entropy 的分解律 ??首先我們提出一個問題作為分解律的思考方向 ,

我們現在假設有 n 個隨機變數 , 每個隨機變數都有自己的Entropy , 那我將其中一個Entropy寫成其餘n-1個的線性組合也就是如下式:

H(X) = Σ i=1 2 3 ...n-1 Ci H(Yi)

第一 , 一定會存在這樣的線性組合的關係嗎 ??

第二, 如果存在這樣的關係 , 那任意給定隨機變數 , 其中線性組合的係數 Ci 如何決定??

在 MIT 的春季"資訊傳輸"的課程 , 上課講義中提到一個架構 entropy 公式的一個原則 - successive choice

H(1/2 , 1/3 , 1/6) = H(1/2 , 1/2) + (1/2) *H(2/3 , 1/3)

這個successive choice我到現在還不清楚他的用意 , 不過要理解這個式子可以從傳統的Probability Tree , 不過先用數學定義說明我的 Probability Tree

Tree Representation : Probability Space ( Ω , F , Ρ ) -> Edge-Labeling Tree

這個 Edge-Labeling 到底是啥 ? 簡單說就是將每個隨機變數及其機率分布用Tree來表現(註:只限用於discreate finite random variable) , 原則其實很簡單 , 但要寫出來很困難 , 首先 , 大家都熟悉entropy的 公式為

H(X) = Σ p log 1/p 改寫成 H(X) = logΠ P ^(-P)

後面的改寫就是Edge-Labeling 的精神 , 請看下圖的例子 , 順便解釋MIT講義中的後面的改寫就是Edge-Labeling 的精神 , 請看下圖 , 這個例子就是MIT Lecture的例子 , 我用 Probability Tree表示
There is three random variable X , Y , Z
X~(1/2 , 1/3 , 1/6)
Y~(1/2 , 1/2)
Z~(2/3 , 1/3)

各位客倌 , 左圖的右邊有兩棵樹 , 左邊的Tree是隨機變數Ｘ的表示 , 那右邊是將左的樹 , 從中間某個Node給截斷(就是虛線箭頭部份) , 分成上下兩棵Tree , 我稱他叫做"分解Decomposition"動作 , 而這個分解的上下兩棵Tree , 分別代表 Y的隨機變數及Ζ的隨機變數 , 不過要注意 , 截斷的Node上面的點代表的數是 1/2 , 所以我們可以將random variable X 分解成 Ｙ and Z , 表示如下 :

H(X) = H(Y)+ 1/2 H(Z)

待續..................................................^^