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

1、信息論基本概念概要n基本概念n鏈式法則nJensen不等式n數(shù)據(jù)處理不等式n費諾不等式n漸進均分性定理n數(shù)據(jù)壓縮(AEP的推論)基本概念-熵nX是一個離散隨機變量是一個離散隨機變量, 取值空間為取值空間為X X, 概率密度函數(shù)p(x)=Pr(X=x), xX X;n定義 一個離散型隨機變量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定義 對于服從聯(lián)合分布為p(x, y)的一對離散隨機

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)基本概念-相對熵與互信息n定義 兩個概率密度函數(shù)為p(x)和q(x)之間的相對熵(或Kullbac

3、k-Leibler距離)定義為 規(guī)定0log(0/0)=0, 0log(0/q)=0, plog(p/0);n定義 考慮兩個隨機變量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)之間的相對熵, 即: )()(log)()(log|XqXpExqxpxpqpDpxX)()(),(log)()(|),()()(,log,);(),(YpXpYXpEypxpyxpDypxpyxpyxpYXIyxpxy XY基本概念-熵與互信息的關(guān)系nI(X;Y)=H(X)-H(X|Y)互信息I(X

4、;Y)是在給定Y知識的條件下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時由于Y的知識而引起關(guān)于X的不確定度的縮減量.n定義 隨機變量X和Y在給定隨機變量Z時的條件互信息(conditional mutual information)定義為)|()|()|,(log),|()|()|;(),(ZYpZXpZYXpEZYXHZXHZYXIzyxp鏈式法則n定理2.2.1(鏈式法則)H(X, Y)

5、=H(X)-H(Y|X)n定理2.5.1(熵的鏈式法則) 設(shè)隨機變量X1, X2, ., Xn服從p(x1, x2, ., xn), 則H(X1, X2, ., Xn)=ni=1H(Xi|Xi-1, ., X1)證明: 重復利用定理2.2.1的展開法則可得.n定理2.5.2(互信息的鏈式法則)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定義 若對于任意的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和一個隨機變量X, 則Ef(X)f(EX)n證明: 這里只證明離散分布情形, 且對分布點的個數(shù)進行歸納證明.對于兩點分布, 不等式變?yōu)閜1f(x1)+p2f(x2)f(p1x1+p2x2)這由凸函數(shù)的定義可直接得到. 假定當分布點個數(shù)為k-1時, 定理成立, 此時記pi=pi/(1-pk)(i=1, 2, ., k

7、-1), 則有kiiikiiikkkkiiikkkkiiikkkkiiixpfxppxpfxpfpxfpxfppxfpxfp11111111)1 ()1 ()()()1 ()()(其中第一個不等式由歸納法假設(shè)得到, 第二個不等式由凸性的定義可得.Jensen不等式(2)-信息不等式n定理2.6.3 (信息不等式)設(shè)p(x), q(x)(xX)為兩個概率密度函數(shù), 則D(p|q)0當且僅當對任意的x, p(x)=q(x), 等號成立.證明: 設(shè)A=x:p(x)0為p(x)的支撐集,則如右.其中,(1)由Jensen不等式得到.01log)(log)(log)()()(log)()(log)()(

8、)(log)(|) 1 (XxAxAxAxAxxqxqxpxqxpxpxqxpxqxpxpqpDJensen不等式(3)n推論(互信息的非負性) 對任意兩個隨機變量X和Y,I(X;Y)0當且僅當X與Y相互獨立, 等號成立.證明: I(X;Y)=D(p(x,y)|p(x)p(y)0, 當且僅當p(x,y)=p(x)p(y)(即X與Y為相互獨立), 等號成立.n定理2.6.5 (條件作用使熵減少)(信息不會有負面影響)H(X|Y)H(X)當且僅當X與Y相互獨立,等號成立.證明: 0I(X;Y)=H(X)-H(X|Y)數(shù)據(jù)處理不等式(1)n定義 如果Z的條件分布依賴于Y的分布, 而與X是條件獨立的,

9、 則稱隨機變量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).證明: 有鏈式法則, 將互信息以兩種不同方式展開:I(X;Y,Z)=I(X;Z)+I(X;Y|Z) =I(X;Y)+I(X;Z|Y)由于在給定Y的情況下, X與Z是條件獨立的, 因此有I(X;Z|Y)=0. 又由于I(X;Y|Z)0, 則有I(X;Y)I(X;Z)當且僅當I(X;Y

10、|Z)=0(即XZY構(gòu)成馬爾可夫鏈), 等號成立. 類似地, 可以證明I(Y;Z)I(X;Z).數(shù)據(jù)處理不等式(3)n推論 特別地, 如果Z=g(Y), 則I(X;Y)I(X;g(Y).證明: XYg(Y)構(gòu)成馬爾可夫鏈.這說明數(shù)據(jù)Y的函數(shù)不會增加關(guān)于X的信息量.n推論 如果XYZ, 則I(X;Y|Z)I(X;Y).證明: 因為I(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于是, 通過觀察”順流”的隨機變量Z, 可以看到X與Y的依賴程度會有所降低(或保持不變

11、). n注意: 當X, Y, Z不構(gòu)成馬爾可夫鏈時, 有可能I(X;Y|Z)I(X;Y).費諾不等式(1)n定理2.10.1(費諾不等式) 對于任何滿足XYX的估計量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.費諾不等式(2)n證明: 定義一個誤差隨機變量E, 當XX時, E=1; 當X=X時, E=0.n利用熵的鏈式法則將H(E,X|X)以兩種不同方式展開, 有XXlog)(log0)1 ()() 1,|

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

13、，它是(n1)個符號不確定性的最大值log(n1)與PE的乘積。 漸進均分性定理(1)n定義(隨機變量的收斂) 給定一個隨即變量序列X1, X2, . 序列X1, X2, 收斂于隨機變量X有如下三種情形:1. 如果對任意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證明: 獨立隨機變量的函數(shù)依然是獨立隨機變量. 因此, 由于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這就證明了該定理.漸進均分性定理(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)-)作為漸進均分性的一個推論, 可以證明典型集A(n)有如下性質(zhì):n定理3.1.21. 如果(x1, x2, ., xn)A(n), 則H(X)-(1/n)logp (

15、x1, x2, ., xn)H(X)+.2. 當n充分大時, PrA(n)1-. 證明: 性質(zhì)1的證明可以直接由A(n)的定義得到. 性質(zhì)2由定理3.1.1直接得到, 這是由于當n時, 事件 (X1, X2, , Xn)A(n)的概率趨于1. 于是對任意0, 存在n0, 使得當nn0時, 有Pr|-(1/n)logp(X1, X2, , Xn)-H(X)|1- 令=, 即可得到性質(zhì)2.漸進均分性定理(2)()()()()()()(2)1 (,221,1,)(XHnnnXHnAXHnnnAAAAnn所以所以充分大時證明：當xPrPr.2,22)()(1)()()()()()()(XHnnnXHn

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