資訊理論

資訊理論（英語：information theory）是應用數學、電子學和電腦科學的一個分支，涉及資訊的量化、儲存和通訊等。資訊理論是由克勞德·山農發展，用來找出訊號處理與通訊操作的基本限制，如數據壓縮、可靠的儲存和數據傳輸等。自創立以來，它已拓展應用到許多其他領域，包括統計推論、自然語言處理、密碼學、神經生物學^[1]、進化論^[2]和分子編碼的功能^[3]、生態學的模式選擇^[4]、熱物理^[5]、量子計算、語言學、剽竊檢測^[6]、圖型識別、異常檢測和其他形式的數據分析。^[7]

提示：此條目的主題不是資訊科學。

• 資訊科技主題

熵是資訊的一個關鍵度量，通常用一條訊息中需要儲存或傳輸一個符號（英語：Symbol rate）的平均位元數來表示。熵衡量了預測隨機變量的值時涉及到的不確定度的量。例如，指定擲硬幣的結果（兩個等可能的結果）比指定擲骰子的結果（六個等可能的結果）所提供的資訊量更少（熵更少）。

資訊理論將資訊的遞移作為一種統計現象來考慮，給出了估算通訊信道容量的方法。資訊傳輸和資訊壓縮是資訊理論研究中的兩大領域。這兩個方面又由信道編碼定理、信源－信道隔離定理相互聯絡。

資訊理論的基本內容的應用包括無失真數據壓縮（如ZIP檔案）、有損數據壓縮（如MP3和JPEG）、信道編碼（如數碼用戶線路（DSL））。這個領域處在數學、統計學、電腦科學、物理學、神經科學和電機工程學的交叉點上。資訊理論對航海家深空探測任務的成敗、光碟的發明、手機的可行性、互聯網的發展、語言學和人類感知的研究、對黑洞的了解，以及許多其他領域都影響深遠。資訊理論的重要子領域有信源編碼、信道編碼、演算法複雜性理論、演算法資訊理論、資訊理論安全性和資訊度量等。

簡述

資訊理論的主要內容可以類比人類最廣泛的交流手段——語言來闡述。

一種簡潔的語言（以英語為例）通常有兩個重要特點： 首先，最常用的詞（比如"a"、"the"、"I"）應該比不太常用的詞（比如"benefit"、"generation"、"mediocre"）要短一些；其次，如果句子的某一部分被漏聽或者由於雜訊干擾（比如一輛車輛疾馳而過）而被誤聽，聽者應該仍然可以抓住句子的大概意思。而如果把電子通訊系統比作一種語言的話，這種健壯性（robustness）是不可或缺的。將健壯性引入通訊是通過信道編碼完成的。信源編碼和信道編碼是資訊理論的基本研究課題。

注意這些內容同訊息的重要性之間是毫不相干的。例如，像「多謝；常來」這樣的客套話與像「救命」這樣的緊急請求在說起來、或者寫起來所花的時間是差不多的，然而明顯後者更重要，也更有實在意義。資訊理論卻不考慮一段訊息的重要性或內在意義，因為這些是數據的質素的問題而不是數據量（數據的長度）和可讀性方面上的問題，後者只是由概率這一因素單獨決定的。

資訊的度量

資訊熵

美國數學家克勞德·山農被稱為「資訊理論之父」。人們通常將山農於1948年10月發表於《貝爾系統技術學報（英語：Bell System Technical Journal）》上的論文《通訊的數學理論（英語：A Mathematical Theory of Communication）》作為現代資訊理論研究的開端。這一文章部分基於哈里·奈奎斯特和拉爾夫·哈特利（英語：Ralph Hartley）於1920年代先後發表的研究成果。在該文中，山農給出了資訊熵的定義：

${\displaystyle H(X)=\mathbb {E} _{X}[I(x)]=\sum _{x\in {\mathcal {X}}}^{}p(x)\log _{2}\left({\frac {1}{p(x)}}\right)}$

其中${\displaystyle {\mathcal {X}}}$為有限個事件x的集合，${\displaystyle X}$是定義在${\displaystyle {\mathcal {X}}}$上的隨機變量。資訊熵是隨機事件不確定性的度量。

資訊熵與物理學中的熱力學熵有着緊密的聯絡:

${\displaystyle S(X)=k_{B}H(X)}$

其中S(X)為熱力學熵，H(X)為資訊熵，${\displaystyle k_{B}}$為波茲曼常數。 事實上這個關係也就是廣義的波茲曼熵公式，或是在正則系綜內的熱力學熵表示式。如此可知，玻爾茲曼與吉布斯在統計物理學中對熵的工作，啟發了資訊論的熵。

資訊熵是信源編碼定理中，壓縮率的下限。若編碼所用的資訊量少於資訊熵，則一定有資訊的損失。山農在大數定律和漸進均分性（英語：Asymptotic equipartition property）的基礎上定義了典型集（英語：Typical set）和典型序列。典型集是典型序列的集合。因為一個獨立同分佈的${\displaystyle X}$序列屬於由${\displaystyle X}$定義的典型集的概率大約為1，所以只需要將屬於典型集的無記憶${\displaystyle X}$信源序列編為唯一可譯碼，其他序列隨意編碼，就可以達到幾乎無損失的壓縮。

例子

設有一個三個面的骰子，三面分別寫有${\displaystyle 1,2,3}$，${\displaystyle X}$為擲得的數，擲得各面的概率為

${\displaystyle {\begin{aligned}\mathbb {P} (X=1)&=1/5,\\\mathbb {P} (X=2)&=2/5,\\\mathbb {P} (X=3)&=2/5,\end{aligned}}}$

則

