0x0 破题
人类干过一件挺荒诞的事:猜了几千年谜,却一直没给"不确定性"这三个字定一个单位。猜天气、猜牌局、猜对方是不是在说真话,靠的都是同一种资源——信息——但这资源多少年来一直是笔糊涂账,只能定性,不能定量。1948 年,Claude Shannon 在贝尔实验室写了一篇论文,把"不确定性"称出了斤两,人类第一次知道,一枚硬币的悬念,原来值 1 bit。
我打算按周啃完"信息论 → 信息经济学 → 机制设计"这条线。第一周啃地基:概率工具,加上信息论最核心的四个量——entropy、conditional entropy、mutual information、KL divergence。这四个量啃不透,后面聊逆向选择、道德风险、机制设计,都是空中楼阁。
0x1 概率复习:期望与 Jensen's inequality
信息论的语言是概率论,这句话不是客套。一个离散随机变量 X,取值 x 的概率是 p(x),这是全部家当。期望 E[X] 是加权平均,没什么可展开的。真正值得单独拎出来的,是 Jensen's inequality。
对于凸函数 f,有 f(E[X]) ≤ E[f(X));对于凹函数,不等号反过来。直觉是:先算平均再代入函数,和先代入函数再算平均,凸函数会让后者更大——函数的"弯曲"本身会制造额外的量。这条不等式看着朴素,却是整个信息论大厦的承重墙:mutual information 非负、KL divergence 非负、entropy 是凹函数,证明都得从这里出发(ANU 信息论课程讲义把 Jensen's inequality、Gibbs' inequality 到 data processing inequality 排成一条推导链,逻辑上环环相扣)。记住这条,后面的非负性证明就不必逐条死记,推一遍就出来了。
0x2 Entropy:不确定性的度量单位
熵的定义并不绕:
H(X) = -Σ_x p(x) log p(x)
log 取以 2 为底,单位是 bit。这个公式在说什么?每个结果 x 出现时,它自带的"意外程度"是 -log p(x)——越稀罕的事件,意外值越高。熵就是这份意外值的期望,即平均每次观测能拿到多少信息量(这一表述与将熵定义为随机变量期望信息量的通行处理一致)。
拿硬币举例:一枚均匀硬币,正反各半, H(X) = -[0.5 log 0.5 + 0.5 log 0.5] = 1 bit,每次抛掷都货真价实地传递 1 bit 信息。如果硬币被做过手脚,99% 正面,结果基本可预测,熵就跌下去了——这也是熵常被理解为"意外程度"或"不可预测性"的原因。熵的另一条性质是:在给定取值个数的前提下,均匀分布的熵最大,分布越偏,熵越小,这一点后面讲信道编码时还会用到。
值得多说一句的是符号背后的野心。Shannon 证明了,一个信源不可能被压缩到低于其熵的比特数——这是一条硬约束,不是工程建议,后面 0x6、0x7 两节会具体展开。
0x3 联合熵与条件熵:知道了一个变量,还剩多少雾
两个变量 X、Y 放在一起看,联合熵是
H(X,Y) = -Σ_{x,y} p(x,y) log p(x,y)
条件熵定义为
H(X|Y) = H(X,Y) - H(Y)
意思是:先把 X、Y 一起的总不确定性算出来,再减去 Y 自身的不确定性,剩下的就是"已知 Y 之后,X 还剩多少雾"。这条定义直接推出一个链式法则:H(X,Y) = H(X) + H(Y|X),把联合不确定性拆成"先看 X 的不确定性"加上"看完 X 之后 Y 还剩的不确定性"。
一个几乎不需要证明就能猜到、但确实可以证明的性质是 H(X|Y) ≤ H(X)——条件永远不会增加不确定性,俗称"conditioning reduces entropy"。多知道一件事,雾只会变薄,不会变厚(极端情况下 Y 与 X 无关,雾厚度不变而已)。
0x4 Mutual information:两个变量之间到底掐着多少信息
把 0x3 的结论倒过来看,就是互信息:
I(X;Y) = H(X) - H(X|Y) = H(X) + H(Y) - H(X,Y)
它衡量的是"知道 Y 之后,X 的不确定性被压缩了多少",这个量对称——I(X;Y) = I(Y;X)——而且非负,等于零当且仅当 X 与 Y 独立。互信息还有一层更本质的写法:它就是联合分布与边缘分布乘积之间的 KL divergence,
I(X;Y) = D(p(x,y) ‖ p(x)p(y))
这句话把 0x4 和 0x5 焊在了一起:互信息不是一个孤立的新概念,而是 KL divergence 在"检验独立性"这个具体场景下的化身。
0x5 KL divergence:说错话要多付多少代价
KL divergence,又叫 relative entropy,定义为
D(p‖q) = Σ_x p(x) log [p(x)/q(x)]
它衡量的是"用分布 q 去近似真实分布 p"所付出的代价。这个量非负(由 0x1 的 Jensen's inequality 直接推出,业内称为 Gibbs' inequality),等于零当且仅当两个分布处处相等;但它不对称,D(p‖q) 一般不等于 D(q‖p),所以不是数学意义上的距离。
KL divergence 有一个特别落地的解释:如果真实分布是 p,但编码时用的是错误分布 q 设计出的最优码长,那么平均码长会比用 p 设计时多付出 D(p‖q) 那么多比特(这一"错误建模的额外代价"解释常见于信源编码的相关课程讲义)。换句话说,KL divergence 量化的是"信念错了,要付多少信息论意义上的利息"——这句话留着,信息经济学那一章讲 signaling 和 screening 时还会用到,概念是相通的。
0x6 AEP:大数定律在信息论里的化身
概率论里的大数定律说,独立同分布变量的样本均值会收敛到期望。信息论里的对应版本叫 asymptotic equipartition property(AEP):
-(1/n) log p(X₁, X₂, …, Xₙ) → H(X)(依概率收敛)
翻译成人话:当 n 足够大,一段长度为 n 的独立同分布序列,其对数概率的均值会稳稳地贴近熵。由此可以把所有可能的序列一分为二——typical set 和其余部分。typical set 里的序列数量大约是 2^{nH(X)} 个,每个的出现概率大致相等;typical set 之外的序列,理论上存在,但加总概率趋近于零(Cover 与 Thomas 所著《Elements of Information Theory》把 AEP 明确定位为大数定律在信息论里的类比,这也是 MIT 信息论课程大纲把 AEP 放在主干位置的原因)。
这个结论看着抽象,落地却极其具体:既然几乎所有的概率质量都挤在 typical set 里,只要能给这 2^{nH(X)} 个序列编码,压缩问题基本就解决了——这就是下一节的伏笔。
0x7 信源编码定理与 Huffman coding:熵是压缩的地板价
Shannon 的 source coding theorem 说得很直白:任何无损压缩方案,平均码长都不可能低于熵,即 H(X) ≤ E[l(X)],而一种具体的、可构造的最优前缀码——Huffman coding——能把平均码长压到 H(X) 与 H(X)+1 之间。
Huffman coding 的身世也值得一提:David Huffman 在 MIT 读博期间,导师 Robert Fano 布置了一道关于最优二进制编码的课程作业,Huffman 想出的自底向上构造前缀码的办法,效率反而超过了 Fano 自己此前提出的 Shannon–Fano coding,论文发表于 1952 年。这大概是学术史上少数"学生作业反超导师方案"的例子,读来有点解气。
Huffman coding 的构造思路简单:把出现概率最小的两个符号合并成一个节点,重复这个过程直到只剩一个根节点,再从根节点回溯赋予每个符号一段二进制前缀码——概率越低的符号,分配的码长越长。这套贪心算法之所以最优,根子还是在熵——熵划定了压缩的地板价,Huffman coding 只是把这块地板价用一种具体、可执行的方式铺了出来。
0x8 信道容量:噪声存在时,信息还能跑多快
前面几节讲的是压缩——同一个信源,能不能用更少的比特表示。信道容量讲的是传输——信息经过一条带噪声的信道,还能保真地跑多快。Shannon 给出的定义是
C = max_{p(x)} I(X;Y)
在所有可能的输入分布 p(x) 里,找一个让互信息最大化的分布,这个最大值就是信道容量。noisy-channel coding theorem 进一步给出一个近乎反直觉的结论:只要传输速率 R 低于 C,总存在一种编码方式,让误码概率随着码长增加趋近于零——噪声不是拦路虎,只要留足冗余,就能把误差压到任意小(这也是 Shannon separation theorem 的由来:先把信源压缩到熵率,再用信道编码把压缩后的比特送过带噪声的信道,两步分开做互不影响最优性)。
这条定理最反直觉的地方在于:它只保证"存在"这样的编码,却不告诉你具体怎么构造——这也是为什么从 1948 年到后来的 turbo code、LDPC code,足足花了半个多世纪,人类才把逼近信道容量的实用编码方案造出来。
Congratulations @x256! You have completed the following achievement on the Hive blockchain And have been rewarded with New badge(s)
Your next target is to reach 1500 upvotes.
You can view your badges on your board and compare yourself to others in the Ranking
If you no longer want to receive notifications, reply to this comment with the word
STOP