估計仍有不確定性
即使譯碼器收到一些資訊,仍可能出錯。錯誤概率如何限制原符號剩餘的不確定性?我們證明有限字母表的一個界,並說明理解它所需的假設。
令 取值於大小為 的集合 , 為有限值觀察。確定性估計器 取值於 。若 ,令 ,否則 ;設 。對數以二為底,,端點值由連續延拓定義。
定理 12.1.1
(Fano 不等式:有限情況)
對任何這樣的聯合分佈與估計器,
證明
(先分出錯誤標記,再取平均)
固定概率為正的觀察值 。由於 由 和 確定,條件熵鏈式法則給出
對每個條件概率為正的分支:當 ,已知 ,故其熵為零;當 , 限於至多 個其他符號,熵至多為 。零概率分支的加權貢獻為零。令 ,包括端點情況,得到
對 取平均。由 的凹性及 Jensen 不等式,。熵最大值界給出 。不可能觀察值的項沒有貢獻。
證明透視
錯誤標記、估計器的取值範圍與凹性在哪裏起作用
證明靠三個事實。第一, 是 的函數,所以加入它不增加熵:,這使鏈式法則的拆分成為恆等式而非不等式。第二,估計器取值於 :在錯誤分支上 避開 ,這正是 而非 的來源。第三,取平均一步用到 的凹性,所以當各條件錯誤率 不相同時,此步會失去精確性。等號成立當且僅當每個 都等於 ,而且在每個概率為正的錯誤分支上, 在 以外的 個符號上均勻分佈。
達到等號的四符號例子
例題 12.1.2
(對稱錯誤可達到此界)
令 在 上均勻。給定 時, 的概率為 ,其他三個值各以概率 出現。取 。則 。由對稱性, 均勻;對每個觀察值 , 的條件分佈在 上的概率為 ,在其他符號上各為 。因此
此處第一個不等式取等號,第二個較鬆的界為 位元。
若錯誤分佈不均勻,第一個不等式便是嚴格的。
例題 12.1.3
(集中的錯誤留下差距)
令 在 上均勻, 的概率為 , 的概率為 ,並取 。則 ;由對稱性 均勻,而給定 時, 的概率為 , 的概率為 。因此
差距恰為 位元:在錯誤分支上 已被確定,所以容許剩下 個符號的那一項完全沒有用上。
正確理解不等式方向
若 ,定理給出 :估計器幾乎必然恢復 。在此有限情況下,逆命題對某個估計器也成立:條件熵為零時,每個正概率觀察值都確定一個 值。但它不必對每個估計器成立,因為估計器可以故意忽略或反轉觀察。
反例模式
零不確定性不代表每個譯碼器正確
令 為公平位元,,刻意選錯誤估計器 。則 ,但 。Fano 界仍成立: 時右邊為 。不能僅由低條件熵推斷某個譯碼器的錯誤率低,也不能不檢查估計器及相關範圍就反解此界。
此界沒有聲稱估計器最優、沒有證明編碼定理,也沒有給出未指定通道的精確錯誤率。它適用於所述有限聯合分佈和所選估計器。反過來,若已知條件熵大於某錯誤率代入右邊的值,該錯誤率便被排除。
例題 12.1.4
(不含任何資訊的觀察)
令 在 上均勻, 與 獨立,於是 位元。令 。其導數 在 時為正,所以 在 上遞增,而
因此 Fano 界 迫使每個估計器都有 ;例如 排除了錯誤率 。固定猜一個符號的錯誤率正是 ,所以在這個退化情況下此界取等號。
常見錯誤
(丟掉二元熵一項)
看似自然的簡化 是錯的。在四符號例子中 位元,而 。是否出錯本身也不確定, 正是為這個標記付出的代價。
常見錯誤
(帶有抹除輸出的估計器)
證明需要 。若譯碼器可輸出符號 ,則出錯時 個值都仍有可能。取公平位元 、與之獨立的 ,以及總是輸出 的譯碼器,則 、,但 。容許抹除時,應把 換成 。
習題
快速檢查
(對 ,化簡第一個 Fano 界。 時它說明甚麼?)
計算 。
解答 · 答案
因 ,有 。零錯誤時右邊為零。
快速檢查
(在四符號例子中,計算 並判斷第一個界是否取等號。)
把每個條件錯誤分佈與等號條件比較。
解答 · 答案
,第一個界取等號,因為每個條件錯誤分佈在其他三個符號上均勻,且所有 都是 。
快速檢查
(若 是公平位元,而估計器總輸出 ,求 和 。)
解答 · 答案
決定 ,所以 ;而估計器總是出錯,所以 。此界成為 。
快速檢查
(當 時,為何可用 限制 ?)
數一數該分支上 的可能取值。
解答
給定 且出錯時, 只能是與 不同的 個值之一;支撐於至多這麼多符號的分佈,其熵至多為其數目的對數。若事件概率為零,其加權貢獻為零。
延伸閱讀
MIT 開放式課程資訊理論第二講 討論 Fano 引理。