本頁使用了標題或全文手工轉換

熵 (資訊理論)

維基百科,自由的百科全書
跳至導覽 跳至搜尋
2 bit的熵。

資訊理論中,(英語:entropy)是接收的每條消息中包含的資訊的平均量,又被稱為資訊熵信源熵平均資訊本體量。這裡,「消息」代表來自分布或數據流中的事件、樣本或特徵。(熵最好理解為不確定性的量度而不是確定性的量度,因為越隨機的信源的熵越大。)來自信源的另一個特徵是樣本的機率分布。這裡的想法是,比較不可能發生的事情,當它發生了,會提供更多的資訊。由於一些其他的原因,把資訊(熵)定義為機率分布的對數的相反數是有道理的。事件的機率分布和每個事件的資訊量構成了一個隨機變量,這個隨機變量的均值(即期望)就是這個分布產生的資訊量的平均值(即熵)。熵的單位通常為位元,但也用Sh、nat、Hart計量,取決於定義用到對數的底。

採用機率分布的對數作為資訊的量度的原因是其可加性。例如,投擲一次硬幣提供了1 Sh的資訊,而擲m次就為m位。更一般地,你需要用log2(n)位來表示一個可以取n個值的變量。

在1948年,克勞德·艾爾伍德·夏農熱力學的熵,引入到資訊理論,因此它又被稱為夏農熵(Shannon entropy)[1][2]

簡介[編輯]

熵的概念最早起源於物理學,用於度量一個熱力學系統的無序程度。在資訊理論裡面,熵是對不確定性的測量。但是在資訊世界,熵越高,則能傳輸越多的資訊,熵越低,則意味著傳輸的資訊越少。

英語文本數據流的熵比較低,因為英語很容易讀懂,也就是說很容易被預測。即便我們不知道下一段英語文字是什麼內容,但是我們能很容易地預測,比如,字母e總是比字母z多,或者qu字母組合的可能性總是超過q與任何其它字母的組合。如果未經壓縮,一段英文文本的每個字母需要8個位元來編碼,但是實際上英文文本的熵大概只有4.7位元。

如果壓縮是無損的,即通過解壓縮可以百分之百地恢復初始的消息內容,那麼壓縮後的消息攜帶的資訊和未壓縮的原始消息是一樣的多。而壓縮後的消息可以通過較少的位元傳遞,因此壓縮消息的每個位元能攜帶更多的資訊,也就是說壓縮資訊的熵更加高。熵更高意味著比較難於預測壓縮消息攜帶的資訊,原因在於壓縮消息裡面沒有冗餘,即每個位元的消息攜帶了一個位元的資訊。夏農的信源編碼定理揭示了,任何無損壓縮技術不可能讓一位元的消息攜帶超過一位元的資訊。消息的熵乘以消息的長度決定了消息可以攜帶多少資訊。

夏農的信源編碼定理同時揭示了,任何無損壓縮技術不可能縮短任何消息。根據鴿籠原理,如果有一些消息變短,則至少有一條消息變長。在實際使用中,由於我們通常只關注於壓縮特定的某一類消息,所以這通常不是問題。例如英語文檔和隨機文字,數位照片和噪音,都是不同類型的。所以如果一個壓縮算法會將某些不太可能出現的,或者非目標類型的消息變得更大,通常是無關緊要的。但是,在我們的日常使用中,如果去壓縮已經壓縮過的數據,仍會出現問題。例如,將一個已經是FLAC格式的音樂文件壓縮為ZIP文件很難使它占用的空間變小。

熵的計算[編輯]

如果有一枚理想的硬幣,其出現正面和反面的機會相等,則拋硬幣事件的熵等於其能夠達到的最大值。我們無法知道下一個硬幣拋擲的結果是什麼,因此每一次拋硬幣都是不可預測的。因此,使用一枚正常硬幣進行若干次拋擲,這個事件的熵是一位元,因為結果不外乎兩個——正面或者反面,可以表示為0, 1編碼,而且兩個結果彼此之間相互獨立。若進行n獨立實驗,則熵為n,因為可以用長度為n位元流表示。[3]但是如果一枚硬幣的兩面完全相同,那個這個系列拋硬幣事件的熵等於零,因為結果能被準確預測。現實世界裡,我們收集到的數據的熵介於上面兩種情況之間。

