資訊理論

數學理論,來自於機率論和統計學領域

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

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

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

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

簡述

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

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

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

資訊的度量

資訊熵

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

 

其中 為有限個事件x的集合, 是定義在 上的隨機變量。資訊熵是隨機事件不確定性的度量。

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

 

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

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

例子

設有一個三個面的骰子,三面分別寫有  為擲得的數,擲得各面的概率為

 

 

聯合熵與條件熵

聯合熵Joint Entropy)由熵的定義出發,計算聯合分佈的熵:

 

條件熵Conditional Entropy),顧名思義,是以條件概率 計算:

 

貝氏定理,有 ,代入聯合熵的定義,可以分離出條件熵,於是得到聯合熵與條件熵的關係式:

 

連鎖法則

可以再對聯合熵與條件熵的關係做推廣,假設現在有 個隨機變量 ,重複分離出條件熵,有:

 

其直觀意義如下:假如接收一段數列 ,且先收到 ,再來是 ,依此類推。那麼收到 後總訊息量為 ,收到 後總訊息量為 ,直到收到 後,總訊息量應為 ,於是這個接收過程給出了連鎖法則。

相互資訊

相互資訊Mutual Information)是另一有用的資訊度量,它是指兩個事件集合之間的相關性。兩個事件  的相互資訊定義為:

 

其意義為, 包含 的多少資訊。在尚未得到 之前,對 的不確定性是 ,得到 後,不確定性是 。所以一旦得到 ,就消除了 的不確定量,這就是  的資訊量。

如果 互為獨立,則 ,於是 

又因為 ,所以

 

其中等號成立條件為  是一個對射函數。

相互資訊與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). 

外部連結