第5讲 信息熵.doc

第5讲 随机变量的信息熵在概率论和统计学中，随机变量表示随机试验结果的观测值。随机变量的取值是不确定的，但是服从一定的概率分布。因此，每个取值都有自己的信息量。平均每个取值的信息量称为该随机变量的信息熵。信息熵这个名称是冯诺依曼向香农推荐的。在物理学中，熵是物理系统的状态函数，用于度量一个物理系统内部状态和运动的无序性。物理学中的熵也称为热熵。信息熵的表达式与热熵的表达式类似，可以视为热熵的推广。香农用信息熵度量一个物理系统内部状态和运动的不确定性。信息熵是信息论的核心和基础概念，具有多种物理意义。香农所创立的信息论是从定义和研究信息熵开始的。这一讲我们学习信息熵的定义和性质。1. 信息熵我们这里考虑离散型随机变量的信息熵，连续型随机变量的信息熵以后有时间再讨论，读者也可以看课本上的定义，先简单地了解一下。定义1.1 设离散型随机变量X的概率空间为我们把X的所有取值的自信息的期望称为X的平均自信息量，通常称为信息熵，简称熵（entropy），记为H(X)，即 信息熵也称为香农熵。注意，熵H(X)是X的概率分布P的函数，因此也记为H(P)。定义1.2 信息熵表达式中的对数底可取任何大于等于2的整数r，所得结果称为r-进制熵，记为Hr(X)，其单位为“r-进制单位”。 我们有 注意，在关于熵的表达式中，我们仍然约定信息熵的物理意义：信息熵可从多种不同角度来理解。（1） H(X)是随机变量X的取值所能提供的平均信息量。（2） 统计学中用H(X)表征随机变量X的不确定性，也就是随机性的大小。例如，假设有甲乙两只箱子，每个箱子里都存放着100个球。甲里面有红蓝色球各50个，乙里面红、蓝色的球分别为99个和1个。显然，甲里面球的颜色更具有不确定性。从两个箱子各摸出一个球，甲里面摸出的球更不好猜。（3） 若离散无记忆信源的符号概率分布为P，则H(P)是该信源的所有无损编码的“平均码长”的极限。 令X是离散无记忆信源的符号集，所有长度为n的消息集合为每个消息i在某个无损编码下的码字为wi，码字长为li比特。假设各消息i出现的概率为pi，则该每条消息的平均码长为因此，平均每个信源符号的码长为这个平均每个信源符号的码长称为该编码的平均码长，其量纲为（码元/信源）。我们有这是信源编码定理的推论。例1.3 课本第26页例2.4. 天气预报的平均信息量。练习： 在电脑主板上，串行接口（Serial Interface）用于向外设输出数据，每次输出1比特符号，若某段时间内输出符号的概率分布为求此时段内该串行接口的信息率，即平均每符号所传递的信息（单位为“比特/符号”）。练习解答：输出0所传递的信息为 输出1所传递的信息为因此，输出符号的信息熵为 于是所求的信息速率为0.919比特每符号。说明：上述信息熵H(X)反映了串行接口传输信息的速率，称为该接口的信息率。2. 熵函数H(P)的性质性质1. 非负性和确定性 H(P)0其中H(P)=0 当且仅当P为退化分布。一个随机变量的概率分布为退化分布，当且仅当该随机变量是常量，即取值唯一（所以其取值是确定的）。性质2. 对称性 性质3. 连续性 对于其中任何变量是连续的。性质4. 扩展性可扩展性1： 可扩展性2：证明：由连续性和可扩展性1立即可得。 证毕 意义：可扩展性表明，一个小概率事件对于熵的影响很小，可以忽略不计。在熵的计算中，可以忽略其中一部分小概率事件。例2.1 中华字海中收录了85000多个汉字，而常用汉字仅有3000个左右。（据统计现代汉语中这2400个汉字在一般书刊文章中所占的字数比例是99%）在计算汉字的熵时，大部分汉字都可以忽略不计，仅统计常用汉字出现的频率，以此作为这些汉字出现的概率，从而计算出汉字的熵。性质5. 可加性注意：即课本第31页的“递增性”。课本上的“可加性”事实上是联合熵的链法则，涉及到条件熵，放在此处不妥，后面再讨论。我们将赋予“递增性”更贴切的含义。定理2.2（可加性公式） 其中令证明：可用熵函数的定义证明，细节留给读者完成。 证毕 可加性公式让我们不断降低信息熵中概率分布的维度，将高维计算简化为低维计算。有的教材称可加性为递推性。例2.3 应用熵函数的可加性计算解：注意，可连续应用可加性公式：连续应用可加性公式，我们有定理2.4 （更一般的可加性公式） 其中解释：我们可以把可加性理解为分步试验结果的熵等于各步试验结果熵的加权组合。设一个随机试验分为两个步骤。第1步共有n个可能结果，其概率分布为。这一步试验结果的熵为。在第1步试验结果的基础上进行第2步试验。假设当第1步试验结果时，第2步试验共有个可能结果，并且其概率分布为对应的熵为 因此，第2步传递的平均信息量为两步所获得的平均信息量之和就是上述（2.1）中的右式。左式可解释为第2步试验的所有可能结果的平均信息量。练习：应用熵函数的可加性计算性质6. 递增性低维分布分解为高维分布时，信息熵严格递增。定理2.5 将n-维概率分布分解为n+1维分布后，熵增大： 证明：由可加性立即可得。 证毕性质7. 严格上凸性定理2.6 熵函数H(P)是严格上凸函数。证明：根据严格上凸性定义，我们设P=(p1, p2, , pn)与Q=(q1,q2, , qn)是两个不同的概率分布并且设为非退化分布，只需证明下列不等式 即 合并同类项后，上述不等式等价变换为注意，是一个n-维概率分布，根据预备知识中所证明的“信息不等式”，我们有其中等号成立当且仅当，即P=Q。我们前面已假设PQ，所以上述不等式中的等号不成立。同理我们有由（2）和（3）可得（1）。 证毕 不等式（1）也可以用基本对数不等式证明。不等式（1）的第二个证明：取，由得根据预备知识中证明的基本对数不等式，（4）中等号成立的充要条件是，即P=Q。我们前面已假设PQ，所以不等式（4）中的等号不成立。因此，我们有同理我们有由（5）和（6）可得（1）。 证毕性质8. 极值性（最大离散熵原理）定理2.7（最大离散熵原理）对于任何n维概率分布p，其中，等号成立的充要条件是p为均匀分布，即证明： 令q为均匀分布(1/n,1/n,1/n)，应用信息不等式立刻可得该定理成立。 证毕记号：我们用H0表示一个随机变量的最大熵。当且仅当某随机变量共有n种取值时， 例2.8 二十问题游戏（the game of twenty problems）。甲心里想到一个事物，让乙猜。乙可以向甲提问，甲只回答是或者不是。若乙在20个问题之内猜出答案，则乙胜，否则甲胜。猜数：一个比较简单的实例是猜数。要猜出一个100以内的正整数至少需要几个问题？至多需几个问题？ 练习：设一条电线上串联了8个灯泡，如图所示。假设其中有且只有一个灯泡坏了，并且各灯泡的损坏概率相同，用万用电表通过测量断路找出坏灯泡。（1）平均需要获得多少信息，才能找出其中的坏灯泡。（2）一次测量所获得的信息的最大期望值是多少？（3）试设计一个最佳测量方案，即测量次数的期望值最小的测量方案。 作业1. 试证明信息熵的可加性。2. 伪币称量问题：今有12枚金币，其中1枚是伪币，其重量不同于真币。用一台没有砝码的天平通过比较金币重量可以找出这枚伪币。（1） 用这台天平找出伪币并知道其偏重还是偏轻需获得多少信息？（2） 求天平的3种称量结果，即等重、左重和右重，的最大平均自信息。（3） 试证明找出这枚伪币至少需要称量3次。（4） 试设计最优的第1次称量方案。（5） 若第1次称量结果为1-4号钱币的总重量大于5-8号钱币的总重量，试设计最优的第2次称量方案。3. 编程2：输入有限维概率分布，输出该分布的熵。附录：热熵1854年克劳修斯定义了物理系统的一种状态函数S，他之称为熵（entropy），现在也称为热熵。一个物理系统从状态o到状态A的熵增量定义为 其中克劳修斯的热力学第二定律：德国物理学家玻尔兹曼的熵公式：划时代的发现 其中W是物理系统的（宏观）状态所对应的所有可能微观状态数，k称为玻尔兹曼常数。伟大意义：（1）