3,094
个编辑
更改
跳到导航
跳到搜索
第142行：
第142行： − − === 统计复杂度=== − − ====柯氏复杂度的问题==== − 智能体在构建和优化斑图重构机器的过程中，由于计算资源的限制，不能无限制地增加模型的大小。因此我们需要一个能够量化模型复杂度的指标，以便监控和调整模型的大小，确保模型能匹配已有的计算资源。[[柯式复杂度]][math]\displaystyle{ K(x) }[/math]，也就是在通用确定性[[图灵机]]（Universal Turing Machine，简称UTM）上运行时生成字符串[math]\displaystyle{ x }[/math]的最小程序长度，是人们常用的一个复杂性度量指标。 − − 然而，柯式复杂度存在两个明显的问题，第一个问题是它的不可计算性，柯氏复杂度仅仅是一个理想化的概念；第二个问题是它可能无法度量程序的结构和动态特性。因为柯式复杂度[math]\displaystyle{ K(x) }[/math]需要考虑字符串中的所有比特，这就包括随机生成的比特。因此，柯氏复杂度会在随机生成的比特上计算出较大的复杂性，而这与我们的直觉不符：复杂性不能等价于随机性。 − − ====统计复杂度==== − 为了解决这两个明显问题，计算力学提出了[[统计复杂度]][math]\displaystyle{ C_μ(x) }[/math]的概念，用来量化模型的复杂性，它可以反映[math]\displaystyle{ x }[/math]的结构和[[动态特性]]，以及能够计算出有效建模所需的计算资源。它的公式为： − − <math> − C_{\mu}(x)=\left\|M_{\min }(x \mid \mathrm{BTM})\right\| − </math> − − 这里， − <math> − C_{\mu}(x) − </math>是统计复杂度<ref name=crutchfield_young_1989/>，表示时间序列<math> − x − </math>的复杂性度量。它反映了在给定精度<math> − \mu − </math>下，能够生成该序列的最小伯努利图灵机的程序长度。 − − 这里，[[伯努利图灵机]]（Bernoulli-Turing machine，简称BTM）是一种[[概率性图灵机]]，是确定性图灵机的一种扩展。它通过引入随机数发生器，可以生成离散的随机序列。伯努利图灵机包含输入纸带、输出纸带、有限状态控制单元和工作纸带。在运行过程中，伯努利图灵机按照常规图灵机的方式读取纸带上的符号和自身的当前状态，并依据内置的规则表进行操作。与普通图灵机不同的是，其规则表中有一些可随机执行的规则，它会根据随机数发生器的采样结果来决定具体的执行路径。例如，在某个状态下，图灵机可能有两种可选的操作，普通图灵机根据确定的规则选择其中一种，而伯努利图灵机则通过随机源（即随机数发生器）以一定的概率来执行其中的某一种操作。 − − <math>M_{\min }(x \mid \mathrm{BTM})</math>代表在能够捕捉数据[math]x[/math]条件下的所有伯努利图灵机中的最小的模型<ref name="bennett_1988">{{cite book |last1=Bennett |first1=C. H. |title=Dissipation, information, computational complexity, and the definition of organization |editor1-last=Pines |editor1-first=D. |book-title=Emerging Syntheses in the Sciences |publisher=Addison-Wesley |location=Redwood City |year=1988}}</ref>。这个模型是能够在允许误差为[math]\mu[/math]的条件下有效预测<math>x</math>的最简单形式。<math>\left\|⋅\right\|</math>这个符号表示对模型复杂度的量化，例如图灵机的指令表长度。 − − 由于内部模型（ϵ-machine）作为一种伯努利图灵机，本身也是用字符串（因果态）来描述的，所以可以用长度、香农熵等指标来度量内部模型的复杂度。当我们使用香农熵来刻画内部模型的复杂度时，我们可以给出对于观测序列来说一个等价的可计算的定义<ref name=crutchfield_young_1989/>： − − <math>C_\mu(\mathcal{x})\equiv H[\mathcal{S}] </math>， − − 其中<math>\mathcal{S} </math>为观测数据<math>\mathcal{x} </math>的因果态集合。 − − 统计复杂度的一个特征是，对于完全随机对象，有[math]\displaystyle{ C_μ(x)=0 }[/math]，如抛硬币产生的序列；以及对于简单的周期性过程，如[math]\displaystyle{ x=00000000…0 }[/math]，都会有[math]\displaystyle{ C_μ(x)=0 }[/math]。因此，统计复杂度的值对于（简单的）周期性过程和完全随机过程都很小。所以，与[[柯氏复杂度]]相比，统计复杂度这种度量[math]\displaystyle{ C_μ(x) }[/math]，相比于[[柯氏复杂度]]来说，剔除了通用图灵机在模拟随机比特时所花费的计算努力。 − − ====两种复杂性的对比==== − − 下图展示了柯式复杂度和统计复杂度随着序列从简单周期性变为完全随机的过程中二者的差异。如图(a)所示，柯式复杂度会随着序列随机性的增加而单调递增。相反，统计复杂度在周期和随机两个极端点上均为零，并在中间达到最大值（见图(b)）。这反映出如下的观点：随机性在统计上是简单的，一个完全随机的过程具有零统计复杂度；周期性在统计上也是简单的，一个完全是周期性的过程具有较低的统计复杂度。复杂过程是在这两个极端之间产生，并且是可预测机制和随机机制的混合，有中等程度随机性的数据具有最大的统计复杂度。 − [[文件:复杂度比较.jpg|居中|无框|600x600像素|]] − − === 香农熵率与复杂度 === − 上文中提到的一个序列的随机性可以用[[香农熵率]]（Shannon Entropy Rate）来度量，香农熵率是信息论中的一个概念，它是[[香农熵]]的扩展，主要用于描述时间序列在单位时间上的平均信息量。在这里，香农熵率可以定义为： − − <math> − h=\lim_{L\to\infty}\frac{H(P(s^L))}L − </math> − − 其中，[math]\displaystyle{ s^L }[/math]是环境信息生成的离散符号序列，[math]\displaystyle{ L }[/math]为序列的长度，<math> P(s^L)</math>是序列[math]\displaystyle{ s^L }[/math]的边际分布，[math]\displaystyle{ H }[/math]是香农熵。在建模框架中，[math]\displaystyle{ h }[/math]可以解释为智能体在预测序列[math]\displaystyle{ s^L }[/math]的后续符号时的误差率。由该公式可见，熵率也就是[[自信息]]的平均值。 − − 香农熵率是归一化的度量信息不确定性程度的指标，信息的不确定性越高，香农熵率越大。对于简单的周期性过程，如[math]\displaystyle{ x=00000000…0 }[/math]，香农熵率为0，对于完全随机的对象，如抛硬币产生的序列，香农熵率为1。 − − 香农熵率与柯式复杂度[math]\displaystyle{ K(x) }[/math]的关系为： − − <math> − \frac{K\left(s^{L}\right)}{L}\underset{L\to\infty}{\operatorname*{\operatorname*{\operatorname*{\rightarrow}}}}h, − </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]所用的最少信息量。 − − ===模型重构=== − − 由于智能体的计算资源是有限的，当测量结果中的数据量超过模型能够处理的极限时，我们就需要构造模型，以更简洁地描述数据。这样做的目的是在保持计算资源不变的情况下，确保智能体仍然能够对外界进行有效的预测。这一过程可以反复迭代地进行，也就是说，因果态序列也可以被看做是原始状态序列，因此智能体可以在因果态基础上再次重构生成该因果态的模型。于是，这便形成了一系列不断升级的层级化的重构过程。 − − 重构的方法主要是通过寻找原有模型中相似的状态组，从而形成因果态；然后，在已经识别出的因果态中，我们进一步抽象出更高层级的'''因果态组'''。这样，随着数据量的增大，我们就可以不断地在上一层级抽象出更高的层级，从而在计算资源有限的情况下，仍然能够应对更大量的数据。譬如，当智能体观测到“121212”时，会把“12”看成是一个模块，用一个字符“A”来表示，于是原本的微观态字符串就可以被重构为“AAA”这样的宏观态字符串，复杂度就降低了。而当模型进一步观测到更长的字符串是“12121231212123”时，它便需要跳出原本的分组，而把“1212123”看成是一个新的模块，可以用一个字符“B”来表示，于是内部模型可以进一步用“BB”这样的新字符串来表示同一个观测对象。这便是一次模型重构不断升级的过程。下表中列举了一种模型重构的可能途径： − [[文件:层次机器示意图1.jpg|居中|无框|600x600像素|WU]] − − 上表为因果时间序列建模层级，展示了可能的前四个层级，每个层级根据其模型类别定义。但这个过程仅仅是一个示例，可以不止四个层级。模型本身由状态（圆圈或方块）和转移（标记箭头）组成，每个模型都有一个独特的起始状态，由一个双重圆圈表示。数据流本身是最低层级，通过将序列测量分组为重复子序列，从数据流中构建出深度为<math>D</math>的树。下一个层级的模型，即具有状态和转移的[[有限自动机]]（Finite Automaton，简称FA），可以通过将树节点分组从树中重构。图中所示的最后一个层级，字符串生成机器（Pattern Matching，简称PM），可以通过将有限状态自动机的状态进行分组并推断出操控寄存器中字符串的生成规则来构建。 − − 考虑一个由<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} </math> ，因为<math>D</math>的增加解释了<math>s</math> 中长度<math>D</math>不断增加的子序列。粗略地说，如果数据流具有随时间衰减得足够快的相关性，则下一级（随机）有限自动机将给出有限表示。状态数<math>\left\|\mathrm{V}\right\| </math>表示数据流中的内存量，因此表示<math>s</math>中测量值之间存在相关性的典型时间长度。但也有可能第 2 级不提供有限表示。那么就需要另一个级别（第 3 级）。 − − ===模型重构算法=== − 上面介绍了斑图重构机器，是智能体识别因果态的一种方式。若结合模型重构的概念，我们可以给出斑图重构机器的完整定义：斑图重构机器（ϵ-machine）是能够用最少的计算资源对测量结果进行有限描述同时复杂度最小的模型。模型重构的算法步骤如下： − − 1. 在最低水平上，设定0级模型为描述数据本身，即<math>M_0=s</math>，将初始层级<math>l</math>设置为比0级高一级，即<math>l=1</math>； − − 2. 从更低模型重构模型<math>M_l=M_{l-1}/∼</math>，其中<math>∼</math>表示<math>l</math>级上的因果等价类； − − <math>M_l=M_{l-1}/∼</math>的含义是，在<math>l-1</math>级上被区别对待的状态在<math>l</math>级上可以被视为同一个因果态。此时因果态集合<math>\mathcal{S} </math>和因果态上的转移概率映射集合<math>T</math>都被更新了； − − 3. 收集更多的数据，增大序列长度<math>L </math>，得到更加精确的一系列模型<math>M_l</math>和因果态集合<math>\mathcal{S} </math>； − − 4. 根据统计复杂度可计算的定义<math>C_\mu(\mathcal{x})\equiv H[\mathcal{S}] </math>，计算模型<math>M_l</math>的统计复杂度。如果随着<math>L </math>增大，模型的统计复杂度发散，即<math>C_μ(M_l) = \lVert M_l \rVert \underset{L \to 0}{\to} \infty</math>，那么回到第二步，得到更高级模型<math>M_{l+1}</math>； − − 5. 如果模型复杂度收敛，意味着算法已经重建好了一个合适的斑图重构机器，程序退出。 − − ==混沌动力学实例== − − === 逻辑斯谛映射 === − 接下来将演示如何将计算力学和模型重构算法应用于一个具体的实际案例<ref name="crutchfield_1994"/>。这个案例是混沌动力学中的[[Logistic映射|逻辑斯谛映射]](logistic map)，作者特别展示了算法在周期倍增的混沌路径上的表现。用于重建模型的数据流来自逻辑斯谛映射的轨迹，该轨迹是通过迭代映射<math>x_{n+1}=f(x_n)</math>生成的，迭代函数为<math>f(x) = rx(1-x)</math>，其中非线性参数<math>\begin{matrix}r&\in&[0,4]\end{matrix}</math>，初始条件<math>x_0\in[0,1]</math>，迭代函数的最大值出现在<math>x_c = \frac12</math>。 − − [[文件:逻辑斯谛曲线.jpg|居中|无框|500x500px|替代=]] − 上图为迭代函数<math>f(x) = rx(1-x)</math>中极限状态<math>x</math>与参数<math>r</math>的关系图<ref name="crutchfield_1994"/>，当<math>r＜3.5699...</math>时函数存在倍周期现象，当<math>r＞3.5699...</math>时会出现混沌现象。由于观察者观测的精细程度有限，若要识别混沌中的有序结构，就需要对<math>x</math>进行粗粒化操作，方法是通过二元分割观察轨迹<math>\mathbf{x}=x_0x_1x_2x_3\ldots </math> ，将其转换为离散序列<math>\mathcal{P}=\{x_n\in[0,x_c)\Rightarrow s=0,x_n\in[x_c,1]\Rightarrow s=1\} </math>，这种划分是“生成”的，这意味着足够长的二进制序列来自任意小的初始条件间隔。因此，可以使用粗粒化的观测<math>\mathcal{P} </math>来研究逻辑斯谛映射中的信息处理。 − − === 统计复杂度-熵率图 === − [[文件:复杂度-熵率图.jpg|居中|无框|600x600像素]] − 上图（a）为逻辑斯谛映射中统计复杂度<math>C_μ </math>与香农熵率<math>H(L)/L </math>的关系<ref name="crutchfield_1994"/>，三角形表示<math>(C_μ ,H(L)/L) </math>的大概位置，对应非线性参数<math>r</math>的 193 个取值，其中子序列长度<math>L=16 </math>，覆盖部分实验数据的粗实线是<math>C_μ =0 </math>时对<math>H(L)/L </math>得出的解析解曲线。 − − 本图表现了两个重要特征。第一个特征是熵率的极值导致零复杂度，也就是说在<math>H(L)/L=0 </math>处最简单的周期过程和在<math>H(L)/L=1 </math>处最随机的过程在统计复杂性上看都是简单的，它们都具有零复杂度，因为它们是由具有单一状态的斑图重构机器描述的；第二个特征是在两个极端情况之间，复杂度明显升高，并在临界熵率值<math>H_c </math>附近出现明显峰值（此处<math>r=3.5699...</math>）。<math>r_c=3.5699...</math>刚好是[[逻辑斯蒂映射]]的临界相变点，当[math]r<r_c[/math]时，模型处于周期行为；当[math]r>r_c[/math]时，模型进入混沌行为区域。因此，当熵率<math>H(L)/L < H_c </math>时，此时的数据集是由呈周期性（包括在混沌区域也呈周期性的参数）变化的参数下产生，大于<math>H_c </math>时数据集由混沌的参数下产生。本图可以对照统计复杂度小节中的图（b）一起理解。 − − 上图（b）为逻辑斯谛映射中在<math>H_c </math>（<math>r=3.5699...</math>）处，<math>L </math>与宏观态数量<math>\left|\mathbf{V}\right| </math>的关系，序列的长度<math>L=64 </math>时，<math>\left|\mathbf{V}\right|=196 </math>，从图中可以看出，随着<math>L </math>的增长，<math>\left|\mathbf{V}\right| </math>的值是发散的，若要用有限的<math>L </math>来描述<math>\left|\mathbf{V}\right| </math>，就需要将模型进行重构，升级为描述能力更强的模型。 − − === 模型升级 === − 下面三张图<ref name="crutchfield_1994"/>展示了模型重构升级进化的一种路径。(a),(b),(c)三张图分别对应了由低到高不同阶次的重构机器的状态转移图。图中的圆圈代表状态，连边代表状态之间的转移，连边上的数字代表一次伯努利过程采样的0或1。 − − [[文件:机器升级状态结构图.jpg|居中|无框|1200x1000像素]] − − 上图（a）为逻辑斯谛映射在<math>H_c </math>（<math>r=3.5699...</math>）处，序列长度<math>L=16 </math>时用斑图重构机器重构后的47个状态的状态转移图。图中每条闭合的链路长度都是16步，例如初始圆圈-1-3-5-9-12-16-19-21-23-27-31-35-39-41-43-45这条路径，它的总步数为16，每两步之间的数字是通过伯努利过程采样的二元分割的结果，每个分支代表它经历了一次伯努利随机过程。但是图（a）捕捉到的规律并不明显，我们将它进行一个简单的转换，用每两步之间的数字组成的序列替换机器中未分支的路径后就得到图（b），图（b）中的分支状态相当有规律。更进一步将图（b）升级为用字符生成器来描述增长的规律性就得到了图（c）。该图的有限自动机有两种状态（原有类型用圆圈表示，新类型用方块表示）和两个寄存器 A 和 B，A 和 B用于保存二进制字符串，初始状态 A 中保存的是0，B中保存的是1，B'表示对保存在B中的字符串的最后一位取反。 − − 图（b）中的字符串操作可以通过将 A 的内容副本附加到 B 上，并用 B 的内容的两个副本替换 A 的内容来描述。这些字符串在方块处迭代，迭代式表示为[math]A\rightarrow BB[/math] 和[math] B\rightarrow BA[/math]。例如图（c）中从起始点-2-4-7-13这条链路，起始字符是1，可以用B描述，在4-7处发生变化，用B'描述，在7处产生了新的类型，B中字符变为10，在这里B'就是11，依此类推，就得到了图（c）。显然（c）的描述方式比（a）的方式更加节省计算资源，它的描述能力也更强。 − − == 与相关研究的比较 == − ===计算力学与因果涌现=== − ====概念对比==== − 计算力学的许多概念上都可以在[[因果涌现]]理论框架下找到对应，通过进行两者之间的对应和比较，我们可以拓展对涌现的理解和研究。 − {| class="wikitable" − |+<big>计算力学和因果涌现的概念对比</big> − !序号 − !计算力学概念 − !因果涌现概念 − !概念的比较 − |- − |1 − |观测序列<math>\overleftarrow{s}</math> − |微观态 − |它们都在状态空间上描述，是系统观测到的最原始的数据，计算力学中的观测序列可以是无限长度的，[[因果涌现]]理论中微观态背后的动力学假设是马尔可夫的。 − |- − |2 − |宏观态<math>\mathcal{R}_i \in \mathcal{R} </math> − |宏观态 − |它们都是对微观态的状态空间做划分而得到的，计算力学中的宏观态<math>\mathcal{R}_i \in \mathcal{R} </math>是直接定义为对历史序列做划分的函数，因果涌现的宏观态则是某一个微观态的分组。 − |- − |3 − |划分映射<math>\eta </math> − |粗粒化策略 − |它们都是定义在微观态的状态空间到宏观态的状态空间（即对微观态的划分）的一个映射，而因果涌现中的粗粒化策略既包括微观态与宏观态的映射关系，也包括对动力学进行归并的方法。 − |- − |4 − |因果态划分<math>\epsilon</math> − |最大化有效信息的粗粒化策略 − |它们都是理论上的最佳信息压缩方法，因果态的映射函数<math>\epsilon</math>是根据预测等价性定义的，不损失微观上的信息；而最大化有效信息的粗粒化策略可能因为损失过多微观的信息得到平凡解。 − |- − |5 − |转移映射<math>T</math> − |最大化EI的宏观动力学 − |有了粗粒化策略自然有一个对应的宏观动力学。 − |- − |6 − |统计复杂度<math>C_{\mu}</math> − |[[有效信息]]EI − |如果将宏观动力学视作一个图灵机模型，那么统计复杂度和有效信息EI都可以看作是对这种模型复杂度的一种度量，且有效信息越大的时候，模型复杂度越低。这一点会在我们考虑到EI与[[动力学可逆性]]的等价性的时候更清楚，这是因为[[动力学可逆性]]是对宏观动力学时间反演对称性的衡量，而对称性是可以降低模型复杂度的。 − |- − |} − − − ====斑图重构机器与NIS系列的对比==== − 计算力学中的斑图重构机器（ϵ-machine）和识别因果涌现的[[NIS]]和[[NIS+|NIS+]]都可以理解为是智能体观察外部世界的内部模型。斑图重构机器通过重构算法得到理想的划分和因果态的过程，与NIS或NIS+通过最大化宏观动力学的[[有效信息]]（Effective information，EI）得到最佳粗粒化策略与涌现的宏观动力学的过程是类似的。可以说，NIS或NIS+就是一个通过神经网络、机器学习技术实现的斑图重构机器（ϵ-machine）。 − − 二者的等价可以体现在两方面：一方面我们希望重构的模型应该足够简洁（因果态具有最小随机性，NIS+中最大化宏观的EI）；另一方面则希望宏观模型仍保留微观态变化的重要信息，有能力预测未来的微观态。 − − 计算力学中，因果态的定义保证了它对微观态具有最大预测性，而香农熵率便可以衡量该预测误差的大小。在NIS或NIS+中，有效信息的最大化保证了模型的简洁性，而微观态预测误差的约束则体现了模型准确性的要求。 − − 另外，我们在前文讨论了统计复杂度关于熵率的变化曲线，该图说明，涌现发生在随机性程度中等的情形下。而在NIS+的框架中，我们用机器的重构预测误差来约束模型，要求其在保证对微观预测尽可能准确（误差低于一定阈值）的前提下，最大化宏观的EI。此时，我们也可以计算宏微观的EI以及它们的差值来判断是否发生因果涌现。如下图所示，最高强度的因果涌现也发生在观测噪音处于中等强度时。 − − [[文件:计算力学 nis+.png|居中|800x800像素|替代=|无框]] − − 上图中，左图是前文中出现过的示意图。它描述了统计复杂度与数据随机性之间的关系，其中随机性通过香农熵率来度量（见前文中的实验部分）。当随机性处于中等强度时，统计复杂度出现峰值。右图来自NIS+应用在SIR（病毒感染动力学）为模型的生成数据上的实验。其中横轴<math>\sigma </math>为该数据中观测噪音的强度，纵轴为因果涌现强度<math>\Delta\mathcal{J} </math>。详情可参考词条[[NIS+|NIS+]]。 − − 右图中，<math>\Delta\mathcal{J} </math>在<math>\sigma=10^{-2} </math>处达到峰值，这与作者模拟中使用的时间步长（<math>dt=0.01 </math>）的大小相对应，是噪音与信号比例相同的情形。对比左右两张图，NIS+所识别的因果涌现强度与统计复杂度有着相似的变化趋势和性质。 − − ===计算力学与马尔科夫链的成块性理论=== − − [[马尔科夫链]]是计算力学的一类特殊情形，即当未来状态仅依赖于上一步历史的情形。在马尔科夫链中，人们很早就开始讨论[[马尔科夫链的成块性]]（lumpability），所谓的[[成块性]]是一种描述马尔科夫链的状态是否可聚类并约简的性质。判断一个马尔科夫链上的划分是否是成块的（lumpable），是看它的马尔科夫状态转移矩阵<math>P</math>中的元素经过划分能不能结成一个个小方块（也就是按照聚类对马尔科夫链进行粗粒化表示）。具体来说，对于成块的马尔科夫链来说，我们可以把<math>N</math>个微观状态划分成<math>M < N</math>个宏观状态，在这个划分过程中，我们能定义微观状态<math>s_1</math>到宏观状态<math>A_1</math>的转移概率就等于<math>s_1</math>到<math>A_1</math>中的各个微观状态的转移概率的加和。我们会发现，在成块的马尔科夫链中，宏观状态中的每一个微观状态转移到另一个宏观状态的转移概率都是一样的。这样会使得马尔科夫状态转移概率矩阵<math>P</math>这个方阵中，出现一个个方块，所以称之为成块性。 − − 判断一个马尔科夫链对'''给定划分 <math>A</math>''' 是否成块的充分必要条件为：对于<math>\forall i, j</math>为两个分组的下标, 那么对于任意两个分组<math>A_i</math>中的微观态：<math>\forall s_k, s_m \in A_i</math>，都必须满足： − − <math> p(s \in A_j | s_k) = p(s \in A_j | s_m)</math>， − − 其中，<math>p(s \in A_j | s_k) = \sum_{s_q \in A_j} p( s_q | s_k)</math> − − 另一方面，在讨论因果态的时候，我们也有类似的条件。对于某个划分得到的宏观态集合<math>\mathcal R</math>，其为因果态的充要条件是：对于任意的宏观态<math> \mathcal R_i</math>，对于任意的<math>\forall i, \forall \overleftarrow{s_t},\overleftarrow{s_{t^{'}}} \in \mathcal R_i</math>，有： − − <math>p(\overrightarrow{s}|\overleftarrow{s_t})=p(\overrightarrow{s} |\overleftarrow{s_{t^{'}}}) </math>， − − 其中<math>\mathcal R_i \in \mathcal R</math>。 − − − 如果将马尔科夫链的状态分组就看作是因果态理论中的粗粒化划分，那么成块性的要求和因果态的要求非常相似，它们都给出了一种对未来状态做预测的等价性。但是，二者又有区别，区别有以下三点： − − '''1. 马尔可夫性假设''' − − 因果态并没有马尔科夫性的假设，但我们总可以把一个序列看成是一个状态，于是就能得到序列映射到序列的马尔科夫转移矩阵。在该概率转移矩阵上，我们可以比较因果态对应的划分映射和满足成块性的划分。 − − '''2. 微观和宏观最大预测性''' − − 上文提到，因果态的状态划分方式能保持微观层面上的最大预测性。也就是说，我们根据微观状态找到对应的因果态之后，即使我们不知道原本的微观状态了，我们还是能准确的得到未来的'''微观'''状态的分布。 − − 而成块性与其不同的是，我们根据微观状态找到对应的宏观状态之后，能够准确的得到未来的'''宏观'''状态的分布。但是在粗粒化过程中，我们会丢失微观状态的辨别信息，而这个信息的损失是不可逆的。所以，我们就无法从宏观状态再还原到微观状态了。 − − 所以，因果态同时保持了微观和宏观的最大预测性，而成块性只能保持宏观的最大预测性。 − − '''3. 因果态比成块性更严格，划分的成块性是满足因果态要求的必要条件''' − − 按照上面的叙述，我们会发现，因果态是比成块性更严格的限制，因为它要求在状态转移矩阵中，属于同一个因果态中的状态的行必须完全一致。 − − 因果态的划分一定是一种成块的状态划分，但反之则不一定。所以说，划分的成块性是满足因果态要求的必要不充分条件。 − − − 二者之间的区别也可以用下图进行直观表示： − − [[文件:因果态成块性.png|居中|700像素|因果态与成块性的对比]] − − 该图展示了我们是怎么处理和理解因果态和成块性的。首先，我们把每条序列看作是一个状态，把序列压缩到了一个<math>t</math>时刻的状态空间，并用一个转移矩阵来描述状态（序列）之间的转移概率。 − − 在因果态中，我们只需要对比转移矩阵的行，把相同的行划分成一组；而在成块性中，我们需要同时考虑矩阵的行与列，通过比较每一行到某几列的转移概率来做分组。 − − ===斑图重构机器与世界模型=== − − 计算力学中的斑图重构机器关心智能体是如何从观测到的时间序列数据中自动地发现因果态，并构建内在的环境模型的，这一点与强化学习领域中的世界模型（也被称为以及模型的强化学习）的想法不谋而合。 − − 强化学习所解决的问题通常可以建模为马尔可夫决策过程（Markov Decision Process，缩写MDP），形式上可表示为<math>(S,A,T,R,\gamma)</math>,其中集合<math>S</math>为状态空间包含所有可能的状态，每个状态<math>s\in S</math>描述了系统在某一时刻的情形。集合<math>A</math>为动作空间，包含所有的动作。<math>T</math>为状态转移概率，<math>T(s'|s,a)</math>表示在状态<math>s</math>下执行动作<math>a</math>转移到<math>s'</math>的概率。奖励函数<math>R(s,a)</math>定义了在状态<math>s</math>采取动作<math>a</math>后获得的即时奖励，折现因子<math>\gamma</math>是一个在 [0, 1] 之间的数，用于折扣未来奖励的影响。当智能体的观测<math>o</math>等于系统状态<math>s</math>时，对应一般的马尔可夫决策过程，当智能体无法直接观测到系统完整的状态时，问题可以描述为部分可观测马尔可夫决策过程（Partially Observable Markov Decision Process，缩写POMDP），POMDP可以描述为一个7元组<math>(S,A,T,R,\Omega,O,\gamma)</math>，<math>\Omega</math>表示观测空间，智能体的观测<math>o \in \Omega</math>，概率为<math>O(o|s',a)</math>。 − − 在强化学习世界模型中，智能体根据和真实环境互动过程所产生的数据训练一个内嵌的世界模型，世界模型作为对真实环境的替代，从而可以通过和世界模型互动学习行动策略，减少和真实环境的互动。对于观测不包含完整的状态信息的POMDP问题，以及观测维度过高导致难以准确建模的MDP问题，人们通常让Agent去学习一个状态的粗粒化表征，这种方式可以帮助算法提升学习效率和任务表现。这种粗粒化表征就是所谓的“世界模型”。 − − 因此，强化学习的世界模型往往需要学习一个低维的隐状态动力学。隐状态的世界模型可以表示为<math>T(z'|z,a)</math>，其中<math>z</math>表示粗粒化之后的隐状态（或者宏观状态），这一点和计算力学中的因果态，以及因果态的转移概率具有一定的相似之处。 − − 世界模型与计算力学中斑图重构机器存在几点差异： − − 1. 强化学习世界模型中的状态转移包含动作，而在斑图重构机器中建模因果态的转移，不涉及智能体动作的建模。 − − 2. 在世界模型的学习中，宏观状态粗粒化的另一个需要考虑的点是状态转移和粗粒化的可交换性，也就是从<math>s</math>粗粒化的表示<math>z</math>经过宏观动力学（世界模型）转移到下一时刻的宏观状态分布<math>P_1(z')</math>，应该尽可能接近从<math>s</math>经过微观动力学（未做表征学习）转移到<math>s'</math>，然后再构建表征<math>z'</math>，从而得到的宏观状态分布<math>P_2(z')</math>，也就是<math>P_1(z)\approx P_2(z')</math>。而斑图重构机器中状态的粗粒化不涉及这一问题的讨论。 − − ==参考文献== − <references /> − − ==编者推荐== − − *[https://pattern.swarma.org/study_group_issue/259 因果涌现第二季：13.计算力学：模式、预测、结构与简洁性] − *[https://pattern.swarma.org/study_group_issue/532 因果涌现第三季：5.计算力学：量化涌现的另一条路径]
无编辑摘要
每个[math]\displaystyle{ \mathcal{S} }[/math]都对应一个<math>\epsilon</math>映射，它和<math>T</math>函数一起组成一个有序对<math>\left \{ \epsilon,T \right \}</math>，这就是“斑图重构机器”（ϵ-machine）。后文“模型的重构”一节中会详细介绍如何获得这个斑图重构机器，以及智能体的内在模型会如何根据观测到的新数据，动态更新<math>\epsilon</math>映射和<math>T</math>函数。
每个[math]\displaystyle{ \mathcal{S} }[/math]都对应一个<math>\epsilon</math>映射，它和<math>T</math>函数一起组成一个有序对<math>\left \{ \epsilon,T \right \}</math>，这就是“斑图重构机器”（ϵ-machine）。后文“模型的重构”一节中会详细介绍如何获得这个斑图重构机器，以及智能体的内在模型会如何根据观测到的新数据，动态更新<math>\epsilon</math>映射和<math>T</math>函数。