第3章 信息論基本概念

1、信息論基本概念 概要 n基本概念 n鏈?zhǔn)椒▌t nJensen不等式 n數(shù)據(jù)處理不等式 n費(fèi)諾不等式 n漸進(jìn)均分性定理 n數(shù)據(jù)壓縮(AEP的推論) 基本概念-熵 nX是一個(gè)離散隨機(jī)變量是一個(gè)離散隨機(jī)變量, 取值空間為取值空間為X X, 概率密度函數(shù) p(x)=Pr(X=x), xX X; n定義 一個(gè)離散型隨機(jī)變量X的熵H(X)定義為 H(X)=-xX Xp(x)log p(x) n單位為比特(2為底), 奈特(e為底); n規(guī)定0log0=0; nH(X)0; nHb(X)=logbaHa(X); nH(p)=-plogp-(1-p)log(1-p); 基本概念-聯(lián)合熵與條件熵 n定義 對(duì)于服

2、從聯(lián)合分布為p(x, y)的一對(duì)離散隨機(jī)變量(X, Y), 其聯(lián)合熵H(X, Y)(joint entropy)定義為 H(X, Y)=-xX XyY Yp(x, y)logp(x, y) 亦即 H(X, Y)=-Elogp(x, y) n定義 若(X,Y)p(x, y), 條件熵(conditional entropy) H(Y|X)定義為: H(Y|X)=xX Xp(x)H(Y|X=x) =-xX Xp(x) yY Yp(y|x)logp(y|x) =-xX XyY Yp(x,y)logp(y|x) =-Ep(x,y)logp(Y|X) 基本概念-相對(duì)熵與互信息 n定義 兩個(gè)概率密度函數(shù)為

3、p(x)和q(x)之間的相對(duì)熵(或Kullback- Leibler距離)定義為 規(guī)定0log(0/0)=0, 0log(0/q)=0, plog(p/0); n定義 考慮兩個(gè)隨機(jī)變量X和Y, 他們的聯(lián)合概率密度函數(shù)為p(x, y), 其邊際概率密度函數(shù)分別為p(x)和p(y). 互信息I(X;Y)為聯(lián)合分布p(x, y)和乘積分布p(x)p(y)之間的相對(duì)熵, 即: )( )( log )( )( log| Xq Xp E xq xp xpqpD p x X )()( ),( log )()(|),( )()( , log,);( ),( YpXp YXp E ypxpyxpD ypxp y

4、xp yxpYXI yxp xy XY 基本概念-熵與互信息的關(guān)系 nI(X;Y)=H(X)-H(X|Y) 互信息I(X;Y)是在給定Y知識(shí)的條件下X的不確定度的縮減量. nI(X;Y)=H(Y)-H(Y|X) X含有Y的信息量等同于Y含有X的信息量. nI(X;Y)=H(X)+H(Y)-H(X, Y) nI(X;Y)=I(Y;X) nI(X;X)=H(X) 基本概念-條件互信息 n條件互信息熵: 在給定Z時(shí)由于Y的知識(shí)而引起關(guān)于X的 不確定度的縮減量. n定義 隨機(jī)變量X和Y在給定隨機(jī)變量Z時(shí)的條件互信息 (conditional mutual information)定義為 )|()|(

5、)|,( log ),|()|()|;( ),( ZYpZXp ZYXp E ZYXHZXHZYXI zyxp 鏈?zhǔn)椒▌t n定理2.2.1(鏈?zhǔn)椒▌t) H(X, Y)=H(X)-H(Y|X) n定理2.5.1(熵的鏈?zhǔn)椒▌t) 設(shè)隨機(jī)變量X1, X2, ., Xn服從p(x1, x2, ., xn), 則 H(X1, X2, ., Xn)=ni=1H(Xi|Xi-1, ., X1) 證明: 重復(fù)利用定理2.2.1的展開(kāi)法則可得. n定理2.5.2(互信息的鏈?zhǔn)椒▌t) I(X1, X2, ., Xn;Y)=ni=1I(Xi;Y|Xi-1, ., X1) 證明: I(X1, X2, ., Xn;Y)

