CSYS5030 Week 09 复杂系统中的信息处理与熵率讲课总结

Posted on In , Word count in article: 3.6k Reading time ≈ 13 mins.
CSYS5030 Module 9 总结：生物计算与计算机科学的对比、动力系统视角下的内禀计算；把计算拆为信息存储、传递、修改的信息动力学框架与记号；熵率的两种定义、平稳时相等、编码解释，并用两状态马尔可夫链给出算例，为 AIS 铺垫。

CSYS5030 Week 09 讲课总结：Information Processing in Complex Systems

课程：CSYS5030 — Information Theory and Self-Organisation 讲师：Associate Professor Joseph Lizier 对应模块：Module 9 - Information processing in complex systems 来源：讲义 PDF Week 9/Lectures/Lec7-InfoProcessing.pdf（标题页为 Information dynamics – Part I – Information processing in complex systems）。本周没有转录稿，Week 9 文件夹里也没有 tutorial 文件，以下按讲义整理，并用标准教材知识补充推导和算例；不包含讲课现场内容。 本周覆盖：信息动力学的哲学 → 记号 → 熵率（entropy rate）

文件说明：Week 6/Lec6-InfoDynamics-PartI-Philosophy.pdf 与本周讲义内容相同（只有公式字体编码差异），是旧编号副本，按内容归到 Week 9。讲义编号 Lec7 是讲座序号（Wrap-up 讲义列出的第 7 讲 Information processing in complex systems），不是周次。

零、课程版图与本周位置

板块 周数 状态
1. Introduction to Information Theory Week 1–4 已完成
2. Empirical Analysis with Information Theory Week 5–8 已完成
3. Information Processing in Complex Systems Week 9–12 本周开始：W9 哲学与熵率 → W10 信息存储 → W11 信息传递 → W12 有效网络推断

上周（Week 08）的结论是：与其找一个「自组织总指标」，不如刻画信息结构化的多个方面——其中最重要的两个就是信息存储和信息传递。第三板块就是把这一想法具体化：用信息论去审视大型系统的时间序列动态。

本周学习目标（讲义）：

  • 理解信息动力学（information dynamics）方法背后的哲学：如何为复杂系统中的信息处理建模；
  • 理解熵率作为第一步考虑。

主要参考：Lizier (2014) JIDT: An information-theoretic toolkit for studying the dynamics of complex systems，附录 A.2、A.3。

一、计算容易识别吗？

1.1 讲义的开场练习

讲义给出一组图片：冯·诺依曼架构、主板、鱼群、蚂蚁、萤火虫、大脑，对每张图问：

  • 这个系统在计算吗？
  • 如果是，它在算什么？
  • 怎么算的：输入/输出/信息是什么？它们如何被操作？

用图灵机（Turing machine）的视角看，电脑显然在计算，而且很容易指出哪里是存储、哪里是处理。但对鱼群、蚁群、大脑，这些问题就很难回答。

1.2 能把生物计算塞进计算机科学的主流范式吗？

Mitchell（Complexity: A Guided Tour, ch. 12）的对比：

问题 计算机科学 生物计算
什么充当系统中的信息？ 数字的、静态的纸带 模拟状态，在空间和时间中分布的模式；通过统计采样获得
信息如何被传递和处理？ 确定性、串行、无差错，集中式规则 去中心化、并行、局部、细粒度、随机的交互；利用随机性
信息如何获得功能/目的/意义？ （人类）设计者 自然选择

1.3 需要新视角：动力系统

Mitchell 的观点：对复杂系统，「动力系统的语言可能比计算的语言更有用」。

初始状态输入动力学过程后续状态输出

内禀信息处理（intrinsic information processing）：只要系统经历一个动力学过程，把初始状态（+输入）变为后续状态（+输出），就在发生信息处理。

生物（及生物启发的）信息处理的两个特点：

  1. 分布式——不像图灵机有一个读写头；
  2. 持续进行——内禀计算不一定会结束，没有「停机」。

那么怎样用计算或信息的语言描述它？答案是三种基本操作：信息存储、传递、修改。在传统 PC 里很容易指出执行这些操作的元件（内存、总线、CPU），但在生物计算中不那么容易。

二、信息动力学（Information Dynamics）

