更改

跳到导航 跳到搜索
删除505字节 、 2024年9月21日 (星期六)
第574行: 第574行:  
除了对向量以及高维动力学的降维之外,[[马尔科夫链的简化]](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>是状态转移系统建模中的一个重要问题。和因果涌现中的粗粒化相似,马尔科夫链的简化主要也是通过将多个状态合并成一个状态来降低马尔科夫链链的复杂度。该过程主要是通过识别一些状态的组合,使得合并后的系统仍然保留马尔科夫性质。
   −
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是一种对分类的衡量,这个概念最早出现在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两种。Soft Partitioning可以看作把微观状态打散重构成了一些宏观状态,而Hard Partitioning则是更严格的,把若干个微观状态分成一个组。而Lumpability就是一个指标,用来评价‘对于某一种Hard Partitioning的微观状态分组分案,是否对微观状态转移矩阵lumpable’。不管状态空间按照哪一个Hard Partitioning方案做分类,它都有对应后续的对转移矩阵和概率空间的粗粒化方案,并满足上面提到的粗粒化的两个规则。但是,其中的某些分组方案lumpable,也有某些分组方案non-lumpable。
 
  −
'''给定一个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}}}}马尔科夫链的粗粒化不仅要对状态空间做,也要对转移矩阵和概率空间做。这三个部分可以同时做,也可以看作为:先对状态空间做,再对转移矩阵和概率空间做;即先对状态做分组,然后再获取对应的粗粒化后的转移矩阵。我们也提到过对状态空间做粗粒化有Hard Partitioning和Soft Partitioning两种。Soft Partitioning可以看作把微观状态打散重构成了一些宏观状态,而Hard Partitioning则是更严格的,把若干个微观状态分成一个组。而Lumpability就是一个指标,用来评价‘对于某一种Hard Partitioning的微观状态分组分案,是否对微观状态转移矩阵lumpable’。不管状态空间按照哪一个Hard Partitioning方案做分类,它都有对应后续的对转移矩阵和概率空间的粗粒化方案(,并满足上面提到的粗粒化的两个规则。但是,其中的某些分组方案lumpable,也有某些分组方案non-lumpable。
      
在看待一个马尔科夫转移矩阵时,我们可以把它想象成一个网络的邻接矩阵。节点为状态,连边为状态转移概率,而粗粒化则是对这个网络做降维。同时离散状态的马尔科夫链,状态空间的大小等于马尔科夫链的大小。粗粒化可以看作对状态空间做分组并投影到新的状态空间。从概率论出发,把状态的发生看作事件,通过计算事件发生的频率来构建概率空间。在降维表达事件的同时也构建了新的概率空间。这三种出发点看似互有联系,但是具体关心的东西不同。第一种关注状态之间的连边拓扑结构,第二种关注不同状态的历史分布和相似性,第三种关注如何降维表达整个系统中的事件概率分布。投影降维、节点分类都是常见的简化方法。
 
在看待一个马尔科夫转移矩阵时,我们可以把它想象成一个网络的邻接矩阵。节点为状态,连边为状态转移概率,而粗粒化则是对这个网络做降维。同时离散状态的马尔科夫链,状态空间的大小等于马尔科夫链的大小。粗粒化可以看作对状态空间做分组并投影到新的状态空间。从概率论出发,把状态的发生看作事件,通过计算事件发生的频率来构建概率空间。在降维表达事件的同时也构建了新的概率空间。这三种出发点看似互有联系,但是具体关心的东西不同。第一种关注状态之间的连边拓扑结构,第二种关注不同状态的历史分布和相似性,第三种关注如何降维表达整个系统中的事件概率分布。投影降维、节点分类都是常见的简化方法。
225

个编辑

导航菜单