97
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − + + + + + − 由上可见，马尔科夫链不只是一个马尔科夫矩阵那么简单，还涉及到了不同的状态，也会有状态之间的状态转移，所以我们可以从不同的角度来看待粗粒化：+ − + − + − + + + 第21行：
第27行： − + + + + + + + + + + + − 所以，我们能看到，对马尔科夫链做粗粒化的时候，不仅要对状态空间做降维，还要对马尔科夫矩阵都要做降维，当中也包含了对概率空间的降维。+ − 那对马尔科夫链做粗粒化做粗粒化的意义是什么呢？我们看到文献中着重强调这两点：+ − + − + − # 在用到马尔科夫决策过程的强化学习里，对马尔科夫链做粗粒化可以减少状态空间的大小，提高训练效率。 + 第94行：
第110行： − 第125行：
第140行： − 第137行：
第151行： − 第143行：
第156行： − − +
无编辑摘要
马尔科夫矩阵是指满足每一行和为1的条件的方阵，而马尔科夫链指的是一个n维的状态的序列<math>x_t\ = \{1, ..., n\}_{t}</math>，每一步的状态转换都有马尔科夫矩阵<math>P</math>决定，即<math>x_{t+1} = P x_t</math>.
马尔科夫矩阵是指满足每一行和为1的条件的方阵，而马尔科夫链指的是一个n维的状态的序列<math>x_t\ = \{1, ..., n\}_{t}</math>，每一步的状态转换都有马尔科夫矩阵<math>P</math>决定，即<math>x_{t+1} = x_t P</math>。
<math>P</math>的每一行对应的每个状态转移到其他状态的概率。比如当<math>x_t</math>等于第一个状态的时候，<math>P</math>的第一行展示了<math>x_{t+1}</math>状态的概率。
<math>P</math>的每一行对应的每个状态转移到其他状态的概率。比如当<math>x_t</math>等于第一个状态的时候，<math>P</math>的第一行展示了<math>x_{t+1}</math>状态的概率。
对马尔科夫链做粗粒化做粗粒化的意义是什么呢？我们看到文献中着重强调这两点：
#我们在研究一个超大的系统的时候，比如复杂城市系统时，并不会关注每一个微观的状态的变化，在粗粒化中我们希望能过滤掉一些我们不感兴趣的噪声和异质性，而是想从中微观尺度中总结一些中尺度或宏观尺度的规律；
#有些状态的转移概率非常相似，所以可以被看成同一类状态，对这种马尔科夫链做partitioning可以减少系统表示的冗余性；
#在用到马尔科夫决策过程的强化学习里，对马尔科夫链做粗粒化可以减少状态空间的大小，提高训练效率。
=粗粒化=
# 对马尔科夫矩阵做粗粒化：在看待一个方阵时，我们可以把它想象成一个网络的邻接矩阵。节点为状态，连边为状态转移概率，而粗粒化则是对这个网络做降维。
马尔科夫链不只是一个马尔科夫矩阵那么简单，还涉及到了不同的状态，也会有状态之间的转移概率，所以我们可以从不同的角度来看待粗粒化：
# 对状态空间做粗粒化：我们这里讨论的是离散状态的马尔科夫链，状态空间的大小等于马尔科夫链的大小。粗粒化可以看作对状态空间做分组并投影到新的状态空间。
# 对转移概率做粗粒化：从概率论出发，把状态的发生看作事件，通过计算事件发生的频率来构建概率空间。在降维表达事件的同时也构建了新的概率空间。
#对马尔科夫矩阵做粗粒化：在看待一个方阵时，我们可以把它想象成一个网络的邻接矩阵。节点为状态，连边为状态转移概率，而粗粒化则是对这个网络做降维。
#对状态空间做粗粒化：我们这里讨论的是离散状态的马尔科夫链，状态空间的大小等于马尔科夫链的大小。粗粒化可以看作对状态空间做分组并投影到新的状态空间。
#对转移概率做粗粒化：从概率论出发，把状态的发生看作事件，通过计算事件发生的频率来构建概率空间。在降维表达事件的同时也构建了新的概率空间。
这三种出发点看似互有联系，但是具体关心的东西不同。第一种关注状态之间的连边拓扑结构，第二种关注不同状态的历史分布和相似性，第三种关注如何降维表达整个系统中的事件概率分布。
这三种出发点看似互有联系，但是具体关心的东西不同。第一种关注状态之间的连边拓扑结构，第二种关注不同状态的历史分布和相似性，第三种关注如何降维表达整个系统中的事件概率分布。
对状态空间<math>S</math>和转移函数<math>T(t):S->S</math>，我们需要一个投影矩阵<math>R:S->S'</math>，和一个新的转移函数<math>T'(t):S'->S'</math>，而且S'和T'要符合马尔科夫链定义。
对状态空间<math>S</math>和转移函数<math>T(t):S->S</math>，我们需要一个投影矩阵<math>R:S->S'</math>，和一个新的转移函数<math>T'(t):S'->S'</math>，而且S'和T'要符合马尔科夫链定义。
所以，我们能看出<math>R</math>是一个对状态空间<math>S</math>的降维函数（得到<math>S'</math>）。而且，我们还需要把<math>T</math>降维成<math>T'</math>。如果<math>T:s_{t+1} = s_{t} P</math>，<math>P</math>为离散马尔科夫矩阵的话，这个针对马尔科夫矩阵的降维可以表示为<math>P = U P' V^T</math>，其中<math>P \in \mathbb{R}^{n \times n}</math>，<math>P' \in \mathbb{R}^{k \times k}</math>，而且<math>U, V \in \mathbb{R}^{n \times k}</math>。
所以，我们能看出<math>R</math>是一个对状态空间<math>S</math>的降维函数（得到<math>S'</math>）。而且，我们还需要把<math>T</math>降维成<math>T'</math>。如果<math>T:s_{t+1} = s_{t} P</math>，<math>P</math>为离散马尔科夫矩阵的话，这个针对马尔科夫矩阵的降维可以表示为
<math>P' = W P V,</math>
其中<math>P \in \mathbb{R}^{n \times n}</math>，<math>P' \in \mathbb{R}^{k \times k}</math>，<math>W \in \mathbb{R}^{k \times n}</math>，<math>V \in \mathbb{R}^{n \times k}</math>。Buchholz<ref>Buchholz, Peter. "Exact and ordinary lumpability in finite Markov chains." ''Journal of applied probability'' 31.1 (1994): 59-75.</ref>的文章中把<math>U</math>称作distributor matrix，而<math>V</math>称作collector matrix。
马尔科夫链的粗粒化可以分成Hard partitioning和Soft partitioning。Hard partitioning是指把若干个微观状态分成一个宏观状态类，且一个微观状态不能同时属于多个宏观状态类，而soft partitioning则会有可能出现这种情况。
在hard aprtitioning的情况下，<math>V_{i, j} = 1\ if\ s_i \in s_j'\ and\ 0\ otherwise</math>。而<math>W = D^{-1}(V)^T, D = diag(\alpha V)</math>，其中<math>\alpha</math>是一个非负对角矩阵。
所以，我们能看到，对马尔科夫链做粗粒化的时候，不仅要对状态空间做降维(<math>R</math>)，还要对马尔科夫矩阵都要做降维(<math>V</math>)，当中也包含了对概率空间的降维(<math>W</math>)。
而且，有文献中还提到了粗粒化的交换律commutative。按照上面的定义，<math>s_t</math>有两个路径能达到<math>s_{t+1}'</math>：
# 我们在研究一个超大的系统的时候，比如复杂城市系统时，并不会关注每一个微观的状态的变化，在粗粒化中我们希望能过滤掉一些我们不感兴趣的噪声和异质性，而是想从中微观尺度中总结一些中尺度或宏观尺度的规律；
#先得到下一步的<math>s_{t+1} = s_{t} P</math>，再做粗粒化得到<math>s_{t+1}' = R(s_{t+1})</math>
# 有些状态的转移概率非常相似，所以可以被看成同一类状态，对这种马尔科夫链做partitioning可以减少系统表示的冗余性；
#先做粗粒化得到<math>s_{t}' = R(s_{t})</math>，再得到下一步的<math>s_{t+1}' = s_{t}' P</math>
而交换律则要求从这两条路径得到的结果应该是一样的，即<math> R(s_{t} P) = R(s_{t}) P</math>。
但是，有时候有些lumpable的矩阵的状态排序被打乱了（如图一中的<math>P_1</math>），或者矩阵包含了如<math>P_2</math>的噪声（如图一中的<math>P</math>，<math>P = P_1 + P_2</math>，<math>P_1^TP_2 = 0</math>）。
但是，有时候有些lumpable的矩阵的状态排序被打乱了（如图一中的<math>P_1</math>），或者矩阵包含了如<math>P_2</math>的噪声（如图一中的<math>P</math>，<math>P = P_1 + P_2</math>，<math>P_1^TP_2 = 0</math>）。
我们看到这两个目标函数是非常相似的。所以，我们就可以通过上述算法或者kMeans来获取最优partition，然后根据这个partition来判断马尔科夫矩阵的lumpability。
我们看到这两个目标函数是非常相似的。所以，我们就可以通过上述算法或者kMeans来获取最优partition，然后根据这个partition来判断马尔科夫矩阵的lumpability。
动力学可逆性相关详情请参照[[因果涌现]]词条。
动力学可逆性相关详情请参照[[因果涌现]]词条。
因果态相关详情请参照[[计算力学]]词条。
因果态相关详情请参照[[计算力学]]词条。
=不同粗粒化方法之间的异同=
=不同粗粒化方法之间的异同=
====动力学可逆性 v.s. Lumpability ====
====动力学可逆性 v.s. Lumpability====
在lumpability的图1中我们提到了lumpable的马尔科夫矩阵可以被重新排列成几个block，这种lumpable的矩阵的动力学可逆性也会很高，在这种情况下动力学可逆性和 Lumpability是一致的。
在lumpability的图1中我们提到了lumpable的马尔科夫矩阵可以被重新排列成几个block，这种lumpable的矩阵的动力学可逆性也会很高，在这种情况下动力学可逆性和 Lumpability是一致的。