㈠ 貝葉斯網專題1：資訊理論基礎
目錄
[toc]
貝葉斯網是一種將概率統計應用於復雜領域，進行不確定性推理和數據分析的工具，其在機器學習和人工智慧領域具有重要的基礎性地位。從技術層面講，貝葉斯網可系統地描述隨機變數之間關系，構造貝葉斯網的主要目的是進行概率推理。
理論上，進行概率推理只需要一個聯合概率分布即可，但聯合概率分布的復雜度與隨機變數規模呈指數級關系，在解決實際問題時不可行。貝葉斯網為解決該問題提供了方法，通過貝葉斯網可將復雜的聯合概率分布分解為一系列規模較小的子模塊，從而降低訓練和推理的復雜度。
本人將主要依據香港科大張連文教授的《貝葉斯網引論》，對其中重要內容進行精煉，並通過接下來的幾篇博客對貝葉斯網展開專題介紹，分三大部分進行：
資訊理論是基於概率論的一門研究信息傳輸和處理的數學理論。它不僅是信息技術的基礎，也在統計力學、機器學習等領域發揮重要作用。在構建貝葉斯網的過程中，可以用資訊理論來進行分析。
Jesen不等式源於函數的凹凸性。在數學中，稱一個函數為凹函數是指向上凹，凸函數是指向下凸，如下圖所示。
證明
用歸納法證明，當 時，式(1)恆等。假設式(1)在 時成立，證明它在 時也成立，即：
命題得證。
Jensen不等式是與函數凹凸性有關的基本性質，在資訊理論中常會用到，比如用於計算信息熵的對數函數就滿足凹函數的Jensen不等式，這在後文證明信息熵的性質時會用到。
一個離散隨機變數 的熵 的定義為：
其中，約定 .上式的對數若以2為底，則熵的單位是比特，若以e為底，則單位是奈特，後文將都以比特為單位。
熵在熱力學中表示系統的混亂程度，在概率論中表示隨機變數的不確定程度，在資訊理論中表示對信源的期望編碼長度。
先來解釋下資訊理論中期望編碼長度：假設有一個信源，可產生A、B、C三種不同的信息，產生的概率分別為1/2、1/4和1/4，我們要設計一套編碼系統來記錄這個信源所產生的信息，所用的比特位數越少越好。顯然，我們應該為出現概率大的信息分配碼長較短的編碼，其長度可通過 來確定，比如我們為A分配碼長為1的編碼，為B和C分配碼長為2的編碼，通過霍夫曼編碼演算法，可將A編碼為0，將B和C編碼為10和11.此時，該信源的編碼平均碼長則為
由此我們可知，熵代表了對信源進行最優編碼時的期望編碼長度。反過來看，如果將這個信源用一個隨機變數來表示，若該隨機變數的不確定性越高（產生的信息種類越多、各種類出現的概率越平均），則需要用來編碼該信源的期望編碼長度也會越大，反之則越短。因而，熵又可以表示隨機變數的不確定程度。
例如，一個取值為0或1的隨機變數 ，計 ，根據熵的定義，有：
隨著p的變化， 的變化曲線如下圖：
證明：
(1)根據熵的定義， 顯然成立。
(2)log為上凹函數，根據Jensen不等式有：
命題得證。
聯合熵是基於聯合概率分布對熵的推廣。兩個離散隨機變數X和Y的聯合熵定義為：
條件熵是基於條件概率分布對熵的推廣。隨機變數X的熵時用它的概率分布P(X)來定義的。如果知道另一個隨機變數Y的取值為y，那麼X的條件分布即為P(X|Y=y)。利用此條件分布可定義給定Y=y時X的條件熵：
熵H(X)度量的是隨機變數X的不確定性，條件熵H(X|Y=y)度量的則是已知Y=y後，X的不確定性。
上式(3)中，當y變化時，H(X|Y=y)也會發生改變，當知道Y的概率分布後，可以計算X關於Y的條件熵的期望值：
H(X|Y)稱為給定Y時X的條件熵。
注意：H(X|Y)和H(X|Y=y)不一樣，後者是已知Y取某一特定值時X的條件熵，即已知Y=y後，X剩餘的不確定性。而前者時在未知Y的取值時，對觀測到Y的取值後X剩餘的不確定性的期望值。尤其值得注意的是，H(X|Y=y)可能比H(X)大，即知道Y的某個具體取值後，有可能增大對X的不確定性。而H(X|Y)永遠不會比H(X)大，即平均來說，知道Y不會增加X的不確定性。下面給出一個具體的例子加以比較：
設已知聯合分布P(X,Y)及其邊緣分布P(X)和P(Y)如下表所示：
從而可得出：
可以看到：觀測到 後，可使X的熵減小；觀測到 後，反而使X的熵增大；但平均而言，對Y的觀測使X的熵減小。
由此，我們定義互信息量為：
稱為Y關於X的信息，表示Y中包含多少關於X的信息。很容易證明 ，因此又稱之為X和Y之間的互信息。
證明：
同理可得：
因此， 得證。
證明：
同理可證
證明：
等式左邊：
等式右邊：
從而等式成立。
聯合熵、條件熵和互信息之間的關系，可用如下文氏圖來表示它們之間的關系：
在1.1.2節介紹熵的概念時，介紹了熵的期望編碼長度的意義。交叉熵的概念也可以從期望編碼長度的意義出發進行理解。
若信源X的理論概率分布為Q(X)，但其實際概率分布為P(X)，則使用理論概率分布構建的霍夫曼編碼在實際概率分布下的期望編碼長度即為交叉熵，定義為：
相對熵則定義為交叉熵與熵之差，即按照信源的理論概率分布Q設計的最優編碼的期望碼長會比按照實際概率分布P設計的最優編碼的期望碼長多幾個比特。其定義如下：
其中約定： ； .
KL(P,Q)又稱為P(X)和Q(X)之間的Kullback-Leibler距離，或KL散度。但嚴格來講，它並不是一個真正意義的距離，因為其不滿足對稱性。
證明：
信息不等式得證。
利用KL散度可以度量兩個概率分布之間的差異。
從1.1.3節給出的聯合熵、條件熵與互信息之間關系的文氏圖可以看出：對於隨機變數X和Y，當互信息I(X,Y)=0時，X和Y相互獨立；且 ，等號也在X和Y獨立時成立。我們也可以給出嚴格證明。
證明：
由KL散度大於等於0可得： ，當且僅當P(X,Y)=P(X)P(Y)時等號成立，即X與Y相互獨立。
由於 ，所以 ，等號在X與Y相互獨立時成立。
從資訊理論的角度，我們可以看出：兩個隨機變數相互獨立等價於它們之間的互信息為0.
該結論還可以進一步推廣到三個隨機變數的情況。
對於隨機變數X,Y,Z，條件熵H(X|Z)是給定Z時X剩餘的不確定性，如果再進一步給定Y，X剩餘的不確定性變為H(X|Z,Y)。這兩者之差即為給定Z時觀測Y的取值會帶來的關於X的信息量，即給定Z時X和Y之間的條件互信息，定義如下：
類似上文證明 ，我們也容易證明：
類似上文證明 和 ，我們也容易證明：
其中等號僅在X與Y在給定Z時互相獨立的情況下成立，記作 .
從資訊理論的角度，我們可以看出：給定Z時，兩個隨機變數X和Y相互條件獨立等價於它們的條件互信息為0，即Y關於X的信息已全部包含在Z中，從而觀測到Z後，再對Y進行觀測不會帶來關於X更多的信息。另一方面，如果X和Y在給定Z時相互不獨立，則 ，即在已知Z的基礎上對Y的進一步觀測將會帶來關於X的新信息，從而降低X的不確定性。