平均互信息的凸性课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,平均互信息,定义及含义,信息/数据处理定理,Review,性质：,对称性、非负性、极值性,平均互信息 定义及含义 信息/数据处理定理Review 性质,1,山农信息论：,为设计有效而可靠的通信系统提供理论依据,2.,给定信道，实现可靠通信的最大的传输速率即信道容量？,信源编码定理：,RR(D),信道编码定理：,RC,问题：对应,互信息的最大值和最小值是否存在？,互信息凸性,回答,2,个问题：有效性，可靠性,1.,给定信源，保精度信源编码所需最小编码速率？,山农信息论：2.给定信道，实现可靠通信的最大的传输速率即信,2,凸集,若集合,（,n,维欧氏空间），有,且对任意实数,，有,显然，,n,维欧氏空间,为一凸集合。,0,1,则称为,C,为凸集合。,凸集若集合（n维欧氏空间），有 且对任意实数，有显然，n,3,概率矢量构成集合为凸集,定义,若一个,K,维矢量,=(,1,2,K,),的所有分量为非负的，且和为,1,，即就称,为概率矢量。,引理,概率矢量全体所构成的区域,R,是凸的。,证：若,R,，对,0,1,构造矢量,=,(1-,),因此,是概率矢量，仍属于,R,，所以,R,是凸的。,概率矢量构成集合为凸集定义 若一个K维矢量=(1,4,凸函数定义,定义在凸集,R,上,的一个,实函数,f,，若它对所有,，,R,和,0,1,满足,f,(,)+(1,),f,(,),f,(,(1,),),就称函数,f,为,R,上的,凸函数,。,若式中不等号的方向相反，就称,f,为,凸函数,。,若等号仅当,=0,或,1,时成立，就称,f,为,严格凸或严格凸,的。,凸函数定义定义在凸集R上的一个实函数f，若它对所有，R,5,在,a,b,上定义的上凸函数,在a,b上定义的上凸函数,6,在,a,b,上定义的下凸函数,在a,b上定义的下凸函数,7,凸函数性质,1),若,f,(,),是凸的，则,-,f,(,),是凸的，反过来也成立。,2),若,f,1,(,),f,2,(,),f,L,(,),是,R,上的凸函数，,c,1,c,2,c,L,是正,数，则 为,R,上的凸函数，若其中任一个是严,格凸的，则和式也是严格凸的。,3),(Jensen,不等式,),若,f,(,),是,R,上的凸函数，则,E,f,(,),f,(,E,(,),凸函数性质1)若f()是凸的，则-f()是凸的，反,8,Jensen,不等式,:,若,f(,),是,R,上的凸函数，则,E,f(,)f(,E,(,),其中，,E,表示数学期望。,证明,：,只对离散情况证明,。,对于离散变量，令 ，则,E,f(,)f(,E,(,),可写成,可用归纳法进行证明。,对两点分布，根据凸函数的定义有,假设当分布点个数为,n,时不等式成立，考察分布点个数为,n+1,时的情况。,Jensen不等式:若f()是R上的凸函数，则,9,对 ，令 则有,对 ，令,10,定理,:,如果函数,f(x),在某个区间上存在非负,(,正,),的二阶导数，则,f(x),为该区间上的凸函数,(,严格凸函数,),。,证明,：利用函数,f(x),在,x,0,点的泰勒级数展开,:,其中,x*,位于,x,0,和,x,之间。,根据假设 ，因此，对任意的,x,，最后一项总是非负。,设 ，,0,1,取 ，可得,类似地，取 ，可得,定理:如果函数f(x)在某个区间上存在非负(正)的二阶导,11,因此,，得,证毕,同理可证：如果函数,f(x),在某个区间上存在的二阶导数,0,（,0,对所有,k,=0,其中,为一常数。,令是定义在R上的凸函数，其中=(1,2,14,证,：,首先证明充分性。,设函数,f,在,点满足,KT,条件，今证明 为极大值，即对任意 ，恒有 。,由于,f,是凸函数，所以,f,(,),(1,),f,(,),f,(1,),0,1,即,f,(,),f,(,),f,(1,),f,(,)/,0,1,证：首先证明充分性。,15,因上式对任意,(0,1),成立，可令,0,，得,因上式对任意(0 1)成立，可令 0，得,16,由,KT,条件有,将其代入上式得,从而证明 为极大值。,现在证明必要性。,令 使,f,达到极大值，并假定偏导数在 处连续。则对任意,有,式中,0,1,。,以,除两边并令,0,得,由KT条件有,17,即,因 为是概率矢量，所以至少有一个分量，例如,i,是严格正的，即,i,0,。,选择另一概率矢量,满足,式中 。,于是有,对于 也可选负值和正数，有,和,即,18,即,对 ，因为概率矢量的关系只能选择 ，,由此,得,证毕,即对 ，因为概率矢量的关系只能选,19,熵的凸性,证明：,令,则,由于,当且仅当 时等号成立,熵的凸性证明：令则由于当且仅当 时等号成,20,平均互信息量凸性,由互信息的定义式：,可知，它是输入分布 及转移概率分布 的函数。,可以记为：,如果转移概率分布固定，,I(X,Y),就是先验概率,Q(X),的函数；,如果信源先验概率固定，,I(X,Y),就是转移概率,P(Y/X),的函数。,平均互信息量凸性由互信息的定义式：,21,例,设二元对称信道,(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(x,i,)p(y,j,/x,i,)log p(y,j,/x,i,),=q(x,i,)-plog p+(1-p)log(1-p),=H(p),其中：,H(p),=,-plog p+(1-p)log(1-p),另外：为了求,H(Y),，利用,w(y,j,)=q(x,i,)p(y,j,/x,i,),；可得：,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),例 设二元对称信道(BSC)的信源空间为：X=0,1,22,当固定信源先验概率分布,时，,I(X,Y),是信道转移概率,p,的下凸函数,，如图所示。,0 1/2 1 p,从图中可知，当信源固定后，存在一种,BSC,信道，,p=1/2,，使在信道输出端获得信息量最小，即等于,0,。,I(X,Y),H(),当固定信源先验概率分布时，I(X,Y)是信道转移概率p的下,23,根据这个关系，,当,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),。,根据这个关系，当p值一定，即固定信道，可知I,24,定理,2.5.2,当条件分布,p(y/x),给定时，平均互信息,I(X;Y),是输入分布,q(x),的凸函数。,证明：,令,q,1,和,q,2,是输入集,X,上的任意两个概率矢量，相应的互信息为,I,1,和,I,2,，令,满足,0,1,，,q,=,q,1,(1,),q,2,是合成概率矢量，此时输入,X,和输出,Y,之间的互信息为,I,。,今需要证明,:.,令,p,1,(xy)=q,1,(x)p(y/x),p,2,(xy)=q,2,(x)p(y/x),有,p(xy)=q(x)p(y/x)=p,1,(xy),(1,)p,2,(xy),定理2.5.2 当条件分布 p(y/x)给定时，平均互信息,25,根据平均互信息的定义，得,因为,log x,是严格凸函数,，,利用Jensen,不等式，所以,根据平均互信息的定义，得因为 log x 是严格凸函数，,26,当信道一定时，平均互信息是信源先验概率的上凸函数,对于一定的信道转移概率分布，总可以找到一个先验概率分布为,P,的信源,X,，使平均互信息达到相应的最大值,I,max,，这时称这个信源为该信道的匹配信源。,不同的信道转移概率对应不同的,I,max,，或者说,I,max,是,P,(,Y,/,X,),的函数。,平均互信息的凸性,当信道一定时，平均互信息是信源先验概率的上凸函数对于一,27,定理,2.5.3,当集,X,的概率分布保持不变时，平均互信息量是转移,概率分布,p(y/x),的下凸,函数。,证明：,令,p,1,和,p,2,是两个任意,转移,概率分布，相应的平均互信息为,I,1,和,I,2,，令,满足,0,1,p,=,p,1,(1,),p,2,是合成条件概率分布，此时输入,X,和输出,Y,之间的互信息为,I,。今需要证明,.,令,根据平均互信息的定义，得,定理2.5.3 当集X的概率分布保持不变时，平均互信息量是,28,因为,logx,是严格凸函数，,利用Jensen,不等式，,所以,证毕,平均互信息的凸性课件,29,当信源一定，平均互信息是信道转移概率的下凸函数,对于一个已知先验概率为,P,的离散信源，总可以找到一个转移概率分布为,P,(,Y/X,),的信道，使平均互信息达到相应的最小值,I,min,。,可以说不同的信源先验概率对应不同的,I,min,，或者说,I,min,是,P,(,X,),的函数。即平均互信息的最小值是由体现了信源本身的特性。,平均互信息的凸性,当信源一定，平均互信息是信道转移概率的下凸函数 平均互信息,30,离散随机矢量,信道,X,Y,问题：,离散随机矢量信道XY问题：,31,平均互信息的凸性课件,32,如果输入是相互独立的，输出,Y,所提供的关于输入,X,的信,息量比每个,Yi,所提供的关于,Xi,的信息量的总和要多。,信道,X,Y,如果输入是相互独立的，输出Y所提供的关于输入X的信信道XY,33,