有趣的信息熵 | Dale 的花园 ^

type

status

date

slug

summary

引入信息量

一条信息的信息量与其不确定性有着直接的关系. 比如说, 我们要搞清楚一件非常非常不确定的事, 或是我们一无所知的事情, 就需要了解大量的信息. 相反, 如果已对某件事了解较多, 则不需要太多的信息就能把它搞清楚. 所以从这个角度来看, 可以认为, 信息量就等于不确定性的多少.

那么如何量化信息量的度量呢？来看一个例子：2014 年举行了世界杯足球赛, 大家都很关心谁会是冠军. 假如我错过了看世界杯, 赛后我问一个知道比赛结果的观众“哪只球队是冠军”？他不愿意直接告诉我, 而让我猜, 并且我每猜一次, 他要收我一元钱才肯告诉我是否猜对了, 那么我要掏多少钱才能知道谁是冠军呢？我可以把球队编上号, 从 1 到 32, 然后提问：“冠军在 1~16 号中吗？”假如他告诉我猜对了, 我会接着提问：“冠军在 1~8 号中吗？”假如他告诉我猜错了, 我自然知道冠军在 9~16 号中. 这样我只需要 5 次, 就能知道哪只球队是冠军. 所以, 谁是世界杯冠军这条消息的信息量只值 5 块钱.

当然, 香农不是用钱, 而是用比特 (bit) 这个概念来度量信息量. 一个比特是一位二进制数, 在计算机中, 一个字节就是 8 比特. 在上面的例子中, 这条消息的信息量是 5 比特. （如果有朝一日有 64 支球队进入决赛, 那么“谁是世界杯冠军”的信息量就是 6 比特, 因为要多猜一次）. 我们发现, 信息量的比特数和所有可能情况的对数函数 log 有关 ( ).

但是实际上可能不需要猜 5 次就能猜出谁是冠军, 因为像西班牙、巴西、德国、意大利这样的球队夺冠的可能性比日本、南非、韩国等球队大得多. 因此, 第一次猜测是不需要把 32 支球队等分成两个组, 而可以把少数几只最可能的球队分成一组, 把其他球队分成另一组. 然后猜冠军是否在那几支热门队中. 重复这样的过程, 根据夺冠概率对余下候选球队分组, 直至找到冠军. 这样也许 3 次或 4 次就能猜出结果. 因此当每只球队夺冠的可能性（概率）不等时, “谁是世界杯冠军”的信息量比 5 比特少. 香农指出, 它的准确信息量应该是：

其中 : 分别是这 32 支球队夺冠的概率. 香农把它称为信息熵 (Entropy), 一般用符号 H 表示. 很容易计算出, 当 32 支球队夺冠概率相同时, 对应的信息熵等于 5 比特. 信息熵本质是信息量的数学期望.

香农（Claude Shannon）在 1971 年的论文“能源和信息”（Energy and information）中写道：我最关心的是该怎么称呼它. 我想称它为“信息”（information），但这个词被过度使用了，所以我决定称它为“不确定性”（uncertainty）. 当我与冯·诺伊曼（John von Neumann）讨论时，他有个更好的主意. 冯·诺伊曼告诉我，“你应该称它为熵，原因有两个. 第一，不确定性这个名称已经被用于统计学；第二，而且更重要的是，没有人知道熵（entropy）究竟是什么，所以你在辩论中总会占有优势.

熵可以用来衡量事件发生的期望的 “惊讶程度”（expected surprise）. 一个事件出现的越频繁则每次该事件出现时携带的信息就少，反之如果一个事件非常少见，则该事件出现的时候携带的信息量就非常高. 如果我们知道某件事情肯定会发生，那么我们就不会得到信息. 例如扔一个所有面都是一个数的骰子，或两面一样的硬币, 在这种情况下，该随机变量的熵为 0，也就是说它实际上并不是随机的. 对于一个随机变量 𝑥 而言，它的所有可能取值的信息量的期望就是熵.

