香农留下的60年悬案：为什么信息论看不见结构？

来源：市场资讯

（来源：图灵人工智能）

单击上方“图灵人工智能”，选择“星标”公众号

您想知道的人工智能干货，第一时间送达

一张社交网络有多少信息？

这个问题听起来应该有一个干净利落的数学回答——毕竟香农在1948年就告诉我们怎么度量信息了。但如果你真的试着用香农的方法去算，你会撞上一堵墙：要度量结构中的信息，你必须先摧毁结构。

把图拆成一组概率，算熵。数字出来了，但两张结构完全不同的图可以给出同一个数字。结构信息在"拆"的那一步就丢了。

这个矛盾不是小问题。早在1953年，Shannon本人就提出了建立结构信息理论的构想，但没有给出方案。半个世纪后，计算机科学家 Brooks Jr. 把结构信息的量化列为计算机科学三大挑战之首，原话是："我认为这个缺失的度量是信息科学理论理解中最根本的缺口。"

然后这个缺口开了60年。

从1955年到2016年，至少七种不同的方法试图解决这个问题。它们全部失败了——而且失败的原因完全相同。

2016年，李昂生在 IEEE Transactions on Information Theory 上发表了一篇38页的论文，提出了一个全新的方案。这个系列要做的事情，是沿着这篇论文的数学脉络，搞清楚一个问题：他们到底做对了什么，让60年没人解决的问题被解决了？

一、1948年：信息有了数学定义

这个定义深刻地改变了信息科学的每一个分支。数据压缩、密码学、机器学习的损失函数——香农熵无处不在。

但香农自己知道，他的定义有一个边界。

二、一个数字看不见结构

两张结构完全不同的图，香农熵却完全相同

三、60年间的所有尝试

接下来60年，一代又一代研究者试图修补这个缺口。

第一次尝试：换一种方式拆图（1955–2008）

最直觉的想法是：度数分布太粗糙了，那换一种更聪明的方式从图里提取分布。

按任意函数拆。 Dehmer（2008）干脆把"怎么提取分布"这件事变成了一个可调参数：你自己选一个函数，把每个节点映射成一个正数，归一化成概率分布，然后算香农熵。这等于承认：没有一种"正确的"提取方式。但这也意味着，同一张图，换个函数就换个答案。

三种方法，同一个模式：从图中提取分布 → 算 。区别只在于"拆"的方式越来越精细，但"拆完交给香农"的框架从未改变。

第二次尝试：不看单张图，看一整类图

Shannon 系综熵沿着系综的思路更进一步。Gibbs 熵只数了系综里有多少张图，Shannon 系综熵则对每条可能的边建模：对每一对节点 ， 是这条边存在的概率， 是不存在的概率。整个系综的熵是：

模型的结构熵（Choi & Szpankowski）是最后一种尝试：给定一个随机图模型 ，算它能生成的所有图的出现概率分布的香农熵 。这度量的是模型的复杂度，跟具体图的结构还是无关。

七条路，同一堵墙

回头看这60年，一个清晰的模式浮现出来：

每一种度量，无论多么精巧，最终都是对某种分布的香农熵。

前三种方法从图里提取分布，后四种方法从图的系综里提取分布。提取方式越来越复杂——按轨道、按距离、按系综、按拉普拉斯矩阵——但拆完之后都是同一个操作：。

为什么所有人都回到了同一个公式？因为这个公式不是一种选择，而是唯一的答案。 香农证明过一个定理：如果你想用一个函数来度量"一个概率分布有多不确定"，并且要求它满足几个最基本的合理性条件（比如概率微小变化时度量也微小变化、均匀分布时不确定性最大），那么满足条件的函数有且只有一个，就是 。

换句话说：一旦你把数据变成了概率分布，你就只剩这一条路可走。 不是研究者们缺乏想象力，而是数学本身封死了所有其他出口。60年间真正的分歧只在于"怎么从图里提取分布"——但只要"提取分布"这一步存在，终点就注定是同一个公式。

所以问题不在于 有什么缺陷——在度量分布的不确定性这件事上，它是完美的，甚至是唯一正确的。问题在于："拆"这个动作就是错的。 结构是不可拆分的——你不能把一张图拆成一堆独立的概率值还指望保留结构信息。

这就像你想理解一首诗的美感，于是你统计了每个字的出现频率，然后用频率分布的熵来度量"诗的信息量"。数字算出来了，但美感早在你做字频统计的那一步就丢了。

那有没有一条不拆的路？ 下一篇，我们看看2016年那篇论文给出了什么答案。

参考

Li, A. & Pan, Y. "Structural Information and Dynamical Complexity of Networks." IEEE Transactions on Information Theory, vol. 62, no. 6, pp. 3290-3339, June 2016. 本文涉及的内容主要来自该论文 §I（Introduction）和 §II（Existing Measures of Graph Entropy）。