第二章Shannon信息論述評

1、第二章 Shannon信息論述評Shannon信息論建立在隨機(jī)事件統(tǒng)計理論的基礎(chǔ)上1。為此，我們先簡述基于頻率論解釋的概率理論，下一章再闡述更廣意義的概率理論2。這里Shannon信息論只是取其要義，我們盡可能使用淺顯易懂的方式敘述，以照顧不熟悉Shannon 理論的讀者。本章還含有對經(jīng)典信息理論的評論，熟悉Shannon 理論的讀者也不妨選看。2.1 基于頻率解釋的概率論 概率論誕生于賭博問題，這里我們也且用擲骰子為例來說明什么是概率。一個骰子可能呈現(xiàn)的數(shù)字是1,2,3,4,5,6中的一個。一般情況下，每個數(shù)字出現(xiàn)的幾率大致相等；比如你擲N600下，1出現(xiàn)的次數(shù)N1大約為100下。設(shè)為110

2、下，則110/600叫做1 出現(xiàn)的幾率（或數(shù)學(xué)幾率）。當(dāng)擲的次數(shù)無窮多時，這個幾率就無窮地接近1/6，1/6就是1出現(xiàn)的概率，即P(X1)1/6其中X表示隨機(jī)變量，對于本例它的取值范圍是集合A1,2,3,4,5,6，即XA。設(shè)一般情況下，Ax1, x2,., xm，按頻率論解釋，概率P(Xxi)被定義為：實驗次數(shù)N為無窮大時，Xxi的次數(shù)Ni和N之比的極限; 即(2.1.1) 按照現(xiàn)代概率論，只要某種測度符合概率的公理化定義，它就構(gòu)成概率測度。這一公理化定義是： 設(shè)是一集合，它的一些子集構(gòu)成Borel域，存在一個映射P：0,1，它滿足條件 (1) P()1; (2) 對于任一Ai，有0 P(A

3、i)1; (3) 若Ai和Aj互不相交，則稱P為上的概率測度。其中(3)被稱為概率的可加性要求。按照這一定義，除了基于頻率論解釋的概率，還存在其他類型的概率(見第三章)。 下面我們簡單地用P(xi)表示P(X=xi)。 對于擲骰子，因為下式P(1)P(2).P(6)1/6成立，所以我們稱X是等概率事件。如果骰子中放了鉛，重心不在骰子中心，則上式將不再成立，各數(shù)字將不再是等概率事件。但是無論如何，總有(2.1.2)上式又叫歸一化條件。 再設(shè)YB y1, y2,., yn。我們稱P(xi, yj)P(Xxi,Yyj)為xi和yj的聯(lián)合概率。根據(jù)定義有(2.1.3)(2.1.4)我們定義P(xi|

4、yj)P(xi, yj)/ P(yj)(2.1.5) 是給定條件yj時xi|的條件概率; 同理,條件概率P(yj| xi)P(xi, yj)/ P(xi)(2.1.6)由(2.1.5)和(2.1.6)得P(xi| yj)P(xi)P(yj|xi)/ P(yj)(2.1.7)這就是著名的Bayes公式。若P(yj |xi)P(yj)，則意味著Yyj和Xxi無關(guān)，這時P(xi, yj)P(xi) P(yj)以上各種概率都是歸一化的。當(dāng)A,B為連續(xù)事件，比如為0,1（實數(shù)區(qū)間）時，P(xi)和P(yj)就變?yōu)閜(x)和p(y)（大寫P變?yōu)樾憄），p(x)和p(y)不再表示概率，而是表示概率密度。p

