《信息论第5讲平均互信息的凸性(含习题)ppt课件》由会员分享，可在线阅读，更多相关《信息论第5讲平均互信息的凸性(含习题)ppt课件（56页珍藏版）》请在金锄头文库上搜索。
1、平均互信息的凸性,第5讲,平均互信息,定义及含义,信息/数据处理定理,凸性,性质： 对称性、非负性、极值性,凸集,若集合,（n维欧氏空间），有,且对任意实数,有,显然，n维欧氏空间,为一凸集合。,01,则称为C为凸集合。,概率矢量构成集合为凸集,定义 若一个K维矢量 =(1, 2, , K)的所有分量为非负的，且和为1，即就称为概率矢量。,引理 概率矢量全体所构成的区域R是凸的。,证：若,R，对01构造矢量=(1-),因此是概率矢量，仍属于R，所以R是凸的。,凸函数定义,定义在凸集R上的一个实函数f，若它对所有,R和01满足 f()+(1 ) f ()f ( (1 ) 就称函数f为R上的凸函数
2、。 若式中不等号的方向相反，就称f为凸函数。 若等号仅当=0或1时成立，就称f为严格凸或严格凸的。,在a,b上定义的上凸函数,在a,b上定义的下凸函数,凸函数性质,1) 若f()是凸的，则-f()是凸的，反过来也成立。,2) 若f1(), f2(), fL()是R上的凸函数，c1,c2,cL是正 数，则 为R上的凸函数，若其中任一个是严 格凸的，则和式也是严格凸的。,3) (Jensen不等式) 若f()是R上的凸函数，则,Ef() f (E (),Jensen不等式:若f()是R上的凸函数，则 E f() f (E () 其中，E表示数学期望。 证明：只对离散情况证明。 对于离散变量，令 ，
3、则E f() f (E () 可写成 可用归纳法进行证明。对两点分布，根据凸函数的定义有 假设当分布点个数为n时不等式成立，考察分布点个数为 n+1时的情况。,对 ，令 则有 证毕,定理: 如果函数f(x)在某个区间上存在非负(正)的二阶导数，则 f(x)为该区间上的凸函数(严格凸函数)。 证明：利用函数f(x)在x0点的泰勒级数展开: 其中x*位于x0和x之间。 根据假设 ，因此，对任意的x，最后一项总是非负。 设 取 ，可得 类似地，取 ，可得,因此，得 证毕 同理可证：如果函数f(x)在某个区间上存在的二阶导数0（0)，则 f(x)为该区间上的上的凸函数(严格凸函数)。,利用该定理，可以
4、立即判定 ： 都是严格凸 函数， 为严格凸函数。,令,是定义在R上的凸函数，其中=(1, 2, , K),存在且在R域上连续，,在R上为极大的充分必要条件是,凸函数性质,Kuhn-Tucker条件,为一概率矢量。假定偏导数,对所有k 0,对所有k =0,其中为一常数。,证：首先证明充分性。 设函数f在点满足KT条件，今证明 为极大值，即对任意 ，恒有 。 由于f是凸函数，所以 f ()(1 ) f ()f (1 ) 0 1 即 f ()f ()f (1 )f ()/ 01,因上式对任意 (0 1)成立，可令 0，得,由KT条件有 将其代入上式得 从而证明 为极大值。 现在证明必要性。令 使f
5、达到极大值，并假定偏导数在 处连续。则对任意 ,有 式中01。 以除两边并令0 得,即 因 为是概率矢量，所以至少有一个分量，例如i是严格正的，即i0。 选择另一概率矢量满足 式中 。 于是有 对于 也可选负值和正数，有 和,即,对 ，因为概率矢量的关系，只能选择 ，由此得,证毕,熵的凸性,证明：,令,则,由于,当且仅当 时等号成立,平均互信息量凸性,由互信息的定义式： 可知，它是输入分布 及转移概率分布 的函数。 可以记为： 如果转移概率分布固定，I(X,Y)就是先验概率Q(X)的函数； 如果信源先验概率固定，I(X,Y)就是转移概率P(Y/X)的函数。,例 设二元对称信道(BSC)的信源空
6、间为：X=0,1; Q(X)=, 1-;,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),其中：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-
7、)(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 从图中可知，当信源固定后，存在一种BSC信道，p=(1-p)=1/2，使在信道输出端获得信息量最小，即等于0。也就是说，信源的信息全部损失在信道中了。这是最差的信道，这个性质说明，每个信源都存在一种最差的信道，此信道的干扰最大。,I(X,Y),H(),根据这个关系，当p值一定，即固定信道，可知I(X,Y)是的上凸函数，其曲线如图： I(X,Y) 1-H(
8、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(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(
9、xy)= q(x)p(y/x)=p1(xy) (1) p2(xy),根据平均互信息的定义，得 因为 log x 是严格凸函数，所以 证毕,当信道一定时，平均互信息是信源先验概率的上凸函数,对于一定的信道转移概率分布，总可以找到一个先验概率分布为P的信源X，使平均互信息达到相应的最大值Imax，这时称这个信源为该信道的匹配信源。 不同的信道转移概率对应不同的Imax，或者说Imax是P(Y/X)的函数。,平均互信息的凸性,定理2.5.3 当集X的概率分布保持不变时，平均互信息量是条件概率分布p(y/x)的凸函数。 证明： 令p1和p2是两个任意条件概率分布，相应的平均互信息为I1和I2，令满足0
10、1,p=p1(1)p2是合成条件概率分布，此时输入X和输出Y之间的互信息为I。今需要证明 . 令 根据平均互信息的定义，得,因为logx是严格凸函数，所以 证毕,当信源一定，平均互信息是信道转移概率的下凸函数 对于一个已知先验概率为P的离散信源，总可以找到一个转移概率分布为P(Y/X)的信道，使平均互信息达到相应的最小值Imin。 可以说不同的信源先验概率对应不同的Imin，或者说Imin是P(X)的函数。即平均互信息的最小值是由体现了信源本身的特性。,平均互信息的凸性,本章小结,熵、互信息定义及含义,互信息与熵的关系,信息处理定理,凸性,信道一定时，平均互信息是信源先验概率的上凸函数,信源一
11、定时，平均互信息是信道转移概率的下凸函数,微分熵的定义及与熵的差别,27个硬币中有一个重量偏轻，其它26个为标准重量。 试用信息量观点分析在不用砝码的天平上至少称多少次，就能发现这个轻的硬币？怎样称？,思考:,设有4枚同值硬币，其中1枚硬币可能是假币，如是假币，其重量与真币不同，但不知比真币轻还是重。现在给你一部没有砝码的天平和1枚真币，要求你回答有无假币？如有假币要求找出那枚假币，并指出那枚假币是比真币轻还是重？ 试用信息量观点分析最少需称多少次才能保证一定能找出那枚假币，并给出具体称法。,思考:,第二章 习题,2.1 莫尔斯电报系统中，若采用点长为0.2s，划长为0.4s，且点和划出现的概
12、率分别为2/3和1/3，试求它的信息速率(bits/s)。 解: 平均每个符号长为 秒 每个符号的熵为 比特 所以，信息速率为 比特/秒,2.3 掷一对无偏的骰子，若告诉你得到的总的点数为：(a) 7；(b) 12。 试问各得到了多少信息量?,解: (a)一对骰子总点数为7的概率是,所以，得到的信息量为,(b) 一对骰子总点数为12的概率是,所以，得到的信息量为,比特,比特,2.4 经过充分洗牌后的一付扑克(含52张牌)，试问： (a) 任何一种特定排列所给出的信息量是多少? (b) 若从中抽取13张牌，所给出的点数都不相同时得到多少信息量?,解: (a)任一特定排列的概率为,所以，给出的信息
13、量为,(b) 从中任取13张牌,所给出的点数都不相同的概率为,所以，得到的信息量为,比特.,比特,2.5 设有一个非均匀骰子，若其任一面出现的概率与该面上的点数成正比，试求各点出现时所给出的信息量，并求掷一次平均得到的信息量。,解:易证每次出现i点的概率为,所以,2-6 园丁植树一行，若有3棵白杨、4棵白桦和5棵梧桐。设这12棵树可随机地排列，且每一种排列都是等可能的。若告诉你没有两棵梧桐树相邻时，你得到了多少关于树的排列的信息? 解: 可能有的排列总数为,没有两棵梧桐树相邻的排列数可如下图求得.,Y X Y X Y X Y X Y X Y X Y X Y,图中:X表示白杨或白桦，它有,种排法
14、，,种排法.,Y表示梧桐树可以栽种的位置，它有,所以共有,*,=1960种排法保证没有两棵梧桐树相邻。,因此，若告诉你没有两棵梧桐树相邻时，得到关于树排列的信息为 =3.822 比特,2.9 随机掷三颗骰子，以X表示第一颗骰子抛掷的结果，以Y表示第一和第二颗骰子抛掷的点数之和，以Z表示三颗骰子的点数之和。试求H(Z|Y)、H(X|Y)、H(Z|XY)，H(XZ|Y)和H(Z|X)。,解:令X=X1,Y=X1+X2,Z=X1+X2+X3, H(X1)=H(X2)=H(X3)=,H(X)= H(X1) =2.585 比特,=2.585 比特,H(Y)= H(X2+X3),= 3.2744 比特,H
15、(Z)= H(X1+X2+X3),= 3.5993 比特,所以 H(Z/Y)= H(X3)= 2.585 比特 H(Z/X) = H(X2+X3)= 3.2744 比特 H(X/Y)=H(X)-H(Y)+H(Y/X) = 2.585-3.2744+2.585 =1.8955 比特 H(Z/XY)=H(Z/Y)= 2.585 比特 H(XZ/Y)=H(X/Y)+H(Z/XY) =1.8955+2.585 =4.4805 比特,2-12 计算习题2.9中的I (Y；Z)，I (X；Z)，I (XY；Z)， I (Y；Z|X)和I (X；Z|Y)。,解: I(Y;Z)=H(Z)-H(Z/Y) =H(Z)- H(X3)= 3.5993-2.
