信息论第5讲 平均互信息的凸性【PPT课件】

平均互信息的凸性 第 5讲 平均互信息 定义及含义 信息 /数据处理定理 ()()()|()()|()();();();();();( 凸性 性质： 对称性、非负性、极值性 凸集 若集合 （ 有 ,且对任意实数 有 (1 ) ,p q C 显然， 为一凸集合。 0 1 则称为 概率矢量构成集合为凸集 定义 若一个 =(1, 2, , K)的所有分量为非负的，且和为 1，即就称 为概率矢量。 引理 概率矢量全体所构成的区域 证：若 , R，对 01构造矢量 = (1-) ,2,10)1( 因此 是概率矢量，仍属于 R，所以 11)1( 凸函数定义 定义在凸集 函数 f，若它对所有, 1满足 f()+(1 ) f ()f ( (1 ) 就称函数 上的 凸 函数 。 若式中不等号的方向相反，就称 函数 。 若等号仅当 =0或 1时成立，就称 格凸 或严格凸 的。 )()1()()1(1( a,b上定义的上凸函数 )1()()1()(a p 1( a,b上定义的下凸函数 凸函数性质 1) 若 f()是凸 的，则 )是凸 的，反过来也成立。 2) 若 ), ), )是 函数， c1,c2,数，则 为 函数，若其中任一个是严 格凸的，则和式也是严格凸的。 3) ( 若 f()是 函数，则 Ef() f (E () 若 f()是 函数，则 E f() f (E () 其中， 证明 ： 只对离散情况证明 。 对于离散变量，令 ，则 E f() f (E () 可写成 可用归纳法进行证明。 对两点分布，根据凸函数的定义有 假设当分布点个数为 察分布点个数为 n+1时的情况。 1 1 2 21( ) ( ) l p p p p f 1 2 1 2( ( 1 ) ) ( ) ( 1 ) ( )f f f 对 ，令 则有 证毕 111,0 1 1 111 1 111111111( ) ( ) ( )( ) ( ) ( )1()n n n n i n i n f p f p f p ff p p ff p 定理 : 如果函数 f(x)在某个区间上存在非负 (正 )的二阶导数，则 f(x)为该区间上的凸 函数 (严格凸 函数 )。 证明 ：利用函数 f(x)在 其中 x*位于 根据假设 ，因此，对任意的 x，最后一项总是非负。 设 取 ，可得 类似地，取 ，可得 20 0 0 0 ( * )( ) ( ) ( ) ( ) ( )2x f x f x x x x x ( * ) 00 1 2(1 )x x x 1 0 0 1 2( ) ( ) ( 1 ) ( ) ( )f x f x f x x x 2 0 0 2 1( ) ( ) ( ) ( )f x f x f x x x 因此 ，得 证毕 同理可证：如果函数 f(x)在某个区间上存在的二阶导数 0（ 0 对所有 k =0 )( f )( )(为一常数。 证 ： 首先证明充分性。 设函数 点满足 证明 为极大值，即对任意 ，恒有 。 由于 函数，所以 f () (1 ) f ()f (1 ) 0 1 即 f () f ()f (1 ) f ()/ 0 1 R ( ) ( ) 0()f 121 1 1 2 2 2 1 21 1 1 2 2 21 2 2 21 2 2 21( ) ( , , , )( (1 ) ) ( )( ( ) , ( ) , , ( ) ) ( , , , )( ( ) , ( ) , , ( ) )( , ( ) , , ( ) )( , ( ) , , ( ) )( K 2121 2 1 1 2, , , ( ) )( , , , ( ) )( , , , , ( ) ) ( , , , )K K K K 0( (1 ) ) ( )( ) ( ) l i m()() 因上式对任意 (0 1)成立，可令 0，得 由 将其代入上式得 从而证明 为极大值。 现在证明必要性。 令 使 f 达到极大值，并假定偏导数在 处连续。则对任意 ,有 式中 0 1。 以 除两边并令 0 得 )()()( 0)()(1 1 ()f RR0)()1( 0)1(0即 因 为是概率矢量，所以至少有一个分量，例如 i0。 选择另一概率矢量 满足 式中 。 于是有 对于 也可选负值和正数，有 和 )()( 其 它 值( ) ( ) 0 0,k1( ) ( ) 0 1( ) ( ) 0 即 ( ) ( ) 对 ，因为概率矢量的关系，只能选择 ，由此得 0k 0 ( ) ( ) 证毕 熵的凸性 证明： ),( 112111 ),( 222212 10 )()1()()1( 2121 令 则 )1(l o g ()1()1( )1(l o g ()1()1(l o g ( 1)1(121 p 由于 l o o g)1( )()1()( 21 当且仅当 时等号成立 21 平均互信息量凸性 由互信息的定义式： 可知，它是输入分布 及转移概率分布 的函数。 可以记为： 如果转移概率分布固定， I(X,Y)就是先验概率 Q(X)的函数； 如果信源先验概率固定， I(X,Y)就是转移概率 P(Y/X)的函数。 () / )p y x( ; ) ( ( ) , ( / ) )I X Y f Q x P y x x y )(l )()(；例 设二元对称信道 (信源空间为： X=0,1; Q(X)= , 1; 0 1 0 p p 1 1 1 因为已知转移概率，所以利用公式 I(X,Y)=H(Y) 。 H(Y/X)=-q(p(yj/ p(yj/=q(-p+(11 =H(p) 其中： H(p)= -p+(11 另外：为了求 H(Y)， 利用 w( q(p(yj/可得： w(y=0)=(1(1-)p w(y=1)=p+(11所以： H(Y)=-(1(1-)p(1(1-)p+p+(11p+(11 =H( (1(1p) 可得平均互信息量为： I(X,Y)=H(1(1-)p)-H(p) 当固定信源先验概率分布 时 ， I(X,Y)是信道转移概率 如图所示 。 0 1/2 1 p 从图中可知，当信源固定后，存在一种 p=(11/2，使在信道输出端获得信息量最小，即等于 0。也就是说，信源的信息全部损失在信道中了。这是最差的信道，这个性质说明，每个信源都存在一种最差的信道，此信道的干扰最大。 I(X,Y) H() 根据这个关系 ， 当 即固定信道 ， 可知 I(X,Y)是 的上凸函数 ， 其曲线如图： I(X,Y) 1-H(p) 0 1/2 1 从图中可知，当 输入符号集 接收端平均每个符号获得的信息量就不同。只有当输入为等概分布时即， p(0)=p(1)=1/2时，接收端的信息量才为最大值 1-H(p)。 定理 当条件分布 p(y/x)给定时，平均互信息 I(X;Y)是输入分布 q(x)的凸 函数。 证明： 令 上的任意两个概率矢量，相应的互信息为2，令 满足 01， q=(1 )时输入 之间的互信息为 I。 今需要证明 : . 令 p1(q1(x)p(y/x), p2(q2(x)p(y/x), 有 p( q(x)p(y/x)=p1( (1 ) p2(1 1 2 2( ) ( ) , ( ) ( )y p x y w y p x y 21 )1( 12( ) ( ) ( ) (1 ) ( )xw y p x y w y w y 根据平均互信息的定义，得 因为 x 是严格凸 函数，所以 证毕 1 2 1 212121212( ) ( )(1 ) ( ) l o g (1 ) ( ) l o g( ) ( )()( ( ) (1 ) ( ) ) l o g()( ) ( )( ) l o g (1 ) ( ) l o g( ) ( )x y x y x yp y x p y I p x y p x yw y w yp y xp x y p x y w yp x y p x yw y w y 1 2 1 21212121212( ) ( )(1 ) ( ) l o g (1 ) ( ) l o g( ) ( )( ) ( )l o g ( ( ) ) (1 ) l o g ( ( ) )( ) ( )( ) ( )l o g ( ( ) ) (1 ) l o g ( ( ) )( ) ( )0x y x yx y x yy x y xw y w I p x y p x yw y w yw y w yp x y p x yw y w yw y w yp x y p x yw y w y 当信道一定时，平均互信息是信源先验概率的上凸函数 1) 对于一定的信道转移概率分布，总可以找到一个先验概率分布为 ，使平均互信息达到相应的最大值 时称这个信源为该信道的匹配信源。 2) 不同的信道转移概率对应不同的 者说 (Y/X)的函数。 平均互信息的凸性 定理 当集 均互信息量是条件概率分布 p(y/x)的凸 函数。 证明： 令 应的平均互信息为 2，令 满足 01,p=(1 )时输入 之间的互信息为 I。今需要证明 . 令 根据平均互信息的定义，得 12(1 )I I I 1 1 1 1 12 2 2 2 2( ) ( ) ( / ) , ( / ) ( ) ( / ) / ( )( ) ( ) ( / ) , ( / ) ( ) ( / ) / ( )( ) ( ) ( / ) , ( / ) ( ) ( / ) / ( )y q x p y x p x y q x p y x w yw y q x p y x p x y q x p y x w yw y q x p y x p x y q x p y x w y 因为 函数，所以 证毕 1 2 1 212121212()(1 ) ( ( ) ( / ) (1 ) ( ) ( / ) ) l o g()( ) ( )( ) ( / ) l o g (1 ) ( ) ( / ) l o g( ) ( )( ) ( )( ) ( / ) l o g (1 ) ( ) ( / ) l o g( / ) ( / )y x yx y x yp x I q x p y x q x p y x y p x yq x p y x q x p y xq x q xp x y p x yq x p y x q x p y xp x y p x y 1 2 1 212121212( ) ( )( 1 ) l o g ( ( ) ( / ) ) ( 1 ) l o g ( ( ) ( / ) )( / ) ( / )( ) ( )l o g ( ( ) ) ( 1 ) l o g ( ( ) )( / ) ( / )l o g ( ( ) ( ) ) ( 1 ) l o g ( ( ) ( ) )0x y x yx y x yx y x yp x y p x I q x p y x q x p y xp x y p x yp x y p x yp x y p x yp x y p x yw y p x y w y p x y 当信源一定 ， 平均互信息是信道转移概率的下凸函数 1) 对于一个已知先验概率为 可以找到一个转移概率分布为 P(Y/X)的信道，使平均互信息达到相应的最小值 2) 可以说不同的信源先验概率对应不同的 者说 (X)的函数。即平均互信息的最小值是由体现了信源本身的特性。 平均互信息的凸性 本章小结 熵、互信息定义及含义 互信息与熵的关系 信息处理定理 )()()()|()()|()();();();( 凸性 信道一定时，平均互信息是信源先验概率的上凸函数 信源一定时，平均互信息是信道转移概率的下凸函数 微分熵的定义及与熵的差别 27个硬币中有一个重量偏轻，其它 26个为标准重量。 试用信息量观点分析在 不用砝码的天平上至少称多少次，就能发现这个轻的硬币？怎样称？ 思考 : 设有 4枚同值硬币，其中 1枚硬币可能是假币，如是假币，其重量与真币不同，但不知比真币轻还是重。现在给你一部没有砝码的天平和 1枚真币，要求你回 答有无假币？如 有假币要求找出那枚假币，并指出那枚假币是比真币轻还是重？ 试用信息量观点分析最少需称多少次才能保证一定能找出那枚假币，并给出具体称法。 思考 : 第二章 习题 莫尔斯电报系统中，若采用点长为 长为 点和划出现的概率分别为 2/3和 1/3，试求它的信息速率 (s)。 解 : 平均每个符号长为 秒 每个符号的熵为 比特 所以，信息速率为 比特 /秒 9 1 8 o o 44 一对无偏的骰子，若告诉你得到的总的点数为：(a) 7； (b) 12。 试问各得到了多少信息量 ? 3665 8 66(lo g 2 g 2 解 : (a)一对骰子总点数为 7的概率是 所以，得到的信息量为 (b) 一对骰子总点数为 12的概率是 所以，得到的信息量为 比特 比特 过充分洗牌后的一付扑克 (含 52张牌 )，试问： (a) 任何一种特定排列所给出的信息量是多少 ? (b) 若从中抽取 13张牌，所给出的点数都不相同时得到多少信息量 ? ! 5!52 1lo g 2 1 3 1 31 3 1 35 2 5 21 3 ! 4 4g 1313522 (a)任一特定排列的概率为 所以，给出的信息量为 (b) 从中任取 13张牌 ,所给出的点数都不相同的概率为 所以，得到的信息量为 比特 . 比特 有一个非均匀骰子，若其任一面出现的概率与该面上的点数成正比，试求各点出现时所给出的信息量，并求掷一次平均得到的信息量。 解 :易证每次出现 21 o (6,5,4,3,2,1,21l o g)(2612园丁植树一行，若有 3棵白杨、 4棵白桦和 5棵梧桐。设这 12棵树可随机地排列，且每一种排列都是等可能的。若告诉你没有两棵梧桐树相邻时，你得到了多少关于树的排列的信息 ? 解 : 可能有的排列总数为 2 7 7 2 0!5!4!3!12 没有两棵梧桐树相邻的排列数可如下图求得 . Y X Y X Y X Y X Y X Y X Y X Y 3758图中 :有 种排法， 种排法 . 有 5837所以共有 * =1960种排法保证没有两棵梧桐树相邻。 因此，若告诉你没有两棵梧桐树相邻时，得到关于树排列的信息为 =特 1 9 6 0l 7 2 0l 2 随机掷三颗骰子，以 求 H(Z|Y)、 H(X|Y)、H(Z| H()和 H(Z|X)。 6解 :令 X=2,Z=2+H(H(H( H(X)= H(=特 =特 H(Y)= H(3) 6l o 36l o o o o o 222222= 比特 H(Z)= H(2+)27216l o o o o o o o o 22222222= 特 所以 H(Z/Y)= H( 比特 H(Z/X) = H(3)= 特 H(X/Y)=H(X)+H(Y/X) = 特 H(Z/H(Z/Y)= 特 H()=H(X/Y)+H(Z/=特 2计算习题 (Y； Z)， I (X； Z)， I (Z)， I (Y； Z|X)和 I (X； Z|Y)。 解 : I(Y;Z)=H(Z) =H(Z)- H( I(X;Z)=H(Z)=I(Z)=H(Z) =H(Z) =I(Y;Z/X)=H(Z/X)= H(3)3) = =I(X;Z/Y)=H(Z/Y)=H(Z/Y) =0 2设有一个系统传送 10个数字： 0, 1, , 9。奇数在传送时以 其它数字总能正确接收。试求收到一个数字平均得到的信息量。 解 :设系统输出 10个数字 接收数字为 Y,显然 101)(101)()()( 9190 H(Y)=比特奇 奇奇奇偶18l o o l o g)()()(l o g)()(0)(l o g),()(l o g),()/(22,2222 xy I(X;Y)= 比特 令 , 一等概消息集，各消息相应被 编成下述二元码字 : 000， 011， 101， 110 001， 010， 100， 111 通过转移概率为 求 (a) 接收的第一个数字 0与 u (b) 接收的前二个数字 00与 u (c) 接收的前三个数字 000与 u (d) 接收的前四个数字 0000与 u 解 :（ a）接收前一个数字为 0的概率 2180)0()()0( i t 1(l o o g)0()0(l o g)0;(2212121 （ b）同理 4180)00()()00( i t 1(l o (l o g)00( )00(l o g)00;( 24122121 （ c）同理 8180)0 0 0()()0 0 0( t 1(l (l 00()000(l 00;(28132121 （ d）同理 )1(6)1()0 0 0 0()()0 0 0 0( 42268180 b i t (6)1()1(8l o g)1(6)1()1(l o g)0000()0000(l o g)0000;(令 X、 Y、 证明下述关系式成立。 (a) H()H(Y|X) H(Z|X)，给出等号成立的条件。 (b) H()=H(Y|X) H(Z| (c) H(Z|H(Z|X)，给出等号成立的条件。 证明 : (b) )/()/()/(1l o g)()/(1l o g)()/()/(1l o g)()/(1l o g)()/(y zx y zx y zx y z (c) )/()/(1l o g)/()()/(1l o g)/()()/(y zx y z 等号成立的条件为 , 对所有 ,即在给定 与 )/()/( ,(a) )/()/()/()/()/( 等号成立的条件同（ c） 对于任意概率事件集 X、 Y、 Z，证明下述三角不等式成立。 H(X|Y) H(Y|Z)H(X|Z) H(X|Y)/H( H(Y|Z)/H(H(X|Z)/H(证明 : (a) )/()/()/()/()/()/(b) 221121221121210,0)()/()()/()/()()/()/()/()/()()/()()/(0)(,0)/()/()/()()/()/()/()/()/()()/()/()/()/()()/()/()/()/()()/()/()/()()/()/()()/()/()()/()()/()()/(若三个随机变量有如下关系： x y=z，其中 x和 证明： H(X)