5、(x,y)等同理。這時有dx(2.1.8) 其他類推。2.2 經(jīng)典通信模型 Shannon信息論中的通信模型如圖2.2.1所示。如果把編譯圖2.2.1 Shannon通信模型 碼部分并入信道，則該模型如圖2.2.2所示。我們且討論信源離散時的情況。這時圖2.2.2 可以具體地變?yōu)閳D2.2.3。 圖2.2.3中從xi到y(tǒng)j的箭頭表示Xxi時Yyj發(fā)生的條件概率是P(yjxi)。我們用P(YX)表示m行n列的條件概率矩陣,因為它是物理信道的抽象，信息論中也稱之為信道。圖2.2.2 簡化的Shannon通信模型圖2.2.3 有噪聲通信模型2. 經(jīng)典信息量公式和Kullback信息公式 為了便于討論，

6、我們從單個事件之間的信息量公式出發(fā)，然后推導(dǎo)出Shannon互信息公式和Shannon熵公式。 經(jīng)典理論中，信息量是對減少的不確定性的度量。它的數(shù)學(xué)表示通常被寫為:(2.1)其中I(xi, yj)是yj提供的關(guān)于xi的信息量; P(xi)是xi的先驗概率，P(xiyj)是xi的后驗概率（給定yj時）。log 表示對數(shù)，可以是自然對數(shù)（以e為底），這時信息量單位是nat; 也可以是以2為底，這時信息量的單位是bit或比特。信息論中一般用bit。 注意:上式所求信息是一系列X和Y發(fā)生后，回過頭來看yj提供關(guān)于xi的信息，而不是某一次yj提供的關(guān)于xi的信息。因為如果某次xi不相應(yīng)yj出現(xiàn)時，就不會

