727
个编辑
更改
跳到导航
跳到搜索
第593行：
第593行： − 除了对向量以及高维动力学的降维之外，[[马尔科夫链的简化]]（或叫做[[马尔科夫链的粗粒化]]）也和因果涌现有着重要的联系。马尔可夫过程的模型约简<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>。+ − 其中，对状态空间做粗粒化有硬分块（Hard Partitioning）和软分块（Soft Partitioning）两种。软分块可以被看作把微观状态打散重构出一些宏观状态，允许微观态的叠加而得到宏观态；而硬分块则是严格的微观态分组，把若干个微观状态分成一个组，不允许重叠和叠加。马尔科夫链的粗粒化不仅要对状态空间做，也要对转移矩阵和概率空间做。这三个部分可以同时做，也可以看作为：先对状态空间做，再对转移矩阵和概率空间做；即先对状态做分组，然后再获取对应的粗粒化后的转移矩阵。于是，这就引出了一个新的问题，即状态分组得到的新马尔科夫链中的转移概率应该如何计算？+ − 于是，人们提出了可聚类性的概念。首先，对于硬分块方法，我们也叫做马尔可夫链状态聚类（Lumping Markov Chain）约简方法；其次，针对任意的状态划分，我们可以定义所谓的可聚类性（lumpability）的概念。可聚类性（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>中。可聚类性（Lumpability）就是一个指标，用来评价“对于某一种硬分块的微观状态分组分案，是否对微观状态转移矩阵是可约简的”。不管状态空间按照哪一个硬分块方案做分类，它都有对应后续的对转移矩阵和概率空间的粗粒化方案<ref>Buchholz, Peter. "Exact and ordinary lumpability in finite Markov chains." ''Journal of applied probability'' 31.1 (1994): 59-75.</ref>。接下来，我们给出正式的定义。+ + + + + + +
→马尔科夫链的简化
===马尔科夫链的简化===
===马尔科夫链的简化===
[[马尔科夫链的简化]]（或叫做[[马尔科夫链的粗粒化]]）也和因果涌现有着重要的联系，因果涌现中的粗粒化过程本质上就是马尔科夫链的简化。马尔可夫过程的模型简化<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>。
其中，对状态空间做粗粒化有硬分组（Hard Partitioning）和软分组（Soft Partitioning）两种。软分组可以看作是把微观状态打散重构出一些宏观状态的过程，并允许微观态的叠加而得到宏观态；而硬分组则是严格的微观态分组，把若干个微观状态分成一个组，不允许重叠和叠加（参见[[马尔科夫链的粗粒化]]）。
马尔科夫链的粗粒化不仅要对状态空间做，也要对转移矩阵做，也就是根据状态的分组简化原转移矩阵以得到新的更小的转移矩阵。除此之外，还要对状态向量做约简。因此，一个完整的粗粒化过程需要同时考虑状态、转移矩阵、状态向量的粗粒化。于是，这就引出了一个新的问题，即状态分组得到的新马尔科夫链中的转移概率应该如何计算？同时，归一化条件是否能够得到保证？
除了这些基本保证之外，还要求对转移矩阵的粗粒化操作与马尔科夫链是可交换的，这能够保证经过粗粒化后的状态向量经过粗粒化后的转移矩阵（相当于宏观动力学）的一步演化，是等价于先对状态向量进行一步转移矩阵演化（相当于微观动力学），之后再进行粗粒化的。这就同时为状态分组（状态的粗粒化过程）以及转移矩阵的粗粒化过程提出了要求。对于这一可交换性的要求，就导致人们提出了[[马尔科夫链可聚类性]]的要求。
针对任意的状态硬划分，我们可以定义所谓的可聚类性（lumpability）的概念。可聚类性（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>中。可聚类性（Lumpability）就是一个数学条件，用来判断“对于某一种硬分块的微观状态分组分案，是否对微观状态转移矩阵是可约简的”。不管状态空间按照哪一个硬分块方案做分类，它都有对应后续的对转移矩阵和概率空间的粗粒化方案<ref>Buchholz, Peter. "Exact and ordinary lumpability in finite Markov chains." ''Journal of applied probability'' 31.1 (1994): 59-75.</ref>。接下来，我们给出正式的定义。
'''给定一个状态划分（state partition） <math>A=\{A_1, A_2, ... ,A_r\}</math>'''，我们能够用下列公式描述一个马尔科夫链的聚类过程(lumped process)，且这个转移概率对任何初始状态(starting vector) <math> \pi </math> 都是一样的：{{NumBlk|:|
'''给定一个状态划分（state partition） <math>A=\{A_1, A_2, ... ,A_r\}</math>'''，我们能够用下列公式描述一个马尔科夫链的聚类过程(lumped process)，且这个转移概率对任何初始状态(starting vector) <math> \pi </math> 都是一样的：{{NumBlk|:|