Entropy Decomposition Rule by Probability Tree - Part 2

我們再舉兩個有關 Decomposition Rule 例子 ,

這兩個例子都是分解 :
X~(1/5 , 1/5 , 1/5 , 1/5 , 1/5 , 1/5)

其中第一個例子 , 也就是左圖 , 我們將他分解為
Y~(1/5 , 4/5) 及 Z~(1/4 , 1/4 , 1/4 , 1/4)
同樣是 , 圖中左邊的Tree代表Random Variable X , 右邊的Tree從標上4/5的Node截斷成上下兩棵Tree , 分別為Y及Ζ , 於是我們就得到


H(1/5 , 1/5 , 1/5 , 1/5 , 1/5) = H(1/5, 4/5)+ 4/5 H(1/4 , 1/4 , 1/4 , 1/4) ;

也就是

H(X) = H(Y) + 4/5 H(Z) , 其中的 4/5就是我們分解時恰好截斷終點



第二個例子是將 X 分解成用另外四個Random Variable 來表示 , 四個分別為
Y~(1/5 , 4/5)
Z~(1/4 , 3/4)
U~(1/3 , 2/3)
W~(1/2 , 1/2)

則分解過程參照右圖的 Probability Tree , 我們把trunk 中的每個 node截斷 , 可以得到四個subtree , 分別就是 Y Z U W四個 random variable , 於是我們可以得到下式

H(1/5 , 1/5 , 1/5 , 1/5 , 1/5) = H(1/5 , 4/5) + 4/5 H(1/4 , 3/4) + 3/5 H(1/3 , 2/3) + 2/5 H(1/2 , 1/2)

也就是

H(X) = H(Y) + 4/5 H(Z) + 3/5 H(U) + 2/5 H(W)

1 , 4/5 , 3/5 , 2/5 分別就是原Probability Tree的中間那排節點

所以我們將原本 successive choice 轉成我們比較可以了解的 Decomposition Rule , 而這個Rule其中最重要的表現就是從Probability Tree , 當然如果你是眼尖的讀者 , 你幾乎可以想像出這個Rule可以寫成一個通式 , 而這個通式就是用到之前我將 entropy 轉變後的公式

H(X) = log Π P^(-P)

OK , 我最後將 Entropy Decomposition Rule 寫出來 , 然而這個通式將會發現這是機率分布本身存在的一個事實 , 而這個事實我們或許應將他視為當初在設計Entropy Formula時就無法避免必須遵守的:

(Entropy Decomposition Rule)

若令 random variable X ~ P_i and ranom variable Y_i ~ d_i 且
Y_i 的樣本空間個數為 m(i)=m_i > 0

d_i = { d_i1 , d_i2 .........., d _ i m(i) }

我們可以得到下列一般化的Decomposition Rule , 而我刻意將這個Rule從 Entropy中抽離 , 得到一個純粹機率的性質如下 , 而其中 C1 = 1 , 而其餘的 Ci 則各代表在分解過程中那些Probability Tree的Node , 同時也回答了我們最初的提問 , 如何決定這分解過程中的係數 Ci :

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)

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

隱藏在訊息理論的圖論最大獨立集 ！！

Maximum Clique Set 在圖論中已是相當知名的NP-Complete ( Richard Karp 於1972年證明) , 如果把它丟在原圖的補圖來看得話 , 它所對應的最大獨立集(Maximum Independent Set ,
簡寫 MIS) 當然也成了NP大魔頭 , 碰到NP的問題通常實在很不受歡迎 , 就如同一個病人背診斷成癌症末期準備等死 , 當然 , 每個要壯烈犧牲的烈士在歷史上總是多少留下一些令人緬懷的事蹟 , Maximum Independent Set 在圖論上最有名的定理是由 Konig 在 1916 年證的 :

If G is a bipartite graph , then MIS 的大小 ＝ minimum size of edge cover

注意喔 !! 這個是在 Biparite Graph 的條件下 , 那一般的 Simple Graph呢 ?? 抱歉!! 當然沒有 , 廢話 , 如果有的話它還會是一個NP-Complete的重病患嗎 , 它只差等N≠NP 得證後(在量子電腦尚未出現前 , 我是堅信ＮＰ不為P , ) , 它就可以跟其他NP-Complete的英雄一起安樂死 , 話說到這 , 今天當然要說點不同的東西 , 提到Shannon在當年發表的 Information Theory , 今天所有學通訊的大學生可以說對它可是又愛又恨(恨的應該是比較多啦!!尤其對台灣學生.....) , 當年的Shannon在界定Channal Capacity時 , 他可能知道但...也可能不知道 , 在這無形中將圖論的最大獨立集問題 , 偷偷地隱藏在Mutual Information I(X;Y) , 喔！﹖ Really !? , 老實說 , 這是我的觀點 , 但需要費點口舌 , 畢竟已經癌症末期的病患要給他新的藥物試試 , 的確要冒一點險 , 而我要將MIS的問題丟進一般的 Simple Graph , 並嘗試用Mutual Information I(X ; Y) 去表現 , 他的式子將如下 :

size of MIS(G) = 2^{max I(X;Y) ,} G is any simple graph ;

挖靠！ 真的是有夠唬爛 , 怎麼可能化約到這麼的簡單 , 其實這可不簡單 , 但先看看下面這個我稱它為 Bipartite Transform 的圖形轉換動作 , 我要將任合Simple Graph 轉成一個Bipartite Graph :

