97
个编辑
更改
无编辑摘要
=Lumpability=
=Lumpability=
Lumpability是一种对分类的衡量，笔者暂时还没找到一个正式的中文翻译。
这个概念最早出现在Kemeny, Snell在1969年的Finite Markov Chains<ref>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>中。书中的定义是这样的：
这个概念最早出现在Kemeny, Snell在1969年的Finite Markov Chains<ref>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>中。书中的定义是这样的：
'''给定一个state partition <math>A=\{A_1, A_2, ... ,A_r\}</math>'''，我们能够用下列公式描述一个粗粒化后的马尔科夫链(lumped process)，且这个转移概率对任何初始状态(starting vector) <math> \pi </math> 都是一样的：
<math>
<math>
Pr_{\pi}[f_n \in A_t |f_{n-1} \in A_s, 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]
</math>
</math>
作者提出了判断一个马尔科夫链对'''给定partition <math>A=\{A_1, A_2, ... ,A_r\}</math>''' 是否lumpable的充分必要条件为：
对于任意一对<math>A_i, A_j</math>，每一个属于<math>A_i</math>的状态<math>s_k</math>的<math>p_{kA_j}</math>都是一样的。
对于任意一对<math>A_i, A_j</math>，每一个属于<math>A_i</math>的状态<math>s_k</math>的<math>p_{kA_j}</math>都是一样的。
这个公式表达的是，群组<math>A_i</math>到群组<math>A_j</math>的转移概率 = 群组<math>A_i</math>中任意状态<math>s_k</math>到群组<math>A_j</math>的转移概率 = 群组<math>i</math>中任意状态<math>s_k</math>到群组<math>A_j</math>中的状态的转移概率的和。
这个公式表达的是，群组<math>A_i</math>到群组<math>A_j</math>的转移概率 = 群组<math>A_i</math>中任意状态<math>s_k</math>到群组<math>A_j</math>的转移概率 = 群组<math>i</math>中任意状态<math>s_k</math>到群组<math>A_j</math>中的状态的转移概率的和。
请注意：lumpability有一个非常重要的前提，即我们要给定一个对马尔科夫链的state的partition，然后根据马尔科夫状态转移矩阵来决定这个partition对这个马尔科夫链是否lumpable。
所以，lumpability并不是一个马尔科夫链的特质，而是对马尔科夫链的某个state partition的特质。
====Lumpability和粗粒化====
我们在粗粒化的部分提到了，马尔科夫链的粗粒化不仅要对状态空间做，也要对转移矩阵和概率空间做。
这三个部分可以同时做，也可以先对状态空间做，再对转移矩阵和概率空间做。
我们也提到过对状态空间做粗粒化有Hard Partitioning和Soft Partitioning两种。Soft Partitioning可以看作把微观状态打散重构成了一些宏观状态，而Hard Partitioning则是做简单的分组。
而Lumpability就是，评价对于任意一种微观状态的Hard Partitioning分组分案，是否对微观状态转移矩阵lumpable。
不管状态空间按照哪一个Hard Partitioning方案做分类，它都有对应后续的对转移矩阵和概率空间的粗粒化方案，并满足上面提到的粗粒化的两个规则。但是，其中的某些分组方案lumpable，也有某些分组方案non-lumpable。
所以，整个链条应该是这样的：Lumpable的粗粒化方案 <math>\in</math> Hard Partitioning <math>\in</math> 良定义的粗粒化方案。
所以，一个满足lumpability的良定义的粗粒化方案应该在原来的两个条件下，再多加两个条件：
#粗粒化后的<math>S'</math>和<math>T'</math>要符合马尔科夫链定义。
#满足交换律
#Hard Partitioning，即存在分组矩阵<math>V_{i, j} = 1\ if\ s_i \in s_j'\ and\ 0\ otherwise</math>
#<math>V</math>是一个lumpable分组。
====基于Lumpability的粗粒化方法====
====基于Lumpability的粗粒化方法====
[[文件:Lump fig1.png|缩略图|398x398像素|图2：Zhang<ref name=":0" /> 文章中的示意图。图中左面四个矩阵都是lumpable马尔科夫矩阵，而右面的P_2是一个噪声矩阵，(P_1)^T P_2 = 0|替代=]]
由上面的lumpability公式我们能获得一个直观上的说法：当马尔科夫矩阵存在block结构，或者状态明显可被分成几类的时候，根据这样的partition，该矩阵就会lumpable，如图2中的<math>\bar{P}</math>所示，把相同的状态（行向量）分成一类的partition显然lumpable。
但是，有时候有些lumpable的矩阵的状态排序被打乱了（如图一中的<math>P_1</math>），或者矩阵包含了如<math>P_2</math>的噪声（如图2中的<math>P</math>，<math>P = P_1 + P_2</math>，<math>P_1^TP_2 = 0</math>）。
我们在实际问题中很多时候要面对的是像<math>P</math>这样的矩阵，我们既无法确定它是否lumpable，也无法决定它的partition，我们甚至不知道它的马尔科夫秩。
我们在实际问题中很多时候要面对的是像<math>P</math>这样的矩阵，我们既无法确定它是否lumpable，也无法决定它的partition，我们甚至不知道它的马尔科夫秩。
我们看到这两个目标函数是非常相似的。所以，我们就可以通过上述算法或者kMeans来获取最优partition，然后根据这个partition来判断马尔科夫矩阵的lumpability。
我们看到这两个目标函数是非常相似的。所以，我们就可以通过上述算法或者kMeans来获取最优partition，然后根据这个partition来判断马尔科夫矩阵的lumpability。