香农的信息论究竟牛在哪里？
上一篇我随手写的一篇回答，没想到大家还是比较喜欢的，远在我的意料之外。 借着这篇回答，想再介绍一下信息论的内容。其实，信息论是一门对数学要求非常高的学科，而且非常的抽象，如果不是相关专业，很难啃下来。所以我这篇文章，目的还是在科普，尽量不想用太多的数学公式，让大家更多的了解一下生活中的信息论，另外了解一下信息论祖师爷——香农。最后补充一下如何用信息论解决上篇回答中评论区很多人提到的”天平称球“问题。下面开始正文。 在科学史上，香农是足以和牛顿、爱因斯坦齐名的天才人物。按照美国学者的说法，虽然爱因斯坦发明了相对论，却并没有把我们带入相对论的时代。而香农开创了信息论，却直接把人类带入了信息时代，所以从这一方面来说，香农的影响力甚至比爱因斯坦还要大。 上面这段话并没有夸大其词，信息时代的基础无非两样东西：计算机和互联网。而香农在这两方面都做出了卓越的贡献，他让计算机从一个简单的计算工具变成了复杂的思考工具，而信息论的发现直接促进了互联网的诞生。 下面详细介绍一下香农的贡献。 香农，美国数学家、电子工程师和密码学家，被誉为信息论的创始人。密歇根大学学士，麻省理工学院博士。香农为人类做出了两个重要贡献，分别是现代信息论和数字电路设计理论。 在数字电路的早期，电路是没有设计理论支撑的，电子工程师搭建完电路要进行很繁杂的排错工作。就和我们现在软件开发完成以后需要测试一样，需要保证软件没有bug。 现在我们会有自动化测试用例，保证测试用例的代码覆盖率一定要达到某个值，尽可能让各个分支都可以跑到，这样软件发布以后才能保证质量。 在当时也是同样，电路设计完成以后，必须尽量保证每个开关的“开”和“关”都测试到，这样才能保证电路在实际使用中不会出现问题。但是一个开关就需要2种状态，n个开关就需要 2^n 种状态，测试的复杂度呈指数级增加。所以当时的测试方法基本都是Ad-hoc测试，即随机测试。这样测试的成本会小很多，不过测试覆盖率会不够，可能会产生意想不到的bug，另外测试和debug的工作还是很繁杂。 很长一段时间，电子工程师都是在这样的工作，直到香农出现。他在大学期间接触到了“布尔代数“，并发现了布尔代数中的“真”和“假”与继电器电路中的“开“和”关”有着对应关系，可以分别用“1”和“0”进行表示。如果能用布尔代数的理论去设计继电器电路，将会有以下重大的意义。 比如一个电子工程师设计了如下的电路 上图中L表示指示灯，A、B表示继电器触点，虚线表示开关是联动的。 因为继电器会有常开和常闭触点，而这些触点是联动的。对于继电器A来说，如果在线圈不通电的情况下，L1回路上的A开关是常开，而L2回路上的A开关是常闭。当A线圈通电以后，L1的A开关闭合，L2的A开关打开，总之A的常开常闭触点总是保证联动的。同理，B也类似，只不过B包括了两个常开触点。 那么上面这个电路其实可以优化成成如下图所示。 而其中的原理就在于布尔代数的化简 Y=AB+\bar{A}B=B 所以，当有了布尔代数，电子工程师再也不会设计出前面那种冗余的电路，而是将电路最简化，节省了电路元件。 更恐怖的是，这个伟大的发明只是香农1937年在麻省理工的硕士毕业论文而已，论文题目叫作《继电器与开关电路的符号分析》。那一年，他才22岁。对比我们现在绝大多数的硕士论文，真的只能自惭形秽。 随着技术发展，集成电路的规模按照摩尔定律的规律每18个月翻一番，如今一个手指甲大小的处理器，已经能够集成几十亿个晶体管，相当于几十亿个开关，但它的基本原理还是离不开香农的这篇论文。 如果用天才来形容香农一点也不为过。可他不仅仅是一个天才，而且是一个颜值爆表的天才，明明可以靠颜值，却偏偏要靠才华。 香农牛在哪里？ 我们可能已经知道，布尔代数和开关电路都不是香农发明的。而在20世纪早期，一些电子工程师其实也领悟到逻辑代数很像某种电子电路的行为。香农只是利用了这些工具发明了新的理论，那香农的这个发现到底牛在哪里呢？ 为了更加清晰的了解香农到底有多么牛，我们来对比一下毕达哥拉斯定理的发现过程。 而香农和普通电子工程师的区别就类似于“毕达哥拉斯定理”和”勾三股四弦五“的区别，普通的电子工程师只是感觉到了”开关电路“和”布尔代数“的类似，但并没有提升到理论的高度。所以即使能利用某些来自布尔代数的灵感去解决部分问题，也只是空中楼阁，并没有坚实的基石作为理论基础，所以也就没法为数字逻辑电路设计提供理论支撑。直到香农从理论上证明了两者的相似性，才奠定了数字逻辑电路设计的理论基础。 我知道截止到前面，说的似乎都有点跑题，并没有提到半点信息论的地方，但是我觉得提到香农这个人，不能不提他在硕士阶段的这个伟大的成就，这篇硕士论文可以说是历史上最牛的硕士论文。从中已经可以看到他深厚的数学功底以及极强的抽象能力。而接下来的正题——信息论，更是将这两方面的能力体现的淋漓尽致。 1948年，就在香农写完硕士论文十年以后，他在贝尔实验室用另一篇神作——通信的数学原理，开创了“信息论”，将人类带入了信息时代。 在香农的时代，人们已经开始关注“信息”这个概念。人与人沟通的语言、小说中的文字、CD中的音乐、电视的图像，这些貌似都是信息。那信息到底是什么呢？如何度量呢？ 因为信息很抽象，它不像长度、时间、大小那么容易被测量，所以很长一段时间以来，人们对信息是什么，如何度量都搞不清楚。当时流行的做法，是从语言文字结构和含义的分析来探索信息本质，并且对信息进行度量，不过效果并不好。 比如，如果今天是星期一。此时有A、B两个人分别说了一句话。 A: 明天星期二 B: 明天下大雨 A、B说的话都只有5个字 ，看起来信息量似乎相同，但和我们的直观感受是不一样的。 A的话明显毫无信息量；而B明显带有一些信息量，告诉了一些我们可能不知道的信息。可是这个信息量该如何衡量呢？ 这就体现出来香农极强的抽象能力了，他揭开了语言、文字这一层蒙布，直接透过现象看到了本质，抓住了信息最本质的特征——消除不确定性。一条信息究竟有多大的信息量，在于它能消除多少不确定性。 B的话，帮你从不确定的天气变成确定的下雨天气，完成了一个把不确定性变成确定性的过程，所以它是有信息量的。一句话能消除的不确定性越多，它的信息量就越大。 长度的量纲是米，重量的量纲是千克，那既然信息可以被度量，信息的量纲是什么呢？ 信息的本质是消除不确定性，也就是如果你面临一个选择题，有A，B两个选项，我告诉你正确答案是A，也就是完成了一个从不确定到确定的过程。这个过程和确定一个二进制位是0还是1本质上是一样的，所以它的量纲就叫做bit，也就是一个二进制数字所代表的的信息量。 十年前，香农将电路开关抽象成0和1，让电路的设计工作变成了利用布尔代数求解的问题；十年后，香农又把信息抽象成了0和1，让改进通讯质量的工作也变成了求解数学题。从这可以看到香农超强的抽象能力，它能够抽丝剥茧，将万千信息的表象过滤掉，直接找到信息的本质，用数学的方式表示出来，并且能够度量大小。 至于信息论在我们生活中到底有什么应用呢？ 5G 我在百度随意搜了一下”5G速度“的关键字，看了一下第一个条目。 我不禁微微一笑，这明显是一个不懂信息论的人写的文章。 在香农以前，大家发现无线广播的频率不能靠的太近，否则互相之间会有干扰。当时大家以为是频率调制的不够准确，于是在调制频率上下了很大功夫。可是无论频率多么准确，这种干扰依然存在。直到香农发现了”信道“，从理论上解释了干扰存在的原因。 上面这个又叫做香农第二定理。通俗的讲，无线广播传送的是人的声音，信道好比马路，人声好比马路上的车。 如果马路的宽度是双车道，就好比两个信道，那么车都在自己的位置上行驶，就不会有任何干扰。但是如果马路的宽度只有一个半车道，硬要划分出双车道来，那么两排车道上的车就会互相干扰，会导致各自车道上的车都无法行驶。 这就和无线广播的信道是一个道理，人的声音是有一定带宽的，如果两个信道之间的频率间隔的太近，那么在低赫兹的广播中人声音的高频部分就会和高赫兹的广播中人声音的低频部分重合，于是就会产生干扰。如下图所示： 早期的家用路由器只有2.4G频段，带宽比较窄，如果很多台设备同时联网就会出现互相干扰，导致丢包，数据传输率就很低。而现在出了双频路由器，同时支持2.4G和5G频段，这样就能同时提供更多的信道，也就能同时连接更多的设备。 所以信息论告诉我们，通信是需要不同的信道的。而上面的那篇文章中，明显忽略了信道这个概念，他是假设一个人独享了5G绝大部分的带宽，而带宽是十分昂贵的，独享带宽只会在实验室或者测试阶段才会出现，实际使用中，一定是会有人和你共享带宽的。 所以，不要奢望5G能让你一秒钟下完一部电影。但是5G可用的频谱范围比4G要广确实是对的，因为频率只能向上扩展，下面的频段已经挤满了，上面的可用的频谱范围还是非常丰富的。正因为5G可用的频谱范围比4G要广，所以5G时代才有可能出现IoT，又叫做万物互联。冰箱可以上网，空调可以上网，洗衣机、微波炉甚至窗帘都可以上网，这么多设备一定得需要更广阔的的频谱范围才可以，这在4G时代是无法满足的。 所以，无论是1G、2G、3G、4G还是5G，其通信的基本原理都脱离不开信息论。我们不要求了解通信的具体细节，但了解一定的信息论常识，可以帮助你辨别媒体上一些吹嘘的文章，也让你对5G、物联网有更客观的认识。 天平称球问题 有人在文章开头那篇回答的评论区问了一个类似的”天平称球“问题，由于篇幅所限，所以没有在那篇文章展开陈述。建议看过前面文章的童鞋可以先回顾一下，没看过的先看一下，这样再看后面效果会更好一些。先来看一种比较简单的情况。 这道我们小学就见过的题其实也是一道地地道道的信息论问题。只不过小学的时候，我们的求解方式可能是这样的： 尝试一种方案，求出结果后再思考看看能否有更优的方案，如果碰巧运气比较好，可能让我想到了次数更少的方案。但是，即使想到了，当我填答案的那一刻，我的心里也是没有底的。因为不确定是否有更少次数的方案。 但当我们到了大学，我们的解题思路就不能还像小学那样了，必须有更高级的理论工具，这就是信息论中的信息熵。 有了它，我们就不必冥思苦想，也不必奇思妙想，只需要按照固定的思路解题即可。这也是我一直推崇的，我本身不喜欢那种需要非常巧妙的解题思路的题目，比如经常会在奥数中遇到的，看了答案以后，会惊叹解题思路的巧妙，可静下心思考，这种思路基本不可复制，即使学会了，以后这种思路也很难应用到另外的题型当中。 我们需要的是一种通用的解题思路，哪怕是笨办法，起码思路可以复制。而信息论就给了这样的一类问题的思考模板。 我们可以思考一下，一个天平称量1次后会有3种结果： 所以“天平称量1次后的结果”这个随机变量Z的信息熵是 \mathrm{H} (Z)=-(\frac{1}{3}log _{2}\frac{1}{3} + \frac{1}{3}log _{2}\frac{1}{3} + \frac{1}{3}log _{2}\frac{1}{3}) = -log_{2}\frac{1}{3}=1.585 天平称量n次会有 3^n 种状态，所以“天平称量n次后的结果”这个随机变量Y的信息熵是 \mathrm{H} (Y)=-\sum _{{i=1}}^{3^n}{\frac{1}{3^n}}{\log _{2}{\frac{1}{3^n}}}=-\log _{2}{\frac{1}{3^n}}=n\log _{2}{3}=1.585n 而“12个外表相同的球中确定1个轻球”这个随机变量X的信息熵为 \mathrm{H} (X)=-log _{2}\frac{1}{12} =3.585 按照题目要求，至少称几次能保证找出这个轻球。翻译成数学语言也就是，随机变量Y的信息熵要大于等于随机变量X的信息熵。即 H(Y) >= H(X) ，即 n >= 2.262，即 n = 3 如果将上述式子简化，即 3^n \ge 12 。 具体的方案呢？还是和1000桶水那个问题类似，既然一个天平能表示3种状态，那我们就采用3进制的表示方式，将12个球进行编号，分别为 天平每一次测量的目标是要能够尽量确定三进制某一位上的数字。 于是我把三进制末尾数是0的取出来，分别是0，3，6，9，然后把末尾数是1的取出来，分别是1， 4， 7，10；最后把末尾是2的取出来，分别是2，5，8，11。 第一次用天平将末尾是0和末尾是1的球取出来，放到天平上。经过第一次，我们可以确定轻球的尾数。 经过第一轮，我们已知了轻球的尾数，这个时候我们再称第二次，目的是确定中间位数字。 于是我们还是分成三份，第一份是中间位是0的数：0，1， 2，9，10，11 第二份是中间位是1的数：3， 4， 5 第三份是中间位是2的数：6，7，8 为了确定中间位的数字，我把第二份放到天平的一侧，记作A；第三份放到天平另一侧，记作B；经过这一轮以后，我能够得出中间位是0，1，2当中的一个。 如果结果中间位是1或者2，由于最末位的数字已经确定，最高位必定是0。所以仅用两次即可找到那只轻球。 如果结果的中间位是0，虽然最末位的数字确定了，但是最高位可能是0或者1，所以还需要一次测量决定最高位，是一个二选一的过程，所以仅需要一次测量即可。 综上，仅需要3次测量就可以找到那只轻球。 前面的这个方案是如何想到的呢？ 天平三种状态决定了需要借助三进制的方式去解决。而我们在前面计算天平所能提供的最大信息熵的时候，默认天平出现的三种状态（左轻右重、左重右轻，左右相等）是等概率的，所以我们在构造天平称球的过程中，一定要尽量保证三种状态出现概率相等。 如果我们第一次就将球进行六六分，那么一定不会出现左右相等的状态，也就是三种状态出现的概率不等，那我们也就浪费了其中一个状态的确认过程。所以无论哪一次称球，都要想办法构造出三种状态都能出现的情况。 有了上面这个基础，我们再来看一种比较复杂的情况。 这个问题和前面那个问题的不同之处在于不知道这个坏球的轻重。这对信息熵来说跟前面的已知坏球是轻的相比有什么影响呢？ 如果有2个球放在天平两侧。 如果已知坏球比较轻，当天平不平衡时，我就可以立刻知道坏球是轻的那一侧。 而当不知道坏球是轻还是重时，如果天平不平衡，我无法判断坏球是重的那一侧还是轻的那一侧，我只能够知道坏球要么是轻的那一个，要么是重的那一个。 所以，在不知道坏球是轻还是重时，每次测量多了一个坏球是轻还是重的不确定性。在上题的基础上，在最高位增加一位表示球的轻重。其中0表示轻，1表示重，如下表所示。于是虽然12个球，但是因为多了一个轻重的不确定性，所以变成24种状态。 于是“12个外表相同的球中确定1个不知轻重的球”这个随机变量X的信息熵为 \mathrm{H} (X)=-log _{2}\frac{1}{24} =4.585 而“天平称量n次后的结果”这个随机变量Y的信息熵没有变，因为天平每次还是只能确定三种状态，所以 \mathrm{H} (Y)=-\sum _{{i=1}}^{3^n}{\frac{1}{3^n}}{\log _{2}{\frac{1}{3^n}}}=-\log _{2}{\frac{1}{3^n}}=n\log _{2}{3}=1.585n 同样，H(Y) >= H(X) ，即 n >= 2.893，即 n = 3 可见，前面那道题并没有充分发挥天平的信息优势，3次还能测出不知轻重的坏球。这就是理论武装头脑的好处，先找到答案，再去想方案。这种自顶向下的思考方式的好处就是我们在思考方案之前有了目标，也有了努力的方向，而不是无头苍蝇一样。 和前面的方案类似，首先将球按照末位0，1，2分成如下3堆，然后将A，B堆放在天平上。 此时会出现3种情况： 经过第一次测量，已经从24种状态中排除了16种状态。本着前面提到的尽量让天平出现三种状态相等的解题思路，我们来构造第二步。 同前面，第二步需要确认中间位。对于中间位来说，第一次测量后的三种结果都是类似的，因为都只剩下8种状态，而且中间位都是0, 1, 2, 0的分布。 而天平平衡时，虽然是8种状态，但仅剩下4个球需要排除，相对简单。而A堆轻的时候，还需要排除8个状态8个球，所以我们来看A堆轻的情形，其他情况类似。 我们将前面A堆和B堆按照中间位进行下面的划分，此时会出现以下分布 可以发现分布不均匀，D堆出现4个球，而E，F各只有2个。如果按照中间位划分测量的话，只能把E、F放在天平两侧，此时如果天平平衡： 也就是说对于D堆，有4个球需要检查，明显不可能在一次办到。所以需要变换方案，让三堆尽量平均分布。（之所以写出这个错误的过程是因为我在第一次尝试的时候确实以为这个方案可行，但是后来发现行不通。但是有信息熵的推导在先，所以我会坚信一定有3次可以做到的方案） 所以此时不能再严格按照中间位进行划分，那应该采用什么方案进行分堆呢？ 为了保证尽量平均分布，分堆的数量必须是3/3/2，而且尽量保证天平称量两个3堆的时候3种状态是等概率出现。于是我采用如下的方案进行划分。 将相同个数的堆D、E放在天平上，此时也会出现3种情况： 经过第二轮称量以后，最多有3个球进行确认。如果天平平衡，将7号，10号球放到天平上称一下。如果D堆轻，只需将0号，3号这两个轻的球放到天平上称一下即可。同理，如果E堆轻，只需将6号，9号球放到天平上称一下即可。 可见，12个球中有1个不知轻重的坏球，最多通过3次测量就可以找到那个坏球，而且还有bonus信息，就是不仅能够找到那个坏球，还能够知道那个坏球是轻还是重。 如果看了文章开头1000桶水找毒药那道题的童鞋可能会发现，这道题的解题思路几乎是照搬那道题的解题思路，虽然表面上是不同类型的题目，但我们要像香农祖师爷学习，透过题目的表象直穿本质。 这两道题目的底层逻辑都是信息熵，当我们掌握了理论工具以后，人之间的差距就在于是否有足够的能力将现实问题抽象成数学或者其他问题，然后用我们熟知的理论工具去解决它。在这一点上，就和解方程式是一样的。解方程本身非常简单，难点是如何将现实的问题抽象成表达式，定义变量，列出方程式。关于这一点详细的陈述在我的另一篇文章 《数学思维在生活中有多大用处？》中有更详细的描述。 自然科学往往不仅仅只能用在处理科学问题上，也能解决生活中面对的很多难题。 香农第二定理 前面介绍了香农第二定理，貌似它只能用来解决通信问题的，即带宽越大，通信的速率越高，通信的速率不可能超过信道容量。但其实香农第二定理甚至可以用来解释阿里巴巴商业的本质。 在古代，一些质量很好的商品大多只能维持在小作坊的规模，因为质量再好，基本上也只是口口相传，街坊邻居知道而已，能在县里有一些名声已经相当不容易了。所以需求有限，生产力很难上规模。从信息论的角度来说，就是流通带宽太窄，信息的传输率低。 后来，传媒业发展，有了报纸、电话、电视，然后出现了广告，商品传播相对容易了很多。很多全国驰名品牌也是在这个时候出来了，比如当时央视的标王——步步高、娃哈哈、蒙牛等，就是看中了央视这个带宽，能让品牌快速的传播。从信息论的角度来看，就是带宽较古代相比得到了很大的提升，能让品牌的传输速率大大提升。 但是由于广告的成本非常高，也就是想获得高带宽，必须支付很高的费用。这个就和家里宽带上网一样，100M和300M的带宽价格肯定不一样。很多质量很好的产品因为无法支付高带宽昂贵的费用，因而无法让大家知晓。 到了互联网时代，商品传播的带宽进一步增加，而且直接拉低了带宽的费用，可以让更多的小商户和大商户一样无差别的享受互联网的带宽，可以让小商户的产品卖到全国各地甚至世界各地。 从本质上来说，阿里巴巴所做的事情就是拓宽商家和消费者信息交流的带宽。 三只松鼠，良品铺子等这样的淘宝品牌，因为享受着淘宝巨大的带宽，甚至成为了上市公司。那问题来了，都是网店，都享受着淘宝巨大的带宽，为什么有的网店成为了上市公司，而有的网店就默默无闻。 原因还是带宽。好的网店，商家的宣传信息可以无差别的传送到消费者那里，得到消费者的认可，信息的有效传送速率很高，也就是有效带宽很高。而不良的商家，虽然享受着巨大的带宽，但是因为欺诈，商品的信息传送到消费者那里已经发生了畸变，就好像虽然网速很高，但是通信总是出错，即有效带宽还是很低。所以即使同样享受着高带宽的基础设施层，但是实际的带宽却有着千差万别。 同理，腾讯通讯工具的本质是拓宽了朋友之间沟通的带宽，百度的本质是拓宽用户获取信息的带宽。可见BAT三家公司的本质其实都是在争夺不同领域的带宽，可见带宽是商业竞争的必争之地。 信息的正交性 我们在生活中经常会遇到决策的难题，尤其是在信息繁杂的时候，我们如何甄选以及如何决策呢？ 比如我们要调查一家上市公司的股票，应该如何获取信息分析呢？ 很多人买股票首先看的是K线、成交量、MACD等技术指标，有的人甚至只用这些指标炒股，而且钻研的非常深，但大部分人仅仅依靠这些信息很难盈利。为什么呢？从信息论的角度来看，这些技术指标反映的都是走势相关的指标，是重合度很高的信息。所以，即使掌握的技术指标再多再深，这些信息也只是集中在一个维度，再多的信息综合起来也起不到累加的效果。 那我们应该如何去做呢？最好去获取多维度的信息，这些信息之间最好是正交的，即互相垂直的信息。 比如，除了技术指标，我还需要看一下财务指标，比如PE(市盈率)，PB(市净率)，ROE(净资产收益率)，净利润增长率等财务指标。这些财务指标和技术指标是来自不同的信息源，也就是正交的。所以这些信息对于我们买入这个决策是有补充信息的作用的。 同理，上市公司每年都会有年报，而年报中的信息是最全面的。从信息论的角度来看，年报中的信息是多维度的，也就是会包含很多组相互正交的信息。 但同时，如果对年报的真实性抱有怀疑态度，那么可以自己亲自去获取其它维度的信息。 比如，对于工厂，如果条件允许，我们可以观察工厂是否一直处于运转状态。如果大部分时间都在停工歇业，而年报中的利润又很高，我们就要给这个数字打一个问号。 对于食品或者快消品行业，我们可以在超市观察，它的商品是否摆在最显眼的位置（因为超市一般会把销量最好的商品放在最显眼的位置，这样商品的销量高，超市的利润也高）？观察一天该商品的购买率跟其它同类产品相比是不是更高？观察商品的生产日期是不是足够近？（这说明销量很好，没有库存积压的现象）等等第一手信息。 从信息论的角度来看，我们亲自采集的这些信息和前面所有的信息都是正交的，将这些多维度的信息组合起来，效果是可以叠加的，这样再进行交叉验证，能让我们对上市公司有更全面的了解。 在一个维度深挖到99%的信息，不如深挖多个维度，即便每个维度只能获得80%的信息。这样更有助于我们做出客观全面的决策。 当我们想看一部电影前，想知道这部电影到底怎么样。正确的做法不是去找专业的影评人或者专家的评价，而是去豆瓣上看一看评分。因为豆瓣上的每一位用户都是不同的信息源，给出的分数都是互相正交的，没有任何相关性。将这些互相正交的信息综合起来，得到的结果才更加客观。而即使再专业的影评人，从信息的角度来考虑，也只是一个维度的信息，在决策时可能会出现很大的偏差。古人其实早已经参透了信息的正交性所蕴含的智慧，正所谓”兼听则明，偏听则暗“。  参考文献 