費(fèi)諾不等式及數(shù)據(jù)處理

1、信息論基本概念概要n基本概念n鏈?zhǔn)椒▌tnJensen不等式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ì)于服從聯(lián)合分布為p(x, y)的一對(duì)離散隨機(jī)

2、變量(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ù)為p(x)和q(x)之間的相對(duì)熵(或Kullbac

3、k-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|XqXpExqxpxpqpDpxX)()(),(log)()(|),()()(,log,);(),(YpXpYXpEypxpyxpDypxpyxpyxpYXIyxpxy XY基本概念-熵與互信息的關(guān)系nI(X;Y)=H(X)-H(X|Y)互信息I(X

4、;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)定義為)|()|()|,(log),|()|()|;(),(ZYpZXpZYXpEZYXHZXHZYXIzyxp鏈?zhǔn)椒▌tn定理2.2.1(鏈?zhǔn)椒▌t)H(X, Y)

5、=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) =H(X1, X2, ., Xn)-H(X1, X2, ., Xn|Y) =ni=1H(Xi|Xi-1, ., X1)- ni=1H(Xi|Xi-1, ., X1, Y) =n

6、i=1I(Xi;Y|Xi-1, ., X1)Jensen不等式(1)n定義 若對(duì)于任意的x1, x2(a, b)及01, 滿足f(x1+(1-)x2) f(x1)+(1-)f(x2)則稱函數(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)分布, 不等式變?yōu)閜1f(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

7、-1), 則有kiiikiiikkkkiiikkkkiiikkkkiiixpfxppxpfxpfpxfpxfppxfpxfp11111111)1 ()1 ()()()1 ()()(其中第一個(gè)不等式由歸納法假設(shè)得到, 第二個(gè)不等式由凸性的定義可得.Jensen不等式(2)-信息不等式n定理2.6.3 (信息不等式)設(shè)p(x), q(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不等式得到.01log)(log)(log)()()(log)()(log)()(

8、)(log)(|) 1 (XxAxAxAxAxxqxqxpxqxpxpxqxpxqxpxpqpDJensen不等式(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(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的條件分布依賴于Y的分布, 而與X是條件獨(dú)立的,

9、 則稱隨機(jī)變量X, Y, Z依序構(gòu)成馬爾可夫(Markov)鏈(記為XYZ). 具體講, 若X, Y, Z的聯(lián)合概率密度函數(shù)可寫為p(x,y,z)=p(x)p(y|x)p(z|y)n則X, Y, Z構(gòu)成馬爾可夫鏈XYZ.數(shù)據(jù)處理不等式(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

10、|Z)=0(即XZY構(gòu)成馬爾可夫鏈), 等號(hào)成立. 類似地, 可以證明I(Y;Z)I(X;Z).數(shù)據(jù)處理不等式(3)n推論 特別地, 如果Z=g(Y), 則I(X;Y)I(X;g(Y).證明: XYg(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的依賴程度會(huì)有所降低(或保持不變

11、). 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=PrXX, 有H(Pe)+Pelog|X|H(X|X)H(X|Y) (1)上述不等式可以減弱為1+ Pelog|X|H(X|Y)或Xlog1)|(YXHPe注釋: 明顯地, 有式(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), 有XXlog)(log0)1 ()() 1,|

12、() 1Pr() 0,|() 0Pr()(),|()(),|()(),|()|(0)|(),|()|(),(eeeeeeePPHPPPHEXXHEEXXHEPHXEXHPHXEXHEHXEXHXEHXXHXXEHXXHXXEH因?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)費(fèi)諾不等式(3)此外，從費(fèi)諾不等式可以看出，接收到y(tǒng)后關(guān)于x的不確定性分為兩部分: 一部分是指接收到y(tǒng)后是否產(chǎn)生錯(cuò)誤的不確定性H(PE)；另一部分是指當(dāng)錯(cuò)誤發(fā)生后，到底是哪個(gè)輸入符號(hào)發(fā)送而造成錯(cuò)誤的最大不確定性

13、，它是(n1)個(gè)符號(hào)不確定性的最大值log(n1)與PE的乘積。 漸進(jìn)均分性定理(1)n定義(隨機(jī)變量的收斂) 給定一個(gè)隨即變量序列X1, X2, . 序列X1, X2, 收斂于隨機(jī)變量X有如下三種情形:1. 如果對(duì)任意0, Pr|Xn-X|0, 則稱為依概率收斂.2. 如果E(Xn-X)20, 則稱為均方收斂.3. 如果PrlimnXn=X=1, 則稱為以概率1(或稱幾乎處處)收斂.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是

14、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的集合, 且滿足性質(zhì):2-n(H(X)+)p(x1, x2, ., xn)2-n(H(X)-)作為漸進(jìn)均分性的一個(gè)推論, 可以證明典型集A(n)有如下性質(zhì):n定理3.1.21. 如果(x1, x2, ., xn)A(n), 則H(X)-(1/n)logp (

15、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, , Xn)-H(X)|1- 令=, 即可得到性質(zhì)2.漸進(jìn)均分性定理(2)()()()()()()(2)1 (,221,1,)(XHnnnXHnAXHnnnAAAAnn所以所以充分大時(shí)證明：當(dāng)xPrPr.2,22)()(1)()()()()()()(XHnnnXHn

16、AXHnAAAppnn所以證明：xxxxxX3. |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, , 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)()()