786
个编辑
更改
→马尔科夫链的简化
马尔可夫过程的模型约简<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>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>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）。在可以长时间运行的系统中，我们会遇到不可约马尔可夫链，对马尔科夫概率转移矩阵实施粗粒化的方法，其实就利用了马尔科夫链的可约性与不可约性。关于具体的粗粒化马尔科夫链的方法，请参考[[马尔科夫链的粗粒化]]。