更改

=== 计算力学中的涌现 ===

=== 计算力学中的涌现 ===

我们直觉中对涌现的定义就是系统出现了新的特征，但是该定义并没有说明“新特征”是什么，以及它“新”在哪里。所以还需要更精确的语言对涌现的概念进行描述。涌现通常被理解为一个过程，该过程所产生的结构并不能直接由控制系统的定义所约束以及被瞬时力所描述。比如一堆随机运动的粒子，虽然它们受到的瞬时力可以用运动方程描述，但是从宏观尺度上却会表现出诸如压强、体积以及温度等新特征。我们需要引入[[斑图]]的概念来明确说明什么是新特征，否则涌现这一概念几乎没有内容，因为几乎任何时间依赖的系统都会表现出涌现特征。

我们直觉中对涌现的定义就是系统出现了新的特征，但是该定义并没有说明“新特征”是什么，以及它“新”在哪里。所以还需要更精确的语言对涌现的概念进行描述。涌现通常被理解为一个[[过程]]，该过程所产生的结构并不能直接由控制系统的定义所约束以及被瞬时力所描述。比如一堆随机运动的粒子，虽然它们受到的瞬时力可以用运动方程描述，但是从宏观尺度上却会表现出诸如压强、体积以及温度等新特征。我们需要引入[[斑图]]的概念来明确说明什么是新特征，否则涌现这一概念几乎没有内容，因为几乎任何时间依赖的系统都会表现出涌现特征。

在计算力学中，斑图通常指的是从时间序列中总结出的规律性结构。实际上，检测到的斑图通常是通过观察者选择的统计数据来隐含假定的，可能某些斑图的功能表现与其数学模型一致，但这些模型本身依赖于一系列理论假设。简而言之，斑图通常是被猜测出来的，观察者通过固定的规律库来预测这些结构，然后再进行验证。可以用通信频道做一个类比，观察者就像是一个已经手握密码本的接收者，任何未能通过密码本解码的信号本质上都是噪声，即观察者未能识别的斑图。

在计算力学中，斑图通常指的是从时间序列中总结出的规律性结构。实际上，检测到的斑图通常是通过观察者选择的统计数据来隐含假定的，可能某些斑图的功能表现与其数学模型一致，但这些模型本身依赖于一系列理论假设。简而言之，斑图通常是被猜测出来的，观察者通过固定的规律库来预测这些结构，然后再进行验证。可以用通信频道做一个类比，观察者就像是一个已经手握密码本的接收者，任何未能通过密码本解码的信号本质上都是噪声，即观察者未能识别的斑图。

智能体面临的基本问题是基于对隐藏环境状态的建模和对未来环境的预测。这需要一个量化的理论来描述智能体如何处理信息和构建模型。

智能体面临的基本问题是基于对隐藏环境状态的建模和对未来环境的预测。这需要一个量化的理论来描述智能体如何处理信息和构建模型。

=== 柯氏复杂度 ===

=== 柯氏复杂度 ===

[[柯式复杂度]][math]\displaystyle{ K(x) }[/math]是指在通用确定性[[图灵机]]（Universal Turing Machine，简称UTM）上运行时输出的最小程序所需的比特数。不同的程序语言描述同一程序的[math]\displaystyle{ K(x) }[/math]是可以比较的，但也无法确定哪种程序语言有最小的[math]\displaystyle{ K(x) }[/math]，同一种程序语言在描述不同程序时[math]\displaystyle{ K(x) }[/math]也并不相同，所以柯式复杂度通常是不可计算的。如果待测对象是由信息源（例如马尔可夫链）生成的离散符号序列[math]\displaystyle{ s^L }[/math] ，[math]\displaystyle{ L }[/math]为序列的长度，柯式复杂度与香农熵率[math]\displaystyle{ h_μ }[/math]的关系为：

[[柯式复杂度]][math]\displaystyle{ K(x) }[/math]是指在通用确定性[[图灵机]]（Universal Turing Machine，简称UTM）上运行时输出的最小程序所需的比特数。不同的程序语言描述同一程序的[math]\displaystyle{ K(x) }[/math]是可以比较的，但也无法确定哪种程序语言有最小的[math]\displaystyle{ K(x) }[/math]，同一种程序语言在描述不同程序时[math]\displaystyle{ K(x) }[/math]也并不相同，所以柯式复杂度通常是不可计算的。如果待测对象是由信息源（例如[[马尔可夫链]]）生成的离散符号序列[math]\displaystyle{ s^L }[/math] ，[math]\displaystyle{ L }[/math]为序列的长度，柯式复杂度与香农熵率[math]\displaystyle{ h_μ }[/math]的关系为：

