本文整理淺介「機率、訊息、熵」三者間的相關的概念。我們想釐清的的問題是：如何度量一個事件的「訊息量」？ “X國(有32隊進入決賽)是本屆世界盃冠軍”這資訊的信息量？ 觀看電視的一個畫面, 得到多少訊息？ 一本五十萬字的中文書平均有多少信息量？
當我們觀測到或聽到一個事件發生時，就得到了一些「訊息」。「訊息量」指的是：該訊息的內涵多寡，更清楚地說：也就是各種不同結果的可能性大小。例如，思考慮下面者兩個事件：
「太陽從東邊出來」與「人咬狗」。
第一句話幾乎是必然事件, 機率為1，這條訊息一點都不令人驚訝，該事件僅有唯一必然結果，無其他可能，訊息量為零。而「人咬狗」是一件稀有事件，機率很小，聽到這件事會覺得很驚訝，因為這件事包含很多不同的可能，訊息量(內涵)較大。因此, 訊息的多寡跟機率很有關係。 一個機率很小的事件，可以提供越多的訊息。換言之，事件的訊息量是其機率的函數。
一般而言，作一個隨機實驗, 令事件A的機率P(A) = p, 今觀測到A 發生, 我們得到訊息 I = f(p) 。訊息量為機率的函數，但問題是： f 是什麼樣的函數呢？回答這個問題之前，有必要先釐清關於「熵」的概念：
「熵」是熱力學的概念，由德國物理學家克勞修斯（Rudolf Clausius）在一八六四年所提出。「熵」的被用來度量一個混亂、不確定系統，其混亂或不確定的程度。熵是對整個隨機實驗, 表現為機率分佈(p1, . . . , pn), 所呈現出的不確定性或混亂程度之度量。
與「熵」相關的理論發展：熱力學第二定律：獨立系統的熵只會增加不會減少。Boltzmann 在1896年強調熱力學的熵與機率具有密切關係。1928年Hartley 將Boltzmann 的想法引進訊息論中, 得到Hartley公式：I=logN 。1948年Shannon 再推廣成Shannon 公式(詳下)。Kolmogorov在1958年將Shannon 熵的公式引入動力系統, 用來研究兩個動力系統的同構問題。
【舉例】來說：假設甲拋擲一個錢幣，乙對丙大喊一聲說：「是人頭！」，則乙對丙的通訊中到底包含了多少資訊呢？
1.若乙的眼力無疑，觀察的正確性是百分百可靠，即訊息能正確傳播的機率為 pcorrect = 1；
而錢幣出現人頭的機率為pi = 1/2，因此 Information Entropy，ΔI = A*log22 。
2.如果乙老眼昏花，看錯的機率是 20％，則 Information Entropy，ΔI = A*log21.6 = 0.47*A。
習慣上我們用 bit(log22 = 1 bit）做為資訊熵的單位，因此比例常數 A 在使用不同對數時有不同的數值。
一條資訊的信息量大小和它的不確定性有直接的關係。
比如說，我們要搞清楚一件非常非常不確定的事，或是我們一無所知的事情，就需要瞭解大量的資訊。相反，如果我們對某件事已經有了較多的瞭解，我們不需要太多的資訊就能把它搞清楚。所以，從這個角度來說，我們可以將不確定性(自由度)的多寡做為信息量的度量。
那麼我們如何量化的度量信息量呢？我們來看一個例子：世界盃賽開賽前，大家都很關心誰會是本屆世界盃冠軍？
假如我錯過了看世界盃，賽後我問一個知道比賽結果的觀眾“哪支球隊是冠軍”？ 他不願意直接告訴我， 而要讓我猜，並且我每猜一次，他就要收一元錢才肯告訴我是否猜對了，那麼我需要付給他多少錢才能知道誰是冠軍呢?
我可以把球隊編上號，從 1 到 32， 然後提問： “冠軍的球隊在 1-16 號中嗎?” 假如他告訴我猜對了， 我會接著問： “冠軍在 1-8 號中嗎?” 假如他告訴我猜錯了， 我自然知道冠軍隊在 9-16 中。 這樣只需要猜五次， 我就能知道哪支球隊是冠軍。所以，誰是世界盃冠軍這條消息的信息量只值五塊錢。
當然，香農不是用錢，而是用 bit的個概念來度量信息量。 一個bit是一位元二進位數字，電腦的一個位元組(byte)是八個bit。
上面的例子中，這條消息的信息量是五 bit。如果有六十四個隊進入決賽，那麼“誰世界盃冠軍”的信息量就會是6個 bit。到此我們可以發現：原來香農的信息量( bit數)來自：所有可能結果的 log 函數；log32=5, log64=6。
事實上，我們不需要猜五次才能猜出誰是冠軍，因為象巴西、德國、義大利這樣的球隊得冠軍的可能性比日本、美國、韓國等隊大的多(這是domain knowledge，事前已知)。因此，我們第一次猜測時不需要把 32 個球隊等分成兩個組，我們可以利用先備知識和分組技巧；如：
可以把少數幾個最可能的球隊分成一組，把其它隊分成另一組。然後我們猜冠軍球隊是否在那幾隻熱門隊中。我們重複這樣的過程，根據奪冠概率對剩下的候選球隊分組，直到找到冠軍隊。這樣，我們也許三次或四次就猜出結果。因此，當每個球隊奪冠的可能性（概率）不等時，“誰是世界盃冠軍”這資訊的信息量則少於5 bit。或者，另一種說法：
融入更多已知訊息而減少訊息的不確定性，故降低了“誰是世界盃冠軍”這資訊的信息量。因為訊息量(內涵)少了，就更容易能猜出正確的冠軍得主。
香農所提出的 information entroipy的公式為：
變數的不確定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大。
例：觀看電視的一個畫面, 得到多少訊息?例如假設畫面分成500行與600列, 一共有500 ×600 = 300, 000 個光點， 再假設每一個光點有10種可分辨的顏色選擇， 一個畫面由許多小光點組成，一個畫面一共有500 ×600 = 300, 000 個光點，每一個光點有10種可能的顏色，於是總共有10^300,000 種機率都相等的可能畫面。因此，觀看一個畫面的訊息量為： 300, 000* log2 10 = 10^6 bits
有了“熵”這個概念，我們就可以回答本文開始提出的問題，即一本五十萬字的中文書平均有多少信息量？
我們知道常用的漢字（一級二級國標）大約有 7000 字。
假設每個國字的用字出現率均等，那麼我們大約需要 13 個比特（即 13 位二進位數字）表示一個漢字(2^13=8192)。
但漢字的使用是不平衡的。實際上，前 10% 的漢字占文本的 95% 以上。因此，即使不考慮上下文的相關性，而只考慮每個漢字的獨立的概率，那麼，每個漢字的資訊熵大約也只有 8-9 個比特。
如果我們再考慮上下文相關性，每個漢字的資訊熵只有5比特左右。
所以，一本五十萬字的中文書，信息量大約是 250 萬比特。
如果用一個好的演算法壓縮一下，整本書可以存成一個 320KB 的檔。如果我們直接用兩位元組的國標編碼存儲這本書，大約需要 1MB 大小，是壓縮檔的三倍。這兩個數量的差距，在資訊理論中稱作“冗餘度”（redundancy)。 需要指出的是我們這裡講的 250 萬比特是個平均數，同樣長度的書，所含的信息量可以差很多。如果一本書重複的內容很多，它的信息量就小，冗餘度就大。 不同語言的冗餘度差別很大，而一般認為漢語的冗餘度是相對小的。
Shannon應用「熵」的觀念來定義訊號傳輸中的資訊量，稱為「資訊熵」(information entropy)，其定義為：
pi 則是被傳播的事件發生的可能機率，
A 則是與「資訊熵」相關的比例常數。
[Example in Matlab]
testA = [1 1 1 1];
testB = [1 2 3 4];
testC = [1 1 2 3];
result = [entropy(0.1*testA') entropy(0.1*testB') entropy(0.1*testC')];
disp( result );
0 2.0000 1.5000
【參考資料】
《科學發展》2004年5月，377期，34～37頁
數學之美系列 4 -- 怎樣度量資訊? 2006年4月26日 上午 08:11:00 發表者：吳軍，Google 研究員
如何找出劣幣? —簡介訊息與熵的概念 蔡聰明- 中研院數學研究所，www.math.sinica.edu.tw/math_media/d223/22303.pdf
http://matlabdatamining.blogspot.tw/2006/11/introduction-to-entropy.html
當我們觀測到或聽到一個事件發生時，就得到了一些「訊息」。「訊息量」指的是：該訊息的內涵多寡，更清楚地說：也就是各種不同結果的可能性大小。例如，思考慮下面者兩個事件：
「太陽從東邊出來」與「人咬狗」。
第一句話幾乎是必然事件, 機率為1，這條訊息一點都不令人驚訝，該事件僅有唯一必然結果，無其他可能，訊息量為零。而「人咬狗」是一件稀有事件，機率很小，聽到這件事會覺得很驚訝，因為這件事包含很多不同的可能，訊息量(內涵)較大。因此, 訊息的多寡跟機率很有關係。 一個機率很小的事件，可以提供越多的訊息。換言之，事件的訊息量是其機率的函數。
一般而言，作一個隨機實驗, 令事件A的機率P(A) = p, 今觀測到A 發生, 我們得到訊息 I = f(p) 。訊息量為機率的函數，但問題是： f 是什麼樣的函數呢？回答這個問題之前，有必要先釐清關於「熵」的概念：
「熵」是熱力學的概念，由德國物理學家克勞修斯（Rudolf Clausius）在一八六四年所提出。「熵」的被用來度量一個混亂、不確定系統，其混亂或不確定的程度。熵是對整個隨機實驗, 表現為機率分佈(p1, . . . , pn), 所呈現出的不確定性或混亂程度之度量。
與「熵」相關的理論發展：熱力學第二定律：獨立系統的熵只會增加不會減少。Boltzmann 在1896年強調熱力學的熵與機率具有密切關係。1928年Hartley 將Boltzmann 的想法引進訊息論中, 得到Hartley公式：I=logN 。1948年Shannon 再推廣成Shannon 公式(詳下)。Kolmogorov在1958年將Shannon 熵的公式引入動力系統, 用來研究兩個動力系統的同構問題。
The formula for entropy in the case of a two-valued variable is as follows:
entropy = -( p * log(p) + (1-p) * log(1-p) )
...where p is the probability of one class (it doesn't matter which one).
Entropy is exactly such a measure. It was devised in the late 1940s by Claude Shannon when he invented information theory (then known as communication theory). Entropy can be applied to variables with more than two values, but graphing the two-value case is much more intuitive.
發展至今，「熵」的概念應用已遍及科學、數學、管理等各領域，然而資訊的度量該如何應用「熵」的概念呢？。
熵與資訊的關係
美國數學家，資訊理論的奠基人Claude Elwood Shannon 在他的著名論文《通信的數學理論》(1948)中提出計算訊息量的公式，(一個訊息由n 個符號所構成，每個符號出現的機率為p)，則有：
這個公式和熱力學的熵的計算方式一樣，故也稱為熵(資訊理論)。從公式可知：
當機率越平均時，也就是個事件機率越均勻(意謂：越無法預測，也越模糊)，「不確定性」(uncertainty)最高，【訊息熵】最大。
故，訊息可以視為「不確定性」或「選擇的自由度」的度量。(information is a measure of one's freedom of choice when one selects a message
)
1.若乙的眼力無疑，觀察的正確性是百分百可靠，即訊息能正確傳播的機率為 pcorrect = 1；
而錢幣出現人頭的機率為pi = 1/2，因此 Information Entropy，ΔI = A*log22 。
2.如果乙老眼昏花，看錯的機率是 20％，則 Information Entropy，ΔI = A*log21.6 = 0.47*A。
習慣上我們用 bit(log22 = 1 bit）做為資訊熵的單位，因此比例常數 A 在使用不同對數時有不同的數值。
【資訊】是個很抽象的概念。我們常常說資訊很多，或者資訊較少，但卻很難說清楚資訊到底有多少。比如：一本五十萬字的中文書到底有多少信息量？1948 年，香農提出了“信息熵” 的概念後，才解決了對資訊的量化度量問題。
一條資訊的信息量大小和它的不確定性有直接的關係。
比如說，我們要搞清楚一件非常非常不確定的事，或是我們一無所知的事情，就需要瞭解大量的資訊。相反，如果我們對某件事已經有了較多的瞭解，我們不需要太多的資訊就能把它搞清楚。所以，從這個角度來說，我們可以將不確定性(自由度)的多寡做為信息量的度量。
那麼我們如何量化的度量信息量呢？我們來看一個例子：世界盃賽開賽前，大家都很關心誰會是本屆世界盃冠軍？
假如我錯過了看世界盃，賽後我問一個知道比賽結果的觀眾“哪支球隊是冠軍”？ 他不願意直接告訴我， 而要讓我猜，並且我每猜一次，他就要收一元錢才肯告訴我是否猜對了，那麼我需要付給他多少錢才能知道誰是冠軍呢?
我可以把球隊編上號，從 1 到 32， 然後提問： “冠軍的球隊在 1-16 號中嗎?” 假如他告訴我猜對了， 我會接著問： “冠軍在 1-8 號中嗎?” 假如他告訴我猜錯了， 我自然知道冠軍隊在 9-16 中。 這樣只需要猜五次， 我就能知道哪支球隊是冠軍。所以，誰是世界盃冠軍這條消息的信息量只值五塊錢。
當然，香農不是用錢，而是用 bit的個概念來度量信息量。 一個bit是一位元二進位數字，電腦的一個位元組(byte)是八個bit。
上面的例子中，這條消息的信息量是五 bit。如果有六十四個隊進入決賽，那麼“誰世界盃冠軍”的信息量就會是6個 bit。到此我們可以發現：原來香農的信息量( bit數)來自：所有可能結果的 log 函數；log32=5, log64=6。
事實上，我們不需要猜五次才能猜出誰是冠軍，因為象巴西、德國、義大利這樣的球隊得冠軍的可能性比日本、美國、韓國等隊大的多(這是domain knowledge，事前已知)。因此，我們第一次猜測時不需要把 32 個球隊等分成兩個組，我們可以利用先備知識和分組技巧；如：
可以把少數幾個最可能的球隊分成一組，把其它隊分成另一組。然後我們猜冠軍球隊是否在那幾隻熱門隊中。我們重複這樣的過程，根據奪冠概率對剩下的候選球隊分組，直到找到冠軍隊。這樣，我們也許三次或四次就猜出結果。因此，當每個球隊奪冠的可能性（概率）不等時，“誰是世界盃冠軍”這資訊的信息量則少於5 bit。或者，另一種說法：
融入更多已知訊息而減少訊息的不確定性，故降低了“誰是世界盃冠軍”這資訊的信息量。因為訊息量(內涵)少了，就更容易能猜出正確的冠軍得主。
香農所提出的 information entroipy的公式為：
H = -（p1*log p1 + p2 * log p2 + ．．． ＋p32 *log p32)
其中，p1，p2 ， ．．．，p32 分別是這 32 個球隊奪冠的概率。用 H 表示，稱為“資訊熵” (Entropy)，單位是比特，代表：訊息所包含準確的信息量。
當 32 個球隊奪冠概率相同時，對應的資訊熵等於五比特。有數學基礎的讀者還可以證明上面公式的值不可能大於五。對於任意一個隨機變數 X（比如得冠軍的球隊），它的熵定義如下：變數的不確定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大。
例：觀看電視的一個畫面, 得到多少訊息?例如假設畫面分成500行與600列, 一共有500 ×600 = 300, 000 個光點， 再假設每一個光點有10種可分辨的顏色選擇， 一個畫面由許多小光點組成，一個畫面一共有500 ×600 = 300, 000 個光點，每一個光點有10種可能的顏色，於是總共有10^300,000 種機率都相等的可能畫面。因此，觀看一個畫面的訊息量為： 300, 000* log2 10 = 10^6 bits
有了“熵”這個概念，我們就可以回答本文開始提出的問題，即一本五十萬字的中文書平均有多少信息量？
我們知道常用的漢字（一級二級國標）大約有 7000 字。
假設每個國字的用字出現率均等，那麼我們大約需要 13 個比特（即 13 位二進位數字）表示一個漢字(2^13=8192)。
但漢字的使用是不平衡的。實際上，前 10% 的漢字占文本的 95% 以上。因此，即使不考慮上下文的相關性，而只考慮每個漢字的獨立的概率，那麼，每個漢字的資訊熵大約也只有 8-9 個比特。
如果我們再考慮上下文相關性，每個漢字的資訊熵只有5比特左右。
所以，一本五十萬字的中文書，信息量大約是 250 萬比特。
如果用一個好的演算法壓縮一下，整本書可以存成一個 320KB 的檔。如果我們直接用兩位元組的國標編碼存儲這本書，大約需要 1MB 大小，是壓縮檔的三倍。這兩個數量的差距，在資訊理論中稱作“冗餘度”（redundancy)。 需要指出的是我們這裡講的 250 萬比特是個平均數，同樣長度的書，所含的信息量可以差很多。如果一本書重複的內容很多，它的信息量就小，冗餘度就大。 不同語言的冗餘度差別很大，而一般認為漢語的冗餘度是相對小的。
Shannon應用「熵」的觀念來定義訊號傳輸中的資訊量，稱為「資訊熵」(information entropy)，其定義為：
ΔI = -A*log( pcorrect/pi )
pcorrect 是資訊傳播時維持正確的機率；pi 則是被傳播的事件發生的可能機率，
A 則是與「資訊熵」相關的比例常數。
熵表示的是不確定性的量度。當未知的信息越多時(自由度越高)，熵就越大。
---------------------------------------------------------------------------------[Example in Matlab]
testA = [1 1 1 1];
testB = [1 2 3 4];
testC = [1 1 2 3];
result = [entropy(0.1*testA') entropy(0.1*testB') entropy(0.1*testC')];
disp( result );
0 2.0000 1.5000
【參考資料】
《科學發展》2004年5月，377期，34～37頁
數學之美系列 4 -- 怎樣度量資訊? 2006年4月26日 上午 08:11:00 發表者：吳軍，Google 研究員
如何找出劣幣? —簡介訊息與熵的概念 蔡聰明- 中研院數學研究所，www.math.sinica.edu.tw/math_media/d223/22303.pdf
http://matlabdatamining.blogspot.tw/2006/11/introduction-to-entropy.html
No comments:
Post a Comment