${\displaystyle H(X)={\frac {1}{5}}\log _{2}(5)+{\frac {2}{5}}\log _{2}\left({\frac {5}{2}}\right)+{\frac {2}{5}}\log _{2}\left({\frac {5}{2}}\right)\approx 1.522.}$

聯合熵與條件熵

聯合熵（Joint Entropy）由熵的定義出發，計算聯合分佈的熵：

${\displaystyle H(X,Y)=\sum _{x\in {\mathcal {X}}}\sum _{y\in {\mathcal {Y}}}^{}p(x,y)\log \left({\frac {1}{p(x,y)}}\right).}$

條件熵（Conditional Entropy），顧名思義，是以條件概率${\displaystyle p(y|x)}$計算：

${\displaystyle H(Y|X)=\sum _{x\in {\mathcal {X}}}\sum _{y\in {\mathcal {Y}}}^{}p(x,y)\log \left({\frac {1}{p(y|x)}}\right).}$

由貝氏定理，有${\displaystyle p(x,y)=p(y|x)p(x)}$，代入聯合熵的定義，可以分離出條件熵，於是得到聯合熵與條件熵的關係式:

${\displaystyle H(X,Y)=H(X)+H(Y|X)=H(Y)+H(X|Y)=H(Y,X).}$

連鎖法則

可以再對聯合熵與條件熵的關係做推廣，假設現在有${\displaystyle n}$個隨機變量${\displaystyle X_{i},i=1,2,...,n}$，重複分離出條件熵，有：

${\displaystyle {\begin{aligned}H(X_{1},X_{2},...,X_{n})&=H(X_{1})+H(X_{2},...,X_{n}|X_{1})\\&=H(X_{1})+H(X_{2}|X_{1})+H(X_{3},...,X_{n}|X_{1},X_{2})\\&=H(X_{1})+\sum _{i=2}^{n}H(X_{i}|X_{1},...,X_{i-1})\end{aligned}}.}$

其直觀意義如下：假如接收一段數列${\displaystyle \{X_{1},X_{2},...,X_{n}\}}$，且先收到${\displaystyle X_{1}}$，再來是${\displaystyle X_{2}}$，依此類推。那麼收到${\displaystyle X_{1}}$後總訊息量為${\displaystyle H(X_{1})}$，收到${\displaystyle X_{2}}$後總訊息量為${\displaystyle H(X_{1})+H(X_{2}|X_{1})}$，直到收到${\displaystyle X_{n}}$後，總訊息量應為${\displaystyle H(X_{1},...,X_{n})}$，於是這個接收過程給出了連鎖法則。

相互資訊

相互資訊（Mutual Information）是另一有用的資訊度量，它是指兩個事件集合之間的相關性。兩個事件${\displaystyle X}$和${\displaystyle Y}$的相互資訊定義為：

${\displaystyle I(X;Y)=H(X)-H(X|Y)=H(X)+H(Y)-H(X,Y)=H(Y)-H(Y|X)=I(Y;X).}$

其意義為，${\displaystyle Y}$包含${\displaystyle X}$的多少資訊。在尚未得到${\displaystyle Y}$之前，對${\displaystyle X}$的不確定性是${\displaystyle H(X)}$，得到${\displaystyle Y}$後，不確定性是${\displaystyle H(X|Y)}$。所以一旦得到${\displaystyle Y}$，就消除了${\displaystyle H(X)-H(X|Y)}$的不確定量，這就是${\displaystyle Y}$對${\displaystyle X}$的資訊量。

如果${\displaystyle X,Y}$互為獨立，則${\displaystyle H(X,Y)=H(X)+H(Y)}$，於是${\displaystyle I(X;Y)=0}$。

又因為${\displaystyle H(X|Y)\leq H(X)}$，所以

${\displaystyle I(X;Y)\leq \min(H(X),H(Y)),}$

其中等號成立條件為${\displaystyle Y=g(X)}$，${\displaystyle g}$是一個對射函數。

相互資訊與G檢定（英語：G-test）以及皮爾森卡方檢定有着密切的聯絡。

應用

資訊理論被廣泛應用在：

• 編碼理論
• 密碼學
• 數據傳輸
• 數據壓縮
• 檢測理論
• 估計理論
• 數據加密

參考文獻

1. F. Rieke, D. Warland, R Ruyter van Steveninck, W Bialek. Spikes: Exploring the Neural Code. The MIT press. 1997. ISBN 978-0262681087.
2. cf. Huelsenbeck, J. P., F. Ronquist, R. Nielsen and J. P. Bollback (2001) Bayesian inference of phylogeny and its impact on evolutionary biology, Science 294:2310-2314
3. Rando Allikmets, Wyeth W. Wasserman, Amy Hutchinson, Philip Smallwood, Jeremy Nathans, Peter K. Rogan, Thomas D. Schneider （頁面存檔備份，存於互聯網檔案館）, Michael Dean (1998) Organization of the ABCR gene: analysis of promoter and splice junction sequences, Gene 215:1, 111-122
4. Burnham, K. P. and Anderson D. R. (2002) Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach, Second Edition (Springer Science, New York) ISBN 978-0-387-95364-9.
5. Jaynes, E. T. (1957) Information Theory and Statistical Mechanics （頁面存檔備份，存於互聯網檔案館）, Phys. Rev. 106:620
6. Charles H. Bennett, Ming Li, and Bin Ma (2003) Chain Letters and Evolutionary Histories （頁面存檔備份，存於互聯網檔案館）, Scientific American 288:6, 76-81
7. David R. Anderson. Some background on why people in the empirical sciences may want to better understand the information-theoretic methods (PDF). November 1, 2003 [2010-06-23]. （原始內容 (pdf)存檔於2011-07-23）.

外部連結

• 山農論文：通訊的數學理論 （頁面存檔備份，存於互聯網檔案館）