<math>

<math>

[math]\displaystyle{ K(s^L )≈C_μ (s^L )+h_μ L }[/math]

[math]\displaystyle{ K(s^L )≈C_μ (s^L )+h_μ L }[/math]

如果在已确定描述语言（程序）的情况下，柯式复杂度[math]\displaystyle{ K(s^L ) }[/math]可以理解为描述[math]\displaystyle{ s^L }[/math]所用的总信息量。[math]\displaystyle{ h_μ L }[/math]为允许损失的信息量。统计复杂度[math]\displaystyle{ C_μ (s^L ) }[/math]可以理解为允许存在误差率[math]\displaystyle{ h_μ }[/math]的情况下，描述[math]\displaystyle{ s^L }[/math]所用的最少信息量。

如果在已确定描述语言（程序）的情况下，柯式复杂度[math]\displaystyle{ K(s^L ) }[/math]可以理解为描述[math]\displaystyle{ s^L }[/math]所用的总[[信息量]]。[math]\displaystyle{ h_μ L }[/math]为允许损失的信息量。统计复杂度[math]\displaystyle{ C_μ (s^L ) }[/math]可以理解为允许存在误差率[math]\displaystyle{ h_μ }[/math]的情况下，描述[math]\displaystyle{ s^L }[/math]所用的最少信息量。

在下图中，展示了柯式复杂度和统计复杂度在从简单周期性到完全随机的过程中的差异。如图(a)所示，柯式复杂度是过程中随机性的单调递增函数，是对信息源不可预测程度的度量，它可以通过香农熵率来衡量其随机性程度。相反，统计复杂度在两个极端点上均为零，并在中间达到最大值（见图(b)）。它基于这样的观点：随机性在统计上是简单的，一个完全随机过程具有零统计复杂度。周期性在统计上也是简单的，一个完全周期性过程具有较低的统计复杂度。复杂过程在这两个极端之间产生，并且是可预测机制和随机机制的混合，有中等程度随机性的数据具有最大的统计复杂度。

在下图中，展示了柯式复杂度和统计复杂度在从简单周期性到完全随机的过程中的差异。如图(a)所示，柯式复杂度是过程中随机性的单调递增函数，是对[[信息源]]不可预测程度的度量，它可以通过香农熵率来衡量其随机性程度。相反，统计复杂度在两个极端点上均为零，并在中间达到最大值（见图(b)）。它基于这样的观点：随机性在统计上是简单的，一个完全随机过程具有零统计复杂度。周期性在统计上也是简单的，一个完全周期性过程具有较低的统计复杂度。复杂过程在这两个极端之间产生，并且是可预测机制和随机机制的混合，有中等程度随机性的数据具有最大的统计复杂度。

[[文件:复杂度比较.jpg|居中|无框|600x600像素]]

[[文件:复杂度比较.jpg|居中|无框|600x600像素]]

因果态是一种特殊的划分方法，它的划分函数记作<math>\epsilon</math>，公式为<math> \epsilon{:}\overleftarrow{S}\mapsto2^{\overset{\leftarrow}{S}}</math>，其中<math> 2^{\overset{\leftarrow}{S}}</math>是<math> \overleftarrow{S}</math>的幂集。根据因果态的定义，则存在如下关系：<math>\epsilon(\stackrel{\leftarrow}{s})\equiv\{\stackrel{\leftarrow}{s}^{\prime}|\mathrm{P}(\stackrel{\rightarrow}{S}=\stackrel{\rightarrow}{s}\mid\stackrel{\leftarrow}{S}=\stackrel{\leftarrow}{s})=\mathrm{P}(\stackrel{\rightarrow}{S}=\stackrel{\rightarrow}{s}\mid\stackrel{\leftarrow}{S}=\stackrel{\leftarrow}{s}^{\prime})，\mathrm{for~all~}\overrightarrow{s}\in\overrightarrow{S},\stackrel{\leftarrow}{s}^{\prime}\in\stackrel{\leftarrow}{S}\} </math>，其中<math>\mathcal{S} </math>为因果态的集合，<math>\stackrel{\leftarrow}{s} </math>为历史序列的随机变量，<math>\mathcal{S} </math>是<math>\mathcal{R} </math>的一种最优形式，因为因果态的如下性质。

