2.3 信息熵的基本性质_信息论基础(第2版)-QQ阅读男生武侠网

上QQ阅读APP看书，第一时间看更新

2.3 信息熵的基本性质

本节介绍熵的基本性质。由于凸函数性是熵和其他信息度量的主要性质之一，所以我们首先介绍凸函数的基本概念。

2.3.1 凸函数及其性质

1.凸函数的定义

多元实值函数 f(x)= f(x1,x2,…,xn)称为定义域上的上凸(cap)函数，若对于任何 α(0≤α≤1)，及任意两矢量x1，x2，有

f(αx1+(1-α)x2)≥α f(x1)+(1−α)f(x2)　　　　　（2.23）

成立；若对于任何α及任意x1，x2，上面不等式反向，则称f(x)为下凸(cup)函数；若仅当x1=x2或α=0(或=1）时不等式中等号成立，则称f(x)为严格上凸（或下凸）函数。

由式（2.23）式可以看到，若f(x)为上凸函数，则-f(x)为下凸函数，反之亦然。因此只研究上凸函数即可，因为由此得到的结果可以很容易地推广到下凸函数的情况。

一元上凸函数曲线如图2.1 所示。我们称x=αx1+(1-α)x2为自变量x1，x2的内插值，称g(x)=αf(x1)+(1-α)f(x2)为函数值 f(x1)和 f(x2)的内插值。从图中可以看出，当 α 从 0 变化到 1时，x从x2变到x1，点(x，g(x))从点(x2，g(x2))沿直线段移动到点(x1，f(x1))，此线段实际上是连接两点的弦。上凸的含义就是：在自变量x1和x2之间的区域，函数f(x)的图线在连接曲线上对应两点弦的上方，也可以说，对于上凸函数，两自变量内插值的函数值不小于两对应函数值的内插值。

2.凸函数的性质

（1）若 f1(x),f2(x),…,fk(x)均为上凸函数，c1,c2,…,ck均为正数，那么∑icifi(x)为上凸函数（或严格上凸函数，若 fi(x)中任意一个为严格上凸）。

图2.1 一元上凸函数的图形说明

证利用式（2.23），有

（2）对于一维随机变量x，若 f(x)在某区间的二阶导数小于等于0，即∂2f(x)/∂x2≤0，则在此区间内为上凸函数（或严格上凸函数，若∂2f(x)/∂x2<0）。（此命题为数学分析的内容，此处证明略）。

（3）Jensen不等式，由下面的定理来描述。

定理2.3 若 f(x)是定义在某区间上的上凸函数，则对于任意一组矢量(x1,x2,…,xk)和任意一组非负数λ1,λ2,…,λk，，有

对于严格上凸函数，仅当x1=…=xk或λi=1(1≤i≤k)且λj=0(j≠i)时，等式成立。

证利用数学归纳法证明。

根据上凸函数的定义式（2.23），说明当k=2时，不等式（2.24）成立。假定k=n时式（2.23）成立，那么当k=n+1时，设，令，有λn+1=1-α，所以

式（2.24）称为Jensen不等式。因为λi可作为随机矢量的概率分布，所以有如下推论。

推论2.1若f(x)为上凸函数，那么

E[f (x)]≤f[E(x)]　　　　　　　　　　　（2.25）

在信息论中，对数函数是最常用的上凸函数，根据式（2.25），有

推论2.2对于一元对数函数log(x)，有

E[log(x)]≤log[E(x)]　　　　　　　　　　　（2.26）

2.3.2 熵的基本性质

1.对称性

概率矢量p=(p1,p2,…,pn)中，各分量的次序任意改变，熵不变，即

H(p1,p2,…,pn)=H(pj1,pj2,…,pjn)　　　　　　（2.27）

其中，j1,j2,…,jn是1,2,…,n的任何一种n级排列。该性质说明熵仅与随机变量总体概率特性（即概率分布）有关，而与随机变量的取值及符号排列顺序无关。

2.非负性

H(p)=H(p1,p2,…,pn)≥0　　　　　　　（2.28）

仅当对某个pi=1时，等式成立。

因为自信息是非负的，熵为自信息的平均，所以也是非负的。不过，非负性仅对离散熵有效，而对连续熵来说这一性质并不成立。

3.确定性

H(1,0)=H(1,0,0)=H(1,0,…,0)=0　　　　　　　　（2.29）

这就是说，当随机变量集合中任一事件概率为1时，熵就为0。这个性质意味着，从总体来看，事件集合中虽含有许多事件，但如果只有一个事件几乎必然出现，而其他事件几乎都不出现，那么，这就是一个确知的变量，其不确定性为0。

4.扩展性

利用可得到上面的结果，其含义是，虽然小概率事件自信息大，但在计算熵时所占比重很小，可以忽略。

5.可加性

熵的可加性首先由香农提出，含义如下：如果一个事件可以分成两步连续选择来实现（多步产生的事件也称复合事件），那么原来的熵H应为H的单独值的加权和。“H的单独值”是指每次选择的熵值，“权值”就是每次选择的概率。先看一个简单例子，某随机事件集合有3个事件，概率分别为p1=1/2，p2=1/3，p3=1/6；这3个事件可以直接产生，也可分两步产生，即先以 1/2 的概率产生两个事件，选择其中之一作为输出，或者在另一事件发生条件下再以2/3和1/3的概率产生两事件，选择其中的一个作为输出。3个事件概率的产生可用图2.2的树来描述，从根节点开始，通过两步选择生成的3片树叶代表3个事件，节点旁边的数值表示该节点的概率，分支旁的数字表示分支的条件概率，原节点的概率乘分支条件概率就得到产生的下一节点（也称子节点）的概率。熵的可加性意味概率矢量的熵：

图2.2 复合事件产生例

H(1/2,1/3,1/6)=H(1/2,1/2)+(1/2)H(1/3,2/3)　　　　　　（2.31）

上式等号右边的第1项是第1步选择的熵；由于第2步选择只有1/2的概率发生，所以第2项是第2步选择的熵与权值1/2的乘积。

上例可以推广到一般情况。设某事件集合包含n×m个事件，概率分别为p1p11，…，p1p1m，p2p21，…，p1p2m，…，pnpn1，…，pnpnm，这 n × m 个事件可以分两步产生，第一步产生 n 个事件，其中每个事件的概率分别为p1，p2，…，pn；第二步再以这n个事件为条件，以pi1，…，pim(i=1，…，n)为条件概率，分别产生m个事件。熵的可加性的一般形式可以表示成

其中，pi,pij≥0，对所有i，j，；，i=1,…,n。

可把这n×m个事件的概率写成n×m阶矩阵，形式如下：

可以看到，矩阵（2.33）从第 1 行到第 n 行，每行元素的和分别为 p1,p2,…,pn，因为{pi,i=1,…,n}满足归一性，故可以视为一个事件集合的概率分布，设此集合为X。矩阵（2.33）从第1列到第m列，每列元素的和为，因，故也可把{qj,j=1,…,m}视为另一个事件集合的概率分布，设此集合为Y，X-Y的条件概率矩阵就是式（2.16），矩阵（2.33）就是 XY 的联合概率矩阵，其中，p(x=ai,y=bj)= pipij，所以H(X)= H(p1,…,pn)，H(XY)=H(p1p11,…,p1p1m,p2p21,…,p2p1m,…,pnpn1,…,pnpnm)，，因此式（2.32）与下面定理中的公式等价。

定理2.4（熵的可加性）

H(XY)=H(X)+H(Y|X)=H(Y)+H(X|Y)　　　　　　（2.34）

证

又

其中，p(x|y)= p(x)p(y|x)/ p(y)= pipij/qj。

如果我们把随机事件产生的过程倒过来看，由n×m个事件的集合变成n个事件的集合的过程相当于原事件集合中符号合并的过程，其中每m个事件合并成一个事件。符号合并前的熵由式（2.32）等号的左边表示，合并后的熵由式（2.32）等号右边的第一项表示，而等号右边第二项大于零，所以我们得到一个结论：随机变量符号集中的符号经合并后，随机变量的熵减小。

例2.12 设某地气象为随机变量X，符号集A={晴，多云，阴，雨，雪，雾，霾}，概率分别为 0.3,0.2,0.2,0.05,0.05,0.05,0.15；现将多云和阴用阴代替，雨和雪用降水代替，雾和霾用雾霾代替，得到简化气象Y，符号集B={晴，阴，降水，雾霾}，求两气象熵的差。

解两气象熵的差可利用熵的可加性公式（2.32），有

H(X)-H(Y)=0.4 ×H(1/2)+0.1×H(1/2)+0.2 ×H(1/4)=0.6623bit/符号

实际上，式（2.32）是熵的可加性常用的一种描述方式，是指通过两步产生随机事件的情况，对于多步产生的随机事件的情况，可用多维随机矢量熵的可加性来描述。

定理2.5（熵的链原则）设N维随机矢量(X1X2…XN)，则有

仅当X1,X2,…,XN统计独立（即Xi独立于X1,X2,…,Xi−1，对i=1,…,N）时，等式成立，即

上式称为熵的强可加性。式（2.35）称作熵的链原则，式中规定φ=X1,X2,…,Xi，当i<1

证通过将联合概率展开，再求平均，得

上面的不等式用到熵的不增原理，仅当X1,X2,…,XN统计独立时，等号成立。

熵的可加性可以从多种角度来理解：

① 复合事件集合的不确定性为组成该复合事件的各简单事件集合不确定性的和；

② 对事件输出直接测量所得信息量等于分成若干步测量所得信息量的和；

③ 事件集合的平均不确定性可以分步解除，各步解除不确定性的和等于信息熵。

例 2.13 现有 12 个外形相同的硬币。知道其中有一个重量不同的假币，但不知它是比真币轻，还是比真币重。现用一无砝码天平对这些硬币进行称重来鉴别假币，无砝码天平的称重有3种结果：平衡，左倾、右倾。问至少称几次才能鉴别出假币并判断出其是轻还是重？

解根据熵的可加性，一个复合事件的不确定性可以通过多次实验分步解除，各次试验所得信息量的总和应该不小于随机变量集合的熵。如果使每次实验所获得的信息量最大，那么所需要的总实验次数就最少。用无砝码天平一次称重实验所得到的最大信息量为 log3，k次称重所得的最大信息量为klog3。设每一个硬币是假币的概率都相同，那么从12个硬币中鉴别其中一个重量不同（不知是否轻或重）的假币所需信息量为log24。而2log3=log9<log24<log27=3log3。所以理论上至少3次称重才能鉴别出假币并判断其轻或重。

6.极值性

定理 2.6（离散最大熵定理）对于有限离散随机变量，当符号集中的符号等概率发生时，熵达到最大值。

证设随机变量有n个符号，概率分布为P(x)；Q(x)为等概率分布，即Q(x)=1/n。根据散度不等式有

即　　H(X)≤log n，仅当P(x)等概率分布时等号成立。

注意

离散最大熵定理仅适用于有限离散随机变量，对于无限可数符号集，只有附加其他约束求最大熵才有意义。

7.上凸性

H(p)=H(p1,p2,…,pn)是概率矢量p的严格的上凸函数。

这就是说，若p=θp1+(1−θ)p2，那么H(p)>θH(p1)+(1-θ)H(p2)，其中p,p1,p2均为n 维概率矢量，0≤θ≤1。该性质可用凸函数性质（1）来证明（提示：先证明-pilog pi是严格上凸的，见习题2.14）。

8.一一对应变换下的不变性

离散随机变量的变换包含两种含义，一是符号集中符号到符号的映射，二是符号序列到序列的变换。首先研究第一种情况。设两随机变量X、Y，符号集分别为A、B，其中Y是X的映射，可以表示为A→B,x f(x)。因此有

所以H(Y | X)=0；H(XY )=H( X )+H(Y | X )=H(X )，而另一方面H(XY )=H(Y )+H(X | Y )≥H(Y )，所以，H(X )≥H(Y )，仅当f是一一对应映射时等号成立，此时H(X |Y )=0。应用类似的论证也可推广到多维随机矢量情况，因此得到如下定理。

定理 2.7 离散随机变量（或矢量）经符号映射后的熵不大于原来的熵，仅当一一对应映射时熵不变。

例2.14 设二维随机矢量XY，其中X，Y为独立同分布随机变量，符号集为A={0，1，2}，对应的概率为{1/3，1/3，1/3}，做变换u=x+y，v=x-y，得到二维随机矢量UV；求H(U),H(V),H(UV)。

解很明显，u，v都是x，y的函数，并且在x，y给定条件下u，v独立，所以p(u)=，上式表明 p(u)是p(x)与p(y)的卷积，可用图解法计算，得U的符号集为{-2，-1，0，1，2}，概率分布为（1/9，2/9，1/3，2/9，1/9），所以

H(U)=H(1/9,2/9,1/3,2/9,1/9)=2.1972bit/符号

同理可得

H(V)=H(U)=2.1972bit/符号

因为变换是一一对应的，所以

H(UV)=H(XY) =H(X)+H(Y)=2 log 3=3.1699bit/2个符号

因为H(UV)<H(U)+H(V)，因此u，v不独立（条件独立）。

下面研究第二种情况。设随机变量X构成的长度为N的序列变换到随机变量Y构成的长度为M的序列，称为由XN到YM的变换，记为XN→YM。其中最有意义的是一一对应的变换，此时有H(XN|YM)=H(YM|XN)=0。由此可以推出

其中，H(XN)为变换前N维联合熵，H(YM)为变换后M维联合熵。可总结为如下定理。

定理2.8 离散随机序列经一一对应变换后，序列的熵不变，但单符号熵可能改变。

实际上，经过这种一一对应变换后，有两种极端情况：①X的一个符号用Y的多个符号表示，如信源编码器；②X的多个符号表示Y的一个符号，如第3章的扩展源。

2.3.3 熵函数的唯一性

可以证明，如果要求熵函数满足以下条件：

① 是概率的连续函数；

② 当各事件等概率时是n（信源符号数）的增函数；

③ 可加性。

那么，熵函数的表示是唯一的，即与式（2.10）的表示形式仅差一个常数因子（见习题2.15）。

2.3.4 有根概率树与熵的计算

根据熵的定义，利用公式（2.10）计算熵是基本方法，下面介绍利用有根概率树计算熵。该方法不仅有时可以简化熵的计算，还可以简化后面几章所介绍的消息平均长度及编码平均码长的计算。

在有根树中，从根节点延伸的分支端点构成1阶节点；从1阶节点延伸的分支端点构成2 阶节点；……最后到末端节点，称作树叶，树叶不再继续延伸。树上的每一个 i 阶节点是其延伸产生的i+1阶节点的父节点，而这些i+1阶节点又是产生它们的i阶节点的子节点。从根节点开始到叶节点终止，每个节点分配相应的概率，此树称有根概率树，其中根节点的概率为 1；每个父节点（设为 u）的概率 p(u)是其所有子节点（设为 vi）概率 p(vi)的和，即，对应分支 p(u→vi)的概率为子节点概率除以父节点概率所得的商，即p(vi|u)=p(vi)/p(u)。所以，每个节点的所有分支概率的和为 1，利用这些分支概率计算得到的熵称为该节点的分支熵。除叶节点外，每个内部节点与其向后延伸的所有分支和节点构成一棵子树，这个内部节点作为子树的根。

设随机变量包含n个符号，各符号的概率分别为p1,p2,…,pn。如果用有根概率树描述该随机变量，那么树叶的数目等于 n，树叶对应的概率就是符号的概率。有根概率树可按如下方法构造：将几个符号分配给几片树叶，每片叶对应一个符号，再将这些树叶任意分组，各组分别合并形成各自的父节点；形成的所有父节点既可以继续分组、合并，也可与未合并的树叶继续分组、合并，形成阶数更低的父节点；……最后合并成一个节点，就是树根。可见同一个随机变量可以有多种结构的有根概率树。图2.2所示的树就是一棵简单的有根概率树。

在有根概率树中，从树叶到树根所经过的分支数目称为该叶到树根的距离，也称叶的深度。树叶的平均深度定义为

其中，pi为树叶的概率，li为树叶的深度，M为树叶的数目。图2.2中有根概率树叶的平均深度为=(1/2)×1+(1/3)× 2+(1/6)× 2=1.5。

设有根树有n片树叶，概率分别为p1,p2,…,pn，定义有根树叶的熵为

很明显，如果树叶与随机变量所取符号一一对应，那么树叶的熵就等于随机变量的熵。图2.2中有根概率树的叶熵为H =H(1/2,1/3,1/6)=1.4591bit/符号。

设有根树的某节点m的子节点的概率分别为pm1,pm2,…,pmr，定义该节点的分支熵为

其中，pm= pm1+pm2+…+pmr，r为节点m的子节点数。很明显，叶节点没有分支熵。

对于有根概率树有下面两个重要结论。

引理 2.1（路径长引理）在一棵有根概率树中，叶的平均深度等于除叶之外所有节点（包括根）概率的和。也就是说，如果有根概率树所有内部节点的概率分别为q1,q2,…,qM，那么叶节点平均深度为

证根据概率树的构造可知，每个内部节点的概率等于以其为根的子树所有叶节点概率的和，而深度为d的叶的概率分别加在从该树叶到根的路径上的d棵子树的根上，因此内部节点概率的和等于叶的概率与其深度乘积的和，而后者就是叶的平均深度。

定理2.9（叶熵定理）离散随机变量的熵等于所对应的有根概率树上所有内部节点（包括根节点，不包括叶）的分支熵用该节点概率加权的和，即

其中，q(ui)为节点ui的概率，H(ui)为节点ui的分支熵（证明略）。

该定理可用数学归纳法和熵的可加性证明。有根概率树计算熵的公式（2.44）实际上就是反复利用熵的可加性公式（2.32）的结果。在用有根概率树计算熵时，要求树叶与符号有一一对应的关系，叶的概率就是符号的概率，而对内部节点产生的分支数无具体要求，每条树枝对应一条件概率，该节点的概率乘以这个条件概率等于对应的子节点的概率。虽然在一般情况下，利用式（2.10）就可计算信息熵，但在有些特殊情况下，特别是符号概率具有某些规律性时，利用有根概率树或熵的可加性计算信息熵，可以简化运算过程。

例2.15 离散随机变量符号集A={a1,a2,a3,a4}，概率为{1-p,p(1-p), p2(1-p),p3}所对应的有根概率树如图2.3所示，计算树叶的平均深度和该随机变量的熵。