812
个编辑
更改
跳到导航
跳到搜索
第42行：
第42行： − ====对状态空间进行粗粒化====+ 第54行：
第54行： − ====对转移概率进行粗粒化====+ 第88行：
第88行： − + − + + + + + + + + + + + + + + + + + 第100行：
第116行： − + + + + + + + + + + + + + − 而且，这只是最简单，最基本的对马尔科夫链的粗粒化，我们下面会介绍不同的指标，在上述的两个规则之上添加更多的规则会得出基于这些指标的粗粒化的方法。+ + + 第118行：
第148行： − + 第229行：
第259行： − + − + 第243行：
第273行： − + − − [[文件:马尔科夫链的粗粒化定义.png|替代=|缩略图|图3：粗粒化图例]] − − 图（3）展示了从某个微观状态<math>s^{(t)}</math>出发，到达下一刻的宏观状态<math>A^{(t+1)}</math>的两条路径<ref name=":7">Coarse graining. ''Encyclopedia of Mathematics.'' URL: <nowiki>http://encyclopediaofmath.org/index.php?title=Coarse_graining&oldid=16170</nowiki></ref>： − #先经过微观动力学达到<math>s^{(t+1)}</math>，再进行粗粒化得到<math>A^{(t+1)}</math> − #先进行粗粒化得到<math>A^{(t)}</math>，再经过宏观动力学到达<math>A^{(t+1)}</math> − 证明如下：+ − − 对于一个成块的<math>P</math>，和它的成块划分<math>\Phi</math>，我们针对<math>\Phi = \left ( \begin{array}{cc} 1 & 0 \\ 0 & 1 \\ 0 & 1 \\ 0 & 1 \end{array} \right )</math>的例子，其他情况类似。 − − 对于这个<math>\Phi</math>，我们知道<math>P_{11}=A_{11}</math>，<math>P_{12}+P_{13}+P_{14}=A_{12}</math>，<math>P_{21}=P_{31}=P_{41}=A_{21}</math>，<math>P_{22}+P_{23}+P_{24}=P_{32}+P_{33}+P_{34}=P_{42}+P_{43}+P_{44}=A_{22}</math>。 − − 由于<math>A_{21}</math>和<math>A_{22}</math>的等于关系，<math>P \Phi = \left ( \begin{array}{cc} P_{11}' & P_{12}' \\ P_{21}' & P_{22}' \\ P_{21}' & P_{22}' \\ P_{21}' & P_{22}' \end{array} \right )</math>。这相当于将<math>P</math>的每一行按照划分进行加总，而<math>P \Phi</math>中同一组的行是相同的。 − − 另一方面，<math>\Phi P'</math>的含义是将<math>P'</math>的每一行按照<math>\Phi</math>复制到对应的微观状态的行中。所以，我们会发现<math>\Phi P'</math>和<math>P \Phi</math>的结果是一样的。 − − − − ===一致性Consistency=== − 这一小节里讨论马尔科夫链的成块划分 与 HOM（Higher-order Macronodes，详情请参考[[复杂网络中的因果涌现]]）之间的关系，以及它们与一致性的联系。 − 以下关于[[动力学的一致性检验]]的描述节选自[[复杂网络中的因果涌现]]： − 定义微观网络<math>G </math>与宏观网络<math>G_M </math>，分别在两个网络上进行[[随机游走]]。在某个时间<math>t</math>，<math>G</math>上的预期分布为<math>P_m(t)</math>，而<math>G_M </math>上的预期分布为 <math>P_M(t)</math>。+ − − 将<math>P_m(t) </math>分布叠加到宏观宏观<math>G_M </math>的相同节点上，得到<math>P_{M|m}(t) </math>分布。通过计算<math>P_M(t) </math>和<math>P_{M|m}(t) </math>之间的KL散度来衡量其不一致性（inconsistency）。如果结果为零，则表示动力学一致。公式如下： − − <math>inconsistency=\sum_{t=0}^T D_{KL}[P_M(t)||P_{M|m}(t)]</math> − − 也就是说，不一致性 表示了 宏观和微观网络节点在不同时刻的概率分布的[[KL散度]]之和。
无编辑摘要
本词条只讨论离散时间马尔科夫链，且动力学（<math>P</math>）不随时间变化的情况，不讨论连续马尔科夫过程。我们可以定义微观状态空间为<math>S=\{s_1, s_2, ... ,s_n\}</math>，微观转移函数<math>P \in \mathcal{R}_{n \times n}</math>是一个大小为n的马尔科夫矩阵。同样的，粗粒化后的宏观状态空间为<math>S'=\{s'_1, s'_2, ... ,s'_r\}</math>，宏观转移函数<math>P' \in \mathcal{R}_{r \times r}</math>。
本词条只讨论离散时间马尔科夫链，且动力学（<math>P</math>）不随时间变化的情况，不讨论连续马尔科夫过程。我们可以定义微观状态空间为<math>S=\{s_1, s_2, ... ,s_n\}</math>，微观转移函数<math>P \in \mathcal{R}_{n \times n}</math>是一个大小为n的马尔科夫矩阵。同样的，粗粒化后的宏观状态空间为<math>S'=\{s'_1, s'_2, ... ,s'_r\}</math>，宏观转移函数<math>P' \in \mathcal{R}_{r \times r}</math>。
===对状态空间进行粗粒化===
我们假设投影函数<math>\Phi</math>是一个<math>n \times r</math>的线性投影矩阵，且符合下列两个条件(1)所有元素非负(2)每行加和等于1。
我们假设投影函数<math>\Phi</math>是一个<math>n \times r</math>的线性投影矩阵，且符合下列两个条件(1)所有元素非负(2)每行加和等于1。
===对转移概率进行粗粒化===
得出<math>\Phi</math>后，对微观马尔科夫矩阵<math>P</math>的降维可以表示为
得出<math>\Phi</math>后，对微观马尔科夫矩阵<math>P</math>的降维可以表示为
==判断粗粒化方案符合的性质==
===判断粗粒化方案符合的性质===
最基本的粗粒化方法的约束是要确保粗粒化后的新的<math>S'</math>和<math>T'</math>要符合马尔科夫链定义。除此之外也有一些其他的规则，比如：
最基本的粗粒化方法的约束是要确保粗粒化后的新的<math>S'</math>和<math>T'</math>要符合马尔科夫链定义。除此之外也有一些其他的规则，比如：
===粗粒化的交换律commutative<ref name=":2" />===
====宏观最大预测性====
宏观最大预测性是指，在将微观状态粗粒化为宏观状态后，我们只用宏观状态就能预测后续的'''宏观'''状态。
具体来说，只需要知道宏观状态<math>A^{(t)}</math>，就可以最大化<math>A^{(t+1)}</math>的预测效果，而微观状态<math>s^{(t+1)}</math>虽然能提供一些额外信息，但是对于预测<math>A^{(t+1)}</math>并无帮助。这意味着条件互信息<math>I(A^{(t+1)}; s^{(t+1)} | A^{(t)}) = 0</math>。宏观动力学不需要任何来自微观状态的修正，就能独立且正确地反映系统在宏观层面上的演化。
<br/>
====微观最大预测性====
微观最大预测性是指，在将微观状态粗粒化为宏观状态后，我们只用宏观状态就能预测'''后续'''的微观状态。
具体来说，只需要知道宏观状态<math>A^{(t)}</math>，就可以最大化<math>s^{(t+1)}</math>的预测效果。
<br/>
====粗粒化的交换律commutative<ref name=":2" />====
图（1）展示了从某个微观状态<math>s^{(t)}</math>出发，到达下一刻的宏观状态<math>A^{(t+1)}</math>的两条路径<ref name=":7">Coarse graining. ''Encyclopedia of Mathematics.'' URL: <nowiki>http://encyclopediaofmath.org/index.php?title=Coarse_graining&oldid=16170</nowiki></ref>：
图（1）展示了从某个微观状态<math>s^{(t)}</math>出发，到达下一刻的宏观状态<math>A^{(t+1)}</math>的两条路径<ref name=":7">Coarse graining. ''Encyclopedia of Mathematics.'' URL: <nowiki>http://encyclopediaofmath.org/index.php?title=Coarse_graining&oldid=16170</nowiki></ref>：
如果我们把粗粒化和（宏观/微观）动力学看作是两个算子，那这两个算子的可交换性指的是：无论从哪个微观状态分布出发，走这两条路径得到的<math>A^{(t+1)}</math>的分布是一样的，即，'''<math>s^{(t)} \Phi P' = s^{(t)} P \Phi</math>'''。
如果我们把粗粒化和（宏观/微观）动力学看作是两个算子，那这两个算子的可交换性指的是：无论从哪个微观状态分布出发，走这两条路径得到的<math>A^{(t+1)}</math>的分布是一样的，即，'''<math>s^{(t)} \Phi P' = s^{(t)} P \Phi</math>'''。
===动力学一致性<ref name=":2" />===
<br/>
====动力学一致性<ref name=":2" />====
好的粗粒化方案是能够尽可能保证原始的网络（或转移矩阵）和粗粒化后的网络（或转移矩阵）尽可能地相似，动力学一致性衡量了在原始网络和粗粒化后网络上演化的状态的轨迹的一致性。详情请见[[复杂网络中的因果涌现]]词条。
好的粗粒化方案是能够尽可能保证原始的网络（或转移矩阵）和粗粒化后的网络（或转移矩阵）尽可能地相似，动力学一致性衡量了在原始网络和粗粒化后网络上演化的状态的轨迹的一致性。详情请见[[复杂网络中的因果涌现]]词条。
以下关于[[动力学的一致性检验]]的描述节选自[[复杂网络中的因果涌现]]：
定义微观网络<math>G </math>与宏观网络<math>G_M </math>，分别在两个网络上进行[[随机游走]]。在某个时间<math>t</math>，<math>G</math>上的预期分布为<math>P_m(t)</math>，而<math>G_M </math>上的预期分布为 <math>P_M(t)</math>。
将<math>P_m(t) </math>分布叠加到宏观宏观<math>G_M </math>的相同节点上，得到<math>P_{M|m}(t) </math>分布。通过计算<math>P_M(t) </math>和<math>P_{M|m}(t) </math>之间的KL散度来衡量其不一致性（inconsistency）。如果结果为零，则表示动力学一致。公式如下：
<math>inconsistency=\sum_{t=0}^T D_{KL}[P_M(t)||P_{M|m}(t)]</math>
也就是说，不一致性 表示了 宏观和微观网络节点在不同时刻的概率分布的[[KL散度]]之和。
<br/>
注意，这是我们从不同来源<ref name=":2" />中总结出来的规则。目前我们还没找到一个严格的完备的马尔科夫粗粒化应该符合的定义。
注意，这是我们从不同来源<ref name=":2" />中总结出来的规则。目前我们还没找到一个严格的完备的马尔科夫粗粒化应该符合的定义。
而且，这只是最简单，最基本的对马尔科夫链的粗粒化，我们下面会介绍不同的概念，它们分别满足上述的不同指标。
=成块性=
=成块性=
成块性的初始定义比较复杂，详见[[马尔科夫链的成块性]]。在此词条中，我们介绍其定义的充分必要条件，一个更直观的解析。在某些文献中，作者们会直接使用这个通俗版的解释，而且这两者之间是存在充分必要条件关系的<ref name=":1" />。
成块性的初始定义比较复杂，详见[[马尔科夫链的成块性]]。在此词条中，我们介绍其定义的充分必要条件，一个更直观的解析。在某些文献中，作者们会直接使用这个通俗版的解释，而且这两者之间是存在充分必要条件关系的<ref name=":1" />。
==成块性的充分必要条件==
===成块性的充分必要条件===
设<math>p_{s_k \rightarrow s_m} = p(s^{(t)} = s_m | s^{(t-1)} = s_k)</math>，<math>p_{s_k \rightarrow A_i} = p(s^{(t)} \in A_i | s^{(t-1)} = s_k) = \sum_{s_m \in A_i} p_{s_k \rightarrow s_m}</math>，<math>p_{A_i \rightarrow A_j} = p(A^{(t)} = A_j | A^{(t-1)} = A_i)</math>，作者<ref name=":1" />提出了判断一个马尔科夫链对'''给定划分 <math>A</math>''' 是否成块的充分必要条件为：
设<math>p_{s_k \rightarrow s_m} = p(s^{(t)} = s_m | s^{(t-1)} = s_k)</math>，<math>p_{s_k \rightarrow A_i} = p(s^{(t)} \in A_i | s^{(t-1)} = s_k) = \sum_{s_m \in A_i} p_{s_k \rightarrow s_m}</math>，<math>p_{A_i \rightarrow A_j} = p(A^{(t)} = A_j | A^{(t-1)} = A_i)</math>，作者<ref name=":1" />提出了判断一个马尔科夫链对'''给定划分 <math>A</math>''' 是否成块的充分必要条件为：
==成块性满足的性质==
===成块性满足的性质===
成块性作为一种较为严格的划分方式，虽然在压缩维度上可能不如其他方法显著，但它能够保留在宏观层面上所有有用的信息，并且确保粗粒化前后过程的一致性。
成块性作为一种较为严格的划分方式，虽然在压缩维度上可能不如其他方法显著，但它能够保留在宏观层面上所有有用的信息，并且确保粗粒化前后过程的一致性。
===宏观最大预测性===
====宏观最大预测性====
宏观最大预测性是指，在将微观状态粗粒化为宏观状态后，我们就不再需要微观状态，只用宏观状态就能预测后续的宏观状态。
宏观最大预测性是指，在将微观状态粗粒化为宏观状态后，我们就不再需要微观状态，只用宏观状态就能预测后续的宏观状态。
===成块划分和粗粒化的可交换性===
====成块划分和粗粒化的可交换性====
如果我们把粗粒化和（宏观/微观）动力学看作是两个算子，那这两个算子的可交换性指的是：无论从哪个微观状态分布出发，走这两条路径得到的<math>A^{(t+1)}</math>的分布是一样的，即，'''<math>s^{(t)} \Phi P' = s^{(t)} P \Phi</math>'''。
如果我们把粗粒化和（宏观/微观）动力学看作是两个算子，那这两个算子的可交换性指的是：无论从哪个微观状态分布出发，走这两条路径得到的<math>A^{(t+1)}</math>的分布是一样的，即，'''<math>s^{(t)} \Phi P' = s^{(t)} P \Phi</math>'''。
我们在[[马尔科夫链的成块性]]中推导了结论：'''基于成块性划分的粗粒化方法满足粗粒化和动力学这两个算子的可交换性。'''
====一致性Consistency====
我们在[[马尔科夫链的成块性]]中推导了结论：'''基于成块性划分的粗粒化方法构建的宏观网络与微观网络是一致的。'''
我们在[[马尔科夫链的成块性]]中推导了结论：'''基于成块性划分的粗粒化方法构建的宏观网络与微观网络是一致的。'''