费诺不等式及数据处理

1、信息论基本概念概要n基本概念n链式法则nJensen不等式n数据处理不等式n费诺不等式n渐进均分性定理n数据压缩(AEP的推论)基本概念-熵nX是一个离散随机变量是一个离散随机变量, 取值空间为取值空间为X X, 概率密度函数p(x)=Pr(X=x), xX X;n定义 一个离散型随机变量X的熵H(X)定义为H(X)=-xX Xp(x)log p(x)n单位为比特(2为底), 奈特(e为底);n规定0log0=0;nH(X)0;nHb(X)=logbaHa(X);nH(p)=-plogp-(1-p)log(1-p);基本概念-联合熵与条件熵n定义 对于服从联合分布为p(x, y)的一对离散随机

2、变量(X, Y), 其联合熵H(X, Y)(joint entropy)定义为H(X, Y)=-xX XyY Yp(x, y)logp(x, y) 亦即 H(X, Y)=-Elogp(x, y)n定义 若(X,Y)p(x, y), 条件熵(conditional entropy) H(Y|X)定义为: H(Y|X)=xX Xp(x)H(Y|X=x) =-xX Xp(x) yY Yp(y|x)logp(y|x) =-xX XyY Yp(x,y)logp(y|x) =-Ep(x,y)logp(Y|X)基本概念-相对熵与互信息n定义 两个概率密度函数为p(x)和q(x)之间的相对熵(或Kullbac

3、k-Leibler距离)定义为 规定0log(0/0)=0, 0log(0/q)=0, plog(p/0);n定义 考虑两个随机变量X和Y, 他们的联合概率密度函数为p(x, y), 其边际概率密度函数分别为p(x)和p(y). 互信息I(X;Y)为联合分布p(x, y)和乘积分布p(x)p(y)之间的相对熵, 即: )()(log)()(log|XqXpExqxpxpqpDpxX)()(),(log)()(|),()()(,log,);(),(YpXpYXpEypxpyxpDypxpyxpyxpYXIyxpxy XY基本概念-熵与互信息的关系nI(X;Y)=H(X)-H(X|Y)互信息I(X

4、;Y)是在给定Y知识的条件下X的不确定度的缩减量.nI(X;Y)=H(Y)-H(Y|X)X含有Y的信息量等同于Y含有X的信息量.nI(X;Y)=H(X)+H(Y)-H(X, Y)nI(X;Y)=I(Y;X)nI(X;X)=H(X)基本概念-条件互信息n条件互信息熵: 在给定Z时由于Y的知识而引起关于X的不确定度的缩减量.n定义 随机变量X和Y在给定随机变量Z时的条件互信息(conditional mutual information)定义为)|()|()|,(log),|()|()|;(),(ZYpZXpZYXpEZYXHZXHZYXIzyxp链式法则n定理2.2.1(链式法则)H(X, Y)

5、=H(X)-H(Y|X)n定理2.5.1(熵的链式法则) 设随机变量X1, X2, ., Xn服从p(x1, x2, ., xn), 则H(X1, X2, ., Xn)=ni=1H(Xi|Xi-1, ., X1)证明: 重复利用定理2.2.1的展开法则可得.n定理2.5.2(互信息的链式法则)I(X1, X2, ., Xn;Y)=ni=1I(Xi;Y|Xi-1, ., X1)证明: I(X1, X2, ., Xn;Y) =H(X1, X2, ., Xn)-H(X1, X2, ., Xn|Y) =ni=1H(Xi|Xi-1, ., X1)- ni=1H(Xi|Xi-1, ., X1, Y) =n

6、i=1I(Xi;Y|Xi-1, ., X1)Jensen不等式(1)n定义 若对于任意的x1, x2(a, b)及01, 满足f(x1+(1-)x2) f(x1)+(1-)f(x2)则称函数f(x)在区间上是凸的(convex).n定理2.6.2 (Jensen不等式)若给定凸函数f和一个随机变量X, 则Ef(X)f(EX)n证明: 这里只证明离散分布情形, 且对分布点的个数进行归纳证明.对于两点分布, 不等式变为p1f(x1)+p2f(x2)f(p1x1+p2x2)这由凸函数的定义可直接得到. 假定当分布点个数为k-1时, 定理成立, 此时记pi=pi/(1-pk)(i=1, 2, ., k

7、-1), 则有kiiikiiikkkkiiikkkkiiikkkkiiixpfxppxpfxpfpxfpxfppxfpxfp11111111)1 ()1 ()()()1 ()()(其中第一个不等式由归纳法假设得到, 第二个不等式由凸性的定义可得.Jensen不等式(2)-信息不等式n定理2.6.3 (信息不等式)设p(x), q(x)(xX)为两个概率密度函数, 则D(p|q)0当且仅当对任意的x, p(x)=q(x), 等号成立.证明: 设A=x:p(x)0为p(x)的支撑集,则如右.其中,(1)由Jensen不等式得到.01log)(log)(log)()()(log)()(log)()(

8、)(log)(|) 1 (XxAxAxAxAxxqxqxpxqxpxpxqxpxqxpxpqpDJensen不等式(3)n推论(互信息的非负性) 对任意两个随机变量X和Y,I(X;Y)0当且仅当X与Y相互独立, 等号成立.证明: I(X;Y)=D(p(x,y)|p(x)p(y)0, 当且仅当p(x,y)=p(x)p(y)(即X与Y为相互独立), 等号成立.n定理2.6.5 (条件作用使熵减少)(信息不会有负面影响)H(X|Y)H(X)当且仅当X与Y相互独立,等号成立.证明: 0I(X;Y)=H(X)-H(X|Y)数据处理不等式(1)n定义 如果Z的条件分布依赖于Y的分布, 而与X是条件独立的,

9、 则称随机变量X, Y, Z依序构成马尔可夫(Markov)链(记为XYZ). 具体讲, 若X, Y, Z的联合概率密度函数可写为p(x,y,z)=p(x)p(y|x)p(z|y)n则X, Y, Z构成马尔可夫链XYZ.数据处理不等式(2)n定理2.8.1 (数据处理不等式)若XYZ, 则有I(X;Y)I(X;Z).证明: 有链式法则, 将互信息以两种不同方式展开:I(X;Y,Z)=I(X;Z)+I(X;Y|Z) =I(X;Y)+I(X;Z|Y)由于在给定Y的情况下, X与Z是条件独立的, 因此有I(X;Z|Y)=0. 又由于I(X;Y|Z)0, 则有I(X;Y)I(X;Z)当且仅当I(X;Y

10、|Z)=0(即XZY构成马尔可夫链), 等号成立. 类似地, 可以证明I(Y;Z)I(X;Z).数据处理不等式(3)n推论 特别地, 如果Z=g(Y), 则I(X;Y)I(X;g(Y).证明: XYg(Y)构成马尔可夫链.这说明数据Y的函数不会增加关于X的信息量.n推论 如果XYZ, 则I(X;Y|Z)I(X;Y).证明: 因为I(X;Y,Z)=I(X;Z)+I(X;Y|Z) =I(X;Y)+I(X;Z|Y)以及利用I(X;Z|Y)=0(由马尔可夫性), I(X;Z)0, 我们有I(X;Y|Z)I(X;Y)n于是, 通过观察”顺流”的随机变量Z, 可以看到X与Y的依赖程度会有所降低(或保持不变

11、). n注意: 当X, Y, Z不构成马尔可夫链时, 有可能I(X;Y|Z)I(X;Y).费诺不等式(1)n定理2.10.1(费诺不等式) 对于任何满足XYX的估计量X, 设Pe=PrXX, 有H(Pe)+Pelog|X|H(X|X)H(X|Y) (1)上述不等式可以减弱为1+ Pelog|X|H(X|Y)或Xlog1)|(YXHPe注释: 明显地, 有式(1)可知Pe=0可推出H(X|Y)=0.费诺不等式(2)n证明: 定义一个误差随机变量E, 当XX时, E=1; 当X=X时, E=0.n利用熵的链式法则将H(E,X|X)以两种不同方式展开, 有XXlog)(log0)1 ()() 1,|

12、() 1Pr() 0,|() 0Pr()(),|()(),|()(),|()|(0)|(),|()|(),(eeeeeeePPHPPPHEXXHEEXXHEPHXEXHPHXEXHEHXEXHXEHXXHXXEHXXHXXEH因为XYX构成马尔科夫链,由数据处理不等式有I(X;X)I(X;Y), 从而H(X|X)H(X|Y). 于是,有H(Pe)+Pelog|X|H(X|X)H(X|Y)费诺不等式(3)此外，从费诺不等式可以看出，接收到y后关于x的不确定性分为两部分: 一部分是指接收到y后是否产生错误的不确定性H(PE)；另一部分是指当错误发生后，到底是哪个输入符号发送而造成错误的最大不确定性

13、，它是(n1)个符号不确定性的最大值log(n1)与PE的乘积。 渐进均分性定理(1)n定义(随机变量的收敛) 给定一个随即变量序列X1, X2, . 序列X1, X2, 收敛于随机变量X有如下三种情形:1. 如果对任意0, Pr|Xn-X|0, 则称为依概率收敛.2. 如果E(Xn-X)20, 则称为均方收敛.3. 如果PrlimnXn=X=1, 则称为以概率1(或称几乎处处)收敛.n定理3.1.1(AEP) 若X1, X2, , Xn为i.i.dp(x), 则-(1/n)logp(X1, X2, , Xn)H(X) 依概率n证明: 独立随机变量的函数依然是独立随机变量. 因此, 由于Xi是

14、i.i.d., 从而logp(Xi)也是i.i.d. 因而, 由弱大数定律,-(1/n)logp(X1, X2, , Xn)= -(1/n)ilogp(Xi) -Elogp(X) 依概率 = H(X)n这就证明了该定理.渐进均分性定理(2)n定义 关于p(x)的典型集A(n)(typical set)是序列(x1, x2, ., xn)Xn的集合, 且满足性质:2-n(H(X)+)p(x1, x2, ., xn)2-n(H(X)-)作为渐进均分性的一个推论, 可以证明典型集A(n)有如下性质:n定理3.1.21. 如果(x1, x2, ., xn)A(n), 则H(X)-(1/n)logp (

15、x1, x2, ., xn)H(X)+.2. 当n充分大时, PrA(n)1-. 证明: 性质1的证明可以直接由A(n)的定义得到. 性质2由定理3.1.1直接得到, 这是由于当n时, 事件 (X1, X2, , Xn)A(n)的概率趋于1. 于是对任意0, 存在n0, 使得当nn0时, 有Pr|-(1/n)logp(X1, X2, , Xn)-H(X)|1- 令=, 即可得到性质2.渐进均分性定理(2)()()()()()()(2)1 (,221,1,)(XHnnnXHnAXHnnnAAAAnn所以所以充分大时证明：当xPrPr.2,22)()(1)()()()()()()(XHnnnXHn

16、AXHnAAAppnn所以证明：xxxxxX3. |A(n)|2n(H(X)+), 其中|A|表示集合A中的元素个数.4. 当n充分大时, |A(n)|(1-)2n(H(X)-).数据压缩(1)n设X1, X2, , Xn为服从概率密度函数p(x)的i.i.d随机变量下面对随机序列Xn进行压缩.n编码:n1. 将Xn中的序列划分为两个集合: 典型集A(n)及其补集.n2. 将每个集合中的所有元素按照某种顺序排序.n3. 用n(H+)+1比特表示A(n)中元素的序号, 并且在这些序号前加0.n4. 对于不属于A(n)中元素用nlog|X|+1比特表示其序号,并且在这些序号前加1.n上述编码方案有如下特点:n编码一一对应, 起始位标识了紧随码字的长度.n对非典型集A(n)c的元素作了枚举, 没有考虑A(n)c元素个数实际上少于Xn中元素个数.n典型序列具有较短的描述长度nH.数据压缩(2)下面证明上述编码方案的码字平均长度为nH(X).n下面用记号xn表示x1, x2, ., xn. 设l(xn)表示相应于xn的码字长度. 若n充分大, 使得PrA(n)1-, 于是, 码字长度的数学期望为) (2log)2logPr)Pr)2log(Pr)2)Pr)2log)()2)()()