《费诺不等式及数据处理讲解》由会员分享，可在线阅读，更多相关《费诺不等式及数据处理讲解（23页珍藏版）》请在金锄头文库上搜索。
1、信息论基本概念 概要 n基本概念 n链式法则 nJensen不等式 n数据处理不等式 n费诺不等式 n渐进均分性定理 n数据压缩(AEP的推论) 基本概念-熵 nX是一个离散随机变量, 取值空间为X, 概率密度函数 p(x)=Pr(X=x), xX; n定义 一个离散型随机变量X的熵H(X)定义为 H(X)=-xXp(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)=-xXyYp(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)=xXp(x)H(Y|X=x) =-xXp(x) yYp(y|x)logp(y|x) =-xXyYp(x,y)logp(y|x) =-Ep(x,y)logp(Y|X) 基本概念-相对熵与互信息 n定义 两个概率密度函数为p(x)和q(x)之间的相对熵(或Kullback- Leible
3、r距离)定义为 规定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)之间的相对熵, 即: 基本概念-熵与互信息的关系 nI(X;Y)=H(X)-H(X|Y) 互信息I(X;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
4、) nI(X;X)=H(X) 基本概念-条件互信息 n条件互信息熵: 在给定Z时由于Y的知识而引起关于X的 不确定度的缩减量. n定义 随机变量X和Y在给定随机变量Z时的条件互信息 (conditional mutual information)定义为 链式法则 n定理2.2.1(链式法则) H(X, Y)=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(互信息的
5、链式法则) 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) =ni=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不等式)
6、若给定凸函数f和一个随机变量X, 则 Ef(X)f(EX) n证明: 这里只证明离散分布情形, 且对分布点的个数进行归纳证明. 对于两点分布, 不等式变为 p1f(x1)+p2f(x2)f(p1x1+p2x2) 这由凸函数的定义可直接得到. 假定当分布点个数为k-1时, 定理成立, 此时记 pi=pi/(1-pk)(i=1, 2, ., k-1), 则有 其中第一个不等式由归纳法假设得到, 第二个不等式由凸性的定义可得. Jensen不等式(2)-信息不等式 n定理2.6.3 (信息不等式 )设p(x), q(x)(xX)为两个 概率密度函数, 则 D(p|q)0 当且仅当对任意的x, p(x
7、)=q(x), 等号成立. 证明: 设A=x:p(x)0为 p(x)的支撑集,则如右. 其中,(1)由Jensen不等式 得到. Jensen不等式(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定
8、义 如果Z的条件分布依赖于Y的分布, 而与X 是条件独立的, 则称随机变量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)=
9、0. 又由于I(X;Y|Z)0, 则有 I(X;Y)I(X;Z) 当且仅当I(X;Y|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
10、)I(X;Y) n于是, 通过观察”顺流”的随机变量Z, 可以看到X与Y的依 赖程度会有所降低(或保持不变). 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) 或 注释: 明显地, 有式(1)可知Pe=0可推出H(X|Y)=0. 费诺不等式(2) n证明: 定义一个误差随机变量E, 当XX时, E=1; 当X=X时, E=0.
11、n利用熵的链式法则将H(E,X|X)以两种不同方式展开, 有 因为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)； 另一部分是指当错误发生后，到底是哪个输 入符号发送而造成错误的最大不确定性，它 是(n1)个符号不确定性的最大值log(n1) 与PE的乘积。 渐进均分性定理(1) n定义(随机变量的收敛) 给定一个随即变量序列X1, X
12、2, . 序 列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是i.i.d., 从而logp(Xi)也是i.i.d 因而, 由弱大数定律, -(1/n)logp(X1, X2, , Xn)
13、= -(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.2 1. 如果(x1, x2, ., xn)A(n), 则H(X)-(1/n)logp (x1, x2, ., xn)H(X)+. 2. 当n充分大时, PrA(n)1-. 证明: 性质1的证明可以
14、直接由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) 3. |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中的序
15、列划分为两个集合: 典型集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-, 于是, 码字长度的数学期望为 其中, =+ log|X|+2/n, 适当选取和n时, 可以任意小. 数据压缩(3) n定理3.2.1 设Xn为服从p(x)的i.i.d序列, 0, 则存 在一个编码将长度为n的序列xn映射为比特串, 使得映射是一一对应的(因而可逆), 且对于充分 大的n, 有 n因而从平均意义上, 用nH(X)比特可表示序列Xn.
