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

1、信息論基本概念,,概要,基本概念鏈?zhǔn)椒▌tJensen不等式數(shù)據(jù)處理不等式費諾不等式漸進均分性定理數(shù)據(jù)壓縮(AEP的推論),基本概念-熵,X是一個離散隨機變量, 取值空間為X, 概率密度函數(shù)p(x)=Pr(X=x), x?X;定義 一個離散型隨機變量X的熵H(X)定義為H(X)=-?x?Xp(x)log p(x)單位為比特(2為底), 奈特(e為底);規(guī)定0log0=0;H(X)?0;Hb(X)=logbaHa(X

2、);H(p)=-plogp-(1-p)log(1-p);,基本概念-聯(lián)合熵與條件熵,定義 對于服從聯(lián)合分布為p(x, y)的一對離散隨機變量(X, Y), 其聯(lián)合熵H(X, Y)(joint entropy)定義為H(X, Y)=-?x?X?y?Yp(x, y)logp(x, y) 亦即 H(X, Y)=-Elogp(x, y)定義 若(X,Y)?p(x, y), 條件熵(conditional entropy) H(

3、Y|X)定義為: H(Y|X)=?x?Xp(x)H(Y|X=x) =-?x?Xp(x) ?y?Yp(y|x)logp(y|x) =-?x?X?y?Yp(x,y)logp(y|x)

4、 =-Ep(x,y)logp(Y|X),基本概念-相對熵與互信息,定義 兩個概率密度函數(shù)為p(x)和q(x)之間的相對熵(或Kullback-Leibler距離)定義為 規(guī)定0log(0/0)=0, 0log(0/q)=0, plog(p/0);定義 考慮兩個隨機變量X和Y, 他們的聯(lián)合概率密度函數(shù)為p(x, y), 其邊際概率密度函數(shù)分別為p(x)和p(y). 互信息I(X;Y)為聯(lián)合

5、分布p(x, y)和乘積分布p(x)p(y)之間的相對熵, 即:,基本概念-熵與互信息的關(guān)系,I(X;Y)=H(X)-H(X|Y)互信息I(X;Y)是在給定Y知識的條件下X的不確定度的縮減量.I(X;Y)=H(Y)-H(Y|X)X含有Y的信息量等同于Y含有X的信息量.I(X;Y)=H(X)+H(Y)-H(X, Y)I(X;Y)=I(Y;X)I(X;X)=H(X),基本概念-條件互信息,條件互信息熵: 在給定Z時由于Y的知

6、識而引起關(guān)于X的不確定度的縮減量.定義 隨機變量X和Y在給定隨機變量Z時的條件互信息(conditional mutual information)定義為,鏈?zhǔn)椒▌t,定理2.2.1(鏈?zhǔn)椒▌t)H(X, Y)=H(X)-H(Y|X)定理2.5.1(熵的鏈?zhǔn)椒▌t) 設(shè)隨機變量X1, X2, ..., Xn服從p(x1, x2, ..., xn), 則H(X1, X2, ..., Xn)=?ni=1H(Xi|Xi-1, ..., X1

7、)證明: 重復(fù)利用定理2.2.1的展開法則可得.定理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

8、(Xi|Xi-1, ..., X1, Y) =?ni=1I(Xi;Y|Xi-1, ..., X1),Jensen不等式(1),定義 若對于任意的x1, x2?(a, b)及0???1, 滿足f(?x1+(1-?)x2)?? f(x1)+(1-?)f(x2)則稱函數(shù)f(x)在區(qū)間上是凸的(convex).定理2.6.2 (Jensen不等式)若給定凸函數(shù)f和一個隨機變量X, 則Ef(X)?f(EX)證

9、明: 這里只證明離散分布情形, 且對分布點的個數(shù)進行歸納證明.對于兩點分布, 不等式變?yōu)閜1f(x1)+p2f(x2)?f(p1x1+p2x2)這由凸函數(shù)的定義可直接得到. 假定當(dāng)分布點個數(shù)為k-1時, 定理成立, 此時記pi’=pi/(1-pk)(i=1, 2, ..., k-1), 則有,其中第一個不等式由歸納法假設(shè)得到, 第二個不等式由凸性的定義可得.,Jensen不等式(2)-信息不等式,定理2.6.3 (信息不等式)

10、設(shè)p(x), q(x)(x?X)為兩個概率密度函數(shù), 則D(p||q)?0當(dāng)且僅當(dāng)對任意的x, p(x)=q(x), 等號成立.證明: 設(shè)A={x:p(x)>0}為p(x)的支撐集,則如右.其中,(1)由Jensen不等式得到.,Jensen不等式(3),推論(互信息的非負性) 對任意兩個隨機變量X和Y,I(X;Y)?0當(dāng)且僅當(dāng)X與Y相互獨立, 等號成立.證明: I(X;Y)=D(p(x,y)||p(x)p

11、(y))?0, 當(dāng)且僅當(dāng)p(x,y)=p(x)p(y)(即X與Y為相互獨立), 等號成立.定理2.6.5 (條件作用使熵減少)(信息不會有負面影響)H(X|Y)?H(X)當(dāng)且僅當(dāng)X與Y相互獨立,等號成立.證明: 0?I(X;Y)=H(X)-H(X|Y),數(shù)據(jù)處理不等式(1),定義 如果Z的條件分布依賴于Y的分布, 而與X是條件獨立的, 則稱隨機變量X, Y, Z依序構(gòu)成馬爾可夫(Markov)鏈(記為X?Y?Z). 具體講

