第5讲平均互信息凸性2014

1、平均互信息平均互信息 定义及含义定义及含义 信息信息/数据处理定理数据处理定理Review)()()()|()()|()();(XYHYHXHXYHYHYXHXHYXI);();();();(VUIYXIZXIYXI 性质：性质： 对称性、非负性、极值性对称性、非负性、极值性山农信息论：山农信息论： 为设计有效而可靠的通信系统提供理论依据为设计有效而可靠的通信系统提供理论依据 ( / )( / )R(D)= min ( ; )R(D)= Inf ( ; )DDp y xPp y xPI X YI X Y，限失真离散信源，限失真连续信源 2.给定信道，实现可靠通信的最大的传输速率即信道给定信道，

2、实现可靠通信的最大的传输速率即信道容量？容量？ 信源编码定理：信源编码定理：RR(D)信道编码定理：信道编码定理：RC()()C = m ax(;)C =sup(;)SSqkQqxQIXYIXY， 离 散 信 道， 连 续 信 道 问题：对应问题：对应互信息的最大值和最小值是否存在？互信息的最大值和最小值是否存在？互信息凸性互信息凸性回答回答2个问题：有效性，可靠性个问题：有效性，可靠性1.给定信源，保精度信源编码所需最小编码速率？给定信源，保精度信源编码所需最小编码速率？凸集凸集若集合若集合nRC（n维欧氏空间），有维欧氏空间），有CqCp , 且对任意实数且对任意实数，有有(1),pqC显

3、然，显然，n维欧氏空间维欧氏空间 为一凸集合。为一凸集合。01则称为则称为C为凸集合。为凸集合。概率矢量构成集合为凸集概率矢量构成集合为凸集定义定义 若一个若一个K维矢量维矢量 =( 1, 2, , K)的所有分量的所有分量为非负的，且和为为非负的，且和为1，即就称，即就称 为概率矢量。为概率矢量。引理引理 概率矢量全体所构成的区域概率矢量全体所构成的区域R是凸的。是凸的。证：若证：若 ,R，对，对0 1构造矢量构造矢量 =(1- )Kkakkk, 2, 10)1 (因此因此 是概率矢量，仍属于是概率矢量，仍属于R，所以，所以R是凸的。是凸的。KkKkkkKkka1111)1 (凸函数定义凸函

4、数定义定义在凸集定义在凸集R上上的一个的一个实函数实函数f，若它对所有，若它对所有，R和和0 1满足满足 f( )+(1 ) f ()f ( (1 ) 就称函数就称函数f为为R上的上的凸凸函数函数。若式中不等号的方向相反，就称若式中不等号的方向相反，就称f为为凸凸函数函数。若等号仅当若等号仅当 =0或或1时成立，就称时成立，就称f为为严格凸严格凸或严格凸或严格凸的。的。在在a,b上定义的上凸函数上定义的上凸函数在在a,b上定义的下凸函数上定义的下凸函数凸函数性质凸函数性质1) 若若f( )是凸是凸的，则的，则-f( )是凸是凸的，反过来也成立。的，反过来也成立。 2) 若若f1( ), f2(

5、 ), fL( )是是R上的凸上的凸函数，函数，c1,c2,cL是正是正数，则数，则 为为R上的凸上的凸函数，若其中任一个是严函数，若其中任一个是严格凸的，则和式也是严格凸的。格凸的，则和式也是严格凸的。 Llllfc1)(3) (Jensen不等式不等式) 若若f( )是是R上的凸上的凸函数，则函数，则Ef( ) f (E ( )Jensen不等式不等式: 若f( )是R上的凸函数，则 E f( ) f (E ( ) 其中，E表示数学期望。证明证明：只对离散情况证明只对离散情况证明。 对于离散变量，令 ，则E f( ) f (E ( ) 可写成可用归纳法进行证明。可用归纳法进行证明。对两点分

6、布，根据凸函数的定义有假设当分布点个数为n时不等式成立，考察分布点个数为n+1时的情况。Llllpp11, 011221()()LLLlllf pppp f1212(1)()(1)() ,01fff对 ，令 则有 111,0niiippniip1 1111111()()()()() nnnnnnnp fp fpfppffpf1111()niinnifppf11111niinniniiifppfp定理定理: 如果函数f(x)在某个区间上存在非负(正)的二阶导数，则 f(x)为该区间上的凸函数(严格凸函数)。 证明证明：利用函数f(x)在x0点的泰勒级数展开:其中x*位于x0和x之间。根据假设 ，

7、因此，对任意的x，最后一项总是非负。设 ，01取 ，可得类似地，取 ，可得20000( *)( )()()()()2fxf xf xfxxxxx( *)0fx012(1)xxx1xx10012()()(1)()()f xf xfxxx2xx20021()()()()f xf xfxxx因此，得 证毕证毕 同理可证：如果函数f(x)在某个区间上存在的二阶导数0（ 0 对所有对所有 k k = 0 = 0 ()f )(kf)(kf其中为一常数。证证：首先证明充分性。首先证明充分性。设函数f在 点满足KT条件，今证明 为极大值，即对任意 ，恒有 。由于f是凸函数，所以 f ( )(1 ) f ( )

8、f (1 ) 0 1即f ( )f ( )f (1 ) f ( )/ 01R( )( ) 0ff( )f 11122212111212221222221( ,(),()( ,(),(1) )( )()( )(),(),()( ,)(),(),()()( ,KKKKKKKKKKKKKffffffffff 233312112,(),()( ,()( ,)KKKkKKKKff 0(1) )( )()( )lim( )()kkkkfffff因上式对任意 (0 1)成立，可令 0，得由KT条件有将其代入上式得从而证明 为极大值。现在证明必要性。令 使f 达到极大值，并假定偏导数在 处连续。则对任意 ,有

9、式中01。以除两边并令0 得()()()kkkkkf 0)()(11KkKkkkff( )f RR0)()1(ff0)1(0ddf即因 为是概率矢量，所以至少有一个分量，例如i是严格正的，即i0。选择另一概率矢量满足式中 。于是有对于 也可选负值和正数，有 和kikkkkf0)()(ilkllilkl其 它 值( )( )0kiff0,k1( )( )0kff，1( )( )0kff，即( )( )kiff对对 ，因为概率矢量的关系只能选择，因为概率矢量的关系只能选择 ，由此由此, 得得0k0( )( )kiff证毕证毕熵的凸性熵的凸性证明：证明：),(112111KpppP),(222212

10、KpppP10)()1 ()()1 (2121PHPHPPH令令则则KiiiiiPpPpPPH1212121)1 (log()1 ()1 (KiiiiKiiiiPpPPpp12121211)1 (log()1 ()1 (log(1)1 (121KiiiPp由于由于KiiiKiiippppPPH12211121log1log)1 ()()1 ()(21PHPH当且仅当当且仅当 时等号成立时等号成立21PP p平均互信息量凸性平均互信息量凸性由互信息的定义式：由互信息的定义式：可知，它是输入分布可知，它是输入分布 及转移概率分布及转移概率分布 的函数。的函数。可以记为：可以记为： 如果转移概率分布

11、固定，I(X,Y)就是先验概率Q(X)的函数； 如果信源先验概率固定，I(X,Y)就是转移概率P(Y/X)的函数。( )q x( / )p y x(;)( ),(/)I X Yf Q xP yxxyyxypxypxqYXI)()(log)()()(；例例 设二元对称信道(BSC)的信源空间为：X=0,1; Q(X)=, 1-;求I(X;Y) 0 1-p 0 p p 1 1-p 1 因为已知转移概率，所以利用公式I(X,Y)=H(Y)-H(Y/X) 。 H(Y/X)=-q(xi) p(yj/xi) log p(yj/xi) =q(xi) -plog p+(1-p) log (1-p) =H(p)

12、 其中：H(p)= -plog p+(1-p) log (1-p) 另外：为了求H(Y)，利用w(yj)= q(xi) p(yj/xi)；可得： w(y=0)=(1-p)+(1-)p w(y=1)=p+(1-)(1-p)H(Y)=-(1-p)+(1-)plog(1-p)+(1-)p+p+(1-)(1-p)logp+(1-)(1-p) =H(1-p)+(1-)p) 可得平均互信息量为： I(X,Y)=H(1-p)+(1-)p)-H(p)当固定信源先验概率分布当固定信源先验概率分布时，时，I(X,Y)是信道转移概率是信道转移概率p的下凸函数的下凸函数，如图所示。 0 1/2 1 p从图中可知，当信

13、源固定后，存在一种BSC信道，p=1/2，使在信道输出端获得信息量最小，即等于0。 I(X,Y) H() 根据这个关系，当当p值一定，即固定信道，可知值一定，即固定信道，可知I(X,Y)是是的上凸函数的上凸函数，其曲线如图： I(X,Y) 1-H(p) 0 1/2 1 从图中可知，当BSC信道的信道矩阵固定后，若输入符号集X的概率分布不同，在接收端平均每个符号获得的信息量就不同。只有当输入为等概分布时即，p(0)=p(1)=1/2时，接收端的信息量才为最大值1-H(p)。定理定理2.5.2 当条件分布当条件分布 p(y/x)给定时，平均互信息给定时，平均互信息I(X;Y)是是输入分布输入分布q

14、(x)的凸的凸函数。函数。证明：令q1和q2是输入集X上的任意两个概率矢量，相应的互信息为I1和I2，令满足01，q=q1(1)q2是合成概率矢量，此时输入X和输出Y之间的互信息为I。 今需要证明: . 令p1(xy)=q1(x)p(y/x), p2(xy)=q2(x)p(y/x), 有 p(xy)= q(x)p(y/x)=p1(xy) (1) p2(xy) 1122( )(),( )()xxw yp xyw yp xyIII21)1 (12( )()( )(1)( )xw yp xyw ywy根据平均互信息的定义，得 121212121212()()(1)()log(1)()log( )(

15、)()()(1)()log( )( )( )()log(1)()log( )( )xyxyxyxyxyp y xp y xIIIp xyp xyw ywyp y xp xyp xyw yw yw yp xyp xyw ywy12121212121212( )( )(1)()log(1)()log( )( )( )( )log()(1)log()( )( )( )( )log()(1)log()( )( )0 xyxyxyxyyxyxw yw yIIIp xypxyw ywyw yw yp xypxyw ywyw yw yp xypxyw ywy因为 log x 是严格凸函数， 利用Jensen

16、不等式， 所以 当信道一定时，平均互信息是信源先验概率的上凸函数当信道一定时，平均互信息是信源先验概率的上凸函数对于一定的信道转移概率分布，总可以找到一个对于一定的信道转移概率分布，总可以找到一个先验概率分布为先验概率分布为P的信源的信源X，使平均互信息达到相，使平均互信息达到相应的最大值应的最大值Imax，这时称这个信源为该信道的匹，这时称这个信源为该信道的匹配信源。配信源。不同的信道转移概率对应不同的不同的信道转移概率对应不同的Imax，或者说，或者说Imax是是P(Y/X)的函数。的函数。 平均互信息的凸性平均互信息的凸性定理定理2.5.3 当集当集X的概率分布保持不变时，平均互信息量是

17、的概率分布保持不变时，平均互信息量是转移转移概率分布概率分布p(y/x)的下凸的下凸函数。函数。证明：令p1和p2是两个任意转移转移概率分布，相应的平均互信息为I1和I2，令满足01,p=p1(1)p2是合成条件概率分布，此时输入X和输出Y之间的互信息为I。今需要证明 . 令 根据平均互信息的定义，得12(1)III1111122222( )( )(/ ),( /)( )(/ )/( )( )( )(/ ),( /)( )(/ )/( )( )( )(/ ),( /)( ) (/ )/( )xxxw yq x py xp x yq x py xw ywyq x py xpx yq x py x

18、wywyq x py xp x yq x p y xwy因为logx是严格凸函数，利用Jensen不等式，所以 证毕121212121212()(1)( )(/)(1) ( )(/)log( )()()( )(/)log(1)( )(/)log( )( )()()( )(/)log(1)( )(/)log( /)( /)xyxyxyxyxyp x yIIIq x pyxq x pyxq xpx ypx yq x pyxq x pyxq xq xp x yp x yq x pyxq x pyxpxypxy121212121212()()(1)log( ) ( / ) (1)log( )( / )

19、( / )( / )()()log() (1)log()( / )( / )log( ) () (1)log( ) ()0 xyxyxyxyxyxyp x yp x yIIIq x p y xq x p y xp x yp x yp x yp x yp xyp xyp x yp x yw y p x yw y p x yn 当信源一定，平均互信息是信道转移概率的下凸函数当信源一定，平均互信息是信道转移概率的下凸函数对于一个已知先验概率为对于一个已知先验概率为P的离散信源，总可以找到一的离散信源，总可以找到一个转移概率分布为个转移概率分布为P(Y/X)的信道，使平均互信息达到相的信道，使平均互信

20、息达到相应的最小值应的最小值Imin。可以说不同的信源先验概率对应不同的可以说不同的信源先验概率对应不同的Imin，或者说，或者说Imin是是P(X)的函数。即平均互信息的最小值是由体现了信源的函数。即平均互信息的最小值是由体现了信源本身的特性。本身的特性。 平均互信息的凸性平均互信息的凸性离散随机矢量离散随机矢量12(,)nXXXX12n11.XX ,X ,XI(X;Y)(;)niiiI XY如果中的分量（，）是相互独立的，则12( ,)nY YYY信道信道XY1(; )(;)niiiI X YI X Y问题：和之间关系，不等式？12n12X ,X ,XI(;)=E log()E log()

21、()()npppp Xp Xp XX Y)X YXX Y)证明： 因为假设，是相互独立的，故有：(问题：问题：11112212()(;)log()()()()log()()()nniiiiiiinnnp x yI XYEp xp xyp xyp xyEp xp xp x另一方面，112211122() ()()(;) - I(X;Y) =log()() ()()log(Jensen()nnniiinnp x y p x yp x yI X YEpp x y p x yp x yEpX YX Y因此，利用不等式）121122XY1122XY1122YY() ()()=log(p(X,Y)()lo

22、g() ()() ( )log( )()()()log( )log10nnnnnnnxxxp x y p x yp x ypp x y p x yp x y ppp x yp x yp x ypX YYYY，如果输入是相互独立的，输出如果输入是相互独立的，输出Y Y所提供的关于输入所提供的关于输入X X的信的信息量比每个息量比每个YiYi所提供的关于所提供的关于XiXi的信息量的总和要多。的信息量的总和要多。信道信道XY12(,)nXXXX12( ,)nY YYY12n1XX ,X ,XI(X;Y)(;)niiiI XY如果中的分量（，）是相互独立的，则12n12n121211221X= (X ,X ,XY= Y ,Y ,Y )(,)() ()()I( ; )(;)nnnniiip y yx x