更改

马尔科夫链的粗粒化 (查看源代码)

2024年9月8日 (日) 16:57的版本

添加658字节、 2024年9月8日 (星期日)

无编辑摘要

第2行：第2行：

<math>P</math>的每一行对应的每个状态转移到其他状态的概率。比如当<math>x_t</math>等于第一个状态的时候，<math>P</math>的第一行展示了<math>x_{t+1}</math>状态的概率。

+

对马尔科夫链做粗粒化做粗粒化的意义是什么呢？我们看到文献中着重强调这两点：

第13行：第15行：

马尔科夫链不只是一个马尔科夫矩阵那么简单，还涉及到了不同的状态，也会有状态之间的转移概率，所以我们可以从不同的角度来看待粗粒化：

−

#对马尔科夫矩阵做粗粒化：在看待一个方阵时，我们可以把它想象成一个网络的邻接矩阵。节点为状态，连边为状态转移概率，而粗粒化则是对这个网络做降维。

+

#对马尔科夫矩阵做粗粒化：在看待一个方阵时，我们可以把它想象成一个网络的邻接矩阵。节点为状态，连边为状态转移概率，状态转移的过程为一个粒子在节点间跳转，而粗粒化则是对这个网络做降维。

#对状态空间做粗粒化：我们这里讨论的是离散状态的马尔科夫链，状态空间的大小等于马尔科夫链的大小。粗粒化可以看作对状态空间做分组并投影到新的状态空间。

−

#对转移概率做粗粒化：从概率论出发，把状态的发生看作事件，通过计算事件发生的频率来构建概率空间。在降维表达事件的同时也构建了新的概率空间。

+

#对概率空间做粗粒化：从概率论出发，把状态的发生看作事件，通过计算事件发生的频率来构建概率空间。在降维表达事件的同时也构建了新的概率空间。

这三种出发点看似互有联系，但是具体关心的东西不同。第一种关注状态之间的连边拓扑结构，第二种关注不同状态的历史分布和相似性，第三种关注如何降维表达整个系统中的事件概率分布。

第23行：第25行：

对马尔科夫链做粗粒化并没有一个统一的定义，目前该题目也没有一个完整的文献综述。在许多文献中，粗粒化coarse-graining和降维dimension reduction是重叠等价的。

−

~~多数文献中会出现如此一个定义：~~

+

多数文献中会出现如此一个定义<ref name=":2">Coarse graining. ''Encyclopedia of Mathematics.'' URL: <nowiki>http://encyclopediaofmath.org/index.php?title=Coarse_graining&oldid=16170</nowiki></ref>：

对状态空间<math>S</math>和转移函数<math>T(t):S->S</math>，我们需要一个投影矩阵<math>R:S->S'</math>，和一个新的转移函数<math>T'(t):S'->S'</math>，而且<math>S'</math>和<math>T'</math>要符合马尔科夫链定义。

第31行：第33行：

−

其中<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。

+

其中<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 name=":1">Buchholz, Peter. "Exact and ordinary lumpability in finite Markov chains." ''Journal of applied probability'' 31.1 (1994): 59-75.</ref>的文章中把<math>W</math>称作distributor matrix，而<math>V</math>称作collector matrix。

+

马尔科夫链的粗粒化可以分成Hard partitioning和Soft partitioning。Hard partitioning是指把若干个微观状态分成一个宏观状态类，且一个微观状态不能同时属于多个宏观状态类，而Soft partitioning则会有可能出现一个微观状态被分在属于多个宏观类的情况。

−

马尔科夫链的粗粒化可以分成Hard partitioning和Soft partitioning。Hard partitioning是指把若干个微观状态分成一个宏观状态类，且一个微观状态不能同时属于多个宏观状态类，而soft partitioning则会有可能出现这种情况。

+

在Hard partitioning的情况下，<math>V_{i, j} = 1\ if\ s_i \in s_j'\ and\ 0\ otherwise</math><ref name=":1" />，即一个表示<math>i</math>属于<math>j</math>列的零一分组矩阵，如果是Soft partitioning的话，<math>V</math>则不一定会是零一矩阵。

−

~~在hard aprtitioning的情况下，<math>V_{i, j} = 1\ if\ s_i \in s_j'\ and\ 0\ otherwise</math>，即一个表示<math>i</math>属于<math>j</math>列的零一分组矩阵。而~~<math>W = D^{-1}(V)^T, D = diag(\alpha V)</math>，其中<math>\alpha</math>是一个非负对角矩阵。

+