因果态是一种特殊的划分方法，它的划分函数记作<math>\epsilon</math>，公式为<math> \epsilon{:}\overleftarrow{S}\mapsto2^{\overset{\leftarrow}{S}}</math>，其中<math> 2^{\overset{\leftarrow}{S}}</math>是<math> \overleftarrow{S}</math>的幂集。根据因果态的定义，则存在如下关系：<math>\epsilon(\stackrel{\leftarrow}{s})\equiv\{\stackrel{\leftarrow}{s}^{\prime}|\mathrm{P}(\stackrel{\rightarrow}{S}=\stackrel{\rightarrow}{s}\mid\stackrel{\leftarrow}{S}=\stackrel{\leftarrow}{s})=\mathrm{P}(\stackrel{\rightarrow}{S}=\stackrel{\rightarrow}{s}\mid\stackrel{\leftarrow}{S}=\stackrel{\leftarrow}{s}^{\prime})，\mathrm{for~all~}\overrightarrow{s}\in\overrightarrow{S},\stackrel{\leftarrow}{s}^{\prime}\in\stackrel{\leftarrow}{S}\} </math>，其中<math>\mathcal{S} </math>为因果态的集合，<math>\stackrel{\leftarrow}{s} </math>为历史序列的随机变量，<math>\mathcal{S} </math>是<math>\mathcal{R} </math>的一种最优形式，因为因果态的如下性质。

性质1（因果态具有最大预测性）：对于所有有效态<math>\mathcal{R} </math>和正整数<math>L </math>，都有<math>H[\stackrel{\rightarrow}{S}^L|\mathcal{R}]\geq H[\stackrel{\rightarrow}{S}^L|\mathcal{S}] </math>，<math>\stackrel{\rightarrow}{S}^L </math>为<math>L </math>个长度的未来序列集合，<math>H[\stackrel{\rightarrow}{S}^L|\mathcal{R}] </math>和<math>H[\stackrel{\rightarrow}{S}^L|\mathcal{S}] </math>是<math>\stackrel{\rightarrow}{S}^L </math>的条件熵。可以理解为因果态集合<math>\mathcal{S} </math>在有效态集合<math>\mathcal{R} </math>的所有类型中，它的预测能力最强，证明过程如下：

性质1（因果态具有最大预测性）：对于所有有效态<math>\mathcal{R} </math>和正整数<math>L </math>，都有<math>H[\stackrel{\rightarrow}{S}^L|\mathcal{R}]\geq H[\stackrel{\rightarrow}{S}^L|\mathcal{S}] </math>，<math>\stackrel{\rightarrow}{S}^L </math>为<math>L </math>个长度的未来序列集合，<math>H[\stackrel{\rightarrow}{S}^L|\mathcal{R}] </math>和<math>H[\stackrel{\rightarrow}{S}^L|\mathcal{S}] </math>是<math>\stackrel{\rightarrow}{S}^L </math>的[[条件熵]]。可以理解为因果态集合<math>\mathcal{S} </math>在有效态集合<math>\mathcal{R} </math>的所有类型中，它的预测能力最强，证明过程如下：