信息熵的性质和表示

香农给出的信息熵的三个性质 :

单调性，发生概率越高的事件，其携带的信息量越低

非负性，信息熵可以看作为一种广度量，非负性是一种合理的必然

累加性，即多随机事件同时发生存在的总不确定性的量度是可以表示为各事件不确定性的量度的和，这也是广度量的一种体现

香农从数学上严格证明了满足上述三个条件的随机变量不确定性度量函数具有唯一形式 :

此公式中对数的底数一般使用 2, 这时信息熵的单位就是比特 ( bit ) ; 当然也可以使用其他底数, 比如 e 对应的单位就是奈特 ( nat )

单调性

事件发生的概率越低，其发生时所能给出的信息量越大. 举一个极端的例子，“太阳从西边升起”所携带的信息量就远大于“太阳从东边升起”，因为后者是一个万年不变的事实，不用特意述说大家都知道；而前者是一个相当不可能发生的事情，如果发生了，那代表了太多的可能性，可能太阳系有重大变故，可能物理法则发生了变化，等等. 从某种角度来考虑，单调性也暗含了一种对信息含量的先验假设，即默认某些事实是不含信息量的（默认事实其实也是一种信息，我理解的默认事实应该指的是概率分布），这其实是把默认情况的信息量定标为 0 了.

累加性

考虑到信息熵的定义涉及到了事件发生的概率，我们可以假设信息熵是事件发生概率的函数：

对于两个相互独立的事件 X = A , Y = B 来说，其同时发生的概率：

其同时发生的信息熵，根据累加性可知：

函数形式

信息熵从代数上需满足两个变量乘积函数值等于两个变量函数值的和，那么这种函数形式应该是对数函数. 再考虑到概率都是小于等于 1 的，取对数之后小于 0，考虑到信息熵的第二条性质，所以需要在前边加上负号.

最大熵原理

重要规律 : 使用拉格朗日乘数法可知, 均匀分布的数据信息熵最大

对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设. 在这种情况下，概率分布最均匀，预测的风险最小. 因为这时概率分布的信息熵最大，所以人们把这种模型称作“最大熵模型”. 我们常说的，不要把所有的鸡蛋放在一个篮子里，其实就是最大熵原理的一个朴素的说法，因为当我们遇到不确定时，就要保留各种可能性.

经典问题

小鼠与毒药

二进制编码

有 100 只一模一样的瓶子, 其中 99 瓶是水，一瓶是看起来像水的毒药. 只要老鼠喝下一小口毒药，一天后则领盒饭, 现在, 你有 7 只老鼠和一天的时间, 如何检验出哪个瓶子里是毒药 ? ( 所有液体可以随便混合, 倒出一点点混合都行, 只要被混合的东西沾了一点点毒药, 小鼠就鼠了 ~ )

解答 : 首先用二进制给瓶子重新编号. 100 个瓶子，需要用 7 位二进制数 ( )

1: 0000001

2: 0000010

3: 0000011

4: 0000100

100: 1100100

编号完成后, 开始混合液体并投喂给小鼠 ( 每个瓶子里的液体可能会投喂给多个小鼠喝, 所以记得每次都不要倒完 ) :

约定二进制编号从左往右数 ( 当然从右往左也行 )

第 1 只小鼠喝下所有二进制编号第 1 位为 1 的瓶子的混合液体.

第 2 只小鼠喝下所有二进制编号第 2 位为 1 的瓶子的混合液体.

第 3 只小鼠喝下所有二进制编号第 3 位为 1 的瓶子的混合液体.

第 7 只小鼠喝下所有二进制编号第 7 位为 1 的瓶子的混合液体.

通过每只小鼠的测试结果（鼠了或没鼠），可以组合出毒液的编号. 每只小鼠的结果相当于毒液编号的一个二进制位：

若第 1 只小鼠挂了，说明毒药的二进制编号的第 1 位为 1, 反之就是 0.

