第5讲平均互信息的凸性2014

平均互信息的凸性第五讲平均互信息–定义及含义–信息/数据处理定理Review)()()()|()()|()();(XYHYHXHXYHYHYXHXHYXI);();();();(VUIYXIZXIYXI–性质：对称性、非负性、极值性山农信息论：为设计有效而可靠的通信系统提供理论依据(/)(/)R(D)=min(;)R(D)=Inf(;)DDpyxPpyxPIXYIXY，限失真离散信源，限失真连续信源2.给定信道，实现可靠通信的最大的传输速率即信道容量？信源编码定理：RR(D)信道编码定理：RC()()C=max(;)C=sup(;)SSqkQqxQIXYIXY，离散信道，连续信道问题：对应互信息的最大值和最小值是否存在？互信息凸性回答2个问题：有效性，可靠性1.给定信源，保精度信源编码所需最小编码速率？凸集若集合nRC（n维欧氏空间），有CqCp,且对任意实数，有(1),pqC显然，n维欧氏空间为一凸集合。0≤λ≤1则称为C为凸集合。概率矢量构成集合为凸集定义若一个K维矢量=(1,2,…,K)的所有分量为非负的，且和为1，即就称为概率矢量。引理概率矢量全体所构成的区域R是凸的。证：若,β∈R，对0≤≤1构造矢量=＋(1-)βKkakkk,2,10)1(因此是概率矢量，仍属于R，所以R是凸的。KkKkkkKkka1111)1(凸函数定义定义在凸集R上的一个实函数f，若它对所有α，β∈R和0≤≤1满足f()+(1－)f(β)≤f(＋(1－)β)就称函数f为R上的凸∩函数。若式中不等号的方向相反，就称f为凸∪函数。若等号仅当=0或1时成立，就称f为严格凸∩或严格凸∪的。[(1)]()(1)()fpqfpfqapqb(1)pqp在[a,b]上定义的上凸函数])1([)()1()(qpfqfpfapqbqp)1(p在[a,b]上定义的下凸函数凸函数性质1)若f()是凸∩的，则-f()是凸∪的，反过来也成立。2)若f1(),f2(),…,fL()是R上的凸∩函数，c1,c2,…,cL是正数，则为R上的凸∩函数，若其中任一个是严格凸的，则和式也是严格凸的。Llllfc1)(3)(Jensen不等式)若f()是R上的凸∩函数，则E[f()]≤f(E())Jensen不等式:若f()是R上的凸∩函数，则E[f()]≤f(E())其中，E表示数学期望。证明：只对离散情况证明。对于离散变量，令，则E[f()]≤f(E())可写成可用归纳法进行证明。对两点分布，根据凸函数的定义有假设当分布点个数为n时不等式成立，考察分布点个数为n+1时的情况。Llllpp11,011221()()LLLlllfppppfαααα1212((1))()(1)(),01fffαααα对，令则有111,0niiippniip11111111()()()()()nnnnnnnpfpfpfppffpfααααα1111()niinnifppfαα11111niinniniiifppfpααα定理:如果函数f(x)在某个区间上存在非负(正)的二阶导数，则f(x)为该区间上的凸∪函数(严格凸∪函数)。证明：利用函数f(x)在x0点的泰勒级数展开:其中x*位于x0和x之间。根据假设，因此，对任意的x，最后一项总是非负。设，0λ1取，可得类似地，取，可得20000''(*)()()'()()()2fxfxfxfxxxxx''(*)0fx012(1)xxx1xx10012()()(1)'()()fxfxfxxx2xx20021()()'()()fxfxfxxx因此，得证毕同理可证：如果函数f(x)在某个区间上存在的二阶导数≤0（0)，则f(x)为该区间上的上的凸∩函数(严格凸∩函数)。1200120021012()(1)()()(1)'()()(1)()'()()()((1))fxfxfxfxxxfxfxxxfxfxx利用该定理，可以立即判定：都是严格凸∪函数，为严格凸∩函数。2,,log(0)xxexxx0og,)l(xxx令是定义在R上的凸∩函数，其中=(1,2,…,K)存在且在R域上连续，在R上为极大的充分必要条件是凸函数性质Kuhn-Tucker条件()fα为一概率矢量。假定偏导数()kfaα对所有’k0对所有’k=0'()fα')(kf')(kf其中为一常数。证：首先证明充分性。设函数f在点满足KT条件，今证明为极大值，即对任意，恒有。由于f是凸∩函数，所以f()＋(1－)f()≤f[＋(1－)]0＜＜1即f()－f()≤{f[＋(1－)]－f()}/0＜＜1Rβ()()0ffβα()fα11122212111212221222221(,(),,())(,(),((1))()(())()((),(),,())(,,,)((),(),,,())())(,KKKKKKKKKKKKKffffffffffβαααβαα233312112,(),())(,,,,())(,,,)KKKkKKKKff0((1))()()()lim()()kkkkfffffβααβαα因上式对任意(0＜＜1)成立，可令→0，得由KT条件有将其代入上式得从而证明为极大值。现在证明必要性。令使f达到极大值，并假定偏导数在处连续。则对任意,有式中0＜＜1。以θ除两边并令θ→0得()()()kkkkkfα0)()(11KkKkkkffαβ()fαRααRβ0)(])1([ααβff0])1([0ddfαβ即因为是概率矢量，所以至少有一个分量，例如i是严格正的，即i0。选择另一概率矢量满足式中。于是有对于也可选负值和正数，有和kikkkkf0)()(ααilkllilkl其它值()()0kiffαα0,k1()()0kffαα，1()()0kffαα，即()()kiffαα对，因为概率矢量的关系只能选择，由此,得0k0()()kiffαα证毕熵的凸性证明：),,,(112111KpppP),,,(222212KpppP10)()1()())1((2121PHPHPPH令则KiiiiiPpPpPPH1212121))1(log())1(())1((KiiiiKiiiiPpPPpp12121211))1(log()1())1(log(1)1(121KiiiPp由于KiiiKiiippppPPH12211121log1log))1(()()1()(21PHPH当且仅当时等号成立21PP平均互信息量凸性由互信息的定义式：可知，它是输入分布及转移概率分布的函数。可以记为：如果转移概率分布固定，I(X,Y)就是先验概率Q(X)的函数；如果信源先验概率固定，I(X,Y)就是转移概率P(Y/X)的函数。()qx(/)pyx(;)((),(/))IXYfQxPyxxyyxypxypxqYXI)()(log)()()(；[例]设二元对称信道(BSC)的信源空间为：X={0,1};[Q(X)]={ω,1-ω};求I(X;Y)01-p0pp11-p1因为已知转移概率，所以利用公式I(X,Y)=H(Y)-H(Y/X)。H(Y/X)=-∑∑q(xi)p(yj/xi)logp(yj/xi)=∑q(xi){-[plogp+(1-p)log(1-p)]}=H(p)其中：H(p)=-[plogp+(1-p)log(1-p)]另外：为了求H(Y)，利用w(yj)=∑q(xi)p(yj/xi)；可得：w(y=0)=ω(1-p)+(1-ω)pw(y=1)=ωp+(1-ω)(1-p)H(Y)=-{[ω(1-p)+(1-ω)p]log[ω(1-p)+(1-ω)p]+[ωp+(1-ω)(1-p)]log[ωp+(1-ω)(1-p)]}=H(ω(1-p)+(1-ω)p)可得平均互信息量为：I(X,Y)=H(ω(1-p)+(1-ω)p)-H(p)当固定信源先验概率分布ω时，I(X,Y)是信道转移概率p的下凸函数，如图所示。01/21p从图中可知，当信源固定后，存在一种BSC信道，p=1/2，使在信道输出端获得信息量最小，即等于0。I(X,Y)H(ω)根据这个关系，当p值一定，即固定信道，可知I(X,Y)是ω的上凸函数，其曲线如图：I(X,Y)1-H(p)01/21ω从图中可知，当BSC信道的信道矩阵固定后，若输入符号集X的概率分布不同，在接收端平均每个符号获得的信息量就不同。只有当输入为等概分布时即，p(0)=p(1)=1/2时，接收端的信息量才为最大值1-H(p)。定理2.5.2当条件分布p(y/x)给定时，平均互信息I(X;Y)是输入分布q(x)的凸∩函数。证明：令q1和q2是输入集X上的任意两个概率矢量，相应的互信息为I1和I2，令θ满足0≤θ≤1，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()(),()()xxwypxywypxyIII21)1(12()()()(1)()xwypxywywy根据平均互信息的定义，得121212121212()()(1)()log(1)()log()()()(()(1)())log()()()()log(1)()log()()xyxyxyxyxypyxpyxIIIpxypxywywypyxpxypxywywywypxypxywywy12121212121212()()(1)()log(1)()log()()()()log(())(1)log(())()()()()log(())(1)log(())()()0xyxyxyxyyxyxwywyIIIpxypxywywywywypxypxywywywywypxypxywywy因为logx是严格凸∩函数，利用Jensen不等式，所以•当信道一定时，平均互信息是信源先验概率的上凸函数1)对于一定的信道转移概率分布，总可以找到一个先验概率分布为P的信源X，使平均互信息达到相应的最大值Imax，这时称这个信源为该信道的匹配信源。2)不同的信道转移概率对应不同的Imax，或者说Imax是P(Y/X)的函数。平均互信息的凸性定理2.5.3当集X的概率分布保持不变时，平均互信息量是转移概率分布p(y/x)的下凸∪函数。证明：令p1和p2是两