<math>\epsilon(\stackrel{\leftarrow}{s})\equiv\{\stackrel{\leftarrow}{s}^{\prime}|\mathrm{P}(\stackrel{\rightarrow}{S}=\stackrel{\rightarrow}{s}\mid\stackrel{\leftarrow}{S}=\stackrel{\leftarrow}{s})=\mathrm{P}(\stackrel{\rightarrow}{S}=\stackrel{\rightarrow}{s}\mid\stackrel{\leftarrow}{S}=\stackrel{\leftarrow}{s}^{\prime}) </math>

<math>\epsilon(\stackrel{\leftarrow}{s})\equiv\{\stackrel{\leftarrow}{s}^{\prime}|\mathrm{P}(\stackrel{\rightarrow}{S}=\stackrel{\rightarrow}{s}\mid\stackrel{\leftarrow}{S}=\stackrel{\leftarrow}{s})=\mathrm{P}(\stackrel{\rightarrow}{S}=\stackrel{\rightarrow}{s}\mid\stackrel{\leftarrow}{S}=\stackrel{\leftarrow}{s}^{\prime}) </math>

==斑图重构机器==

==斑图重构机器==

智能体如何处理测量结果才能识别其中因果态呢？为了解决这个问题，计算力学建立了名为斑图重构机器（ϵ-machine）的模型，它可以重构测量结果中的序列，去除随机噪声后识别其中的因果态。斑图重构机器的大小可以用统计复杂度衡量，它的形式化定义可以用公式表示为<math>M=(\mathcal{S},T)</math>，其中<math>T</math>为状态到状态映射的集合，满足<math>S_{t+1}=TS_t</math>，<math>S</math>为集合<math>\mathcal{S} </math>中的任意一个因果态，它类似于一个粗粒化后的宏观动力学。<math>T_{ij}^{\left ( s \right )}</math>为两个因果态<math>S_i</math>和<math>S_j</math>之间的因果态转移概率映射，<math>T_{ij}^{(s)}\equiv\mathrm{P}(\mathcal{S}'=\mathcal{S}_j,\stackrel{\to}{S}^1=s|\mathcal{S}=\mathcal{S}_i)</math>。每个[math]\displaystyle{ \mathcal{S} }[/math]都有<math>\epsilon</math>函数和<math>T</math>函数，这两个函数可以组成一个有序对<math>\left \{ \epsilon,T \right \}</math>，通过学习<math>\epsilon</math>和<math>T</math>函数可以提高机器识别因果态的准确度。

智能体如何处理测量结果才能识别其中因果态呢？为了解决这个问题，计算力学建立了名为斑图重构机器（ϵ-machine）的模型，它可以重构测量结果中的序列，去除随机噪声后识别其中的因果态。斑图重构机器的大小可以用统计复杂度衡量，它的形式化定义可以用公式表示为<math>M=(\mathcal{S},T)</math>，其中<math>T</math>为状态到状态映射的集合，满足<math>S_{t+1}=TS_t</math>，<math>S</math>为集合<math>\mathcal{S} </math>中的任意一个因果态，它类似于一个粗粒化后的[[宏观动力学]]。<math>T_{ij}^{\left ( s \right )}</math>为两个因果态<math>S_i</math>和<math>S_j</math>之间的因果态转移概率映射，<math>T_{ij}^{(s)}\equiv\mathrm{P}(\mathcal{S}'=\mathcal{S}_j,\stackrel{\to}{S}^1=s|\mathcal{S}=\mathcal{S}_i)</math>。每个[math]\displaystyle{ \mathcal{S} }[/math]都有<math>\epsilon</math>函数和<math>T</math>函数，这两个函数可以组成一个有序对<math>\left \{ \epsilon,T \right \}</math>，通过学习<math>\epsilon</math>和<math>T</math>函数可以提高机器识别因果态的准确度。

如果将模型构建视为一个动态过程，那么在模型构建和完善过程中，它的两个量化指标香农熵率<math>h_μ </math>和统计复杂度<math>C_μ  </math>可以分别用来监测智能体模型的预测能力和模型大小。由于外部环境实际熵率与智能体内部模型的熵率之间的绝对差异决定了智能体的预测误差率，因此模型的熵率越接近外部环境的熵率，智能体的生存机会就越高。但这种生存能力是有代价的，这个代价由智能体在进行预测时必须投入的计算资源决定的，这种代价的量度就是模型的统计复杂度。

如果将模型构建视为一个动态过程，那么在模型构建和完善过程中，它的两个量化指标香农熵率<math>h_μ </math>和统计复杂度<math>C_μ  </math>可以分别用来监测智能体模型的预测能力和模型大小。由于外部环境实际熵率与智能体内部模型的熵率之间的绝对差异决定了智能体的预测误差率，因此模型的熵率越接近外部环境的熵率，智能体的生存机会就越高。但这种生存能力是有代价的，这个代价由智能体在进行预测时必须投入的计算资源决定的，这种代价的量度就是模型的统计复杂度。

[[文件:层次机器示意图1.jpg|居中|无框|600x600像素|WU]]

[[文件:层次机器示意图1.jpg|居中|无框|600x600像素|WU]]

上表为因果时间序列建模层级，展示了可能的前四个层级，但这个过程是开放式的，可以不止四个层级，每个层级根据其模型类别定义。模型本身由状态（圆圈或方块）和转移（标记箭头）组成，每个模型都有一个独特的起始状态，由一个内嵌的圆圈表示。数据流本身是最低层级，通过将序列测量分组为重复子序列，从数据流中构建出深度为的树。下一个层级的模型，即具有状态和转移的有限自动机（Finite Automaton，简称FA），通过将树节点分组从树中重构。所示的最后一个层级，字符串生成机器（Pattern Matching，简称PM），通过将FA状态分组并推断出操控寄存器中字符串的生成规则来构建。

上表为因果时间序列建模层级，展示了可能的前四个层级，但这个过程是开放式的，可以不止四个层级，每个层级根据其模型类别定义。模型本身由状态（圆圈或方块）和转移（标记箭头）组成，每个模型都有一个独特的起始状态，由一个内嵌的圆圈表示。数据流本身是最低层级，通过将序列测量分组为重复子序列，从数据流中构建出深度为的树。下一个层级的模型，即具有状态和转移的[[有限自动机]]（Finite Automaton，简称FA），通过将树节点分组从树中重构。所示的最后一个层级，字符串生成机器（Pattern Matching，简称PM），通过将FA状态分组并推断出操控寄存器中字符串的生成规则来构建。

考虑一个由<math>m</math>个测量结果构成的数据流<math>s</math>，如果它是周期性的，那么第0级（Level 0），即测量结果本身，它的表示方法依赖于<math>m</math>。在极限<math>m\to\infty </math>情况下，第0级会产生一个无穷大的表示。当然，第0级是最准确的数据模型，尽管它几乎没有任何帮助，几乎不值得被称为“模型”。相比之下，一个深度为<math>D</math>的树将给出一个有限表示，即使数据流的长度是无限的，只要数据流具有周期小于等于<math>D</math>。这个树有长度为<math>D</math>的路径，由数据流的周期给出。这些路径中的每一个都对应于<math>s</math>中重复模式的一个不同阶段。如果<math>s</math>是非周期性的，那么树模型类将不再是有限的，并且与<math>m</math>无关。 事实上，如果数据流具有正熵（<math>h_μ＞0 </math>），那么树的大小将呈指数增长，<math>\approx\left\|\mathcal{A}\right\|^{Dh_{\mu}} </math> ，因为<math>D</math>的增加解释了<math>s</math> 中长度<math>D</math>不断增加的子序列。粗略地说，如果数据流具有随时间衰减得足够快的相关性，则下一级（随机）有限自动机将给出有限表示。状态数<math>\left\|\mathrm{V}\right\| </math>表示数据流中的内存量，因此表示<math>s</math>中测量值之间存在相关性的典型时间。但也有可能第 2 级不提供有限表示。那么就需要另一个级别（第 3 级）。

考虑一个由<math>m</math>个测量结果构成的数据流<math>s</math>，如果它是周期性的，那么第0级（Level 0），即测量结果本身，它的表示方法依赖于<math>m</math>。在极限<math>m\to\infty </math>情况下，第0级会产生一个无穷大的表示。当然，第0级是最准确的数据模型，尽管它几乎没有任何帮助，几乎不值得被称为“模型”。相比之下，一个深度为<math>D</math>的树将给出一个有限表示，即使数据流的长度是无限的，只要数据流具有周期小于等于<math>D</math>。这个树有长度为<math>D</math>的路径，由数据流的周期给出。这些路径中的每一个都对应于<math>s</math>中重复模式的一个不同阶段。如果<math>s</math>是非周期性的，那么树模型类将不再是有限的，并且与<math>m</math>无关。 事实上，如果数据流具有正熵（<math>h_μ＞0 </math>），那么树的大小将呈指数增长，<math>\approx\left\|\mathcal{A}\right\|^{Dh_{\mu}} </math> ，因为<math>D</math>的增加解释了<math>s</math> 中长度<math>D</math>不断增加的子序列。粗略地说，如果数据流具有随时间衰减得足够快的相关性，则下一级（随机）有限自动机将给出有限表示。状态数<math>\left\|\mathrm{V}\right\| </math>表示数据流中的内存量，因此表示<math>s</math>中测量值之间存在相关性的典型时间。但也有可能第 2 级不提供有限表示。那么就需要另一个级别（第 3 级）。