集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织

更改

马尔科夫链的粗粒化 (查看源代码)

2026年5月21日 (四) 20:57的版本

删除2,268字节 、 2026年5月21日 (星期四)
无编辑摘要
第222行： 第222行：  
===定义===
 
===定义===
   −
在[[计算力学]]中，状态被理解为智能体接收到的全部历史信息，因此系统从过去到未来的变化被描述为一个离散的平稳[[随机过程]]。状态空间为双（向）无限序列的集合 <math>\overleftrightarrow{S}=\{\cdots, s_{-2}, s_{-1}, s_0, s_1, s_2, \cdots\}</math>，即无限长的时间序列。基于当前时刻 <math>t</math>，我们可以将 <math>\overleftrightarrow{S}</math> 分为单侧前向序列 <math>\overleftarrow{s_t}=\{\cdots, s_{t-3}, s_{t-2}, s_{t-1}\}</math> 和单侧后向序列 <math>\overrightarrow{s_t}=\{s_t, s_{t+1}, s_{t+2}, s_{t+3},\cdots\}</math> 两部分。所有可能的未来序列 <math>\overrightarrow{s_t}</math> 形成的集合记作 <math>\overrightarrow{S}</math>，所有可能的历史序列 <math>\overleftarrow{s_t}</math> 形成的集合记作 <math>\overleftarrow{S}</math>。
+
在[[计算力学]]中，因果态原本是针对一般平稳随机过程定义的。对于一般随机过程，当前时刻以前的全部历史 <math>\overleftarrow{s_t}</math> 都可能影响未来，因此因果态会把具有相同未来预测分布的历史归为一类：
   −
因果态是一种对系统状态的粗粒化描述，并不预设系统具有马尔科夫性。为了把因果态和马尔科夫链的粗粒化理论进行比较，可以定义马尔科夫链的因果态：假设系统是一个<math>K</math>阶的马尔科夫链（系统在<math>t</math>时刻的状态分布由前 K 个时刻的状态决定），则可将 <math>\overleftarrow{S}</math> 重新定义为 <math>S^K</math>。
+
<math>
 +