7、有這樣的信息。這就是為什么Shannon 奠基性論文中沒有該公式而且也不談單個信號的信息。后面我們將看到，僅當(dāng)我們考慮預(yù)測和檢驗，并且xi確實相應(yīng)預(yù)測yj發(fā)生時，上式才能用于單個信號比如語句“明天有雨”或電壓表讀數(shù)“230伏”的信息的度量。而經(jīng)典信息論不考慮預(yù)測信息。 上式也可以寫成(2.3.2)等式右邊兩項分別表示先驗不確定性和后驗不確定性。若后驗不確定性為0，則公式變?yōu)?2.3.3)據(jù)Bayes公式可得 (2.3.4）這表明兩個事件相互提供的信息量必然相等。若兩事件相互無關(guān)，則P(xiyj)P(xi)且P(yjxi)P(yj)，I(xi; yj)0。這顯然合理。 值得注意的是，I(xi;

8、yj)也可能是負(fù)的。下面舉個例子看經(jīng)典信息量的計算。 例2.3.1 假設(shè)A,B是互不相容事件集合；X Ax1抽煙多的人，x2抽煙少的人；YB y1有肺病，y2無肺病；P(x1)0.3，P(y1)0.2，P(x1, y1)0.12; 求I(x1; y1)和I(x2; y1)。解P(x1| y1)0.12/0.2=0.6I(x1; y1)log(0.6/0.3)=1 bitP(x2| y1)1- P(x1| y1)=0.4P(x2)1- P(x1)=0.7I(x2; y1)log(0.4/0.7)=-0.81 bit 解畢求I(xi; yj)的數(shù)學(xué)期望就得到y(tǒng)j提供的關(guān)于xi的平均信息量： (2.

9、3.5)上式和Kullbak信息公式類似，但是有更豐富的內(nèi)涵。我們且也稱之為Kullback公式。后面將說明，如果把P(Xyj)理解為預(yù)測的可能性測度，則I(X; yj) 就是預(yù)測和事實一致時的平均信息?？梢宰C明I(X; yj)必然大于0，它不等于X的熵的減量H(X)H(Xyj）該減量可能為負(fù)值。 例2.3.2 在上例的基礎(chǔ)上，求y1提供的關(guān)于X 的平均信息量。解I(X; y1)0.610.4(0.81)0.28 bit 2.4 Shannon互信息公式 同樣，求I(X; yj)的數(shù)學(xué)期望，我們得到X和Y 之間的平均信息量(2.4.1)這就是著名的Shannon互信息公式；其中H(X)和H(Y

10、)分別是X和Y的熵；H(XY)和H(YX)分別是X和Y的條件熵; H(X,Y)是X和Y的聯(lián)合熵。并且(2.4.2) (2.4.3)(2.4.4)H(Y)，H(YX)可以類推。這幾種熵之間存在的關(guān)系是H(X)H(YX)H(X,Y)H(Y)H(XY)(2.4.5）可以證明，上述諸熵皆大于或等于0。 當(dāng)P(yj| xi)0,1（對于所有i，j）或P(YX)0,1 時，表示信道無噪聲，這時H(YX)0，I(X;Y)H(Y)。當(dāng)P(yj| xi)P(yj)時，表明噪聲極大，這時H(YX)H(Y)，I(X;Y)0。 若YX，則H(YX)H(XX)0，I(X;X)H(X)。I(X;X)叫做X的自信息，因為它

11、在數(shù)值上與H(X)相等，所以人們有時也稱H(X)為自信息。但需注意，當(dāng)我們說H(X)是X 的平均信息量時，我們實際上指的是I(X;X)。2.5 連續(xù)信源的熵和交互熵 有人說，連續(xù)信源的Shannon熵存在先天不足4。在經(jīng)典理論中，求連續(xù)信源熵的權(quán)宜方法是把連續(xù)信源離散化，然后用離散信源的Shannon熵度量。 設(shè)Aa,b，我們把a(bǔ),b分成m等份，每個等份的寬度是(ba)/m。再設(shè)第i個區(qū)間的概率密度不變，為p(xi)，則P(xi)p(xi), (2.5.1)令m+，則0，得到X的Shannon熵 (2.5.2)上式中，第二項為無窮大；第一項為Hr(X)，Hr(X)被稱之為相對熵，它一般為有限值

12、，但可能為負(fù)值。比如ba1 且 p(x)1/( ba）時，有p(x)1，從而有當(dāng)信源和信宿皆連續(xù)時，互信息仍然存在，為dxdy(2.5.3) 其中p(x,y)為聯(lián)合概率密度，p(yx)是條件概率密度。Hr(Y)和Hr(Y|X)可從Hr(X)類推。 對于連續(xù)信源，雖然I(X;Y)仍有意義，但是Hr(Y)和Hr(Y|X)等皆無實際意義且可能為負(fù)值。2.6 信道容量和信道編碼 Shannon 定義了兩個重要函數(shù)：信道容量和保真度信息率1,5。關(guān)于后者的理論后來又有所發(fā)展，并且保真度信息率被改稱為信息率失真（information ratedistortion）6。信道容量和信息率失真分別是通信的數(shù)量

13、和質(zhì)量指標(biāo)。如果把通信系統(tǒng)和生產(chǎn)系統(tǒng)相類比，則信道容量就相當(dāng)于生產(chǎn)能力，而信息率失真就相當(dāng)于給定產(chǎn)品質(zhì)量要求時，單位產(chǎn)品所需要的最少勞動量。 首先我們介紹信道容量。 給定信道P(YX)，信源H(X)不同，互信息I(X;Y)也不同。信道容量被定義為：給定信道P(YX)時，改變信源P(X) 使得互信息I(X;Y)達(dá)最大，這個最大值就是信道容量。設(shè)C 是所有可能的信源構(gòu)成的集合，則信道容量C的數(shù)學(xué)定義是(2.6.1) 信道容量告訴我們不要期望用有限容量的信道傳遞過量的信息。求信道容量的具體方法在經(jīng)典信息論中有詳細(xì)討論; 下面我們只簡要介紹一下連續(xù)高斯信道即有正態(tài)分布疊加噪聲的信道的容量。設(shè)XAB(-

14、,+)，疊加性噪聲Z是均值為0，方差（或功率）為的高斯變量，則輸出為YX+Z，并且(2.6.2)(2.6.3)可以證明，在輸出功率Pwo的限制下，Hr(Y)在Y為正態(tài)分布時有最大值;這時I(X;Y)也有最大值： (2.6.4)其中Pwi是輸入功率。上式表示，和輸入功率相比，噪聲功率越小，信道容量越大。 Shannon信道編碼定理告訴我們，給定信道時，只要傳遞的信息小于C，我們總可以通過在原信源和信道之間加一個編碼環(huán)節(jié)作某種編碼，使得在信道輸出端無失真地譯出信源信號的概率無窮地接近于1。編碼的目的實際上就是使信源和信道相匹配。2.7 Shannon熵的編碼意義 使用電報通信的早期，人們用長短不同

15、的信號表示所要傳遞的字母A,B,C,.。設(shè)長短信號分別用0,1表示，則一個字母可用一個0-1碼，比如001表示。后來發(fā)現(xiàn)，用較短的0-1 碼表示經(jīng)常出現(xiàn)的字母，比如E，而用較長的0-1碼表示較少出現(xiàn)的字母，比如X，這樣就能在傳遞相同電文的情況下所用0-1碼的總長度最短，或每個字母所用平均碼長最短。然而，要想不失真地，即在H(XY)0的情況下，傳遞電報電文，平均碼長最多能縮短到多少呢？Shannon理論告訴我們，這個平均碼長的極限就是H(X)（即H(X)的bit數(shù)）。 本節(jié)和下一節(jié)都假設(shè)信源信號前后無關(guān)或信源是無記憶的。 下面我們用一個例子來說明H(X)的編碼意義。它來自文獻(xiàn)7。 例2.7.1

16、假定信源可以輸出8個獨立的消息： A,B,C,D,E,F,G,H；它們出現(xiàn)的概率、各種編碼以及相應(yīng)的平均碼長c如表2.7.1所示。表2.7.1 幾種編碼的平均碼長c xi A B C D E F G P(i) 0.1 0.18 0.4 0.05 0.06 0.1 0.07 0.04 H(X)=2.55等長碼 000 001 011 010 110 111 101 100 c=3.00Fano碼 100 01 00 1110 1101 101 1100 1111 c=2.64Haffman碼 011 001 1 00010 0101 0000 0100 00011 c=2.61 表中結(jié)果顯示，采

17、用適當(dāng)?shù)木幋a方法可使平均碼長c接近H(X)。如果把相繼的幾個字母當(dāng)作一個字來編碼，平均碼長會無限地接近H(X)?？梢奡hannon熵有其客觀性。2.8 限失真編碼和信息率失真論 保真度信息率之所以被改稱為信息率失真，主要是因為Shannon的“保真度”是用失真度來定義的。在廣義信息論中，通信質(zhì)量被認(rèn)為是由主觀信息量的相對多少來確定的，不僅和失真，也和逼真（或信號的意義）有關(guān)，我們將用“保質(zhì)（量)信息率”一詞取而代之。 我們先看限失真編碼問題。 設(shè)信源發(fā)出xi時，信道輸出yj; 則yj可能在不同程度上失真。我們用dij（0,+）表示yj相對于xi的失真量，則Y 相對于X的平均失真量為(2.8.1

18、)dij是怎么來的？在經(jīng)典信息論中，它是主觀人為定義的。當(dāng)xi和yj皆是數(shù)字時，常用的定義是7dijf(yjxi)(2.8.2)f是只增不減函數(shù)。比如dij(yjxi) 2下面舉例說明降低失真要求可以大大縮短平均碼長。 例2.8.1 設(shè)有二元信源，AB0,1，P(x1)P(x2)1/2,我們把信源信號四個分為一組，編譯碼如表2.8.1所示。表2.8.1 有失真編碼組號信源信號編碼譯碼10001 0000 0011 100100000121010 1011 0010 111001101030111 0110 0101 111110011141100 1101 1000 0100111100第一行

19、是說0001和0000等四組碼同樣用00編碼，譯碼同樣得0001; 其他類推。較之無失真編碼，如此編碼使平均失真量由0 升到(3/16)a0.188a，而平均碼長則降低到2/40.5。 現(xiàn)在問:給定信源和限失真D，平均碼長最短能達(dá)多少? Shannon離散無記憶信源限失真編碼定理告訴我們，這一極限就是保真度信息率或信息率失真。 設(shè)D是所要求的平均失真上限，D是所有使d(X,Y)D的信道的集合，則信息率失真被定義為(2.8.3) 之所以說信息率而不說信息是因為I(X;Y)在這里表示的是單位符號傳遞的信息。 求R(D)函數(shù)的一般方法是在一些限制條件下，利用拉氏（Largrange）乘子法，改變P(

20、YX) (反映編譯碼方法改變)，求I(X;Y)的極小值。下面即是。已知(2.8.4)(2.8.5)(2.8.6)其中令P(yj| xi)的泛函(2.8.7)再令F對所有P(yj| xi)的偏導(dǎo)數(shù)為0，得令logii/P(xi)，得(2.8.8)由上式和(2.8.6)得(2.8.9)最后得R(D)函數(shù)的參量表示:（2.8.10a） (2.8.10b）可以證明dR/dDs。s是函數(shù)R(D)的斜率，它的物理意義是增加單位失真量時信息率R的增量。因為R隨D減小而增大，所以s為負(fù)值。 對于連續(xù)信源有類似結(jié)論。 現(xiàn)以二元信源為例說明失真函數(shù)dij對稱情況下R(D) 函數(shù)的計算及其性質(zhì); 5.節(jié)還將討論它在

21、廣義信息論中的形式。設(shè)二元信源和失真如例2.8.1，最后推導(dǎo)出(2.8.11a)(2.8.11b)R(D)函數(shù)如圖2.8.所示。圖中假設(shè)P(x1)P(x2)，H(X)1bit 。圖示實線表明，要想減小D，必須增大R；當(dāng)D0時，R 1 bit ，表示無失真地傳遞信號需要1 bit的互信息。圖2.8.1 二元信源失真對稱時的R(D)函數(shù) 其中虛線部分是按式(2.8.1)畫出來的，由于經(jīng)典理論不考慮謊言信息或負(fù)信息，所以虛線部分不好理解，經(jīng)典信息論中對此也避而不談?？催^本書后面保質(zhì)信息率的討論可以理解。 例2.8.3 設(shè)有連續(xù)信源和信宿AB(,+)，信源呈正態(tài)分布，失真函數(shù)為方差，即d(x,y)(y

22、x)2時，s(D)和R(D)函數(shù)為（詳見5）：(2.8.12)圖2.8.顯示了，當(dāng)D近于0時，R(D)為無窮大。這說明對于連續(xù)信源，失真不可避免。當(dāng)D時，R(D)0；這表示，若允許失真等于y和x的方差，無須信息傳遞，不管X取何值，輸出Y一律等于X的均值即可。圖2.8.2 正態(tài)變量信源在均方誤差準(zhǔn)則下的R(D)函數(shù) 率失真函數(shù)告訴我們在D的限制下，信號單位符號最少需要傳遞多少信息；然而它并沒有告訴我們怎樣對信源編碼才能真地在D的限制下，使I(X;Y)近于R(D)。這是一個復(fù)雜問題。一種較為有效的方法是矢量空間法8。這種方法是，把一組n個信源信號看作是n維矢量空間中的一點，把該空間化成若干塊，每一

23、塊用一個點來代表，即編成同一個碼傳送，并且譯碼譯成同樣的n個信號。例2.8.2就采用了這種方法，不過平均碼長0.5和極限值R(3/16)0.304還有差距; 增大n可以使平均碼長更短。 R(D)函數(shù)的反函數(shù)D(R)為給定信息率R時，失真d(X,Y) 的最小值，也有其優(yōu)化通信意義。 如果dij不是yj相應(yīng)xi時產(chǎn)生的失真量，而是價值損失，則D就表示價值損失限制，R(D) 就表示限價值損失時的最小信息率5。2.9 Shannon信息論的局限性 Shannon或經(jīng)典信息論局限性具體表現(xiàn)在:不便于度量語義信息、感覺信息、信源信道可變時的信息以及單個信號的信息。作為數(shù)據(jù)壓縮理論依據(jù)的率失真理論也遠(yuǎn)不完善

24、。究其原因，乃是因為它只考慮信號傳遞，而不考慮信號的意義或觀察者對信號意義的理解；或者說，它只考慮客觀信息，而不考慮主觀信息。由于不考慮意義問題，它也就不會考慮意義的模糊性或事件之間的相似性; 不考慮預(yù)測和事實檢驗，從而不能度量單個語句、感覺或測量信號的信息。 我們先看忽略意義或語義所導(dǎo)致的種種困難。 如果允許我們總結(jié)經(jīng)驗知識并賦信號以意義，則即使信源信道可變，我們也可以根據(jù)經(jīng)驗知識或信號的意義推測實際發(fā)生的X，從而獲得信息（見4.2節(jié)）。因為Shannon 理論避免考慮意義，信源信道可變時的信息就無法度量。 如果按照Shannon理論度量語言提供的信息，則信息只和語句及事件的概率和條件概率有

25、關(guān)，和語義或人對語言的理解無關(guān)。若某氣象臺總是把有雨報成無雨，把無雨報成有雨，而另一氣象臺總是作正確預(yù)報，按Shannon公式，兩者提供的信息量是同樣的。而實際上，一個人如聽信了錯的預(yù)報，他對事實就更加無知，因而他得到的信息量就應(yīng)該是負(fù)的。 再比如，一個讀數(shù)不正確的溫度表，或一桿斤兩不正確的秤，如按Shannon理論度量信息，則它們和正常的表或秤提供的信息一樣多，而實際上提供的信息更少，甚至是負(fù)的。 控制系統(tǒng)中的信號，比如根據(jù)雷達(dá)測量數(shù)據(jù)所做的飛機(jī)位置的預(yù)測，也是有意義的，控制的依據(jù)就是信號的意義。由于經(jīng)典理論的局限性，涉及意義的信息無法度量，因而預(yù)測評價就只能用失真量，比如用均方差作為尺度。

26、 按照常識，失真時信息就少，不失真時信息就多；失真量應(yīng)能通過信息量得到反映; 常識還告訴我們，把偶然事件預(yù)測正確和把必然事件預(yù)測正確，兩者應(yīng)有不同的評價。后面我們看到用廣義信息或語義信息作為評價尺度不僅可以反映失真，而且可以給更精確、更大膽的預(yù)測以更高的評價。 當(dāng)然，作為客觀信息測度，Shannon 信息量也有其重要意義。但是，現(xiàn)實生活中我們更關(guān)心主觀信息的多少。 Shannon理論要求集合B中皆為互不相容事件。然而，對于語言來說，兩個語句，比如“天將下雨”和“天將下大雨”，作為B中元素，從符號的角度來看是互不相容的，但是它們的意義可能是相容的，比如后者蘊含前者，后者出現(xiàn)等價于兩者同時出現(xiàn)。這種情況使得用Shannon 理論解決語義信息問題更加不可能。對于感覺或測量信息也有類似情況。 我們再看忽略模糊性或元素之間的相似性所導(dǎo)致的種種困難。 Shannon理論要求兩個事件xi和xj 要么完全相同，要么完全不同。若相同的元素構(gòu)成一個子集，則這些子集構(gòu)成集合A的一個劃分。由于這一原因，用Shan