以比特衡量依賴
兩個變量各自可能不確定,但仍能互相透露資訊。互資訊透過比較聯合分佈與邊際分佈的乘積來量度這種依賴。它是對稱的,儘管所用的相對熵並不對稱;它本身也不是因果影響的量度。
定義 9.2.1
(互資訊)
令 有有限取值域,對數以二為底。以 表示聯合概率, 表示邊際概率。求和時省略概率為零的項,等價於取 。只要 ,兩個邊際值均為正,故下式的比值有定義。互資訊為
這是以比特計的相對熵 。
定義 9.2.2
(熵與條件熵)
對有限隨機變量 ,定義
只有概率為正的 才需要條件概率。
定理 9.2.3
(非負性與獨立)
對有限隨機變量 ,,且等號恰在對所有 都有 時成立,亦即 獨立。
證明
(互資訊就是一個相對熵)
定義 的和式,就是聯合分佈 相對於乘積分佈 在數對字母表上的相對熵,以二為底計算。兩者在該字母表上都是概率分佈,而且凡 為正之處 也為正。交叉熵與相對熵一節的 Gibbs 不等式給出非負性,且等號恰在 時成立。改變對數的底只是乘以正常數 。這個結論使用完整聯合分佈,而非只檢查相關性為零。
命題 9.2.4
(互資訊是不確定性的減少)
對有限隨機變量 ,
證明
(拆開比值的對數)
當 ,寫 。乘以 並求和:第一部分給出 ;第二部分中,把 對 求和得 ,所以給出 。交換 與 的角色,便得另一個表達式。
因此觀察 使關於 的平均不確定性減少 比特。單個觀察結果可能不同;此等式對結果取平均。
條件資訊與鏈式法則
定義 9.2.5
(條件互資訊)
對每個 的 ,構造條件聯合分佈及其條件邊際分佈。定義
每個求和項都非負。當且僅當 與 在 的每個正概率取值下條件獨立時,結果為零。
在 的每個取值內應用上面的恆等式再取平均,得 。
定理 9.2.6
(互資訊的鏈式法則)
對有限隨機變量 ,
無需任何獨立性假設。
證明
(條件熵逐項相消)
對聯合變量 應用無條件恆等式,得 。把它寫成 。第一個括號是 ,第二個是 :中間項相消。交換 與 的角色,便得第二個表達式。
處理不能增加關於輸入的資訊
定義 9.2.7
(馬爾可夫(Markov)鏈)
若對每個概率為正的 , 與 在給定 時條件獨立,即 ,則稱 構成馬爾可夫(Markov)鏈。
定理 9.2.8
(數據處理不等式)
若 是馬爾可夫鏈,則 。等號恰在 時成立,亦即 與 在 的每個正概率取值下條件獨立。
證明
(鏈式法則的兩種次序)
馬爾可夫條件表明 中每個條件相對熵都是零,所以 。於是由鏈式法則,。把同一個量按另一種次序展開,得 。因此
因為條件互資訊非負。差距恰為 ,這也給出取等號的條件。
證明透視
馬爾可夫條件在哪裏起作用
證明把同一個量 按兩種次序計算。次序 是用到馬爾可夫假設的地方:它令第二項為零,所以在 之外加入 ,並不能再多透露關於 的資訊。次序 不需要任何假設,那裏只用到條件互資訊是相對熵的平均、因而非負這一點。所以不等式的差距恰是被丟棄的那一項 。去掉馬爾可夫條件,被破壞的只是第一種次序,下面的反例顯示結論此時可以失效。
這個數據處理不等式針對滿足該條件獨立性的指定聯合分佈。它並不是說 的每個函數都保留全部資訊,也不是說光憑箭頭記法就證明了因果關係。
反例模式
沒有馬爾可夫條件,額外的變量可以增加資訊
設想一個斷言:只要 由 與其他變量構成,就有 。令 為獨立的公平比特,。取 、、。由獨立性,。給定 時,比特 決定 ,所以條件聯合分佈在兩個格上各有概率 ,邊際均勻,它相對於邊際乘積的相對熵為 。因此 。由於 是與 獨立的公平比特,鏈式法則給出 。所以 帶有關於 的整整一個比特,而 一點也沒有。 不是馬爾可夫鏈:給定 時,比特 決定 。
算例
例題 9.2.9
(兩個噪音階段)
令 為公平比特。令 互相獨立,。設 、,其中 為模二加法。這些變量滿足 。 與 都是公平比特,且
其中 。有效錯誤率 來自 恰有一個為一:。第一式由 與 得到;第二式因為 獨立於 ,且為參數 的伯努利(Bernoulli)變量,故 。數值上 、 比特。不等式保證第二個通道沒有增加關於 的資訊。
例題 9.2.10
(含零概率格的聯合表)
設 、、、。邊際分佈為 與 。省略零概率格,
核對:,而 ,因為 迫使 , 時 是公平比特。所以 ,兩者一致。
例題 9.2.11
(有損的函數與無損的函數)
令 在 上均勻分佈,,故 比特。取 。給定 時, 在兩個值上均勻,所以 ,。差距為 ,與取等條件的預測一致。改取 ,這是一個一一對應的重新標記,則 、,等號成立。極端情形是常數 ,此時 。
常見錯誤
常見錯誤
(相關性為零不等於獨立)
令 在 上均勻分佈,。則 ,,所以相關性為零。但 是 的函數,故 , 比特。獨立要求整個聯合分佈可以分解。
常見錯誤
(互資訊是平均值,並不保證每次觀察都減少不確定性)
令 ,;每當 就有 ,且 。則 ,,所以觀察到 時,關於 的不確定性由 比特升至一比特。觀察到 (概率 )則確定 。平均而言 ,所以 比特為正。這種減少只是對結果的平均。
練習
快速檢查
(若 是公平比特 的確定性複本,求 。若 改為獨立的公平比特,結果如何?)
使用 。
解答 · 答案
若為複本,,所以 比特。若 是獨立的公平比特,聯合分佈等於邊際分佈的乘積,定義中每個比值都是一,故 。
快速檢查
(在噪音階段的例子中,解釋為何 的概率是 ,以及為何兩個噪音必須具有所述獨立性才能這樣計算。)
兩者之和為一,恰當一個噪音比特為一而另一個為零。
解答 · 答案
恰當兩個比特中一個為一、另一個為零。有獨立性時,概率為 ;沒有獨立性,兩個事件的聯合概率就不是乘積。噪音 還必須獨立於 ,這樣 才相當於錯誤率 的通道,且 。
快速檢查
(當 是常數時,比較 與 ,並在不假設 與 獨立的情況下解釋這個不等式。)
常數 的 是多少?
解答 · 答案
常數 給出 ,所以 。互資訊非負,故無論 與 的依賴如何,。這是數據處理不等式的平凡情形: 是馬爾可夫鏈,因為常數與任何變量都獨立。