離散信息的度量

北京郵電大學(xué)信息工程學(xué)院 第 2章 離散信息的度量 北京郵電大學(xué)信息工程學(xué)院 2.1 自信息和互信息 自信息 自信息 聯(lián)合自信息 條件自信息 互信息 互信息 互信息的性質(zhì) 條件互信息 北京郵電大學(xué)信息工程學(xué)院 2.1.1 自信息 事件集合 X 中的事件 的自信息： iax )(a- l o gP)(aI iXiX 簡(jiǎn)記 ii - l og p)I(a l og p( x )- I ( X ) 或01ip1i ip其中： 1） ， 2） 非負(fù))( XI對(duì)數(shù)的底數(shù)大于 1 北京郵電大學(xué)信息工程學(xué)院 本書符號(hào)的約定 X集合x事件)(aPx ix 的概率ia),(P XY ji ba聯(lián)合概率北京郵電大學(xué)信息工程學(xué)院 比特x2lo g奈特xln哈特x10lo g比特奈特 443.11 比特哈特 32.31 關(guān)于對(duì)數(shù)底的選取 北京郵電大學(xué)信息工程學(xué)院 事件發(fā)生的不確定性事件發(fā)生前 事件包含的信息量事件發(fā)生后 2.1.1 自信息 自信息為隨機(jī)變量 自信息的含義包含兩方面： 北京郵電大學(xué)信息工程學(xué)院 2.1 例 箱中有 90個(gè)紅球， 10個(gè)白球。現(xiàn)從箱中隨機(jī)地取出一個(gè)球。求： （ 1）事件 “ 取出一個(gè)紅球 ” 的不確定性； （ 2）事件 “ 取出一個(gè)白球 ” 所提供的信息量； （ 3）事件 “ 取出一個(gè)紅球 ” 與 “ 取出一個(gè)白球 ”的發(fā)生，哪個(gè)更難猜測(cè)？ 北京郵電大學(xué)信息工程學(xué)院 （ 1）設(shè) 表示 “ 取出一個(gè)紅球 ” 的事件，則 故事件 的不確定性為： 比特 （ 2）設(shè) 表示 “ 取出一個(gè)紅球 ” 的事件，則 故事件 所提供的信息量為： 比特 （ 3）因?yàn)?，所以事件 “ 取出一個(gè)白球 ” 的發(fā)生更難猜測(cè)。 解： 9.0)( 1 ap1a1 5 2.09.0log)( 1 aI1a2a 1.0)( 2 ap2a323.31.0log)( 2 aI)()( 12 aIaI 北京郵電大學(xué)信息工程學(xué)院 聯(lián)合自信息 事件集合 XY 中的事件 的自信息： ji byax ,)b,(a- l o g P)b,(aI jiXYjiXY 簡(jiǎn)記 log p( xy )- I ( X Y ) 其中： 1） p(xy)要滿足非負(fù)和歸一化條件 北京郵電大學(xué)信息工程學(xué)院 2.1(續(xù) ) 例 箱中球不變，現(xiàn)從箱中隨機(jī)取出兩個(gè)球。求： （ 1）事件 “ 兩個(gè)球中有紅、白球各一個(gè) ” 的不確定性； （ 2）事件 “ 兩個(gè)球都是白球 ” 所提供的信息量； （ 3）事件 “ 兩個(gè)球都是白球 ” 和 “ 兩個(gè)球都是紅球 ” 的發(fā)生，哪個(gè)事件更難猜測(cè)？ 北京郵電大學(xué)信息工程學(xué)院 三種情況都是求聯(lián)合自信息。設(shè) x為紅球數(shù)， y為白球數(shù)。 解： (1) 11/22/99100 1090)1,1( 2100110190 CCCPXY460.211/2lo g)1,1( I 比特 (2) 110/12/991002/910)2,0(2100210 CCPXY7 8 2.61 1 0/1lo g)2,0( I 比特 (3) 110/892/99100 2/8990)0,2( 2100290 CCPXY306.0110/89lo g)0,2( I 比特 因?yàn)?，所以事件“兩個(gè)球都是白球”的發(fā)生更難猜測(cè)。 )0,2()2,0( II 北京郵電大學(xué)信息工程學(xué)院 條件自信息 )b|(a- l o g P)b|(aI jiY|XjiY|X 簡(jiǎn)記 y)|lo gp ( x- Y)|I ( X p(x|y)要滿足非負(fù)和歸一化條件 事件 給定，事件 的自信息： jby iax 北京郵電大學(xué)信息工程學(xué)院 事件發(fā)生的不確定性事件發(fā)生前 事件包含的信息量事件發(fā)生后 條件自信息的含義包含兩方面： ij a，xby 給定ij a，xby 給定自信息、條件自信息和聯(lián)合自信息之間的關(guān)系 I(xy)= I(x)+ I(y|x)= I(y)+ I(x|y) 北京郵電大學(xué)信息工程學(xué)院 2.1(續(xù) ) 例 箱中球不變，現(xiàn)從箱中先拿出一球，再拿出一球，求： （ 1）事件 “ 在第一個(gè)球是紅球條件下，第二個(gè)球是白球 ”的不確定性； （ 2）事件 “ 在第一個(gè)球是紅球條件下，第二個(gè)球是紅球 ”所提供的信息量。 北京郵電大學(xué)信息工程學(xué)院 這兩種情況都是求條件自信息，設(shè) r表示紅球， w表示白球。 解： (1) 比特 (2) 比特 99/10)|( rxwyp307.399/10l o g)|( rxwyI99/89)|( rxryp154.099/89l o g)|( rxryI北京郵電大學(xué)信息工程學(xué)院 2.2 例 有 8 8=64個(gè)方格，甲將一棋子放入方格中， 讓 乙猜 ： 1）將方格按順序編號(hào)，讓乙猜順序號(hào)的困難程度為何？ 2）將方格按行和列編號(hào)，當(dāng)甲告訴乙方格的行號(hào)后，讓乙猜列順序號(hào)的困難程度為何？ 解： 兩種情況下的不確定性 1) I(xy)=log2 64=6 bit 2) I(x|y)=-log2 p(x|y)=-log2(1/8)=3 bit 北京郵電大學(xué)信息工程學(xué)院 2.1.2 互信息 互信息 互信息的性質(zhì) 條件互信息 北京郵電大學(xué)信息工程學(xué)院 互信息 簡(jiǎn)記 通過計(jì)算 離散隨機(jī)事件 之間的互信息： ji b，yax / i j;Xi( / b )( ; ) l o gP ( a )XYX Y i jPaI a b ( / )( ; ) l o g()p x yI x ypx ( ; ) l o g jiijipI a bp或 )|()();( yxIxIyxI I(x;y)與 I(x|y)的區(qū)別？ 北京郵電大學(xué)信息工程學(xué)院 互信息的性質(zhì) 互易性 當(dāng)事件 x， y統(tǒng)計(jì)獨(dú)立時(shí)，互信息為 0，即I(x;y)=0 互信息可正可負(fù) 任何兩事件之間的互信息不可能大于其中任一事件的自信息 北京郵電大學(xué)信息工程學(xué)院 設(shè) e表示 “ 降雨 ” ， f表示 “ 空中有烏云 ” ，且 P(e)=0.125， P(e|f)=0.8 求： 1） “ 降雨 ” 的自信息 2） “ 空中有烏云 ” 條件下 “ 降雨 ” 的自信息 3） “ 無雨 ” 的自信息 4） “ 空中有烏云 ” 條件下 “ 無雨 ” 的自信息 5） “ 降雨 ” 與 “ 空中有烏云 ” 的互信息 6） “ 無雨 ” 與 “ 空中有烏云 ” 的互信息 2.3 例 )(eI)|( feI)(eI)|( feI);( feI);( feI北京郵電大學(xué)信息工程學(xué)院 這兩種情況都是求條件自信息，設(shè) r表示紅球， w表示白球。 解： 1) I(e)= -log0.125 =3 bit 2) I(e |f)= -log0.8 =0.322 bit 3) I( )= -log0.875 =0.193 bit 4) I( |f)= -log0.2 =2.322 bit 5) I(e； f)= 3 0.322 =2.678 bit 6) I( ； f)= 0.193 2.322 = -2.129 bit eee北京郵電大學(xué)信息工程學(xué)院 ( / )( ; / ) l o g( / )p x y zI x y zp x z條件互信息 除條件外，條件互信息的含義與互信息的含義與性質(zhì)都相同 設(shè)聯(lián)合集 XYZ，在給定 zZ 條件下 x(X) 與y(Y ) 之間的互信息定義為 ： 北京郵電大學(xué)信息工程學(xué)院 2.2 信息熵 信息熵的定義與計(jì)算 條件熵與聯(lián)合熵 熵的基本性質(zhì) 北京郵電大學(xué)信息工程學(xué)院 I(x)為事件 x的自信息 表示對(duì)隨機(jī)變量 x用 p(x)來進(jìn)行取平均運(yùn)算 熵的單位為比特（奈特）信源符號(hào) ()pxE信息熵的定義與計(jì)算 離散信源 X的熵定義為自信息的平均值 ,記為 H(X) ()( ) ( ) ( ) l o g ( )px xH X E I x p x p x 北京郵電大學(xué)信息工程學(xué)院 信源輸出前 信源的平均不確定性 信源輸出后 一個(gè)信源符號(hào)所提供的平均信息量 表示信源隨機(jī)性大?。?H（ X）大的，隨機(jī)性大 信源輸出后，不確定性就解除 解除信源不確定性所需信息量 信息熵 H(X)的含義 北京郵電大學(xué)信息工程學(xué)院 一電視屏幕的格點(diǎn)數(shù)為 500 600=300000，每點(diǎn)有10個(gè)灰度等級(jí)，若每幅畫面等概率出現(xiàn)，求每幅畫面平均所包含的信息量 2.4 例 解： 可能的畫面數(shù)是多少？ 代入公式： 30000010300000101 pb i tpXH 630 000022 10)10(l o g)/1(l o g)( 北京郵電大學(xué)信息工程學(xué)院 2.5 例 A、 B兩城市天氣情況概率分布如下表 ： 晴 陰 雨 A城市 0 8 0 15 0 05 B城市 0 4 0 3 0 3 問哪個(gè)城市的天氣具有更大的不確定性？ 北京郵電大學(xué)信息工程學(xué)院 所以， B城市的天氣具有更大的不確定性。 解： 符號(hào)比特 / 884.0 05.0l o g05.015.0l o g15.08.0l o g8.0)05.0,15.0,8.0()( HAH符號(hào)比特 / 5 7 1.1 3.0l o g3.03.0l o g3.04.0l o g4.0)3.0,3.0,4.0()( HBH北京郵電大學(xué)信息工程學(xué)院 2.6 例 有甲、乙兩箱球，甲箱中有紅球 50、白球 20、黑球 30；乙箱中有紅球 90、白球 10。現(xiàn)做從兩箱中分別隨機(jī)取一球的實(shí)驗(yàn)，問從哪箱中取球的結(jié)果隨機(jī)性更大？ 解： 設(shè) A、 B分別代表甲、乙兩箱，則 所以，從甲箱中取球的結(jié)果隨機(jī)性更大。 符號(hào)比特 / 4 8 6.1 3.0l o g3.02.0l o g2.05.0l o g5.0)03,2.0,5.0()( HAH符號(hào)比特 / 4 6 9.01.0l og1.09.0l og9.0)1.0,9.0()( HBH北京郵電大學(xué)信息工程學(xué)院 信息熵的計(jì)算 定理 2.1 離散信源的熵等于所對(duì)應(yīng)的有根概率樹上所有節(jié)點(diǎn) (包括根節(jié)點(diǎn)，不包括葉 )的分支熵用該節(jié)點(diǎn)概率加權(quán)的和，即 i ii uHuqXH )()()(其中， q(ui)為節(jié)點(diǎn) ui的概率， H(ui)為節(jié)點(diǎn) ui的分支熵。 北京郵電大學(xué)信息工程學(xué)院 2.6 例 2 / 31 / 3r : 1p1 - p1 / 21 / 2a3: 2 ( 1 - p ) / 3b2: 2 / 3b1: 2 p / 3a1: p / 3a2: p / 3a4: 1 / 3北京郵電大學(xué)信息工程學(xué)院 ()( / ) ( / ) p x yH Y X E I y x x yxypyxp )/(l o g)( x yxypxypxp )/(l o g)/()(xxYHxp )/()(的熵取某一特定值時(shí)為在 YxxypxypxYHy )/(l o g)/()/(條件熵 條件熵： 聯(lián)合集 XY上，條件自信息 I(y|x)的平均值 北京郵電大學(xué)信息工程學(xué)院 2.7 例 隨機(jī)變量 X和 Y，符號(hào)集均為 0， 1 解： 求 H(Y|X) 32)0(x p 31)1(x p21)0|1()0|0( xypxyp 1)1|1( xyp)1|()1()0|()0()|()()|( xYHxpxYHxpxYHxpXYHx符號(hào)比特 / 32)1(31)21(32 HH北京郵電大學(xué)信息工程學(xué)院 ()( ) ( ) p x yH X Y E I x y x yyxpyxp )(l o g)(聯(lián)合熵 聯(lián)合熵： 聯(lián)合集 XY上，對(duì)聯(lián)合自信息 I(xy)的平均值 北京郵電大學(xué)信息工程學(xué)院 2.7(續(xù) ) 例 由已知條件可得 XY的聯(lián)合概率分布，如下表所示 解： 求 H(XY) Y p(xy) 0 1 X 0 1 0 313131符號(hào)比特 / 585.13l og)31,31,31()Y( HXH北京郵電大學(xué)信息工程學(xué)院 熵的基本性質(zhì) 凸函數(shù) 信息散度 熵的基本性質(zhì) 各類熵的關(guān)系 熵函數(shù)的唯一性 北京郵電大學(xué)信息工程學(xué)院 凸函數(shù) 1l o g)()(iiippppHXH 元函數(shù)為 1)( nXH2n當(dāng) )()1,(),()( 11121 pHppHppHpH 下面我們來定義凸函數(shù) LOOK一下 北京郵電大學(xué)信息工程學(xué)院 對(duì)于 (01) 及任意兩矢量 x1,x2，有 fx 1+(1-)x 2f(x 1)+(1-)f(x 2) 上凸函數(shù) (cap) x1 x2 若當(dāng)且僅當(dāng) x1 = x2或 = 0,1時(shí)等式成立 嚴(yán)格上凸函數(shù) 對(duì)于 (01) 及任意兩矢量 x1,x2，有 fx 1+(1-)x 2 f(x 1)+(1-)f(x 2) 下凸函數(shù) (cup) x1 x2 若當(dāng)且僅當(dāng) x1 = x2或 = 0,1時(shí)等式成立 嚴(yán)格下凸函數(shù) 北京郵電大學(xué)信息工程學(xué)院 定理 ： )(11qkkkqkkk xfxf f(x)是區(qū)間上的實(shí)值連續(xù)嚴(yán)格上凸函數(shù) 任意一組 x1,x2, ,xq 1, 2, , q， k=1 當(dāng)且僅當(dāng) x1=x2=x q或 k=1（ 1 k q）且 j=0（ j k）時(shí)，等式成立 Jenson不等式 北京郵電大學(xué)信息工程學(xué)院 證 利用數(shù)學(xué)歸納法。根據(jù)上凸函數(shù)的定義有 f x1+(1- )x2 f(x1)+(1- )f(x2) 其中 0log24 熵的鏈原則 舉例 北京郵電大學(xué)信息工程學(xué)院 極值性： 熵的基本性質(zhì) (2) 定理 2. 4. 3 (離散最大熵定理 ) 對(duì)于離散隨機(jī)變量集合，當(dāng)集合中的事件等概率發(fā)生時(shí)，熵達(dá)到最大值 證 設(shè)隨機(jī)變量集合有 n個(gè)符號(hào)，概率分布為 P(x) ； Q(x)為等概率分布，即 Q(x)=1/n。 根據(jù)散度不等式有 x xQxPxPQPD)()(l o g)()/( x x nxPxPxP )/1l o g ()()(l o g)(0lo g)( nXHnXH lo g)( 北京郵電大學(xué)信息工程學(xué)院 確定性： 上凸性： 熵的基本性質(zhì) (3) H(1,0) = H(1,0,0)= = H(1,0,0) = 0 。 當(dāng)隨機(jī)變量集合中任一事件概率為 1時(shí)，熵為 0 H(p)=H(p1,p2,pn) 是 (p1,p2,pn) 的嚴(yán)格的上凸函數(shù) 北京郵電大學(xué)信息工程學(xué)院 各類熵的關(guān)系 條件熵不大于信息熵： 定理 （熵的不增原理） )()|( YHXYH 在信息處理過程中，條件越多，熵越小。 )/(l o g)/()()(l o g)()/()( xypxypxpyqyqXYHYHY x y x y yqxypxypxp)()/(l o g)/()(0北京郵電大學(xué)信息工程學(xué)院 各類熵的關(guān)系 聯(lián)合熵不大于個(gè)信息熵的和： NiiN XHXXXH121 )()(證明思路：熵的可加性 )()|( YHXYH 聯(lián)合熵與信息熵、條件熵的關(guān)系 H(XY)= H(X) + H(Y/X ) 北京郵電大學(xué)信息工程學(xué)院 熵函數(shù)的唯一性 是概率的連續(xù)函數(shù) 信源符號(hào)等概率時(shí)是 n（信源符號(hào)數(shù)）的增函數(shù) 可加性 如果要求熵函數(shù)滿足以下條件： 那么，熵函數(shù)的表示是唯一的。 北京郵電大學(xué)信息工程學(xué)院 2.3 平均互信息 平均互信息的定義 平均互信息的性質(zhì) 平均條件互信息 北京郵電大學(xué)信息工程學(xué)院 集合與事件之間的互信息 集合 X與事件 y=bj之間的互信息： 由事件 y=bj提供的關(guān)于集合 X的平均條件互信息（用條件概率平均） x xpyxPyxPyXI)()|(l o g)|();(定理 I(X； y) 0， 僅當(dāng) y與所有 x 獨(dú)立時(shí)，等式成立。 證 根據(jù)散度的定義，有 僅當(dāng)對(duì)所有 x， p(x)= p(x / y ) 時(shí)，等式成立 , 證畢。 /( ; ) ( / / ) 0X y XI X y D P P北京郵電大學(xué)信息工程學(xué)院 平均互信息 集合 X、 Y之間的平均互信息： xxYIxpYXI );()();(yx ypxypxypxp, )()/(l o g)/()( yxxxypxpxypxypxp, )/()()/(l o g)/()( jiiijiijiji ppppp,l o g北京郵電大學(xué)信息工程學(xué)院 I(X ;Y) H(Y |X)H(X |Y)H(Y )H(X )H (XY )平均互信息與熵的關(guān)系 I(X;Y)= H(X)- H(X|Y) I(X;Y)= H(Y)- H(X|Y) I(X;Y)=H(X)+ H(Y)- H(XY) 北京郵電大學(xué)信息工程學(xué)院 平均互信息的性質(zhì) 非負(fù)性： 定理 ： I(X;Y)0 僅當(dāng) X， Y 獨(dú)立時(shí)，等式成立 證明思路： 0);( yXI 0 其均值 互易性 (對(duì)稱性 )： );();( XYIYXI 凸函數(shù)性 北京郵電大學(xué)信息工程學(xué)院 定理： I(X;Y)為概率分布 p(x)的上凸函數(shù)。 證明思路： )(),(21 xpxp設(shè))()1()()(,10 21 xpxpxp 取令)()1()()( 21 xpIxpIxpI 那么只要證)();( xpIYXI 北京郵電大學(xué)信息工程學(xué)院 ppppqq111)1()0( ppppq 2)1()1()0( ppppppq 21)1()1()1)(1()1( )2()( ppHYH 二元信源 X輸出符號(hào)為 0,1， PX(0)= ，條件概率分別為 PY|X(0|0) = PY|X(1|1)=1-p， PY|X(1|0)= PY|X(0|1)=p， 求 I(X;Y)。 例 解： )1()1()0()0(qPqPYY 北京郵電大學(xué)信息工程學(xué)院 ( | ) ( 1 ) l o g ( 1 ) l o g ( 1 ) l o g ( 1 ) l o g ( 1 ) H Y X p p p p p p p p )()1l o g ()1(l o g pHpppp )()2()|()();(pHppHXYHXHYXI0)21()21();(,21,21,21HHYXIpp當(dāng)有極大值時(shí)當(dāng) 可見： 1）這是一個(gè)上凸函數(shù)； 2） 212 pp 02/1(21 ）（移項(xiàng) p北京郵電大學(xué)信息工程學(xué)院 北京郵電大學(xué)信息工程學(xué)院 定理： 對(duì)于固定的概率分布 p(x)， I(X;Y)為條件概率p(x|y)的下凸函數(shù)。 證明思路： )|(),|(21 xypxyp設(shè))|()1()|()|(,10 21 xypxypxyp 取令 yxyp 1)|( )|();( xypIYXI 記)|()1()|()|( 21 xypIxypIxypI 那么只要證北京郵電大學(xué)信息工程學(xué)院 固定 ，pHppHYXI )()2();( 10I( X ;Y )H( )1 / 2p續(xù) 例 解： 這是一個(gè)下凸函數(shù) 北京郵電大學(xué)信息工程學(xué)院 I(X； Y) H(X) I(X； Y) H(Y) 極值性： 北京郵電大學(xué)信息工程學(xué)院 平均條件互信息 設(shè)聯(lián)合集 XYZ， Z條件下， X與 Y之間的平均互信息： );()|;()( )|()|( )|(l o g)( )|(l o g);( zxIzyxIxp zxpzxp yzxpxp yzxpyzxI 由于( ; ) ( ; / ) ( ; )I x y z I x z y I x y zyxzyx zxpyzxpxyzpzxpyzxpZYXI, )|()|(l o g)()|()|( l o g)|;();()/;();()/;();( ZXIZYXIYXIYZXIYZX：I， 得兩邊求平均北京郵電大學(xué)信息工程學(xué)院 0)/;( ZYXI等式成立時(shí)當(dāng)且僅當(dāng) 0)/()/;()|()|( / YZZXX Y Z PPPDZYX，Iyzxpzxp 定理：平均條件互信息是非負(fù)的： 等式成立當(dāng)且僅當(dāng) ，yzxpzxp )|()|( 證明： ,( / )( ; / ) ( ) l o g( / )()( ) l o g( / ) ( )x y zx y zp x y zI X Y Z p x y