若第 2 只小鼠挂了，说明毒药的二进制编号的第 2 位为 1, 反之就是 0.

依此类推.

假设测试结果如下：

第 1 只小鼠：寄

第 2 只小鼠：活

第 3 只小鼠：寄

第 4 只小鼠：活

第 5 只小鼠：活

第 6 只小鼠：活

第 7 只小鼠：寄

通过上面的结果可以确定毒药编号的二进制表示为 1010001，即十进制的 81

称量小球

计算最小称量次数

给定 N 个小球, 其外形完全一样, 中间有一个特殊小球重量和其他 N -1 个有细微差别, 需要借助天平来揪出这个特殊小球, 那么称量小球的最低次数和 N 有怎样的函数关系呢 ?

称量小球其实就是前面世界杯猜夺冠概率游戏的翻版. 你随意给球分组, 并询问天平 ”冠军” 在哪一边, 不同点在于天平会反馈三种结果, 即平衡, 左倾和右倾. 所以每一次称量能取得的最大信息熵为 . 如果我们事先知道特殊小球是偏重还是偏轻, 那么发现特殊小球所需的最大信息熵为 ( 最大信息熵, 在称量过程中表现为直到最后一轮才发现特殊小球, 这是最坏的结果, 但也确实会发生. 在算数上表现为所有小球概率均一, 即特殊小球出现的概率为 1/N, 根据信息熵公式得 ). 如果不知道特殊小球偏重偏轻, 那么发现特殊小球的最大信息熵为 ( 特殊小球出现的概率为 1/2N, 对比前一种情况, 这里乘了一个 1/2 是因为考虑到偏轻或偏重都有可能 ). 设我们称量小球的次数为 k, 那么经过 k 论称量, 能取得的最大信息熵即为 . 如果我们想要得到特殊小球, 就要求 “可取得的最大信息熵” ≥ “给定的最大信息熵”.

若事先知道特殊小球偏重还是偏轻, 需满足 :

事先不知道特殊小球偏重还是偏轻, 需满足 :

这就是小球问题 “最少称量次数” 的通解, 但使用最低次数的称量办法则需要人们自己想象, 这也是我们智慧的表现. 不过从 “每次称量取得最大信息熵, 不然上述公式等号不成立” 的角度看, 我们每次称量时应往 “平均” 的角度思考从而取得最大的信息熵.

大约在十年前, 我就曾在查理九世书中见到了 12 个小球 3 次的称量问题, 当时我脑瓜子还很灵光还快就想出了解决办法, 然后我爷爷又增加了些许难度到 13 个球, 最终我还是机智地给出了办法. 我想这次回家能不能把这个 “最终结论” 说给他听听呢, 哈哈 ~

N = 13 的称量过程

不知道特殊小球轻还是重时, 使用 3 次天平, 有关系式 : , 所以能称量的最大小球数量就是 13 , 可以说是极限了. 称量过程如下 :

定理一 : 若剩下两颗未知小球和至少一颗标准球, 则只需要称量一次就可以找出特殊小球. 因为 : 可随意选一颗未定球与标准球称重, 若不平衡则它就是特殊球, 若平衡则另一颗球是特殊球

定理二 : 若剩下三颗未知小球但知道特殊球是偏重还是偏轻, 则只需称量一次就可以找出特殊小球. 因为 : 假设特殊球偏重, 可随意选两颗进行称重, 若平衡则剩下一颗为特殊球, 不平衡则重的是特殊球.

初始分为 4, 4, 5 三组, 天平两端各放四颗球, 剩下五颗待定, 进行第一次称量

若第一次称量平衡, 则天平上的八颗均为标准球, 剩下五颗球, 编号为 C1 ~ C5, 将 C1, C2, C3 放置在天平一端, 另一端放三颗标准球, 进行第二次称量, C4 和 C5 待定.

若第二次称量平衡, 根据定理一, 可在第三次称量中找出特殊球 ( C4 或 C5 )
多第二次称量不平衡, 我们就知道特殊球是偏重还是偏轻了, 根据定理二, 第三次称量可解出特殊球