6、 =H(X1, X2, ., Xn)-H(X1, X2, ., Xn|Y) =ni=1H(Xi|Xi-1, ., X1)- ni=1H(Xi|Xi-1, ., X1, Y) =ni=1I(Xi;Y|Xi-1, ., X1) Jensen不等式(1) n定義 若對(duì)于任意的x1, x2(a, b)及01, 滿足 f(x1+(1-)x2) f(x1)+(1-)f(x2) 則稱(chēng)函數(shù)f(x)在區(qū)間上是凸的(convex). n定理2.6.2 (Jensen不等式)若給定凸函數(shù)f和一個(gè)隨機(jī)變量X, 則 Ef(X)f(EX) n證明: 這里只證明離散分布情形, 且對(duì)分布點(diǎn)的個(gè)數(shù)進(jìn)行歸納證明. 對(duì)于兩點(diǎn)分布,

7、 不等式變?yōu)?p1f(x1)+p2f(x2)f(p1x1+p2x2) 這由凸函數(shù)的定義可直接得到. 假定當(dāng)分布點(diǎn)個(gè)數(shù)為k-1時(shí), 定理成立, 此時(shí)記 pi=pi/(1-pk)(i=1, 2, ., k-1), 則有 k i ii k i iikkk k i iikkk k i iikkk k i ii xpf xppxpf xpfpxfp xfppxfpxfp 1 1 1 1 1 1 1 1 )1 ( )1 ()( )()1 ()()( 其中第一個(gè)不等式由歸納法假設(shè)得到, 第二個(gè)不等式由凸性的定義可得. Jensen不等式(2)-信息不等式 n定理2.6.3 (信息不等式) 設(shè)p(x), q(

8、x)(xX)為兩個(gè) 概率密度函數(shù), 則 D(p|q)0 當(dāng)且僅當(dāng)對(duì)任意的x, p(x)=q(x), 等號(hào)成立. 證明: 設(shè)A=x:p(x)0為 p(x)的支撐集,則如右. 其中,(1)由Jensen不等式 得到. 0 1log )(log )(log )( )( )(log )( )( log)( )( )( log)(| ) 1 ( Xx Ax Ax Ax Ax xq xq xp xq xp xp xq xp xq xp xpqpD Jensen不等式(3) n推論(互信息的非負(fù)性) 對(duì)任意兩個(gè)隨機(jī)變量X和Y, I(X;Y)0 當(dāng)且僅當(dāng)X與Y相互獨(dú)立, 等號(hào)成立. 證明: I(X;Y)=D(

9、p(x,y)|p(x)p(y)0, 當(dāng)且僅當(dāng) p(x,y)=p(x)p(y)(即X與Y為相互獨(dú)立), 等號(hào)成立. n定理2.6.5 (條件作用使熵減少)(信息不會(huì)有負(fù)面影響) H(X|Y)H(X) 當(dāng)且僅當(dāng)X與Y相互獨(dú)立,等號(hào)成立. 證明: 0I(X;Y)=H(X)-H(X|Y) 數(shù)據(jù)處理不等式(1) n定義 如果Z的條件分布依賴(lài)于Y的分布, 而與X 是條件獨(dú)立的, 則稱(chēng)隨機(jī)變量X, Y, Z依序構(gòu)成馬 爾可夫(Markov)鏈(記為XYZ). 具體講, 若X, Y, Z的聯(lián)合概率密度函數(shù)可寫(xiě)為 p(x,y,z)=p(x)p(y|x)p(z|y) n則X, Y, Z構(gòu)成馬爾可夫鏈XYZ. 數(shù)據(jù)

10、處理不等式(2) n定理2.8.1 (數(shù)據(jù)處理不等式)若XYZ, 則有 I(X;Y)I(X;Z). 證明: 有鏈?zhǔn)椒▌t, 將互信息以兩種不同方式展開(kāi): I(X;Y,Z)=I(X;Z)+I(X;Y|Z) =I(X;Y)+I(X;Z|Y) 由于在給定Y的情況下, X與Z是條件獨(dú)立的, 因此有 I(X;Z|Y)=0. 又由于I(X;Y|Z)0, 則有 I(X;Y)I(X;Z) 當(dāng)且僅當(dāng)I(X;Y|Z)=0(即XZY構(gòu)成馬爾可夫鏈), 等號(hào) 成立. 類(lèi)似地, 可以證明I(Y;Z)I(X;Z). 數(shù)據(jù)處理不等式(3) n推論 特別地, 如果Z=g(Y), 則I(X;Y)I(X;g(Y). 證明: XYg

11、(Y)構(gòu)成馬爾可夫鏈. 這說(shuō)明數(shù)據(jù)Y的函數(shù)不會(huì)增加關(guān)于X的信息量. n推論 如果XYZ, 則I(X;Y|Z)I(X;Y). 證明: 因?yàn)镮(X;Y,Z)=I(X;Z)+I(X;Y|Z) =I(X;Y)+I(X;Z|Y) 以及利用I(X;Z|Y)=0(由馬爾可夫性), I(X;Z)0, 我們有 I(X;Y|Z)I(X;Y) n于是, 通過(guò)觀察”順流”的隨機(jī)變量Z, 可以看到X與Y的 依賴(lài)程度會(huì)有所降低(或保持不變). n注意: 當(dāng)X, Y, Z不構(gòu)成馬爾可夫鏈時(shí), 有可能 I(X;Y|Z)I(X;Y). 費(fèi)諾不等式(1) n定理2.10.1(費(fèi)諾不等式) 對(duì)于任何滿足XYX的估計(jì)量X, 設(shè) Pe

12、=PrXX, 有 H(Pe)+Pelog|X|H(X|X)H(X|Y) (1) 上述不等式可以減弱為 1+ Pelog|X|H(X|Y) 或 Xlog 1)|( YXH P e 注釋: 明顯地, 有式(1)可知Pe=0可推出H(X|Y)=0. 費(fèi)諾不等式(2) n證明: 定義一個(gè)誤差隨機(jī)變量E, 當(dāng)XX時(shí), E=1; 當(dāng)X=X時(shí), E=0. n利用熵的鏈?zhǔn)椒▌t將H(E,X|X)以兩種不同方式展開(kāi), 有 X X log)( log0)1 ()( ) 1,|() 1Pr() 0,|() 0Pr()( ),|()( ),|()( ),|()|( 0)|( ),|()|(),( ee eee e e

13、PPH PPPH EXXHEEXXHEPH XEXHPH XEXHEH XEXHXEH XXH XXEHXXHXXEH 因?yàn)閄YX構(gòu)成馬爾科夫鏈,由數(shù)據(jù)處理不等式有I(X;X)I(X;Y), 從而 H(X|X)H(X|Y). 于是,有 H(Pe)+Pelog|X|H(X|X)H(X|Y) 漸進(jìn)均分性定理(1) n定義(隨機(jī)變量的收斂) 給定一個(gè)隨即變量序列X1, X2, . 序 列X1, X2, 收斂于隨機(jī)變量X有如下三種情形: 1. 如果對(duì)任意0, Pr|Xn-X|0, 則稱(chēng)為依概率收斂. 2. 如果E(Xn-X)20, 則稱(chēng)為均方收斂. 3. 如果PrlimnXn=X=1, 則稱(chēng)為以概率1