另一個稍微複雜的例子是假設一個隨機變量X,取三種可能值,機率分別為,那麼編碼平均位元長度是:。其熵為3/2。

因此熵實際是對隨機變量的位元量和順次發生機率相乘再總和的數學期望

定義[編輯]

依據Boltzmann's H-theorem,夏農把隨機變量X的熵值 Η(希臘字母Eta)定義如下,其值域為{x1, ..., xn}:

其中,P為X機率質量函數(probability mass function),E為期望函數,而I(X)是X的資訊量(又稱為資訊本體)。I(X)本身是個隨機變數。

當取自有限的樣本時,熵的公式可以表示為:

在這裏b對數所使用的,通常是2,自然常數e,或是10。當b = 2,熵的單位是bit;當b = e,熵的單位是nat;而當b = 10,熵的單位是Hart。

pi = 0時,對於一些i值,對應的被加數0 logb 0的值將會是0,這與極限一致。

還可以定義事件 X 與 Y 分別取 xi 和 yj 時的條件熵

其中p(xiyj)為 X = xi 且 Y = yj 時的機率。這個量應當理解為你知道Y的值前提下隨機變量 X 的隨機性的量。

範例[編輯]

拋硬幣的熵H(X)(即期望資訊本體),以位元度量,與之相對的是硬幣的公正度Pr(X=1).

注意圖的最大值取決於分布;在這裡,要傳達一個公正的拋硬幣結果至多需要1位元,但要傳達一個公正的拋骰子結果至多需要log2(6)位元。

如果有一個系統S內存在多個事件S = {E1,...,En},每個事件的機率分布P = {p1, ..., pn},則每個事件本身的訊息(資訊本體)為:

(對數以2為底,單位是位元(bit))
(對數以為底,單位是納特/nats)

如英語有26個字母,假如每個字母在文章中出現次數平均的話,每個字母的訊息量為:

以日文五十音平假名作為相對範例,假設每個平假名日語文字在文章中出現的機率相等,每個平假名日語文字可攜帶的資訊量為:

而漢字常用的有2500個,假如每個漢字在文章中出現次數平均的話,每個漢字的資訊量為:

實際上每個字母和每個漢字在文章中出現的次數並不平均,比方說較少見字母(如z)和罕用漢字就具有相對高的資訊量。但上述計算提供了以下概念:使用書寫單元越多的文字,每個單元所包含的訊息量越大。

熵是整個系統的平均消息量,即:

因為和熱力學中描述熱力學熵玻爾茲曼公式本質相同(僅僅單位不同,一納特的資訊量即相當於k焦耳開爾文的熱力學熵),所以也稱為「熵」。

如果兩個系統具有同樣大的消息量,如一篇用不同文字寫的同一文章,由於漢字的資訊量較大,中文文章應用的漢字就比英文文章使用的字母要少。所以漢字印刷的文章要比其他應用總體數量少的字母印刷的文章要短。即使一個漢字占用兩個字母的空間,漢字印刷的文章也要比英文字母印刷的用紙少。

熵的特性[編輯]

可以用很少的標準來描述夏農熵的特性,將在下面列出。任何滿足這些假設的熵的定義均正比以下形式

其中,K是與選擇的度量單位相對應的一個正比常數。

下文中,pi = Pr(X = xi)且

連續性[編輯]

該量度應連續,機率值小幅變化只能引起熵的微小變化。

對稱性[編輯]

符號xi重新排序後,該量度應不變。

等。

極值性[編輯]

當所有符號有同等機會出現的情況下,熵達到最大值(所有可能的事件同等機率時不確定性最高)。

等機率事件的熵應隨符號的數量增加。

可加性[編輯]

熵的量與該過程如何被劃分無關。

最後給出的這個函數關係刻畫了一個系統與其子系統的熵的關係。如果子系統之間的相互作用是已知的,則可以通過子系統的熵來計算一個系統的熵。

給定n個均勻分布元素的集合,分為k個箱(子系統),每個裡面有 b1, ..., bk 個元素,合起來的熵應等於系統的熵與各個箱子的熵的和,每個箱子的權重為在該箱中的機率。

對於正整數bi其中b1 + ... + bk = n來說,

選取k = nb1 = ... = bn = 1,這意味著確定符號的熵為零:Η1(1) = 0。這就是說可以用n進位熵來定義n個符號的信源符號集的效率。參見資訊冗餘

進一步性質[編輯]