2.1 计算 = 存储 + 传递 + 修改

我们平时描述计算时用的是三个词，信息动力学给每个词配上一个信息论度量：

计算的要素 信息动力学中的度量 对应模块
Memory（记忆） Information storage（信息存储）→ Active Information Storage Module 10
Signalling（信号传递） Information transfer（信息传递）→ Transfer Entropy Module 11
Processing（处理） Information modification（信息修改） 本课只提及

分布式计算是任何涉及这些特征的过程，例如：

  • 大脑中的信息处理
  • 元胞自动机的时间演化
  • 基因调控网络计算细胞行为
  • 鸟群计算集体朝向
  • 蚁群计算到达食物的最短路线
  • 「宇宙在计算它自己的未来！」

总体思路：用计算通常被描述的那套语言去量化内禀计算，就能理解自然如何计算，以及它为什么复杂。

2.2 核心问题

复杂系统中一个变量的下一状态是如何被计算出来的？ 它是系统内部一次局部计算的输出。

把复杂系统看作多元时间序列，对某个目标变量 的下一个值 ，讲义提出一连串问题：

  1. 中的信息来自哪里？怎样度量？（应该去哪里找？）
  2. 能否把 中的信息处理建模为：
    • 存储了多少信息？
    • 传递了多少信息，又该归因于哪个源？
  3. 这些部分能否分割？它们会不会重叠？

这一框架贯穿接下来三周：先看目标自己的过去（存储），再看其他源（传递），最后在网络层面选出全部「父节点」（有效网络推断）。

2.3 可以分析哪些多元时间序列？

讲义回顾了两个例子：

  • Scissors-Paper-Rock：我们是怎样给出招行为建模的？——用自己上一招、对手上一招去预测下一招，其实已经在做「存储 vs 传递」的区分。
  • 初等元胞自动机（ECA）rule 54：横轴是格子，纵轴是时间（向下）。能否用对信息的操作来刻画 CA 的更新？Module 10/11 的 tutorial 会在 rule 54 上计算局部存储与局部传递。

信息动力学研究的是：

  • 目标变量的状态更新，
  • 以及这些度量在空间和时间上的动态（即局部/pointwise 值的时空图）。

（Lizier 2013, The local information dynamics of distributed computation in complex systems）

三、记号

  • 考虑一组时间序列过程
  • 每个过程由一串随机变量 组成；
  • 其实现（realisation）为 ；
  • 时间指标 可数（离散时间）。

连续块向量（状态）——长度为 的过去：

注意下标： 以 结尾（包含当前时刻），预测的对象是 。下周会把它解释为目标底层状态的 Takens 嵌入。

形式化的核心问题：

随机变量 中的信息，在多大程度上来自其他变量 （ ）？

（当然也包括来自 自己的过去 。）

四、熵率（Entropy Rate）

4.1 历史上的第一步

在信息动力学之前，人们刻画时间序列过程的第一个量就是熵率。讲义给出两种定义：

定义 1：块熵随块长增长的极限速率

即平均每个符号的熵；在「块熵 vs 」的图上，它是渐近斜率。

定义 2：给定过去后，下一个随机变量的不确定性

在块熵图上，它是相邻两点的增量 的极限——由链式法则，

关键结论：

对平稳过程成立

记号提醒（讲义脚注）：本课的撇号与 Cover & Thomas §4.2 正好相反——这里不带撇的 是条件熵形式，带撇的 是块熵除以 的形式。

为什么平稳时相等（标准证明思路）：平稳时 单调不增且有下界，故收敛到 ；而

是 的 Cesàro 平均，收敛到同一极限。

4.2 熵率的含义

  • 隐含的建模步骤：我们把过程自身的过去当作第一个信息源，然后问：还剩多少不确定性？
  • 熵率衡量的是过程「真正新」的部分——即使知道全部历史，每一步仍然无法预测的信息量。
  • 这正好为下周铺路：

从过去可预测的部分（）

即 ：下一个值的不确定性 = 来自过去的信息（存储） + 剩余的不确定性（熵率）。

4.3 编码解释（讲义思考题）