\overleftarrow{s_t}\sim \overleftarrow{s_{t'}}
 +
\quad \Longleftrightarrow \quad
 +
P(\overrightarrow{s_t}\mid \overleftarrow{s_t})
 +
=
 +
P(\overrightarrow{s_{t'}}\mid \overleftarrow{s_{t'}}).
 +
</math>
   −
[[文件:因果态的定义.jpg|缩略图|因果态示意图， t = 9 和 t = 13 为同一因果态 |400x400px|替代=]]
+
也就是说，若两段历史对未来序列给出的预测分布完全相同，它们就属于同一个因果态。因果态可以理解为一种“预测等价类”：它只保留预测未来所需的信息，而把对未来预测没有影响的历史差异压缩掉。由因果态及其转移结构构成的最小预测模型，通常称为 <math>\epsilon</math>-机器。
    +
对于一阶马尔科夫链，情况会大大简化。因为马尔科夫链满足
    +
<math>
 +
P(X_{t+1}\mid X_t,X_{t-1},\ldots)=P(X_{t+1}\mid X_t),
 +
</math>
   −
因果态这种宏观态划分方法，具有最强的预测能力。形式化定义如下：
+
所以预测未来不再需要完整历史，只需要当前状态。此时，因果态可以直接定义在微观状态上：若两个微观状态 <math>s_i</math> 和 <math>s_j</math> 对下一步状态给出的转移分布完全相同，则它们属于同一个因果态：
−
 
  −
对于任意时刻 <math>t</math> 和 <math>t^{'}</math>，若给定过去状态 <math>\overleftarrow{s_t}</math> 和 <math>\overleftarrow{s_{t^{'}}}</math> 时，未来状态 <math>\overrightarrow{s}</math> 的分布完全相同，则称 <math>\overleftarrow{s_t}</math> 与 <math>\overleftarrow{s_{t^{'}}}</math> '''等价'''，也叫'''预测等价性'''（predictive equivalence），记为：
     −
{{NumBlk|:|
   
<math>
 
<math>
−
t \sim t^{'} \equiv \overleftarrow{s_{t^{'}}} \sim \overleftarrow{s_t} \triangleq P(\overrightarrow{s}|\overleftarrow{s_t} ) = P(\overrightarrow{s} |\overleftarrow{s_{t^{'}}} )
+
s_i \sim s_j
 +
\quad \Longleftrightarrow \quad
 +
P(X_{t+1}=\cdot \mid X_t=s_i)
 +
=
 +
P(X_{t+1}=\cdot \mid X_t=s_j).
 
</math>
 
</math>
−
|{{EquationRef|4}}}}
      +
用转移矩阵 <math>P</math> 表示，就是 <math>P</math> 的第 <math>i</math> 行和第 <math>j</math> 行完全相同：
   −
 
+
<math>
−
[[计算力学]]认为，包括人类在内的智能体，每时每刻都在对周围环境观察，得到大量的观测数据，并在自己的内部（大脑中）构建简洁的机制来预测观测数据的变化（一种隐马尔科夫模型）。所以，引入了 ϵ-machine（ϵ-机器）的概念来描述这种机制。
+
s_i \sim s_j
−
 
+
\quad \Longleftrightarrow \quad
−
ϵ-机器根据当前时间步的状态和历史记忆，来预测未来状态。其工作机制是：根据 <math>\overleftarrow{s_t}</math> 而判断 <math>t</math> 时刻系统处于哪个因果态 <math>E_t</math> ，并根据该因果态预测未来轨迹 <math>\overrightarrow{s_t}</math>。
+
P_{i\cdot}=P_{j\cdot}.
−
 
  −
因果态可定义为ϵ-机器的映射 <math>\epsilon{:}\overleftarrow{S}\mapsto2^{\overleftarrow{S}}</math>，<math>E = \{E_t\}_{t \in \mathbb{N} }</math>，<math>E_t = \epsilon( \overleftarrow{s_t} )</math>，满足：<math>
  −
\epsilon(\stackrel{\leftarrow}{s})\equiv\{\stackrel{\leftarrow}{s}^{\prime}|\mathrm{P}(\overrightarrow{S}=\overrightarrow{s}\mid\stackrel{\leftarrow}{S}=\stackrel{\leftarrow}{s})=\mathrm{P}(\overrightarrow{S}=\overrightarrow{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>
   −
所有的'''因果态'''的集合由预测等价关系"[math]\sim[/math]"诱导的商集定义：[math]\mathcal{S}=\stackrel{\leftarrow}{S}/\sim[/math]
+
因此，在一阶马尔科夫链中，因果态划分就是把具有相同出转移分布的微观状态合并起来。它比成块性更严格：成块性只要求同组状态转移到各个宏观组的总概率相同，而因果态要求同组状态转移到每一个微观状态的概率都相同。换句话说，成块性保留的是宏观未来的预测能力，因果态保留的是微观未来的预测能力。
   −
如上图所示<ref name="crutchfield_1994">{{cite journal |last1=Crutchfield |first1=James P. |title=The Calculi of Emergence: Computation, Dynamics, and Induction |journal=Physica D: Nonlinear Phenomena |volume=75 |year=1994 |pages=11-54 |url=https://dl.acm.org/doi/10.1016/0167-2789%2894%2990273-9}}</ref>，<math>t_9</math> 和 <math>t_{13}</math> 时刻对未来状态的预测分布相同，处于同一因果态；<math>t_{11}</math>时刻预测分布不同，处于不同的因果态。
+
若考虑 <math>K</math> 阶马尔科夫链，也可以把长度为 <math>K</math> 的历史片段 <math>(X_{t-K+1},\ldots,X_t)</math> 当作新的状态。此时因果态仍然是预测等价类，只是等价关系定义在这些长度为 <math>K</math> 的历史状态上。一般计算力学中的无限历史定义，可以看作是这个思想在非有限阶随机过程中的推广。
    
<br/>
 
<br/>
    
===因果态的主要性质===
 
===因果态的主要性质===
−
为什么我们要关注因果态这样一种特定的宏观态？下面是因果态的两个主要性质，它们体现了因果态为何是一种理想的宏观态：
+
为什么我们要关注因果态这样一种特定的宏观态？对于马尔科夫链来说，因果态的意义可以概括为两点：最大预测性和最小随机性。
    
====微观最大预测性====
 
====微观最大预测性====
   −
微观最大预测性是指，在将微观状态粗粒化为宏观状态后，我们只用宏观状态就能预测'''后续'''的微观状态。
+
微观最大预测性是指，在将微观状态粗粒化为宏观状态后，因果态保留了预测下一步微观状态所需的全部信息。设 <math>C_t=\epsilon(X_t)</math> 表示当前微观状态所属的因果态，则有
   −
具体来说，只需要知道宏观状态 <math>A^{(t)}</math>，就可以最大化 <math>s^{(t+1)}</math> 的预测效果。
+
<math>
 +
P(X_{t+1}\mid X_t)=P(X_{t+1}\mid C_t).
 +
</math>
 +
 
 +
也就是说，只要知道当前因果态，就和知道当前微观状态一样，能够给出同样的下一步预测分布。对于任意其他粗粒化 <math>R_t=f(X_t)</math>，通常都有
 +
 
 +
<math>
 +
H(X_{t+1}\mid R_t)\geq H(X_{t+1}\mid C_t).
 +
</math>
   −
对于宏观态 <math>\mathcal{\forall 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>\mathcal{S}</math> 为因果态划分，所有可能的历史序列记作 <math>\overleftarrow{S}</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>\hat{\mathcal{R}}</math> 和 <math>\hat{\mathcal{R}}^{\prime}</math>，都有 <math>H[\hat{\mathcal{R}}^{\prime}|\hat{\mathcal{R}}]\geq H[\mathcal{S}^{\prime}|\mathcal{S}]</math>，其中 <math>\hat{\mathcal{R}}^{\prime}</math> 和 <math>\mathcal{S}^{\prime}</math> 分别是该过程的下一时刻状态和下一时刻因果态。
+
因果态不仅预测能力强，而且在保持这种预测能力的前提下尽可能简洁。它不会把预测未来所需的信息丢掉，也不会保留对预测没有帮助的多余微观差异。
   −
该性质可以被理解为在相同预测能力的前提下，因果态集合 [math]\displaystyle{ \mathcal{S} }[/math] 在所有的宏观态 [math]\displaystyle{ \mathcal{R} }[/math] 的集合中，随机性最小。
+
对于一阶马尔科夫链来说，如果两个状态的转移矩阵行完全相同，那么它们对未来的预测没有差别，应当被合并；如果两行不同，那么它们对下一步状态的预测不同，就不应属于同一个因果态。因此，因果态可以看作“在不损失微观预测能力的前提下，对状态空间做出的最小充分划分”。
−
 
  −
用[[互信息]]的角度去理解的话，上式等价于 <math>I(\mathcal{S}^{\prime};\mathcal{S})\geq I(\hat{\mathcal{R}}^{\prime};\hat{\mathcal{R}})</math>，可以理解为因果态为所有的与它自己的下一时刻的互信息中的最大的一个宏观态。
      
<br/>
 
<br/>
第595行： 第609行：     
从长期行为看，马尔科夫链中的状态可以先分成两类：'''滑过态（Transient）'''和'''常返态（Recurrent）'''。滑过态只是在过渡阶段被访问，离开后最终可能不再返回；常返态则会被反复访问。常返态进一步组成'''闭合常返类'''：同一类中的状态彼此可达，而且一旦进入该类就不会再离开。若一个常返类的返回步数存在公因子 <math>d>1</math>，它还可以继续分解为 <math>d</math> 个'''周期子类'''，系统按固定顺序在这些子类之间循环。
 
从长期行为看，马尔科夫链中的状态可以先分成两类：'''滑过态（Transient）'''和'''常返态（Recurrent）'''。滑过态只是在过渡阶段被访问，离开后最终可能不再返回；常返态则会被反复访问。常返态进一步组成'''闭合常返类'''：同一类中的状态彼此可达，而且一旦进入该类就不会再离开。若一个常返类的返回步数存在公因子 <math>d>1</math>，它还可以继续分解为 <math>d</math> 个'''周期子类'''，系统按固定顺序在这些子类之间循环。
 +
 +
===随机吸引子和对应分组===
    
在稳态或长时间视角下，随机吸引子给出的不是任意聚类，而是一种按照'''长期命运'''进行的自然划分：会进入同一个闭合常返类的状态、处在同一个周期相位中的状态，或者只承担过渡作用的滑过态，应该被区别对待。若这些集合被看作宏观态，我们就可以尝试构造宏观转移矩阵。这里需要区分两种情况。
 
在稳态或长时间视角下，随机吸引子给出的不是任意聚类，而是一种按照'''长期命运'''进行的自然划分：会进入同一个闭合常返类的状态、处在同一个周期相位中的状态，或者只承担过渡作用的滑过态，应该被区别对待。若这些集合被看作宏观态，我们就可以尝试构造宏观转移矩阵。这里需要区分两种情况。
第670行： 第686行：     
所以，随机动力学的意义不只是重新表述马尔科夫链，而是把'''长期命运相同的状态'''显式区分出来：常返类、周期类和滑过态之间的边界，本身就提供了一种值得优先尊重的粗粒化基准。详细的数学公式和证明可参考[[马尔科夫链中的随机动力学]]。
 
所以，随机动力学的意义不只是重新表述马尔科夫链，而是把'''长期命运相同的状态'''显式区分出来：常返类、周期类和滑过态之间的边界，本身就提供了一种值得优先尊重的粗粒化基准。详细的数学公式和证明可参考[[马尔科夫链中的随机动力学]]。
 +
 +
<br/>
    
==不同粗粒化方法之间的异同==
 
==不同粗粒化方法之间的异同==
Liangjh
812

个编辑

取自“https://wiki.swarma.org/index.php/特殊:移动版差异/50089”