夏農熵滿足以下性質,藉由將熵看成「在揭示隨機變量X的值後,從中得到的資訊量(或消除的不確定性量)」,可來幫助理解其中一些性質。

  • 增減一機率為零的事件不改變熵:
具有均勻機率分布的信源符號集可以有效地達到最大熵logb(n):所有可能的事件是等機率的時候,不確定性最大。
  • 計算 (X,Y)得到的熵或資訊量(即同時計算XY)等於通過進行兩個連續實驗得到的資訊:先計算Y的值,然後在你知道Y的值條件下得出X的值。寫作
  • 如果Y=f(X),其中f是確定性的,那麼Η(f(X)|X) = 0。應用前一公式Η(X, f(X))就會產生
所以Η(f(X)) ≤ Η(X),因此當後者是通過確定性函數傳遞時,變量的熵只能降低。
  • 如果XY是兩個獨立實驗,那麼知道Y的值不影響我們對X值的認知(因為兩者獨立,所以互不影響):
  • 兩個事件同時發生的熵不大於每個事件單獨發生的熵的總和,且僅當兩個事件是獨立的情況下相等。更具體地說,如果XY是同一機率空間的兩個隨機變量,而 (X,Y)表示它們的笛卡爾積,則
在前兩條熵的性質基礎上,很容易用數學證明這一點。

和熱力學熵的聯繫[編輯]

物理學家和化學家對一個系統自發地從初始狀態向前演進過程中,遵循熱力學第二定律而發生的熵的變化更感興趣。在傳統熱力學中,熵被定義為對系統的宏觀測定,並沒有涉及機率分布,而機率分布是資訊熵的核心定義。

根據Jaynes(1957)的觀點,熱力學熵可以被視為夏農資訊理論的一個應用: 熱力學熵被解釋成與定義系統的微態細節所需的進一步夏農資訊量成正比,波茲曼常數為比例系數,其中系統與外界無交流,只靠古典熱力學的巨觀變數所描述。加熱系統會提高其熱力學熵,是因為此行為增加了符合可測巨觀變數 的系統微態的數目,也使得所有系統的的完整敘述變得更長。(假想的)麥克斯韋妖可利用每個分子的狀態資訊,來降低熱力學熵,但是Landauer(於1961年)和及其同事則證明了,讓小妖精行使職責本身——即便只是了解和儲存每個分子最初的夏農資訊——就會給系統帶來熱力學熵的增加,因此總的來說,系統的熵的總量沒有減少。這就解決了Maxwell思想實驗引發的悖論。Landauer法則也為現代計算機處理大量資訊時所產生的熱量給出了下限,雖然現在計算機的廢熱遠遠比這個限制高。

逸聞[編輯]

貝爾實驗室曾流傳一則可信度不高的傳聞:馮諾依曼建議夏農為這個概念取名為「熵」,理由是這個熱力學名詞別人不懂,容易被唬住。[4]

參見[編輯]

參考[編輯]

  1. ^ Shannon, Claude E. A Mathematical Theory of Communication. Bell System Technical Journal. July 1948, 27 (3): 379–423. doi:10.1002/j.1538-7305.1948.tb01338.x. hdl:10338.dmlcz/101429.  (PDF, archived from here)
  2. ^ Shannon, Claude E. A Mathematical Theory of Communication. Bell System Technical Journal. October 1948, 27 (4): 623–656. doi:10.1002/j.1538-7305.1948.tb00917.x. hdl:11858/00-001M-0000-002C-4317-B.  (PDF, archived from here)
  3. ^ Douglas Robert Stinson; Maura Paterson. 第2.4节“熵”. Cryptography Theory and Practice [密碼學理論與實踐] 2. 
  4. ^ 詹姆斯·格雷克. 第9章“熵及其妖”. The Information: A History, a Theory, a Flood [資訊簡史]. 高博 (翻譯), 樓偉珊 (審校), 高學棟 (審校), 李松峰 (審校) 1. 人民郵電出版社. 2013: 265. ISBN 978-7-115-33180-9 (中文(中國大陸)). 根據在貝爾實驗室里流傳的一個說法,是約翰·馮·諾依曼建議夏農使用這個詞,因為沒有人懂這個詞的意思,所以他與人爭論時可以無往而不利。這件事雖然子虛烏有,但聽起來似乎有點道理。 

外部連結[編輯]