若第一次称量不平衡, 则将总重量较轻的四颗球编号为 L1 ~ L4, 它们都有偏轻的嫌疑但也可能都是标准球; 将总重量较重的四颗球编号为 H1 ~ H4, 它们都有偏重的嫌疑但也可能都是标准球. 将 L1, L2, H1 置于天平一端, L3, L4, H2 置于另一端, 进行第二次称量. 剩下 H3, H4 待定

若第二次称量平衡, 则 H3 或 H4 中的特殊球必偏重, 根据定理二, 第三次称量可解出特殊球
若第二次称量不平衡, 且 L1, L2, H1 一端更重, 那三颗球有嫌疑 : H1 可能偏重, L3 可能偏轻, L4 可能偏轻, 其他球必然是标准球. 我们在第三次称量时比较 L3 和 L4 即可. 若平衡, 则特殊球为偏重的 H1, 若不平衡则特殊球为 L3 与 L4 中较轻的那颗.
若第二次称量不平衡, 且 L1, L2, H1 一端更轻, 那三颗球有嫌疑 : H2 可能偏重, L1 可能偏轻, L2 可能偏轻, 其他球必然是标准球. 我们在第三次称量时比较 L1 和 L2 即可. 若平衡, 则特殊球为偏重的 H2, 若不平衡则特殊球为 L1 与 L2 中较轻的那颗.

优秀的三进制

在生活中我们习惯了使用十进制, 二进制, 十二, 十六, 二十六 ( 英文字母 ), 六十等整数进制. 但理论上 e ( ≈ 2.718 ) 进制才是最为优秀的进制 ! 这很让人吃惊不是么, 一个无理数怎么作进制使用呢 ? 但我们可以妥协一点, 使用最靠近 e 的三进制吧 !

单个 x 进制整数的信息熵为 , 假定一个 x 进制位对资源的占用与 x 是正比例函数 ( 比如用电平表示数字大小, 二进制位数字的一个位只需两个电平, 而 x 进制就要准备 x 个不同的电平 )

一个 x 进制位的信息熵与其消耗资源的比值为 :

注意到, 这个函数在 ( 0, e ) 上递增, 在 ( e, +∞ ) 上递减. 当 x = e 时取得最大值

这说明在消耗同样资源的场景下, e 进制能带来更大的信息熵. 或者在提供同样信息熵的情景下, e 进制对资源的消耗更少

在 “一个 x 进制位对资源的占用与 x 是正比例函数” 的前提下, e 进制是数学上最优秀的进制

考虑整数进制, 由于 ln2 / 2 ≈ 0.347 ＜ ln3 / 3 ≈ 0.366, 所以三进制是最优秀的整数进制

当然, 上面只讨论了一位数字的情况, 当扩充到 m 位整数时, 假设资源消耗可以用 m · x 来表示

m 位 x 进制数可以表示个整数

我们设定 P 为常数, 现在寻找合适的 x 取值, 在可以表示 P 的前提下, 资源消耗最小

f(x) = mx =

显然, f(x) 在 ( 0, e ) 上递减, 在 ( e, +∞ ) 上递增. 当 x = e 时取得最小值

计算得出 : f(2) > f(3)

所以, 在足以表示任意整数 P 的前提下, 三进制是最优秀的整数进制

当然, 上面都是基于极其理想的场景, 在实际电子信息工业中, 二进制 ( 包括衍生的八进制, 十六进制等 ) 的流行程度远远高于其他进制. 虽然 20 世纪五十年代末莫斯科国立大学研制过三进制计算机 setun, 并且在算法方面展现了其独到的优势, 但并没有得到重视和普及开来. 在之后的几十年里, 硬件水平取得了极大进步, 但绝大多数计算机还是以二进制作为数字存储方式, 这里我让 Claude AI 总结了二进制的优势 :

Binary VS Ternary