熵 (資訊理論)

在資訊理論中，熵。熵的單位通常為位元，但也用Sh、nat、Hart計量，取決於定義用到對數的底。採用機率分佈的對數作為資訊的量度的原因是其可加性。例如，投擲一次硬幣提供了1 Sh的資訊，而擲m次就為m位。更一般地，你需要用log2("n")位來表示一個可以取"n"個值的變數。在1948年，克勞德·艾爾伍德·夏農將熱力學的熵，引入到資訊理論，因此它又被稱為夏農熵(Shannon entropy)。簡介.熵的概念最早起源於物理學，用於度量一個熱力學系統的無序程度。在資訊理論裡面，熵是對不確定性的測量。但是在資訊世界，熵越高，則能傳輸越多的資訊，熵越低，則意味著傳輸的資訊越少。英語文字資料流的熵比較低，因為英語很容易讀懂，也就是說很容易被預測。即便我們不知道下一段英語文字是什麼內容，但是我們能很容易地預測，比如，字母e總是比字母z多，或者qu字母組合的可能性總是超過q與任何其它字母的組合。如果未經壓縮，一段英文文字的每個字母需要8個位元來編碼，但是實際上英文文字的熵大概只有4.7位元。這是由於英文的編碼包含了各式符號，如逗號、引號等。因此英文輸入法使用了8個位元來表達一共256個字母及符號。如果壓縮是無損的，即透過解壓縮可以百分之百地恢復初始的訊息內容，那麼壓縮後的訊息攜帶的資訊和未壓縮的原始訊息是一樣的多。而壓縮後的訊息可以透過較少的位元傳遞，因此壓縮訊息的每個位元能攜帶更多的資訊，也就是說壓縮資訊的熵更加高。熵更高意味著比較難於預測壓縮訊息攜帶的資訊，原因在於壓縮訊息裡面沒有冗餘，即每個位元的訊息攜帶了一個位元的資訊。夏農的信源編碼定理揭示了，任何無失真壓縮技術不可能讓一位元的訊息攜帶超過一位元的資訊。訊息的熵乘以訊息的長度決定了訊息可以攜帶多少資訊。夏農的信源編碼定理同時揭示了，任何無失真壓縮技術不可能縮短任何訊息。根據鴿籠原理，如果有一些訊息變短，則至少有一條訊息變長。在實際使用中，由於我們通常只關注於壓縮特定的某一類訊息，所以這通常不是問題。例如英語文件和隨機文字，數字照片和噪音，都是不同型別的。所以如果一個壓縮演算法會將某些不太可能出現的，或者非目標型別的訊息變得更大，通常是無關緊要的。但是，在我們的日常使用中，如果去壓縮已經壓縮過的資料，仍會出現問題。例如，將一個已經是FLAC格式的音樂檔案壓縮為ZIP檔案很難使它佔用的空間變小。熵的計算.如果有一枚理想的硬幣，其出現正面和反面的機會相等，則拋硬幣事件的熵等於其能夠達到的最大值。我們無法知道下一個硬幣拋擲的結果是什麼，因此每一次拋硬幣都是不可預測的。因此，使用一枚正常硬幣進行若干次拋擲，這個事件的熵是一位元，因為結果不外乎兩個——正面或者反面，可以表示為codice_1編碼，而且兩個結果彼此之間相互獨立。若進行codice_2次獨立實驗，則熵為codice_2，因為可以用長度為codice_2的位元流表示。但是如果一枚硬幣的兩面完全相同，那個這個系列拋硬幣事件的熵等於零，因為結果能被準確預測。現實世界裡，我們收集到的資料的熵介於上面兩種情況之間。另一個稍微複雜的例子是假設一個隨機變數codice_5，取三種可能值，機率分別為，那麼編碼平均位元長度是：。其熵為3/2。因此熵實際是對隨機變數的位元量和順次發生機率相乘再總和的數學期望。定義.依據Boltzmann's H-theorem，夏農把隨機變數"X"的熵值 Η定義如下，其值域為{"x"1, ..., "x""n"}：formula_1。其中，P為"X"的機率質量函式。I("X")本身是個隨機變數。當取自有限的樣本時，熵的公式可以表示為：formula_2在這裡"b"是對數所使用的底，通常是2,自然常數e，或是10。當"b" = 2，熵的單位是bit；當"b" = e，熵的單位是nat；而當"b" = 10,熵的單位是Hart。"p""i" = 0時，對於一些"i"值，對應的被加數0 log"b" 0的值將會是0，這與極限一致。formula_3。還可以定義事件 "X" 與 "Y" 分別取 "xi" 和 "yj" 時的條件熵為formula_4其中"p"("xi", "yj")為 "X" = "xi" 且 "Y" = "yj" 時的機率。這個量應當理解為你知道"Y"的值前提下隨機變數 "X" 的隨機性的量。範例.如果有一個系統S記憶體在多個事件S = {E1...,En}，每個事件的機率分佈P = {p1, ..., pn}，則每個事件本身的訊息為：formula_5formula_6如英語有26個字母，假如每個字母在文章中出現次數平均的話，每個字母的訊息量為：formula_8以日文五十音平假名作為相對範例，假設每個平假名日語文字在文章中出現的機率相等，每個平假名日語文字可攜帶的資訊量為：formula_9而漢字常用的有2500個，假如每個漢字在文章中出現次數平均的話，每個漢字的資訊量為：formula_10實際上每個字母和每個漢字在文章中出現的次數並不平均，比方說較少見字母和罕用漢字就具有相對高的資訊量。但上述計算提供了以下概念：使用書寫單元越多的文字，每個單元所包含的訊息量越大。熵是整個系統的平均訊息量，即：formula_11因為和熱力學中描述熱力學熵的玻爾茲曼公式本質相同，所以也稱為“熵”。如果兩個系統具有同樣大的訊息量，如一篇用不同文字寫的同一文章，由於漢字的資訊量較大，中文文章應用的漢字就比英文文章使用的字母要少。所以漢字印刷的文章要比其他應用總體數量少的字母印刷的文章要短。即使一個漢字佔用兩個字母的空間，漢字印刷的文章也要比英文字母印刷的用紙少。熵的特性.可以用很少的標準來描述夏農熵的特性，將在下面列出。任何滿足這些假設的熵的定義均正比以下形式formula_12其中"，K"是與選擇的度量單位相對應的一個正比常數。下文中，"pi" = Pr("X" = "xi")且formula_13連續性.該量度應連續，機率值小幅變化只能引起熵的微小變化。對稱性.符號"xi"重新排序後，該量度應不變。formula_14等。極值性.當所有符號有同等機會出現的情況下，熵達到最大值。formula_15。等機率事件的熵應隨符號的數量增加。formula_16可加性.熵的量與該過程如何被劃分無關。最後給出的這個函式關係刻畫了一個系統與其子系統的熵的關係。如果子系統之間的相互作用是已知的，則可以透過子系統的熵來計算一個系統的熵。給定"n"個均勻分佈元素的集合，分為"k"個箱，每個裡面有 "b"1, ..., "bk" 個元素，合起來的熵應等於系統的熵與各個箱子的熵的和，每個箱子的權重為在該箱中的機率。對於正整數"bi"其中"b"1 + ... + "bk" = "n"來說，formula_17。選取"k" = "n"，"b"1 = ... = "bn" = 1，這意味著確定符號的熵為零：Η1(1) = 0。這就是說可以用"n"進位制熵來定義"n"個符號的信源符號集的效率。訊冗餘。進一步性質.夏農熵滿足以下性質，藉由將熵看成「在揭示隨機變數"X"的值後，從中得到的資訊量」，可來幫助理解其中一些性質。formula_18formula_19具有均勻機率分佈的信源符號集可以有效地達到最大熵log"b"("n")：所有可能的事件是等機率的時候，不確定性最大。formula_20。formula_21所以Η("f"("X")) ≤ Η("X")，因此當後者是透過確定性函式傳遞時，變數的熵只能降低。formula_22。formula_23。在前兩條熵的性質基礎上，很容易用數學證明這一點。和熱力學熵的聯絡.物理學家和化學家對一個系統自發地從初始狀態向前演進過程中，遵循熱力學第二定律而發生的熵的變化更感興趣。在傳統熱力學中，熵被定義為對系統的宏觀測定，並沒有涉及機率分佈，而機率分佈是資訊熵的核心定義。根據Jaynes的觀點，熱力學熵可以被視為夏農資訊理論的一個應用：熱力學熵被解釋成與定義系統的微態細節所需的進一步夏農資訊量成正比，波茲曼常數為比例系數，其中系統與外界無交流，只靠古典熱力學的巨觀變數所描述。加熱系統會提高其熱力學熵，是因為此行為增加了符合可測巨觀變數的系統微態的數目，也使得所有系統的的完整敘述變得更長。和及其同事則證明瞭，讓小妖精行使職責本身——即便只是瞭解和儲存每個分子最初的夏農資訊——就會給系統帶來熱力學熵的增加，因此總的來說，系統的熵的總量沒有減少。這就解決了Maxwell思想實驗引發的悖論。蘭道爾原理也為現代計算機處理大量資訊時所產生的熱量給出了下限，雖然現在計算機的廢熱遠遠比這個限制高。逸聞.貝爾實驗室曾流傳一則可信度不高的傳聞：馮諾依曼建議夏農為這個概念取名為“熵”，理由是這個熱力學名詞別人不懂，容易被唬住。