讲义问：熵率的编码解释是什么？（想想给英文文本的字母编码。）

  • 第 1 周学过：独立同分布信源，最优编码平均每个符号至少需要 bits。
  • 但英文字母不是独立的：看到 th 之后 e 的概率很高。如果编码器利用前文上下文（例如对每种上下文用不同的码表），平均每个符号所需 bit 数可以降到 过去。
  • 所以 熵率 = 利用全部历史进行最优编码时，平均每个符号所需的最少 bit 数——它是有记忆信源的压缩极限。
  • 也可以从块的角度理解：把 个字母打包成一个块编码，平均每个字母需 bits， 就是 。两种理解平稳时相同。

4.4 算例（补充，用于理解）

例 1：独立同分布过程

过去 ，所以 。过去没有任何帮助，没有存储。

例 2：周期过程 0101…

一旦知道上一个值，下一个值完全确定： 。但 bit。所以全部 1 bit 都可以从过去预测——下周会看到 bit。

例 3：两状态马尔可夫链（W11 的 heartbeat 源过程）

转移概率： ， 。

平稳分布（令 ）：

一阶马尔可夫，只需 的过去：

其中 ： ， 。

而 bits，所以约一半的不确定性可以从过去预测（ bits），另一半是每一步真正的「新信息」。（巧合吗？W11 会看到，目标完全复制这个源时，TE 恰好等于这个 0.3735 bits——源每一步产生的新信息全部传给了目标。）

例 4：块熵图上的直观

过程 随 斜率（熵率） 「截距」含义
i.i.d. 从原点出发的直线 0：没有结构
周期 2 先升到 1 bit 后保持水平 0 1 bit：全部是结构
一般有记忆过程 先较快上升，然后趋于斜率 的直线 渐近线的截距 = excess entropy（下周）

块熵逼近渐近线的快慢反映了过程的结构/记忆——这就是下周的 excess entropy / predictive information。

4.5 从熵率到信息动力学

熵率只回答了「剩下多少不确定性」，而信息动力学想回答的是「已经解释掉的那部分信息来自哪里」：

H(X_{n+1})
 ├── 来自自身过去的信息         → 信息存储（AIS, Week 10）
 ├── 来自其他源、且过去没给出的 → 信息传递（TE, Week 11）
 │      └── 多个源时：逐个条件化 → 条件 TE、有效网络（Week 11–12）
 └── 剩余不确定性               → 条件于所有源后的熵率

五、讲义小结

  • 介绍了信息动力学方法背后的哲学：用存储、传递、修改来分析复杂系统中的信息处理。
  • 把熵率作为理解时间序列过程动态更新的第一步。
  • 下一讲：复杂系统中的信息存储。

六、本周考点速记 / 易错点

  1. Mitchell 对比表：计算机科学（数字静态纸带；确定、串行、无差错、集中；人类设计者） vs 生物计算（模拟、时空分布的模式、统计采样；去中心、并行、局部、随机且利用随机性；自然选择）。
  2. 内禀信息处理：动力学过程把初态+输入变为后态+输出。生物计算分布式、持续进行（不一定终止）。
  3. 计算三要素 ↔︎ 信息动力学：Memory ↔︎ 存储；Signalling ↔︎ 传递；Processing ↔︎ 修改。
  4. 核心问题：目标变量下一个值 的信息从哪里来？存储多少、传递多少、归因于谁、能否分割/是否重叠。
  5. 记号： ，以 结尾，预测 。
  6. 熵率两种定义： （块熵斜率）； （给定过去的条件熵，块熵增量）。平稳时相等。本课撇号与 Cover & Thomas 相反。
  7. 熵率的含义：把过去当作第一个信息源后剩余的不确定性；编码上是有记忆信源每符号的最小平均码长。
  8. ——熵率与下周 AIS 互补。
  9. i.i.d. 过程熵率 = ；确定性周期过程熵率 = 0。
  10. 两状态马尔可夫链： ， 离开的概率。

七、下周预告

Week 10 — Module 10: Information storage：

  • Active Information Storage 及其局部值；
  • 历史长度 怎么选（Ragwitz、最大化偏差修正 AIS、非均匀嵌入）；
  • JIDT 的 AUTO_EMBED_METHOD；
  • CA rule 54 上的局部 AIS：blinker 和 domain 是主要的存储实体。