离散信息的度量

北京邮电大学信息工程学院 第 2章 离散信息的度量 北京邮电大学信息工程学院 2.1 自信息和互信息 自信息 自信息 联合自信息 条件自信息 互信息 互信息 互信息的性质 条件互信息 北京邮电大学信息工程学院 2.1.1 自信息 事件集合 X 中的事件 的自信息： iax )(a- l o gP)(aI iXiX 简记 ii - l og p)I(a l og p( x )- I ( X ) 或01ip1i ip其中： 1） ， 2） 非负)( XI对数的底数大于 1 北京邮电大学信息工程学院 本书符号的约定 X集合x事件)(aPx ix 的概率ia),(P XY ji ba联合概率北京邮电大学信息工程学院 比特x2lo g奈特xln哈特x10lo g比特奈特 443.11 比特哈特 32.31 关于对数底的选取 北京邮电大学信息工程学院 事件发生的不确定性事件发生前 事件包含的信息量事件发生后 2.1.1 自信息 自信息为随机变量 自信息的含义包含两方面： 北京邮电大学信息工程学院 2.1 例 箱中有 90个红球， 10个白球。现从箱中随机地取出一个球。求： （ 1）事件 “ 取出一个红球 ” 的不确定性； （ 2）事件 “ 取出一个白球 ” 所提供的信息量； （ 3）事件 “ 取出一个红球 ” 与 “ 取出一个白球 ”的发生，哪个更难猜测？ 北京邮电大学信息工程学院 （ 1）设 表示 “ 取出一个红球 ” 的事件，则 故事件 的不确定性为： 比特 （ 2）设 表示 “ 取出一个红球 ” 的事件，则 故事件 所提供的信息量为： 比特 （ 3）因为 ，所以事件 “ 取出一个白球 ” 的发生更难猜测。 解： 9.0)( 1 ap1a1 5 2.09.0log)( 1 aI1a2a 1.0)( 2 ap2a323.31.0log)( 2 aI)()( 12 aIaI 北京邮电大学信息工程学院 联合自信息 事件集合 XY 中的事件 的自信息： ji byax ,)b,(a- l o g P)b,(aI jiXYjiXY 简记 log p( xy )- I ( X Y ) 其中： 1） p(xy)要满足非负和归一化条件 北京邮电大学信息工程学院 2.1(续 ) 例 箱中球不变，现从箱中随机取出两个球。求： （ 1）事件 “ 两个球中有红、白球各一个 ” 的不确定性； （ 2）事件 “ 两个球都是白球 ” 所提供的信息量； （ 3）事件 “ 两个球都是白球 ” 和 “ 两个球都是红球 ” 的发生，哪个事件更难猜测？ 北京邮电大学信息工程学院 三种情况都是求联合自信息。设 x为红球数， y为白球数。 解： (1) 11/22/99100 1090)1,1( 2100110190 CCCPXY460.211/2lo g)1,1( I 比特 (2) 110/12/991002/910)2,0(2100210 CCPXY7 8 2.61 1 0/1lo g)2,0( I 比特 (3) 110/892/99100 2/8990)0,2( 2100290 CCPXY306.0110/89lo g)0,2( I 比特 因为 ，所以事件“两个球都是白球”的发生更难猜测。 )0,2()2,0( II 北京邮电大学信息工程学院 条件自信息 )b|(a- l o g P)b|(aI jiY|XjiY|X 简记 y)|lo gp ( x- Y)|I ( X p(x|y)要满足非负和归一化条件 事件 给定，事件 的自信息： jby iax 北京邮电大学信息工程学院 事件发生的不确定性事件发生前 事件包含的信息量事件发生后 条件自信息的含义包含两方面： ij a，xby 给定ij a，xby 给定自信息、条件自信息和联合自信息之间的关系 I(xy)= I(x)+ I(y|x)= I(y)+ I(x|y) 北京邮电大学信息工程学院 2.1(续 ) 例 箱中球不变，现从箱中先拿出一球，再拿出一球，求： （ 1）事件 “ 在第一个球是红球条件下，第二个球是白球 ”的不确定性； （ 2）事件 “ 在第一个球是红球条件下，第二个球是红球 ”所提供的信息量。 北京邮电大学信息工程学院 这两种情况都是求条件自信息，设 r表示红球， w表示白球。 解： (1) 比特 (2) 比特 99/10)|( rxwyp307.399/10l o g)|( rxwyI99/89)|( rxryp154.099/89l o g)|( rxryI北京邮电大学信息工程学院 2.2 例 有 8 8=64个方格，甲将一棋子放入方格中， 让 乙猜 ： 1）将方格按顺序编号，让乙猜顺序号的困难程度为何？ 2）将方格按行和列编号，当甲告诉乙方格的行号后，让乙猜列顺序号的困难程度为何？ 解： 两种情况下的不确定性 1) I(xy)=log2 64=6 bit 2) I(x|y)=-log2 p(x|y)=-log2(1/8)=3 bit 北京邮电大学信息工程学院 2.1.2 互信息 互信息 互信息的性质 条件互信息 北京邮电大学信息工程学院 互信息 简记 通过计算 离散随机事件 之间的互信息： ji b，yax / i j;Xi( / b )( ; ) l o gP ( a )XYX Y i jPaI a b ( / )( ; ) l o g()p x yI x ypx ( ; ) l o g jiijipI a bp或 )|()();( yxIxIyxI I(x;y)与 I(x|y)的区别？ 北京邮电大学信息工程学院 互信息的性质 互易性 当事件 x， y统计独立时，互信息为 0，即I(x;y)=0 互信息可正可负 任何两事件之间的互信息不可能大于其中任一事件的自信息 北京邮电大学信息工程学院 设 e表示 “ 降雨 ” ， f表示 “ 空中有乌云 ” ，且 P(e)=0.125， P(e|f)=0.8 求： 1） “ 降雨 ” 的自信息 2） “ 空中有乌云 ” 条件下 “ 降雨 ” 的自信息 3） “ 无雨 ” 的自信息 4） “ 空中有乌云 ” 条件下 “ 无雨 ” 的自信息 5） “ 降雨 ” 与 “ 空中有乌云 ” 的互信息 6） “ 无雨 ” 与 “ 空中有乌云 ” 的互信息 2.3 例 )(eI)|( feI)(eI)|( feI);( feI);( feI北京邮电大学信息工程学院 这两种情况都是求条件自信息，设 r表示红球， w表示白球。 解： 1) I(e)= -log0.125 =3 bit 2) I(e |f)= -log0.8 =0.322 bit 3) I( )= -log0.875 =0.193 bit 4) I( |f)= -log0.2 =2.322 bit 5) I(e； f)= 3 0.322 =2.678 bit 6) I( ； f)= 0.193 2.322 = -2.129 bit eee北京邮电大学信息工程学院 ( / )( ; / ) l o g( / )p x y zI x y zp x z条件互信息 除条件外，条件互信息的含义与互信息的含义与性质都相同 设联合集 XYZ，在给定 zZ 条件下 x(X) 与y(Y ) 之间的互信息定义为 ： 北京邮电大学信息工程学院 2.2 信息熵 信息熵的定义与计算 条件熵与联合熵 熵的基本性质 北京邮电大学信息工程学院 I(x)为事件 x的自信息 表示对随机变量 x用 p(x)来进行取平均运算 熵的单位为比特（奈特）信源符号 ()pxE信息熵的定义与计算 离散信源 X的熵定义为自信息的平均值 ,记为 H(X) ()( ) ( ) ( ) l o g ( )px xH X E I x p x p x 北京邮电大学信息工程学院 信源输出前 信源的平均不确定性 信源输出后 一个信源符号所提供的平均信息量 表示信源随机性大小： H（ X）大的，随机性大 信源输出后，不确定性就解除 解除信源不确定性所需信息量 信息熵 H(X)的含义 北京邮电大学信息工程学院 一电视屏幕的格点数为 500 600=300000，每点有10个灰度等级，若每幅画面等概率出现，求每幅画面平均所包含的信息量 2.4 例 解： 可能的画面数是多少？ 代入公式： 30000010300000101 pb i tpXH 630 000022 10)10(l o g)/1(l o g)( 北京邮电大学信息工程学院 2.5 例 A、 B两城市天气情况概率分布如下表 ： 晴 阴 雨 A城市 0 8 0 15 0 05 B城市 0 4 0 3 0 3 问哪个城市的天气具有更大的不确定性？ 北京邮电大学信息工程学院 所以， B城市的天气具有更大的不确定性。 解： 符号比特 / 884.0 05.0l o g05.015.0l o g15.08.0l o g8.0)05.0,15.0,8.0()( HAH符号比特 / 5 7 1.1 3.0l o g3.03.0l o g3.04.0l o g4.0)3.0,3.0,4.0()( HBH北京邮电大学信息工程学院 2.6 例 有甲、乙两箱球，甲箱中有红球 50、白球 20、黑球 30；乙箱中有红球 90、白球 10。现做从两箱中分别随机取一球的实验，问从哪箱中取球的结果随机性更大？ 解： 设 A、 B分别代表甲、乙两箱，则 所以，从甲箱中取球的结果随机性更大。 符号比特 / 4 8 6.1 3.0l o g3.02.0l o g2.05.0l o g5.0)03,2.0,5.0()( HAH符号比特 / 4 6 9.01.0l og1.09.0l og9.0)1.0,9.0()( HBH北京邮电大学信息工程学院 信息熵的计算 定理 2.1 离散信源的熵等于所对应的有根概率树上所有节点 (包括根节点，不包括叶 )的分支熵用该节点概率加权的和，即 i ii uHuqXH )()()(其中， q(ui)为节点 ui的概率， H(ui)为节点 ui的分支熵。 北京邮电大学信息工程学院 2.6 例 2 / 31 / 3r : 1p1 - p1 / 21 / 2a3: 2 ( 1 - p ) / 3b2: 2 / 3b1: 2 p / 3a1: p / 3a2: p / 3a4: 1 / 3北京邮电大学信息工程学院 ()( / ) ( / ) p x yH Y X E I y x x yxypyxp )/(l o g)( x yxypxypxp )/(l o g)/()(xxYHxp )/()(的熵取某一特定值时为在 YxxypxypxYHy )/(l o g)/()/(条件熵 条件熵： 联合集 XY上，条件自信息 I(y|x)的平均值 北京邮电大学信息工程学院 2.7 例 随机变量 X和 Y，符号集均为 0， 1 解： 求 H(Y|X) 32)0(x p 31)1(x p21)0|1()0|0( xypxyp 1)1|1( xyp)1|()1()0|()0()|()()|( xYHxpxYHxpxYHxpXYHx符号比特 / 32)1(31)21(32 HH北京邮电大学信息工程学院 ()( ) ( ) p x yH X Y E I x y x yyxpyxp )(l o g)(联合熵 联合熵： 联合集 XY上，对联合自信息 I(xy)的平均值 北京邮电大学信息工程学院 2.7(续 ) 例 由已知条件可得 XY的联合概率分布，如下表所示 解： 求 H(XY) Y p(xy) 0 1 X 0 1 0 313131符号比特 / 585.13l og)31,31,31()Y( HXH北京邮电大学信息工程学院 熵的基本性质 凸函数 信息散度 熵的基本性质 各类熵的关系 熵函数的唯一性 北京邮电大学信息工程学院 凸函数 1l o g)()(iiippppHXH 元函数为 1)( nXH2n当 )()1,(),()( 11121 pHppHppHpH 下面我们来定义凸函数 LOOK一下 北京邮电大学信息工程学院 对于 (01) 及任意两矢量 x1,x2，有 fx 1+(1-)x 2f(x 1)+(1-)f(x 2) 上凸函数 (cap) x1 x2 若当且仅当 x1 = x2或 = 0,1时等式成立 严格上凸函数 对于 (01) 及任意两矢量 x1,x2，有 fx 1+(1-)x 2 f(x 1)+(1-)f(x 2) 下凸函数 (cup) x1 x2 若当且仅当 x1 = x2或 = 0,1时等式成立 严格下凸函数 北京邮电大学信息工程学院 定理 ： )(11qkkkqkkk xfxf f(x)是区间上的实值连续严格上凸函数 任意一组 x1,x2, ,xq 1, 2, , q， k=1 当且仅当 x1=x2=x q或 k=1（ 1 k q）且 j=0（ j k）时，等式成立 Jenson不等式 北京邮电大学信息工程学院 证 利用数学归纳法。根据上凸函数的定义有 f x1+(1- )x2 f(x1)+(1- )f(x2) 其中 0log24 熵的链原则 举例 北京邮电大学信息工程学院 极值性： 熵的基本性质 (2) 定理 2. 4. 3 (离散最大熵定理 ) 对于离散随机变量集合，当集合中的事件等概率发生时，熵达到最大值 证 设随机变量集合有 n个符号，概率分布为 P(x) ； Q(x)为等概率分布，即 Q(x)=1/n。 根据散度不等式有 x xQxPxPQPD)()(l o g)()/( x x nxPxPxP )/1l o g ()()(l o g)(0lo g)( nXHnXH lo g)( 北京邮电大学信息工程学院 确定性： 上凸性： 熵的基本性质 (3) H(1,0) = H(1,0,0)= = H(1,0,0) = 0 。 当随机变量集合中任一事件概率为 1时，熵为 0 H(p)=H(p1,p2,pn) 是 (p1,p2,pn) 的严格的上凸函数 北京邮电大学信息工程学院 各类熵的关系 条件熵不大于信息熵： 定理 （熵的不增原理） )()|( YHXYH 在信息处理过程中，条件越多，熵越小。 )/(l o g)/()()(l o g)()/()( xypxypxpyqyqXYHYHY x y x y yqxypxypxp)()/(l o g)/()(0北京邮电大学信息工程学院 各类熵的关系 联合熵不大于个信息熵的和： NiiN XHXXXH121 )()(证明思路：熵的可加性 )()|( YHXYH 联合熵与信息熵、条件熵的关系 H(XY)= H(X) + H(Y/X ) 北京邮电大学信息工程学院 熵函数的唯一性 是概率的连续函数 信源符号等概率时是 n（信源符号数）的增函数 可加性 如果要求熵函数满足以下条件： 那么，熵函数的表示是唯一的。 北京邮电大学信息工程学院 2.3 平均互信息 平均互信息的定义 平均互信息的性质 平均条件互信息 北京邮电大学信息工程学院 集合与事件之间的互信息 集合 X与事件 y=bj之间的互信息： 由事件 y=bj提供的关于集合 X的平均条件互信息（用条件概率平均） x xpyxPyxPyXI)()|(l o g)|();(定理 I(X； y) 0， 仅当 y与所有 x 独立时，等式成立。 证 根据散度的定义，有 仅当对所有 x， p(x)= p(x / y ) 时，等式成立 , 证毕。 /( ; ) ( / / ) 0X y XI X y D P P北京邮电大学信息工程学院 平均互信息 集合 X、 Y之间的平均互信息： xxYIxpYXI );()();(yx ypxypxypxp, )()/(l o g)/()( yxxxypxpxypxypxp, )/()()/(l o g)/()( jiiijiijiji ppppp,l o g北京邮电大学信息工程学院 I(X ;Y) H(Y |X)H(X |Y)H(Y )H(X )H (XY )平均互信息与熵的关系 I(X;Y)= H(X)- H(X|Y) I(X;Y)= H(Y)- H(X|Y) I(X;Y)=H(X)+ H(Y)- H(XY) 北京邮电大学信息工程学院 平均互信息的性质 非负性： 定理 ： I(X;Y)0 仅当 X， Y 独立时，等式成立 证明思路： 0);( yXI 0 其均值 互易性 (对称性 )： );();( XYIYXI 凸函数性 北京邮电大学信息工程学院 定理： I(X;Y)为概率分布 p(x)的上凸函数。 证明思路： )(),(21 xpxp设)()1()()(,10 21 xpxpxp 取令)()1()()( 21 xpIxpIxpI 那么只要证)();( xpIYXI 北京邮电大学信息工程学院 ppppqq111)1()0( ppppq 2)1()1()0( ppppppq 21)1()1()1)(1()1( )2()( ppHYH 二元信源 X输出符号为 0,1， PX(0)= ，条件概率分别为 PY|X(0|0) = PY|X(1|1)=1-p， PY|X(1|0)= PY|X(0|1)=p， 求 I(X;Y)。 例 解： )1()1()0()0(qPqPYY 北京邮电大学信息工程学院 ( | ) ( 1 ) l o g ( 1 ) l o g ( 1 ) l o g ( 1 ) l o g ( 1 ) H Y X p p p p p p p p )()1l o g ()1(l o g pHpppp )()2()|()();(pHppHXYHXHYXI0)21()21();(,21,21,21HHYXIpp当有极大值时当 可见： 1）这是一个上凸函数； 2） 212 pp 02/1(21 ）（移项 p北京邮电大学信息工程学院 北京邮电大学信息工程学院 定理： 对于固定的概率分布 p(x)， I(X;Y)为条件概率p(x|y)的下凸函数。 证明思路： )|(),|(21 xypxyp设)|()1()|()|(,10 21 xypxypxyp 取令 yxyp 1)|( )|();( xypIYXI 记)|()1()|()|( 21 xypIxypIxypI 那么只要证北京邮电大学信息工程学院 固定 ，pHppHYXI )()2();( 10I( X ;Y )H( )1 / 2p续 例 解： 这是一个下凸函数 北京邮电大学信息工程学院 I(X； Y) H(X) I(X； Y) H(Y) 极值性： 北京邮电大学信息工程学院 平均条件互信息 设联合集 XYZ， Z条件下， X与 Y之间的平均互信息： );()|;()( )|()|( )|(l o g)( )|(l o g);( zxIzyxIxp zxpzxp yzxpxp yzxpyzxI 由于( ; ) ( ; / ) ( ; )I x y z I x z y I x y zyxzyx zxpyzxpxyzpzxpyzxpZYXI, )|()|(l o g)()|()|( l o g)|;();()/;();()/;();( ZXIZYXIYXIYZXIYZX：I， 得两边求平均北京邮电大学信息工程学院 0)/;( ZYXI等式成立时当且仅当 0)/()/;()|()|( / YZZXX Y Z PPPDZYX，Iyzxpzxp 定理：平均条件互信息是非负的： 等式成立当且仅当 ，yzxpzxp )|()|( 证明： ,( / )( ; / ) ( ) l o g( / )()( ) l o g( / ) ( )x y zx y zp x y zI X Y Z p x y