207
个编辑
更改
→马尔科夫链的简化
===马尔科夫链的简化===
===马尔科夫链的简化===
除了对向量以及高维动力学的降维之外，[[马尔科夫链的简化]]（Lumping Markov Chain）也和因果涌现有着重要的联系。和因果涌现中的粗粒化相似，马尔科夫链的简化主要也是通过将多个状态合并成一个状态来降低马尔科夫链链的复杂度。该过程主要是通过识别一些状态的组合，使得合并后的系统仍然保留马尔科夫性质。
除了对向量以及高维动力学的降维之外，[[马尔科夫链的简化]]（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>是状态转移系统建模中的一个重要问题。和因果涌现中的粗粒化相似，马尔科夫链的简化主要也是通过将多个状态合并成一个状态来降低马尔科夫链链的复杂度。该过程主要是通过识别一些状态的组合，使得合并后的系统仍然保留马尔科夫性质。
为了满足上述条件，我们可以从三个视角入手，在看待一个马尔科夫转移矩阵时，我们可以把它想象成一个网络的邻接矩阵。节点为状态，连边为状态转移概率，而粗粒化则是对这个网络做降维。同时离散状态的马尔科夫链，状态空间的大小等于马尔科夫链的大小。粗粒化可以看作对状态空间做分组并投影到新的状态空间。从概率论出发，把状态的发生看作事件，通过计算事件发生的频率来构建概率空间。在降维表达事件的同时也构建了新的概率空间。这三种出发点看似互有联系，但是具体关心的东西不同。第一种关注状态之间的连边拓扑结构，第二种关注不同状态的历史分布和相似性，第三种关注如何降维表达整个系统中的事件概率分布。投影降维、节点分类都是常见的简化方法。
从底层的理论角度，有限马尔可夫链的状态简化可以视为马尔科夫状态转移矩阵的一种特殊分解<ref>Barreto A M S, Fragoso M D. Lumping the states of a finite Markov chain through stochastic factorization[J]. IFAC Proceedings Volumes, 2011, 44(1): 4206-4211.</ref>，该分解称为随机因子分解。较小的马尔可夫链与原始模型具有相同的可约性<ref name=":16" />和相同的闭集数，两条链的平稳分布通过线性变换相关联。通过奇异值谱分析，可以通过马尔可夫过程的秩和特征，来描述它的可表示性、聚集性和集总性等性质。反之，也可以用谱方法来估计低秩马尔可夫模型的转移矩阵，估计马尔可夫特征跨越的前导子空间，并恢复状态空间的状态聚合和可分块划分等潜在结构。而奇异值谱的分布，反应的集总性和可逆性的概念起着核心作用<ref>Marin A, Rossi S. On the relations between lumpability and reversibility[C]//2014 IEEE 22nd International Symposium on Modelling, Analysis & Simulation of Computer and Telecommunication Systems. IEEE, 2014: 427-432.</ref>，反过来，马尔科夫过程的近似动力学可逆性，和有效信息与因果涌现也有着重要联系<ref name=":2"/><ref>F. Kelly, Reversibility and stochastic networks. New York: Wiley, 1979.</ref>。在约简的过程中，如果能巧妙地选择要合并的状态，使得合并后的转移矩阵保留了原始转移矩阵的主要奇异值（尤其是最大奇异值或靠前的几个奇异值），则可以认为新的链很好地近似了原始链的主要动力学特征。而对聚合方案的最优化策略<ref>P. Buchholz, Exact and ordinary lumpability in finite Markov chains, J. Appl. Probab. 31 (1994) 59–75.</ref><ref>Derisavi S, Hermanns H, Sanders W H. Optimal state-space lumping in Markov chains[J]. Information processing letters, 2003, 87(6): 309-315.</ref>，和因果涌现的最优化都会受可逆性影响。
如果我们要对马尔科夫链进行约简，首先就要对其状态进行聚类，而这种操作的重要前提就是马尔科夫链是否可约<ref name=":16">Gebali F, Gebali F. Reducible Markov Chains[J]. Analysis of Computer Networks, 2015: 157-189.</ref>。可约马尔可夫链描述的系统具有特定状态，一旦系统访问了其中一种状态，就无法访问其他状态。但如果从任何状态开始，系统都能够直接、一步或间接地通过一个或多个中间状态到达图中的任何其他状态，这样的马尔可夫链就称为不可约马尔可夫链（irreducible Markov Chain）。在可以长时间运行的系统中，我们会遇到不可约马尔可夫链，对马尔科夫概率转移矩阵实施粗粒化的方法，其实就利用了马尔科夫链的可约性与不可约性。关于具体的粗粒化马尔科夫链的方法，请参考[[马尔科夫链的粗粒化]]。
如果我们要对马尔科夫链进行约简，首先就要对其状态进行聚类，而这种操作的重要前提就是马尔科夫链是否可约<ref name=":16">Gebali F, Gebali F. Reducible Markov Chains[J]. Analysis of Computer Networks, 2015: 157-189.</ref>。可约马尔可夫链描述的系统具有特定状态，一旦系统访问了其中一种状态，就无法访问其他状态。但如果从任何状态开始，系统都能够直接、一步或间接地通过一个或多个中间状态到达图中的任何其他状态，这样的马尔可夫链就称为不可约马尔可夫链（irreducible Markov Chain）。在可以长时间运行的系统中，我们会遇到不可约马尔可夫链，对马尔科夫概率转移矩阵实施粗粒化的方法，其实就利用了马尔科夫链的可约性与不可约性。关于具体的粗粒化马尔科夫链的方法，请参考[[马尔科夫链的粗粒化]]。