12、, 若X, Y, Z的聯(lián)合概率密度函數(shù)可寫為p(x,y,z)=p(x)p(y|x)p(z|y)則X, Y, Z構(gòu)成馬爾可夫鏈X?Y?Z.,數(shù)據(jù)處理不等式(2),定理2.8.1 (數(shù)據(jù)處理不等式)若X?Y?Z, 則有I(X;Y)?I(X;Z).證明: 有鏈?zhǔn)椒▌t, 將互信息以兩種不同方式展開:I(X;Y,Z)=I(X;Z)+I(X;Y|Z) =I(X;Y)+I(X;Z|Y)由于在給定Y的情況下, X

13、與Z是條件獨立的, 因此有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(即X?Z?Y構(gòu)成馬爾可夫鏈), 等號成立. 類似地, 可以證明I(Y;Z)?I(X;Z).,數(shù)據(jù)處理不等式(3),推論 特別地, 如果Z=g(Y), 則I(X;Y)?I(X;g(Y)).證明: X?Y?g(Y)構(gòu)成馬爾可夫鏈.這說明數(shù)據(jù)Y的函數(shù)不會增加關(guān)于X的信息量.推論 如果X?Y

14、?Z, 則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)于是, 通過觀察”順流”的隨機變量Z, 可以看到X與Y的依賴程度會有所降低(或保持不變). 注意: 當(dāng)X, Y, Z不構(gòu)成馬爾可夫鏈時, 有可能I(X;Y|Z

15、)>I(X;Y).,費諾不等式(1),定理2.10.1(費諾不等式) 對于任何滿足X?Y?X的估計量X, 設(shè)Pe=Pr{X?X}, 有H(Pe)+Pelog|X|?H(X|X)?H(X|Y) (1)上述不等式可以減弱為1+ Pelog|X|?H(X|Y)或,注釋: 明顯地, 有式(1)可知Pe=0可推出H(X|Y)=0.,費諾不等式(2),證明: 定義一個誤差隨機變量E, 當(dāng)X

16、?X時, E=1; 當(dāng)X=X時, E=0.利用熵的鏈?zhǔn)椒▌t將H(E,X|X)以兩種不同方式展開, 有,因為X?Y?X構(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)；另一部分是指當(dāng)錯

17、誤發(fā)生后，到底是哪個輸入符號發(fā)送而造成錯誤的最大不確定性，它是(n－1)個符號不確定性的最大值log(n－1)與PE的乘積。,漸進均分性定理(1),定義(隨機變量的收斂) 給定一個隨即變量序列X1, X2, ???. 序列X1, X2, ???收斂于隨機變量X有如下三種情形:1. 如果對任意??>0, Pr{|Xn-X|>?}?0, 則稱為依概率收斂.2. 如果E(Xn-X)2?0, 則稱為均方收斂.3. 如果P

18、r{limn??Xn=X}=1, 則稱為以概率1(或稱幾乎處處)收斂.定理3.1.1(AEP) 若X1, X2, ???, Xn為i.i.d?p(x), 則-(1/n)logp(X1, X2, ???, Xn)?H(X) 依概率證明: 獨立隨機變量的函數(shù)依然是獨立隨機變量. 因此, 由于Xi是i.i.d., 從而logp(Xi)也是i.i.d.. 因而, 由弱大數(shù)定律,-(1/n)logp(X1, X2, ???, Xn)=

19、 -(1/n)?ilogp(Xi) ?-Elogp(X) 依概率 = H(X)這就證明了該定理.,漸進均分性定理(2),定義 關(guān)于p(x)的典型集A?(n)(typical set)是序列(x1, x2, ..., xn)?Xn的集合, 且滿足性質(zhì):2-n(H(X)+?)?p(x1, x2, ..., x

20、n)?2-n(H(X)-?)作為漸進均分性的一個推論, 可以證明典型集A?(n)有如下性質(zhì):定理3.1.21. 如果(x1, x2, ..., xn)?A?(n), 則H(X)-??-(1/n)logp (x1, x2, ..., xn)?H(X)+?.2. 當(dāng)n充分大時, Pr{A?(n)}>1-?. 證明: 性質(zhì)1的證明可以直接由A?(n)的定義得到. 性質(zhì)2由定理3

21、.1.1直接得到, 這是由于當(dāng)n??時, 事件 (X1, X2, ???, Xn)?A?(n)的概率趨于1. 于是對任意?>0, 存在n0, 使得當(dāng)n?n0時, 有Pr{|-(1/n)logp(X1, X2, ???, Xn)-H(X)|1-? 令?=?, 即可得到性質(zhì)2.,漸進均分性定理(2),3. |A?(n)|?2n(H(X)+

22、?), 其中|A|表示集合A中的元素個數(shù).,4. 當(dāng)n充分大時, |A?(n)|?(1-?)2n(H(X)-?).,數(shù)據(jù)壓縮(1),設(shè)X1, X2, ???, Xn為服從概率密度函數(shù)p(x)的i.i.d隨機變量下面對隨機序列Xn進行壓縮.編碼:1. 將Xn中的序列劃分為兩個集合: 典型集A?(n)及其補集.2. 將每個集合中的所有元素按照某種順序排序.3. 用n(H+?)+1比特表示A?(n)中元素的序號, 并且在這些序號前加0

23、.4. 對于不屬于A?(n)中元素用nlog|X|+1比特表示其序號,并且在這些序號前加1.上述編碼方案有如下特點:編碼一一對應(yīng), 起始位標(biāo)識了緊隨碼字的長度.對非典型集A?(n)c的元素作了枚舉, 沒有考慮A?(n)c元素個數(shù)實際上少于Xn中元素個數(shù).典型序列具有較短的描述長度?nH.,數(shù)據(jù)壓縮(2),下面證明上述編碼方案的碼字平均長度為nH(X).下面用記號xn表示x1, x2, ..., xn. 設(shè)l(xn)表示相應(yīng)于