812
个编辑
更改
跳到导航
跳到搜索
第42行：
第42行： − − 第52行：
第50行： + + 第84行：
第84行： + + 第89行：
第91行： + − + + + 第97行：
第102行： − 因此，根据目前有迹可循的对马尔科夫链的粗粒化的定义来说，我们要求一个良定义的粗粒化方法上述提到过的两个规则：+ − #粗粒化后的<math>S'</math>和<math>T'</math>要符合马尔科夫链定义。+ − #满足交换律 − 但是注意，这是我们从不同来源<ref name=":2" />中总结出来的规则。目前我们还没找到一个严格的完备的定义。 − 而且，这只是最简单，最基本的对马尔科夫链的粗粒化，我们下面会介绍不同的指标，在上述的两个规则之上添加更多的规则会得出基于这些指标的粗粒化的方法。 + − + − 在这个词条里，我们主要讨论Hard partitioning，主要参考的是<ref name=":0">Zhang, Anru, and Mengdi Wang. "Spectral state compression of markov processes." ''IEEE transactions on information theory'' 66.5 (2019): 3202-3231.</ref><ref name=":3" />，对Soft state aggregation感兴趣的朋友可以自行参阅S. P. Singh, T. Jaakkola, and M. I. Jordan, “Reinforcement learning with soft state aggregation"<ref>Singh, Satinder, Tommi Jaakkola, and Michael Jordan. "Reinforcement learning with soft state aggregation." ''Advances in neural information processing systems'' 7 (1994).</ref>和Duan, Yaqi, Tracy Ke, and Mengdi Wang. "State aggregation learning from markov transition data." ''Advances in Neural Information Processing Systems'' 32 (2019).<ref>Duan, Yaqi, Tracy Ke, and Mengdi Wang. "State aggregation learning from markov transition data." ''Advances in Neural Information Processing Systems'' 32 (2019).</ref>
→粗粒化
本词条只讨论离散时间马尔科夫链，且动力学（<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_{i, j} = 1\ if\ s_i \in s_j'\ and\ 0\ otherwise</math><ref name=":1" />，即一个表示<math>i</math>属于<math>j</math>列的零一分组矩阵。如果是软划分的话，<math>\Phi</math>则不一定会是零一矩阵。
在硬划分的情况下，<math>\Phi_{i, j} = 1\ if\ s_i \in s_j'\ and\ 0\ otherwise</math><ref name=":1" />，即一个表示<math>i</math>属于<math>j</math>列的零一分组矩阵。如果是软划分的话，<math>\Phi</math>则不一定会是零一矩阵。
在这个词条里，我们主要讨论Hard partitioning，主要参考的是<ref name=":0">Zhang, Anru, and Mengdi Wang. "Spectral state compression of markov processes." ''IEEE transactions on information theory'' 66.5 (2019): 3202-3231.</ref><ref name=":3" />，对Soft state aggregation感兴趣的朋友可以自行参阅S. P. Singh, T. Jaakkola, and M. I. Jordan, “Reinforcement learning with soft state aggregation"<ref>Singh, Satinder, Tommi Jaakkola, and Michael Jordan. "Reinforcement learning with soft state aggregation." ''Advances in neural information processing systems'' 7 (1994).</ref>和Duan, Yaqi, Tracy Ke, and Mengdi Wang. "State aggregation learning from markov transition data." ''Advances in Neural Information Processing Systems'' 32 (2019).<ref>Duan, Yaqi, Tracy Ke, and Mengdi Wang. "State aggregation learning from markov transition data." ''Advances in Neural Information Processing Systems'' 32 (2019).</ref>
所以，我们能看到，对马尔科夫链做粗粒化的时候，不仅要对状态空间做降维(<math>\Phi</math>)，还要对马尔科夫矩阵都要做降维，当中也包含了对概率空间的降维(<math>W</math>)。
所以，我们能看到，对马尔科夫链做粗粒化的时候，不仅要对状态空间做降维(<math>\Phi</math>)，还要对马尔科夫矩阵都要做降维，当中也包含了对概率空间的降维(<math>W</math>)。
<math>W</math>
式子{{EquationRef|1}}中我们发现，<math>\Phi</math>和<math>P</math>都是给定的，所以我们在这一步要做的是决定<math>W</math>。<math>W</math>的基础限制是要使得<math>P'</math>符合马尔科夫矩阵定义，所以有无限多种<math>W</math>的选项。从这些选项中，我们也能挑出某些符合我们想要的特征的<math>W</math>。
====判断粗粒化方案符合的性质====
====判断粗粒化方案符合的性质====
最基本的粗粒化方法的约束是要确保粗粒化后的新的<math>S'</math>和<math>T'</math>要符合马尔科夫链定义。除此之外也有一些其他的规则，比如：
粗粒化的交换律commutative<ref name=":2" />。按照上面的定义，<math>s^{(t)}</math>有两个路径能达到<math>s'^{(t+1)}</math>：
=====粗粒化的交换律commutative<ref name=":2" />=====
按照上面的定义，<math>s^{(t)}</math>有两个路径能达到<math>s'^{(t+1)}</math>：
#先得到下一步的<math>s^{(t+1)} = s^{(t)} P</math>，再做粗粒化得到<math>s'^{(t+1)} = s^{(t+1)} \Phi </math>
#先得到下一步的<math>s^{(t+1)} = s^{(t)} P</math>，再做粗粒化得到<math>s'^{(t+1)} = s^{(t+1)} \Phi </math>
而交换律则要求从这两条路径得到的结果应该是一样的，即<math> s_{t} P \Phi = s_{t} \Phi P'</math>。
而交换律则要求从这两条路径得到的结果应该是一样的，即<math> s_{t} P \Phi = s_{t} \Phi P'</math>。
=====动力学一致性<ref name=":2" />=====
好的粗粒化方案是能够尽可能保证原始的网络（或转移矩阵）和粗粒化后的网络（或转移矩阵）尽可能地相似，动力学一致性衡量了在原始网络和粗粒化后网络上演化的状态的轨迹的一致性。详情请见[[复杂网络中的因果涌现]]词条。
注意，这是我们从不同来源<ref name=":2" />中总结出来的规则。目前我们还没找到一个严格的完备的马尔科夫粗粒化应该符合的定义。
而且，这只是最简单，最基本的对马尔科夫链的粗粒化，我们下面会介绍不同的指标，在上述的两个规则之上添加更多的规则会得出基于这些指标的粗粒化的方法。
=Lumpability=
=Lumpability=