飞云浦
信息熵
星期二 一月 14, 2014 2:56 pm
信息熵
周人
现代科技的进步离不开数学的思维与推导。过去的几十年，对当代文明影响最大的科技进步之一发生在对于需要交流的人类而言，几乎和吃饭睡觉一样重要的通讯领域。不断改进通讯质量与速度的科学研究一直是工程师们孜孜以求的事业。1948年，麻省理工学院的数学博士、在贝尔实验室里研究通讯技术的克劳德 • 香农于《贝尔系统技术杂志》上发表了他一生中最伟大的论文《通讯的数学理论》，引入了全新的思想，引领了现代信息论研究的大潮。在这篇改变人类历史进程的文章中，他引进了“信息熵”的基本概念，它在数学上量化了通讯过程中的“信息漏失”之统计本质，具有划时代的意义。
香农生于美国的密歇根州，二十岁时本科毕业于密歇根大学，并拿回家数学和电子工程两个学士文凭。由于在本科修一门课时对英国数学家乔治 • 布尔贡献的“布尔代数”深有体会，他二十一岁在麻省理工完成的《中继及开关电路的符号分析》硕士论文被评价为二十世纪最有价值的硕士论文之一，因为它用布尔代数的理论首次证明，数学中的“符号逻辑”与电路中的“0-1数字”具有一致性，从而论证了数字线路的逻辑设计之可能性。
香农的信息熵本质上是关于我们司空见惯的“不确定性”现象的数学化度量。譬如说，如果我们听到天气预报“今天中午下雨的可能性是百分之九十。”就会不约而同地想到了出门带伞。如果预报是“有百分之五十的可能性下雨”，我们就难以决定是否带伞，因为带了伞而不下雨则觉得多此一举。根据常识，第一个天气预报表达的下雨这个事件的不确定性程度较小，而第二个关于下雨的不确定度就大多了。
对于一般的不确定事件，我们怎样数学化它的不确定程度呢？设想有n个“基本事件”，各自出现的概率分别为p1,p2,…,pn，则它们构成一个样本空间，可以简记为数组(p1,p2,…,pn)。样本空间最简单的例子是抛硬币游戏，它只有两个基本事件：“正面朝上”或“反面朝上”的概率均为1/2，其对应的样本空间为(1/2,1/2)。如果铸币厂别出心裁地将硬币做成两面不对称，使得抛硬币时正面朝上的概率增加到 3/5，而反面朝上的概率减少到2/5，则对应的样本空间就是(3/5,2/5)。如果我们用H(1/2,1/2)来表示第一个样本空间的不确定度，用H(3/5, 2/5)表示第二个样本空间的不确定度，那么显然H(1/2,1/2) > H(3/5,2/5)。
更一般地，若用H(p1,p2,…,pn)记样本空间(p1,p2,…,pn)所对应的不确定度，直觉同样告诉我们，当所有的基本事件都有同样的概率1/n时，其不确定度最大。因而，不确定度函数H应该满足基本不等式：对所有的其和为1的非负数p1,p2,…,pn，
H(p1,p2,…,pn) ≤ H(1/n,1/n,…,1/n)。
如果我们不抛硬币，而像拉斯维加斯赌场的常客那样掷骰子，每掷一次，小立方骰子的每一个面朝上的概率均为1/6，其不确定度当然大于玩硬币时正面或反面朝上的不确定度。将这个直观一般化，就有不确定度函数H 应该满足的单调性要求：
（1） H(1/n,1/n,…,1/n)是自然数n的严格递增函数。
假设某大学的物理系赵教授、数学系钱教授和孙教授竞争理学院牛院长的一笔科研基金，他们每人申请成功的概率分别为1/2、1/3、1/6。院长为求公平，让每个系得此奖励的机会均等。若物理学拿到资助，就落赵教授手中。如数学系得到，钱教授有2/3的概率拿到，孙教授则有1/3的机会获得。故三教授获得院长基金的不确定度，等于物理系或数学系拿到基金的不确定度，加上数学系赢得的概率与在它拿到的条件下，钱教授或孙教授得之的不确定度乘积。换言之，H(1/2,1/3,1/6) = H(1/2,1/2) + ½ H(2/3,1/3)。推而广之，得出不确定度的“加权和”性质：
（2） 如果一个不确定事件分解成几个持续事件，则原先事件的不确定度等于持续事件不确定度的加权和。
加在不确定度函数头上的第三个基本要求从数学上讲是十分自然的：
（3）不确定度函数H是(p1,p2,…,pn)的连续函数。
可以证明：任何在所有样本空间上定义的函数H，只要它满足以上的“三项基本原则”，除了一个正常数因子，就非如下的表达式莫属：H(p1,p2,…,pn) = - (p1 ln p1 + p2 ln p2 + … + pn ln pn)，其中ln 是自然对数的符号。这个漂亮的结果是现代信息论的基础，然而它的证明无需什么高深的数学，需要的只是一种创造性的思维、一手精湛的代数技巧、一个巧妙的极限思想。如果在表达式中乘上热力学中著名的玻尔兹曼常数，信息熵完全就和十九世纪美国最伟大的数学物理学家吉布斯在统计热力学中得到的“吉布斯熵”一模一样。香农如此得到的非负函数
H(p1,p2,…,pn) = - (p1 ln p1 + p2 ln p2 + … + pn ln pn)， (H)
按照大数学家冯 • 诺依曼的建议，被定义为样本空间(p1,p2,…,pn)所对应的信息熵。现在，这个数被广称为“香农熵”，以纪念创造出它的信息论之父。
现在，我们给出上述结论高中生也能看得懂的一个初等证明，这是活学活用中学代数的极好机会。我们分三步证明。
第一步：把H(1/n,1/n,…,1/n)记为A(n)。设n = 8。我们屡次应用上述条件（2）来论证公式A(23) = 3A(2):
A(23) = A(2)+[2-1A(2)+2-1A(2)]+[4-1A(2)+4-1A(2)+4-1A(2)+4-1A(2)]
= A(2)+A(2)+A(2) = 3A(2)。
运用数学归纳法就得到
A(sm) = A(s)+s[s-1A(s)]+…+s-m+1[s-(-m+1)A(s)] = m A(s)。 (a)
现在假设四个正整数t,s,n,m满足不等式
sm ≤ tn < sm+1 。
两边求对数，有 m ln s ≤ n ln t ≤ (m+1)ln s，即
m/n ≤ ln t/ln s < m/n + 1/n。
因而我们得到不等式
|m/n – ln t/ln s| < 1/n。 (b)
由熵的条件（1），A(k)是k的递增函数。故条件（a）推出m A(s) ≤ n A(t) < (m+1)A(s)，继而有
|m/n – A(t)/A(s)| < 1/n。 (c)
(b)和(c)保证了
|A(t)/A(s) – ln t/ln s| < 2/n。
既然n是任意的，就有等式A(t)/A(s) = ln t/ln s，或言之，
A(t)/ln t ≡ A(s)/ln s。
故存在正常数C（就取为1），使得对所有正整数t，A(t) = C ln t = ln t。因此
H(1/n,…,1/n) = ln n = - ∑in=1(1/n)ln(1/n)，
即熵公式（H）在p1 = p2 = … = pn = 1/n时成立。
第二步：现在证明公式（H）对所有和为1的正有理数pi都对。我们先用p1 = 1/2, p2 = 1/3, p3 = 1/6来阐述证明的思想。构造示意图。根据熵条件（2），
H(1/6,…,1/6) = H(1/2,1/3,1/6)+2-1H(1/3,1/3,1/3)+3-1H(1/2,1/2)
+6-1H(1)。
示意图
所以，
H(1/2,1/3,1/6) = H(1/6,…,1/6)-2-1H(1/3,1/3,1/3)-3-1H(1/2,1/2)
-6-1H(1)。
如此的分解是为了用到第一步的结果。如果注意到有理数的分数形式
p1 = 1/2 = 3/(3+2+1) = n1/(n1+n2+n3),
p2 = 1/3 = 2/(3+2+1) = n2/(n1+n2+n3),
p3 = 1/6 = 1/(3+2+1) = n3/(n1+n2+n3)，
上述的分解就能写成
H(p1,p2,p3) = A(n1+n2+n3)–[p1A(n1)+p2A(n2)+p3A(n3)]。
同样的道理用到一般情形p1,p2,…,pk:设
pi = ni/(n1+…+nk),i=1,2,…,k，
则有等式
H(p1,p2,…,pk) = A(n1+…+nk) - [p1A(n1)+…+pkA(nk)]。
由上面的第一步，A(n) = ln n。代入到上式，给出
H(p1,p2,…,pk) = ln(n1+…+nk) – (p1ln n1+…+pkln nk)
= （p1+…+pk）ln(n1+…+nk) – (p1ln n1+…+pkln nk)
= -[p1ln(n1/(n1+…+nk)+…+pkln(nk/(n1+…+nk)
= -(p1ln p1+…+pkln pk)。
第三步：既然熵公式（H）对所有和为1的所有正有理数成立，连续性条件（3）推出它对所有和为1的非负实数成立。这就完成了证明。
细看一下香农熵的公式，除了负号，它是基本函数x ln x的有限个函数值之和。这个函数的图像就像大厨师手中侧面看过去的长勺子。向上弯曲的曲线有几何性质：连接上面任意两点的直线段都在这两点之间的曲线段之上。运用初等微分学，读者可以证明，对任意两个正数a和b，有
a – a ln a ≤ b – a ln b，
称为吉布斯不等式。运用它可以证明信息熵的确满足我们一开始就指出的最大熵性质，即当所有的pi都取为1/n时，信息熵取值最大，等于ln n。
香农为他的最伟大贡献的起名故事也很有趣。最初他并没有借用“熵”这个词来表达他关于信息传输中的“不确定性”的度量化。他甚至都不太了解他这个量与古典的热力学熵之间的相似性。他想把它称为“information（信息）”，但认为此术语太大众化，在日常生活中已被滥用。他又考虑过就用“uncertainty（不确定性）”，但它却是抽象名词，缺乏数量化的特色。终于有一天，他见到了当时全世界最有名的数学家冯 • 诺依曼。真是找对了人，后者马上告诉他：“就叫它熵吧，这有两个好理由。一是你的不确定性函数已在统计物理中称为熵。二是没人真正懂得什么是熵，这就让你进退自如。”
新语丝——2013年10月31日
请使用以下网址来引用本篇文章:
http://coviews.com/trackback.php?e=15051
酷我-北美枫 首页
-> Blogs(博客)
-> 飞云浦
-> 信息熵
|
|
|