G(V,E) is a set of simple graphs and there's a subset of G(V,E) denote G'(A x B , E) which is a set of bipartite graphs
Then we define a function F : G(V,E) -> G'(A x B , E)
s.t V=A 且 B=E 並滿足下列
for all x , y ∈ V
if (x,y)∈E(G) => N(x)∩ N(y) ∈ B 註: N(x) is the set of vertices which connect to x
if (x,y)∈E(G) => N(x)∩ N(y) = Φ
if (x,y)≠(x',y') => N(x)∩ N(y) ≠N(x')∩ N(y')

we say F is a bipartite transform

上面這些零零總總的數學定義 , 簡單用白話說就是 , 我對於處理 Simple Graph 我有一個策略 : 就是把所有的 Simple Graph G 都轉成一個 Bipartite Graph G' , 但注意這個轉換不會是一對一 ,但不影響我們接下來的論述 , 那其中G'(A X B , E)的 A 及 B是bipartite graph 的兩個 subvertex set , 所以 A 及 B 本身就成了G'下的一個 Independent Set , 其中 A 這個部份對應的是原來G的全部的vertices , 至於B這個部份對應到原來G中所有的Edges , 所以要是原來圖中Ｇ有四個點及五個邊 , 轉換過去G'就是 A有四個點 , B 有五個點 , 且 在原圖Ｇ中有邊相連的點 , 則在G'的A中他們就有共同的相連點於B中(或稱作有共同的 Neighborhood) , 反之 , 在原圖中不互相連的點 , 則在G'終究不會有共同的Neighborhood , 最後還要注意 , 任意在B中的點只會跟Ａ中某唯一兩點相連 ,
說完了 , 想看例子嗎 , 看看上圖吧 :

沒錯 , 就是這麼簡單的一個轉換 , 但現在說到這我們必須暫時離開一下圖論 , 我們進入Shannon的Channel Capacity, 參照Thomas Cover的Elements of Information Theory 的第八章的第Ｐ.186的 Figure 8.4 , 喔.....好眼熟的圖喔 , 對 , 但暫時先不要想圖論 , 我們套一下股市唬爛大師張國治的語調 , 看到沒呀 , 老師有沒有說啦 , 阿!! , 老師是不是跟你說 , Shannon跟我們講不能怎樣!? 傳送時不能兩點送到一點啦, 不然就會有Error呀 , "有Error , 有Error , 有Error " (又甩筆 數 123456789 秒...) 結束！！
啥！﹖這樣就結束 , 有沒有搞錯 , 張國治有沒有搞錯我不知道 , 但Shannon絕對沒說錯 , 你現在很清楚對於Decoder端收到的Message如果來自兩個以上的Message , 肯定它在解碼的時候就糗大 ,除非它是上帝 , 我們先假設傳送端及接收端都不是上帝 , 所以 , 要避免Error發生 , 傳送端就不應把兩個Message 送到同一個Symbol給Decoder , 所以 , 把傳送端要傳的訊息看成 G' 的 Ａ , 把Decoder會收到的相對應的Message Symbol看成G' 的 B , 如果不要有Error , 就是相當於傳送A中不會有共同的Neighborhood , 就如同上圖的B點跟D點 , 但可以在找更多點來傳嗎 , 在這個圖中是沒有辦法的 , 所以最大傳輸量就是這兩點 , 所以套句Shannon的語言 , 你每次傳輸最多就是傳兩個Symbol , 也就是一次最多傳一個bit , C = maxI(A ; B) = 1 , 所以 , 各位還記得Capacity要求的是最多的傳輸下不會Error的數量 , 再說一次喔 , 是最多 最多..... , 這表示什麼 , 就是找 G'的A中最大點的數量使他們之間都不會有共同的Neighborhood在B中 , 現在我們來看我們定義的 Bipartite Transform F , 不過這時候要看它的Inverse , 在原圖G中 , 什麼樣的點集(vertex set)轉換至G'中不會有共同的Neighborhood , 沒錯就是互相不會有邊相連的Independent Set , 但Shannon說Capacity就是要找最Maximum的傳輸量 , 這不就是告訴我們 ,
就是找原圖Ｇ的 Maximum Independent Set , 所以簡單的推敲後 , 你是不是也看出對於所有的Simple Graph G , 在Bipartite Transform的概念下 ,我們得到

size of MIS(G) = 2^{max I(Ａ;B)}

其實說到這 ,差不多說完了 , 但眼尖的人一定發現把訊息理論的訊息傳輸看成圖論的一條單純的Edge相連 , 總是覺得怪怪的, 沒錯 , 訊息理論的每個訊息傳遞都有所屬的機率 , 但如果你在圖論的edge來看 , 他們每個邊相對於任何一個相連的點 , 地位都是相同的 , 也就是 uniform distribution , 所以這裡簡單的說 , 我引進圖論的最大獨立集的觀點 , 其實遠遠不足以覆蓋Channal Capacity的問題 , 我們對於上面最後的公式應該還要假設 , A對於Ｂ點傳輸的conditional probability都是 uniformly , 這個前提對於引進圖論觀點是很重要的 , 當然我們知道 , 大部分的Channel的特性不可能都是uniformly , 所以Information Theory在Maxiumu Mutual Information的難度是遠遠超過圖論的Maximum Independent Set , 這部份是應該還有空間去討論 , 這個討論包括我們必須可能對圖的每一邊要視為有各自的weight , 不過 , 最近讀完Shannon的另一項在Source Coding 的貢獻 Rate Distortion ,它在圖論幾何的性質 , 我預估將是對應到圖得 Ｍininmum Vertex Cover 或是 Minimum Dominating Set , 這一連串Max-Min Relation是數學與應用科學中相當值得去刻畫的性質........