14、(或稱(chēng)幾乎處處)收 斂. n定理3.1.1(AEP) 若X1, X2, , Xn為i.i.dp(x), 則 -(1/n)logp(X1, X2, , Xn)H(X) 依概率 n證明: 獨(dú)立隨機(jī)變量的函數(shù)依然是獨(dú)立隨機(jī)變量. 因此, 由于 Xi是i.i.d., 從而logp(Xi)也是i.i.d. 因而, 由弱大數(shù)定律, -(1/n)logp(X1, X2, , Xn)= -(1/n)ilogp(Xi) -Elogp(X) 依概率 = H(X) n這就證明了該定理. 漸進(jìn)均分性定理(2) n定義 關(guān)于p(x)的典型集A(n)(typical set)是序列(x1, x2, ., xn)Xn的集

15、合, 且滿足性質(zhì): 2-n(H(X)+)p(x1, x2, ., xn)2-n(H(X)-) 作為漸進(jìn)均分性的一個(gè)推論, 可以證明典型集A(n)有如下性質(zhì): n定理3.1.2 1. 如果(x1, x2, ., xn)A(n), 則H(X)-(1/n)logp (x1, x2, ., xn)H(X)+. 2. 當(dāng)n充分大時(shí), PrA(n)1-. 證明: 性質(zhì)1的證明可以直接由A(n)的定義得到. 性質(zhì)2由定理3.1.1直接得到, 這是由于當(dāng)n時(shí), 事件 (X1, X2, , Xn)A(n)的概率趨于1. 于是對(duì)任意0, 存在n0, 使得當(dāng)nn0時(shí), 有 Pr|-(1/n)logp(X1, X2,

16、 , Xn)-H(X)|1- 令=, 即可得到性質(zhì)2. 漸進(jìn)均分性定理(2) )()( )()( )( )( )( 2)1 (, 2 2 1 ,1, )( XHnn nXHn A XHn n n A A A An n 所以 所以充分大時(shí)證明：當(dāng) x Pr Pr .2, 2 2 )( )(1 )()( )()( )( )( )( XHnn nXHn A XHn A A A p p n n 所以 證明： x x x x x X 3. |A(n)|2n(H(X)+), 其中|A|表示集合A中的元素個(gè)數(shù). 4. 當(dāng)n充分大時(shí), |A(n)|(1-)2n(H(X)-). 數(shù)據(jù)壓縮(1) n設(shè)X1, X2

17、, , Xn為服從概率密度函數(shù)p(x)的i.i.d隨機(jī)變量下面 對(duì)隨機(jī)序列Xn進(jìn)行壓縮. n編碼: n1. 將Xn中的序列劃分為兩個(gè)集合: 典型集A(n)及其補(bǔ)集. n2. 將每個(gè)集合中的所有元素按照某種順序排序. n3. 用n(H+)+1比特表示A(n)中元素的序號(hào), 并且在這些序 號(hào)前加0. n4. 對(duì)于不屬于A(n)中元素用nlog|X|+1比特表示其序號(hào),并 且在這些序號(hào)前加1. n上述編碼方案有如下特點(diǎn): n編碼一一對(duì)應(yīng), 起始位標(biāo)識(shí)了緊隨碼字的長(zhǎng)度. n對(duì)非典型集A(n)c的元素作了枚舉, 沒(méi)有考慮A(n)c元素個(gè)數(shù) 實(shí)際上少于Xn中元素個(gè)數(shù). n典型序列具有較短的描述長(zhǎng)度nH. 數(shù)據(jù)壓縮(2) 下面證明上述編碼方案的碼字平均長(zhǎng)度為nH(X). n下面用記號(hào)xn表示x1, x2, ., xn. 設(shè)l(xn)表示相應(yīng)于xn的碼字長(zhǎng)度. 若n 充分大, 使得PrA(n)1-, 于是, 碼字長(zhǎng)度的數(shù)學(xué)期望為 ) ( 2log) 2logPr)Pr )2log(Pr)2)Pr )2log)()2)( )()()()( )()( )()( )()( )()( )()( Hn nHn n