225
个编辑
更改
→马尔科夫链的简化
===马尔科夫链的简化===
===马尔科夫链的简化===
除了对向量以及高维动力学的降维之外，[[马尔科夫链的简化]]（Lumping Markov Chain）也和因果涌现有着重要的联系。马尔可夫过程的模型约简<ref>Zhang A, Wang M. Spectral state compression of markov processes[J]. IEEE transactions on information theory, 2019, 66(5): 3202-3231.</ref>是状态转移系统建模中的一个重要问题。和因果涌现中的粗粒化相似，马尔科夫链的简化主要也是通过将多个状态合并成一个状态来降低马尔科夫链的复杂度。该过程主要是通过识别一些状态的组合，使得合并后的系统仍然保留马尔科夫性质。
除了对向量以及高维动力学的降维之外，[[马尔科夫链的简化]]（Lumping Markov Chain）也和因果涌现有着重要的联系。马尔可夫过程的模型约简<ref>Zhang A, Wang M. Spectral state compression of markov processes[J]. IEEE transactions on information theory, 2019, 66(5): 3202-3231.</ref>是状态转移系统建模中的一个重要问题。和因果涌现中的粗粒化相似，马尔科夫链的简化主要也是通过将多个状态合并成一个状态来降低马尔科夫链的复杂度。对马尔科夫链做粗粒化做粗粒化的意义是什么呢主要有三点，第一，我们在研究一个超大的系统的时候，比如复杂城市系统时，并不会关注每一个微观的状态的变化，在粗粒化中我们希望能过滤掉一些我们不感兴趣的噪声和异质性，而从中微观尺度中总结一些中尺度或宏观尺度的规律；第二，有些状态的转移概率非常相似，所以可以被看成同一类状态，对这种马尔科夫链做partitioning可以减少系统表示的冗余性；第三，在用到马尔科夫决策过程的强化学习里，对马尔科夫链做粗粒化可以减少状态空间的大小，提高训练效率。在许多文献中，粗粒化coarse-graining和降维dimension reduction是重叠等价的<ref>Coarse graining. ''Encyclopedia of Mathematics.'' URL: <nowiki>http://encyclopediaofmath.org/index.php?title=Coarse_graining&oldid=16170</nowiki></ref>。
'''给定一个state partition <math>A=\{A_1, A_2, ... ,A_r\}</math>'''，我们能够用下列公式描述一个粗粒化后的马尔科夫链(lumped process)，且这个转移概率对任何初始状态(starting vector) <math> \pi </math> 都是一样的：{{NumBlk|:|
<math>
\begin{aligned}
&Pr_{\pi}[f_0 \in A_i] \\
&Pr_{\pi}[f_1 \in A_j | f_0 \in A_i] \\
&Pr_{\pi}[f_n \in A_t |f_{n-1} \in A_s, f_1 \in A_j, f_0 \in A_i]
\end{aligned}
</math>
|{{EquationRef|3}}}}
作者提出了判断一个马尔科夫链对'''给定partition <math>A=\{A_1, A_2, ... ,A_r\}</math>''' 是否lumpable的充分必要条件为：
对于任意一对<math>A_i, A_j</math>，每一个属于<math>A_i</math>的状态<math>s_k</math>的<math>p_{kA_j}</math>都是一样的。
也就是说{{NumBlk|:|
<math>
\begin{aligned}
p_{s_k A_j} = \sum_{s_m \in A_j} p_{s_k s_m} = p_{A_i A_j}, k \in A_i
\end{aligned}
</math>
|{{EquationRef|4}}}}这个公式表达的是，群组<math>A_i</math>到群组<math>A_j</math>的转移概率 = 群组<math>A_i</math>中任意状态<math>s_k</math>到群组<math>A_j</math>的转移概率 = 群组<math>i</math>中任意状态<math>s_k</math>到群组<math>A_j</math>中的状态的转移概率的和。
可约简性（Lumpability）是一种对分类的衡量，这个概念最早出现在Kemeny, Snell在1969年的有限马尔科夫链（Finite Markov Chains）<ref name=":33">Kemeny, John G., and J. Laurie Snell. ''Finite markov chains''. Vol. 26. Princeton, NJ: van Nostrand, 1969. https://www.math.pku.edu.cn/teachers/yaoy/Fall2011/Kemeny-Snell_Chapter6.3-4.pdf</ref>中。马尔科夫链的粗粒化不仅要对状态空间做，也要对转移矩阵和概率空间做。这三个部分可以同时做，也可以看作为：先对状态空间做，再对转移矩阵和概率空间做；即先对状态做分组，然后再获取对应的粗粒化后的转移矩阵。我们也提到过对状态空间做粗粒化有硬分块（Hard Partitioning）和软分块（Soft Partitioning）两种。软分块可以看作把微观状态打散重构成了一些宏观状态，而硬分块则是更严格的，把若干个微观状态分成一个组。而可约简性（Lumpability）就是一个指标，用来评价‘对于某一种硬分块的微观状态分组分案，是否对微观状态转移矩阵可约简’。不管状态空间按照哪一个硬分块方案做分类，它都有对应后续的对转移矩阵和概率空间的粗粒化方案<ref>Buchholz, Peter. "Exact and ordinary lumpability in finite Markov chains." ''Journal of applied probability'' 31.1 (1994): 59-75.</ref>，并满足上面提到的粗粒化的两个规则。但是，其中的某些分组方案可约（lumpable），也有某些分组方案不可约（non-lumpable）。
可约简性（Lumpability）是一种对分类的衡量，这个概念最早出现在Kemeny, Snell在1969年的有限马尔科夫链（Finite Markov Chains）<ref name=":33">Kemeny, John G., and J. Laurie Snell. ''Finite markov chains''. Vol. 26. Princeton, NJ: van Nostrand, 1969. https://www.math.pku.edu.cn/teachers/yaoy/Fall2011/Kemeny-Snell_Chapter6.3-4.pdf</ref>中。马尔科夫链的粗粒化不仅要对状态空间做，也要对转移矩阵和概率空间做。这三个部分可以同时做，也可以看作为：先对状态空间做，再对转移矩阵和概率空间做；即先对状态做分组，然后再获取对应的粗粒化后的转移矩阵。我们也提到过对状态空间做粗粒化有硬分块（Hard Partitioning）和软分块（Soft Partitioning）两种。软分块可以看作把微观状态打散重构成了一些宏观状态，而硬分块则是更严格的，把若干个微观状态分成一个组。而可约简性（Lumpability）就是一个指标，用来评价‘对于某一种硬分块的微观状态分组分案，是否对微观状态转移矩阵可约简’。不管状态空间按照哪一个硬分块方案做分类，它都有对应后续的对转移矩阵和概率空间的粗粒化方案<ref>Buchholz, Peter. "Exact and ordinary lumpability in finite Markov chains." ''Journal of applied probability'' 31.1 (1994): 59-75.</ref>，并满足上面提到的粗粒化的两个规则。但是，其中的某些分组方案可约（lumpable），也有某些分组方案不可约（non-lumpable）。
lumpable的马尔科夫矩阵可以被重新排列成几个block，这种lumpable的矩阵的动力学可逆性也会很高，在这种情况下动力学可逆性和 Lumpability是一致的。关于具体的粗粒化马尔科夫链的方法，请参考[[马尔科夫链的粗粒化]]。
lumpable的马尔科夫矩阵可以被重新排列成几个block，这种lumpable的矩阵的动力学可逆性也会很高，在这种情况下动力学可逆性和 Lumpability是一致的。关于具体的粗粒化马尔科夫链的方法，请参考[[马尔科夫链的粗粒化]]。