而<math>W = D^{-1}(V)^T, D = diag(\alpha V)</math>，其中<math>\alpha</math>是一个非负对角矩阵。

所以，我们能看到，对马尔科夫链做粗粒化的时候，不仅要对状态空间做降维(<math>R</math>)，还要对马尔科夫矩阵都要做降维(<math>V</math>)，当中也包含了对概率空间的降维(<math>W</math>)。

第43行：第47行： −

~~而且，有文献中还提到了粗粒化的交换律commutative。按照上面的定义，~~<math>s_t</math>有两个路径能达到<math>s_{t+1}'</math>：

+

而且，有资料中还提到了粗粒化的交换律commutative<ref name=":2" />。按照上面的定义，<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>

−

#先做粗粒化得到<math>s_{t}' = R(s_{t})</math>，再得到下一步的<math>s_{t+1}' = s_{t}' P</math>

+

# 先做粗粒化得到<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>。

第54行：第58行：

因此，根据目前有迹可循的对马尔科夫链的粗粒化的定义来说，我们要求一个良定义的粗粒化方法上述提到过的两个规则：

−

# 粗粒化后的<math>S'</math>和<math>T'</math>要符合马尔科夫链定义。

+

#粗粒化后的<math>S'</math>和<math>T'</math>要符合马尔科夫链定义。

−

# 满足交换律

+

#满足交换律

−

~~但是注意，这是我们从不同来源中总结出来的规则。目前我们还没找到一个严格的完备的定义。~~

+

但是注意，这是我们从不同来源<ref name=":2" />中总结出来的规则。目前我们还没找到一个严格的完备的定义。

而且，这只是最简单，最基本的对马尔科夫链的粗粒化，我们下面会介绍不同的指标，在上述的两个规则之上添加更多的规则会得出基于这些指标的粗粒化的方法。

第63行：第67行： −

~~在这个词条里，我们主要讨论hard~~ partitioning，主要参考的是Anru Zhang和Mengdi Wang的Spectral State Compression of Markov Processes<ref name=":0">Zhang, Anru, and Mengdi Wang. "Spectral state compression of markov processes." ''IEEE transactions on information theory'' 66.5 (2019): 3202-3231.</ref>~~，对soft~~ state aggregation感兴趣的朋友可以自行参阅S. P. Singh, T. Jaakkola, and M. I. Jordan, “Reinforcement learning with soft state aggregation,~~” in Proc. Adv. Neural Inf. Process. Syst.~~, ~~1995~~, pp. ~~361–368~~.

+

在这个词条里，我们主要讨论Hard partitioning，主要参考的是Anru Zhang和Mengdi Wang的Spectral State Compression of Markov Processes<ref name=":0">Zhang, Anru, and Mengdi Wang. "Spectral state compression of markov processes." ''IEEE transactions on information theory'' 66.5 (2019): 3202-3231.</ref>，对Soft state aggregation感兴趣的朋友可以自行参阅S. P. Singh, T. Jaakkola, and M. I. Jordan, “Reinforcement learning with soft state aggregation."<ref>Singh, Satinder, Tommi Jaakkola, and Michael Jordan. "Reinforcement learning with soft state aggregation." ''Advances in neural information processing systems'' 7 (1994).</ref>

=Rank=

第89行：第93行：

Lumpability是一种用于分类的定义，笔者暂时还没找到一个正式的中文翻译，而不同文献对于这个概念的解释也有所不同。

−

这个概念最早出现在Kemeny, Snell ~~1976~~. Finite ~~Markov Chains中。书中的定义是这样的~~

+

这个概念最早出现在Kemeny, Snell在1969年的Finite Markov Chains<ref>Kemeny, John G., and J. Laurie Snell. ''Finite markov chains''. Vol. 26. Princeton, NJ: van Nostrand, 1969.</ref>中。书中的定义是这样的：

给定一个partition <math>A=\{A_1, A_2, ... ,A_r\}</math>，我们能够用下列公式描述一个粗粒化后的马尔科夫链(lumped process)，且这个转移概率对任何初始状态(starting vector) <math> \pi </math> 都是一样的：

第129行：第133行：

#先获取一个n*n维的马尔科夫矩阵P，或者是马尔科夫链的频率采样；

−

#获取r<n 的马尔科夫秩，或指定一个r；

+

# 获取r<n 的马尔科夫秩，或指定一个r；

#对P进行SVD分解，<math>P = U \Sigma V^T</math>，其中U为左奇异向量，V为右奇异向量。

#通过下列公式得到最优partition <math>\Omega_1, \Omega_2, ... , \Omega_r</math>

Liangjh

48

个编辑