| 第111行： |
第111行： |
| | 而且，这只是最简单，最基本的对马尔科夫链的粗粒化，我们下面会介绍不同的指标，在上述的两个规则之上添加更多的规则会得出基于这些指标的粗粒化的方法。 | | 而且，这只是最简单，最基本的对马尔科夫链的粗粒化，我们下面会介绍不同的指标，在上述的两个规则之上添加更多的规则会得出基于这些指标的粗粒化的方法。 |
| | | | |
| − | =Lumpability= | + | =成块性= |
| | | | |
| − | [[Lumpability]]是一种描述状态分类的衡量，笔者暂时还没找到一个正式的中文翻译。 | + | [[马尔科夫链的成块性]]成块性（Lumpability）是一种描述马尔科夫链是否可聚类或可粗粒化性质的概念，最早由Kemeny和Snell在其1969年著作Finite Markov Chains<ref name=":1">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>中阐述。Lump一词有‘块’的意思。判断一个[[马尔科夫链]]是否可成块（lumpable），就是要判定是否存在一种状态划分方式，能够将原始的马尔科夫链压缩为一个保留其动力学特征的简化链。这种划分需确保：虽然抹除了聚类内部状态的微观差异，但能精确保持块间转移机制。这一特性为状态空间的合理划分提供了严格的数学判据。 |
| | | | |
| − | 这个概念最早出现在Kemeny, Snell在1969年的Finite Markov Chains<ref name=":3">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>中。
| + | 符合成块性的粗粒化方案有很多很好的性质，如保证了对宏观层面上的最大预测性、保证了微观与宏观过程的一致性等。这使得成块性成为马尔科夫链维度约简研究中最常用的标准之一。 |
| | | | |
| − | 为了严谨的介绍这一定义，我们会详细翻译文章中的部分。不感兴趣的读者可以跳到更简洁直观的‘lumpable partition的充分必要条件'部分。
| + | 成块性的初始定义比较复杂，详见[[马尔科夫链的成块性]]。在此词条中，我们介绍其定义的充分必要条件，一个更直观的解析。在某些文献中，作者们会直接使用这个通俗版的解释，而且这两者之间是存在充分必要条件关系的<ref name=":1" />。 |
| | | | |
| − | ===最初定义=== | + | ==成块性的充分必要条件== |
| | | | |
| − | 首先定义<math>s^{(t)}</math>表示系统在<math>t</math>时刻处于各微观状态的概率，微观状态空间为<math>S=\{s_1, s_2, ... ,s_n\}</math>。
| + | 设<math>p_{s_k \rightarrow s_m} = p(s^{(t)} = s_m | s^{(t-1)} = s_k)</math>，<math>p_{s_k \rightarrow A_i} = p(s^{(t)} \in A_i | s^{(t-1)} = s_k) = \sum_{s_m \in A_i} p_{s_k \rightarrow s_m}</math>，<math>p_{A_i \rightarrow A_j} = p(A^{(t)} = A_j | A^{(t-1)} = A_i)</math>，作者<ref name=":1" />提出了判断一个马尔科夫链对'''给定划分 <math>A</math>''' 是否成块的充分必要条件为： |
| | | | |
| − | 给定一个任意状态划分（state partition） <math>A=\{A_1, A_2, ... ,A_r\}</math>，也可以把其理解为宏观的状态空间。<math>S</math> 和 <math>A</math> 之间的硬性划分映射关系<math>\Phi:S \rightarrow A</math>为：<math>A_i \in S, A_i \neq \empty, A_i \cap A_j = \empty , \forall i, j, \cup_i A_i = S</math>。这种映射关系是指：<math>A</math>中的每个元素<math>A_i</math>都包括了若干个<math>s_i</math>；<math>A_i</math>和<math>A_j</math>之间没有交集，即每个<math>s_i</math>不会同时属于<math>A_i</math>和<math>A_j</math>；<math>S</math>中的每个元素必须属于某个<math>A</math>的元素，即<math>A</math>覆盖了<math>S</math>。
| + | '''''定理1：''''' |
| − | | |
| − | 在这里，我们考虑的是线性的马尔科夫过程的投影，所以<math>\Phi</math>是一个<math>n \times n</math>的投影矩阵。因此，我们可以定义宏观状态<math>A^{(t)} = s^{(t)} \Phi</math>为微观状态<math>s^{(t)}</math>在宏观空间上的投影。
| |
| − | | |
| − | [[文件:Lumpable矩阵粗粒化示例.png|缩略图|500x500像素|图2：矩阵粗粒化示例]]对于任意状态划分 <math>A</math>，我们能够定义一个lumped process，即把微观的动力学轨迹<math>s^{(t)}</math>通过投影矩阵<math>\Phi</math>投影到<math>A</math>的空间上。
| |
| | | | |
| − | 比如，我们有某条微观状态序列<math>\{ s^{(1)}, ..., s^{(6)} \}</math> 是 <math>\{ s_1, s_3, s_4, s_2, s_2, s_3 \}</math>，对于投影矩阵<math>\Phi = \left ( \begin{array}{cc} 1 & 0 \\ 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{array} \right )</math>，我们得到的投影后的宏观状态序列为<math>\{ A_1, A_2, A_2, A_1, A_1, A_2 \}</math>
| + | '''给定划分 <math>A</math>是成块的充分必要条件为：''' |
| | | | |
| − | '''''定义1'''''：'''Lumped process''' | + | '''对于任意一对<math>A_i, A_j</math>，每一个属于<math>A_i</math>的状态<math>s_k</math>的<math>p_{s_k \rightarrow A_j}</math>都是一样的。也就是说，<math>A_i</math>里的每一个状态<math>s_k</math>转移到<math>A_j</math>中的所有状态的转移概率之和是相同的，''' |
| | | | |
| − | '''Lumped process，是微观轨迹在宏观空间上的投影。这种投影可以写作下列公式：'''
| |
| − |
| |
| − | {{NumBlk|:|
| |
| − | <math>
| |
| − | Pr_{\pi}[s^{(0)} \in A_i]
| |
| − | </math>
| |
| − | |{{EquationRef|3.1}}}}
| |
| − | {{NumBlk|:|
| |
| − | <math>
| |
| − | Pr_{\pi}[s^{(1)} \in A_j | s^{(0)} \in A_i]
| |
| − | </math>
| |
| − | |{{EquationRef|3.2}}}}
| |
| | {{NumBlk|:| | | {{NumBlk|:| |
| | <math> | | <math> |
| − | Pr_{\pi}[s^{(t)} \in A_m | s^{(t-1)} \in A_k, ... , s^{(1)} \in A_j, s^{(0)} \in A_i]
| + | \forall i, j, \forall s_k, s_m \in A_i, p_{s_k \rightarrow A_j} = p_{s_m \rightarrow A_j} |
| | </math> | | </math> |
| − | |{{EquationRef|3.3}}}} | + | |{{EquationRef|3}}}} |
| | | | |
| − | '''其中，<math> \pi </math>为初始微观状态。'''
| + | 满足这个条件后，我们就可以将<math>A_j</math>中的所有微观状态<math>s_l</math>合并为一个宏观状态<math>A_j</math>，因为它们从其他宏观状态的转入概率是一致的。同样的，我们也可以将<math>A_i</math>中的所有微观状态<math>s_k</math>合并为一个宏观状态<math>A_i</math>，因为这些微观状态<math>s_k</math>（和<math>A_i</math>）到其他宏观状态的转出概率是一致的。 |
| | | | |
| − | 这些公式描述了：
| + | 例如，在下图中，<math>s_1</math>和<math>s_2</math>都属于<math>A_1</math>，它们到<math>A_1</math>和<math>A_1</math>的转移概率是一样的；同样，<math>s_3</math>和<math>s_4</math>都属于<math>A_2</math>，它们到宏观状态的转移概率也是一样的。因此，<math>[[1,2], [3, 4]]</math>是<math>P</math>的一个成块划分。 |
| | | | |
| − | # 式子3.1：系统在<math>t=0</math>的微观状态<math>s^{(0)}</math>属于某个宏观状态<math>A_i</math>的概率；
| + | [[文件:成块性充分必要条件.png|居中|700像素|成块性充分必要条件实例]] |
| − | # 式子3.2：已知在<math>t=0</math>的微观状态<math>s^{(0)}</math>属于某个宏观状态<math>A_i</math>，那么在时间<math>t=1</math>的微观状态<math>s^{(1)}</math>属于某个宏观状态<math>A_j</math>的概率；
| |
| − | # 式子3.3：已知历史微观状态<math>\{s^{(0)}, ... , s^{(t-1)} \}</math>对应的宏观状态，那么在时间<math>t</math>的微观状态<math>s^{(t)}</math>属于某个宏观状态<math>A_m</math>的概率；
| |
| | | | |
| − | 回想一下图（1）中 微观状态->微观动力学->粗粒化->宏观状态 的这一条路径。我们现在有了微观动力学<math>\{s^{(0)}, ... , s^{(t-1)} \}</math>，也有了微观到宏观的粗粒化过程<math>A</math>。所以式子（3）描述的lumped process正是先走微观动力学再聚合的这条路径的<math>A^{(t)}</math>。它描述了我们从任意一个初始状态<math>s^{(0)}</math>（或状态分布<math>\pi</math>），一直走微观动力学，然后在<math>t</math>时刻做粗粒化得到<math>A^{(t)}</math>的过程。
| |
| | | | |
| − | 需要注意的是，虽然任意一个状态划分 <math>A</math>都能走这样的路径，并形成lumped process，但不是所有的这些lumped process都是有意义且满足交换律的。他们不一定能够得出一个宏观动力学来描述式子（3）中微观状态的宏观投影，也不一定会拥有马尔科夫性。
| + | 基于这个条件，我们可以定义成块划分的宏观动力学<math>A^{(t)} = A^{(t-1)} P'</math>： |
| | | | |
| − | 我们暂且先不考虑‘失败’的情况，先关注‘成功’的部分。书中接下来就定义了什么叫做lumpable 划分：
| + | '''''定义1'''''：'''成块性的宏观动力学''' |
| | | | |
| − | '''''定义2'''''：'''lumpable partition 划分'''
| + | '''对于给定的微观状态<math>S</math>，微观动力学<math>p_{s_k \rightarrow s_m}</math>和成块的划分 <math>A</math>，宏观动力学<math>p_{A_i \rightarrow A_j}</math>等于<math>A_i</math>中任意状态<math>s_k</math>到<math>A_j</math>的概率：''' |
| − | | |
| − | '''对于一个给定的状态 <math>A</math>，当下列两个条件都满足时，<math>A</math>是一个lumpable partition 划分。'''
| |
| − | | |
| − | # '''定义1中式子(3)描述的lumped process具有马尔科夫性，即式子(3.3)可写成<math>Pr_{\pi} \left [s^{(t)} \in A_m | s^{(t-1)} \in A_k, ... , s^{(1)} \in A_j, s^{(0)} \in A_i \right ] = Pr_{\pi} \left [s^{(t)} \in A_m | s^{(t-1)} \in A_k \right ]</math>'''
| |
| − | # '''转移概率(Transition probability)，即式子(3.3)，对任何微观初始状态(starting vector) <math> \pi </math> 都保持一致'''
| |
| − | | |
| − | [[文件:Lumpable和non-lumpable的例子.png|缩略图|图3：对lumpable和non-lumpable矩阵做粗粒化|替代=|600x600像素]]不满足上述两个条件的，都不被定义为lumpable partition。也就是说，不是所有的lumped process都是lumpable的，即使他们的命名方式相似。
| |
| − | | |
| − | | |
| − | | |
| − | 从图3的lumpable例子中，我们看到对于分组矩阵<math>\Phi = \left ( \begin{array}{cc} 1 & 0 \\ 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{array} \right )</math>，lumpable的动力学TPM可以找到一个lumped process，而这个lumped process是满足马尔可夫性，且对所有初始状态都保持一致的。也就是说，无论<math>s^{(t)}</math>是什么，<math>\{ s^{(t)}, s^{(t+1)} \}</math>投影到宏观空间上的<math>\{ A^{(t)}, A^{(t+1)} \}</math>的<math> P( A^{(t+1)} | A^{(t)} )</math>都保持一致。
| |
| − | | |
| − | <br />
| |
| − | | |
| − | 对于例子中的non-lumpable矩阵，我们或许可以给它强制定义一个lumped process的TPM，比如<math> P_1' = \left ( \begin{array}{cc} 0.6 & 0.4 \\ 0.2 & 0.8 \\ \end{array} \right )</math>，但这个lumped process并不能对任何微观初始状态保持一致，只能对<math>s^{(t)} = \pi = \left [ \begin{array}{cc}1 & 0 & 0 & 0 \end{array} \right ]</math>适用。
| |
| − | | |
| − | 而<math>s^{(t)} = \pi = \left [ \begin{array}{cc}0 & 1 & 0 & 0 \end{array} \right ]</math>不适用这个lumped process。它适用的是<math> P_2' = \left ( \begin{array}{cc} 0.5 & 0.5 \\ 0.2 & 0.8 \\ \end{array} \right )</math>。这里的不适用是指，这个lumped process不能描述这个<math>\pi</math>为初始状态出发的微观状态序列投影的宏观状态序列。
| |
| − | | |
| − | 我们看到，对于这个分组矩阵<math>\Phi = \left ( \begin{array}{cc} 1 & 0 \\ 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{array} \right )</math>，马尔科夫矩阵有两个lumped process <math> P_1'</math>和<math> P_2'</math>，而它们各自只适用于一些微观初始状态(starting vector) <math> \pi </math>，并不满足定义2中的条件，所以<math>A</math>对于这个TPM来说不是一个lumpable partition。事实上，这个TPM只存在一个lumpable partition，就是不做任何的分组，所以它无法按照lumpability的定义进行粗粒化。
| |
| − | | |
| − | | |
| − | | |
| − | | |
| − | ===lumpable partition的充分必要条件===
| |
| − | | |
| − | 通过上面的例子，我们可以对lumpable partition有一些直观的理解。我们可以留意到，在lumpable partition中，有两个分组，所以有四个框。每一个框里，每一列相加的和都是一样的，比如左上角的框中，<math>0.3 + 0.3 = 0.2 + 0.4</math>。这就是lumpable partition更通俗的解释，在某些文献中，并不会使用上面提及的定义，而是直接使用这个通俗版的解释。<ref name=":3" />中作者指出，这两者之间是存在充分必要条件关系的。
| |
| − | | |
| − | 设<math>p_{s_k \rightarrow s_m} = p(s^{(t)} = s_m | s^{(t-1)} = s_k)</math>，<math>p_{s_k \rightarrow A_i} = p(s^{(t)} \in A_i | s^{(t-1)} = s_k) = \sum_{s_m \in A_i} p_{s_k \rightarrow s_m}</math>，<math>p_{A_i \rightarrow A_j} = p(A^{(t)} = A_j | A^{(t-1)} = A_i)</math>
| |
| − | | |
| − | 作者提出了判断一个马尔科夫链对'''给定partition <math>A</math>''' 是否lumpable的充分必要条件为：
| |
| − | | |
| − | '''''定理1：'''''
| |
| − | | |
| − | '''给定partition <math>A</math>是lumpable的充分必要条件为：'''
| |
| − | | |
| − | '''对于任意一对<math>A_i, A_j</math>，每一个属于<math>A_i</math>的状态<math>s_k</math>的<math>p_{s_k \rightarrow A_j}</math>都是一样的。'''
| |
| − | | |
| − | | |
| − | | |
| − | 顺着这个条件，我们也能对lumpable partition，定义宏观动力学<math>\{A^{(0)}, ... , A^{(t-1)} \}</math>了：
| |
| − | | |
| − | '''''定义3'''''：'''lumpability的宏观动力学'''
| |
| − | | |
| − | '''对于给定的微观状态<math>S</math>，微观动力学<math>p_{s_k \rightarrow s_m}</math>和lumpable partition <math>A</math>，宏观动力学<math>p_{A_i \rightarrow A_j}</math>等于<math>A_i</math>中任意状态<math>s_k</math>到<math>A_j</math>的概率：''' | |
| | | | |
| | {{NumBlk|:| | | {{NumBlk|:| |
| 第219行： |
第156行： |
| | |{{EquationRef|4}}}} | | |{{EquationRef|4}}}} |
| | | | |
| − | 这个公式表达的是，群组<math>A_i</math>到群组<math>A_j</math>的转移概率 = 群组<math>A_i</math>中任意状态<math>s_k</math>到群组<math>A_j</math>的转移概率 = 群组<math>A_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>A_i</math>中任意状态<math>s_k</math>到群组<math>A_j</math>中的所有状态的转移概率之和。 |
| − | | |
| − | 对于lumpable partition <math>A</math>定义宏观动力学后，我们就能走另外一条路径了：微观状态->粗粒化->宏观动力学->宏观状态。
| |
| − | | |
| − | | |
| − | | |
| − | '''必要性部分的证明：'''
| |
| − | | |
| − | 必要性是指，如果一个马尔可夫链的partition <math>A</math>是lumpable，那么就肯定会满足上述的这个特定条件。
| |
| − | | |
| − | 从lumpable partition 的定义可知，<math>A</math>的转移概率满足宏观马尔可夫性，且这个转移概率<math>Pr_{\pi} [ s^{(1)} \in A_j | s^{(0)} \in A_i ]</math>对每个<math>\pi</math>保持一致，即在<math>t=0</math>时无论从哪个具体的初始状态<math>\pi</math>开始，只要它属于<math>A_i</math>这个群组里，在<math>t=1</math>时刻转移到<math>A_j</math>的概率都相同。
| |
| − | | |
| − | 我们设这个（<math>A_i</math>中任意微观状态<math>s_k</math>的）共同的转移概率为<math>\hat{p}_{A_i \rightarrow A_j}</math>。当初始状态<math>\pi</math>属于某个<math>A_i</math>时（<math>\pi \in A_i</math>），<math>p_{s_k \rightarrow A_j} = Pr_{\pi \in A_i} [ s^{(1)} \in A_j ] = \hat{p}_{A_i \rightarrow A_j}</math>。
| |
| − | | |
| − | 所以，这说明了，如果一个马尔可夫链的lumped process满足lumpability，那么从任一集合到另一集合的转移概率必须是集合间的固定值，而与集合内的具体状态（不管是<math>\pi</math>还是<math>s_k</math>）无关。这个固定值就是式子（4）定义的宏观状态转移概率，所以满足了该条件。
| |
| − | | |
| − | '''充分性部分的证明：'''
| |
| − | | |
| − | 充分性是指，如果一个马尔可夫链的某个partition <math>A</math>满足这个条件，那么它就是lumpable。我们要证明的是，如果上述条件满足，那么马尔可夫性成立，即对于任何给定的<math>t</math>，转移概率<math>Pr \left [ s^{(t)} \in A_j | s^{(t-1)} \in A_i, \ldots, s^{(1)} \in A_k, s^{(0)} \in A_m \right ]</math>只依赖于<math>A_i</math>和<math>A_j</math>，而不依赖于<math>A_i</math>中的具体状态或是<math>t-1</math>前的宏观状态。
| |
| − | | |
| − | 条件要求所有<math>s_k \in A_i</math>，转移概率<math>p_{s_k \rightarrow A_j} = p_{A_i \rightarrow A_j}</math>，这意味着无论我们从<math>A_i</math>中的哪个微观状态转移过来，转移到<math>A_j</math>的概率都是相同的。
| |
| − | | |
| − | 因此，当我们知道<math>t-1</math>的宏观状态是<math>A_i</math>时，我们计算<math>t</math>时刻转移到<math>A_j</math>的概率时，只需要用<math>p_{A_i \rightarrow A_j}</math>，而不需要关心<math>A_i</math>中的具体状态。
| |
| − | | |
| − | 由于转移概率只依赖于群组<math>A_i</math>和<math>A_j</math>，而不依赖于<math>A_i</math>中的具体状态，因此我们可以将<math>A_i</math>中的所有状态合并为一个状态，并且这个合并后的链仍满足马尔可夫性。所以，上述条件为lumpability的充分条件。
| |
| − | | |
| − | | |
| − | | |
| − | 从这两个证明里，我们也能看到微观动力学的路径和宏观动力学的路径的一致性。无论我们从<math>A_i</math>中的哪个具体状态<math>s^{(t-1)}</math>开始，只要我们知道当前的宏观状态是<math>A_i</math>，我们就可以计算下一步转移到<math>A_j</math>的概率，而不依赖于<math>s^{(t-1)}</math>。这表明，微观<math>s^{(t-1)}</math>->宏观<math>A^{(t-1)}</math>->宏观动力学-><math>A^{(t)}</math>不会影响未来状态的预测，因此从<math>s^{(t-1)}</math>出发的两个路径得出的<math>A^{(t)}</math>的概率是一致的。
| |
| − | | |
| − | | |
| | | | |
| − | '''请注意'''：lumpability有一个非常重要的前提，即我们要给定一个对马尔科夫链的state的partition，然后根据马尔科夫状态转移矩阵来决定这个partition对这个马尔科夫链是否lumpable。 | + | 我们也可以直接定义<math>P</math>和<math>P'</math>之间的关系： |
| | | | |
| − | 所以，lumpability并不是一个马尔科夫链的特质，而是对马尔科夫链的某个state partition的特质。我们不能直接说某个马尔科夫链是lumpable或non-lumpable，但是我们可以说，对于某个马尔科夫链的某几个状态partition是lumpable或non-lumpable。
| + | <math>P' = \Phi^T P (\Phi^T)^{-1} = \Phi^T P \Phi (\Phi^T \Phi)^{-1}</math>， |
| | | | |
| − | ==Lumpability正例和反例==
| + | 其中，<math>\Phi^T \Phi</math>是一个对角阵，对角线上的元素为每个<math>A_i</math>包括了多少个微观状态的计数，其逆矩阵就是把对角线上的元素全部取倒数。 |
| | | | |
| − | 对于一个马尔科夫链，有些分组partition是lumpable，有些分组是non-lumpable。这里用一个简单的例子提供正例和反例。
| + | 对于一个马尔科夫链，有些分组是成块的，有些分组是不成块的。这里用一个简单的例子提供正例和反例。 |
| | | | |
| | 我们用到的是这样一个转移矩阵： | | 我们用到的是这样一个转移矩阵： |
| 第276行： |
第183行： |
| | ====正例==== | | ====正例==== |
| | | | |
| − | 我们可以看到，123行都是一样的，所以把他们<math>\{s_1, s_2, s_3\}</math>分在一组<math>A_1</math>，并把状态<math>s_4</math>分在另外一组<math>A_2</math>，看起来像是一个合理的正例。 | + | 我们可以看到，123行都是一样的，所以把他们<math>\{s_1, s_2, s_3\}</math>分在一组<math>A_1</math>，并把状态<math>s_4</math>分在另外一组<math>A_2</math>，看起来像是一个合理的正例。接下来我们来计算一下。 |
| − | | |
| − | 接下来我们来计算一下。
| |
| − | | |
| − | 设<math>p_{s_1 \rightarrow s_2} = p(s^{(t)} = s_2 | s^{(t-1)} = s_1)</math>，<math>p_{s_1 \rightarrow A_2} = p(s^{(t)} \in A_2 | s^{(t-1)} = s_1)</math>
| |
| | | | |
| | 第1组<math>A_1</math>的状态<math>s_1</math>到第1组<math>A_1</math>，<math>p_{s_1 \rightarrow A_1} = p_{A_1 \rightarrow A_1} = \sum_{s_m \in A_1} p_{s_1 \rightarrow s_m} = p_{s_1 \rightarrow s_1} + p_{s_1 \rightarrow s_2} + p_{s_1 \rightarrow s_3} = 0.3 \times 3 = 0.9 </math> | | 第1组<math>A_1</math>的状态<math>s_1</math>到第1组<math>A_1</math>，<math>p_{s_1 \rightarrow A_1} = p_{A_1 \rightarrow A_1} = \sum_{s_m \in A_1} p_{s_1 \rightarrow s_m} = p_{s_1 \rightarrow s_1} + p_{s_1 \rightarrow s_2} + p_{s_1 \rightarrow s_3} = 0.3 \times 3 = 0.9 </math> |
| 第300行： |
第203行： |
| | \end{aligned} | | \end{aligned} |
| | </math> | | </math> |
| − |
| |
| | | | |
| | ====反例==== | | ====反例==== |
| | | | |
| − | 现在我们来看一个反例：把状态12分为一组，状态34分为另一组，
| + | 现在我们来看一个反例：把状态12分为一组，状态34分为另一组。同样的，我们来计算一下。这次我们需要对3和4分开计算了。 |
| − | | |
| − | 同样的，我们来计算一下。这次我们需要对3和4分开计算了。
| |
| | | | |
| | 第1组<math>A_1</math>的状态<math>s_1</math>到第1组<math>A_1</math>，<math>p_{s_1 \rightarrow A_1} = p_{A_1 \rightarrow A_1} = \sum_{s_m \in A_1} p_{s_1 \rightarrow s_m} = p_{s_1 \rightarrow s_1} + p_{s_1 \rightarrow s_2} = 0.3 \times 2 = 0.6 </math> | | 第1组<math>A_1</math>的状态<math>s_1</math>到第1组<math>A_1</math>，<math>p_{s_1 \rightarrow A_1} = p_{A_1 \rightarrow A_1} = \sum_{s_m \in A_1} p_{s_1 \rightarrow s_m} = p_{s_1 \rightarrow s_1} + p_{s_1 \rightarrow s_2} = 0.3 \times 2 = 0.6 </math> |
| 第316行： |
第216行： |
| | 第2组<math>A_2</math>的状态<math>s_4</math>到第1组<math>A_1</math>，<math>p_{s_4 \rightarrow A_1} = \sum_{s_m \in A_1} p_{s_4 \rightarrow s_m} = p_{s_4 \rightarrow s_1} + p_{s_4 \rightarrow s_2} = 0.1 \times 2 = 0.2 </math> | | 第2组<math>A_2</math>的状态<math>s_4</math>到第1组<math>A_1</math>，<math>p_{s_4 \rightarrow A_1} = \sum_{s_m \in A_1} p_{s_4 \rightarrow s_m} = p_{s_4 \rightarrow s_1} + p_{s_4 \rightarrow s_2} = 0.1 \times 2 = 0.2 </math> |
| | | | |
| − | 这里我们就能看到，<math>p_{s_3 \rightarrow A_1} \neq p_{s_4 \rightarrow A_1}</math>，当同一组的两个状态<math>s_3</math>和<math>s_4</math>对其他组的转移概率不一样的话，如果我们强行按照这样来分组（也没办法强行，因为我们不知道<math>p_{A_2 \rightarrow A_1} = p_{s_3 \rightarrow A_1}</math>还是<math>p_{A_2 \rightarrow A_1} = p_{s_4 \rightarrow A_1}</math>），假设<math>p_{A_2 \rightarrow A_1} = 0.6</math>，我们会发现这样的粗粒化结果违背了Lumpability一开始的定义<ref name=":3" />（公式(3)），即粗粒化后的'''转移概率对所有的初始微观状态<math>\pi</math>都适用'''。因为当<math>\pi = s_4</math>的时候，<math>p_{A_2 \rightarrow A_1} = 0.6</math>这个转移概率就是错的，即使<math>\pi \neq s_4</math>，任何初始微观状态<math>\pi</math>都会在某时刻<math>n</math>达到<math>s_4</math>并导致转移概率出错。 | + | 这里我们就能看到，<math>p_{s_3 \rightarrow A_1} \neq p_{s_4 \rightarrow A_1}</math>，当同一组的两个状态<math>s_3</math>和<math>s_4</math>对其他组的转移概率不一样的话，如果我们强行按照这样来分组（也没办法强行，因为我们不知道<math>p_{A_2 \rightarrow A_1} = p_{s_3 \rightarrow A_1}</math>还是<math>p_{A_2 \rightarrow A_1} = p_{s_4 \rightarrow A_1}</math>），假设<math>p_{A_2 \rightarrow A_1} = 0.6</math>，我们会发现这样的粗粒化结果违背了成块性一开始的定义<ref name=":1" />（公式(1)），即粗粒化后的'''转移概率对所有的初始微观状态<math>\pi</math>都适用'''。因为当<math>\pi = s_4</math>的时候，<math>p_{A_2 \rightarrow A_1} = 0.6</math>这个转移概率就是错的，即使<math>\pi \neq s_4</math>，任何初始微观状态<math>\pi</math>都会在某时刻<math>n</math>达到<math>s_4</math>并导致转移概率出错。 |
| | | | |
| | | | |
| − | ====一个更复杂的正例====
| |
| | | | |
| − | 三个相同状态的例子可能稍微有点简单，接下来我们来看一个稍微复杂一点的例子：
| + | '''请注意'''：成块性有一个非常重要的前提：我们需要给定一个对马尔科夫链的状态划分，然后根据马尔科夫状态转移矩阵来判断这个划分对这个马尔科夫链是否成块。 |
| | | | |
| − | <math>
| + | 所以，成块性并不是一个马尔科夫链本身的属性，而是对马尔科夫链的某个状态划分的属性。直接说某个马尔科夫链成块或是不成块是不严谨的。相反，我们应该说，对于某个马尔科夫链的某个状态划分是成块或不成块的。然而，为了简略表达，当我们说某个马尔科夫链成块时，我们通常是指它存在某种成块的状态划分。 |
| − | \begin{aligned}
| |
| − | P = P_{s_i \rightarrow s_j} = \left [
| |
| − | \begin{array}{cc:cc}
| |
| − | 0.2 & 0.4 & 0.3 & 0.1 \\
| |
| − | 0.4 & 0.2 & 0.1 & 0.3 \\
| |
| − | \hdashline0.2 & 0.1 & 0.2 & 0.5 \\
| |
| − | 0.1 & 0.2 & 0 & 0.7
| |
| − | \end{array}
| |
| − | \right ]
| |
| − | \end{aligned}
| |
| − | </math>
| |
| | | | |
| − | 对于这个马尔科夫矩阵，<math>\{\{1,2\}, \{3,4\}\}</math>是一个lumpable的分组。分组后的转移矩阵为：
| + | 这一前提也提醒我们，在讨论成块性时，必须明确状态划分的方式。不同的划分方式可能导致不同的结论。一个马尔科夫链可能在某种划分下是成块的，而在另一种划分下则不成块。因此，成块性更多地反映了状态划分与马尔科夫链的适配性，而不是马尔科夫链本身的特性。 |
| − | <math>
| |
| − | \begin{aligned}
| |
| − | P = P_{A_k \rightarrow A_l} = \left [
| |
| − | \begin{array}{c:c}
| |
| − | 0.6 & 0.4 \\
| |
| − | \hdashline0.3 & 0.7
| |
| − | \end{array}
| |
| − | \right ]
| |
| − | \end{aligned}
| |
| − | </math>
| |
| | | | |
| | + | <br/> |
| | | | |
| − | ==Lumpability和粗粒化==
| |
| | | | |
| − | 我们在粗粒化的部分提到了，马尔科夫链的粗粒化不仅要对状态空间做，也要对转移矩阵和概率空间做。
| |
| | | | |
| − | 这三个部分可以同时做，也可以看作为：先对状态空间做，再对转移矩阵和概率空间做；即先对状态做分组，然后再获取对应的粗粒化后的转移矩阵。
| + | ==成块性满足的性质== |
| | | | |
| − | 我们也提到过对状态空间做粗粒化有Hard Partitioning和Soft Partitioning两种。Soft Partitioning可以看作把微观状态打散重构成了一些宏观状态，而Hard Partitioning则是更严格的，把若干个微观状态分成一个组。
| + | 成块性作为一种较为严格的划分方式，虽然在压缩维度上可能不如其他方法显著，但它能够保留在宏观层面上所有有用的信息，并且确保粗粒化前后过程的一致性。 |
| | | | |
| − | 而Lumpability就是一个指标，用来评价‘对于某一种Hard Partitioning的微观状态分组分案，是否对微观状态转移矩阵lumpable’。
| + | ===宏观最大预测性=== |
| | | | |
| | + | 宏观最大预测性是指，在将微观状态粗粒化为宏观状态后，我们就不再需要微观状态，只用宏观状态就能预测后续的宏观状态。 |
| | | | |
| | + | 具体来说，只需要知道宏观状态<math>A^{(t)}</math>，就可以最大化<math>A^{(t+1)}</math>的预测效果，而微观状态<math>s^{(t+1)}</math>虽然能提供一些额外信息，但是对于预测<math>A^{(t+1)}</math>并无帮助。这意味着条件互信息<math>I(A^{(t+1)}; s^{(t+1)} | A^{(t)}) = 0</math>。宏观动力学不需要任何来自微观状态的修正，就能独立且正确地反映系统在宏观层面上的演化。 |
| | | | |
| − | 不管状态空间按照哪一个Hard Partitioning方案做分类，它都有对应后续的对转移矩阵和概率空间的粗粒化方案（公式(1)和(2)）<ref name=":1" />，其中有些分组满足交换律，有些则不满足。
| + | 尽管成块性划分能够准确预测宏观动力学，但它无法确保像[[计算力学]]中的因果态那样的微观最大预测性。因为在聚类过程中会损失微观状态的信息，使得我们无法辨别某个<math>A^{(t)}</math>具体是哪个微观态<math>s^{(t)}</math>。这个信息的损失是不可逆的，所以从微观粗粒化到宏观之后，就无法再还原到微观了。 |
| | | | |
| − | 其中的某些分组方案lumpable，也有某些分组方案non-lumpable。
| |
| | | | |
| − | 所以，整个链条应该是这样的：
| |
| | | | |
| − | [[文件:粗粒化关系图.png|无框]]
| + | ===成块划分和粗粒化的可交换性=== |
| | | | |
| | + | [[文件:马尔科夫链的粗粒化定义.png|替代=|缩略图|图3：粗粒化图例]] |
| | | | |
| − | 所以，一个满足lumpability的良定义的粗粒化方案应该在原来的两个条件下，再多加两个条件：
| + | 图（3）展示了从某个微观状态<math>s^{(t)}</math>出发，到达下一刻的宏观状态<math>A^{(t+1)}</math>的两条路径<ref name=":7">Coarse graining. ''Encyclopedia of Mathematics.'' URL: <nowiki>http://encyclopediaofmath.org/index.php?title=Coarse_graining&oldid=16170</nowiki></ref>： |
| | + | #先经过微观动力学达到<math>s^{(t+1)}</math>，再进行粗粒化得到<math>A^{(t+1)}</math> |
| | + | #先进行粗粒化得到<math>A^{(t)}</math>，再经过宏观动力学到达<math>A^{(t+1)}</math> |
| | | | |
| − | #粗粒化后的<math>S'</math>和<math>T'</math>要符合马尔科夫链定义；
| + | 如果我们把粗粒化和（宏观/微观）动力学看作是两个算子，那这两个算子的可交换性指的是：无论从哪个微观状态分布出发，走这两条路径得到的<math>A^{(t+1)}</math>的分布是一样的，即，'''<math>s^{(t)} \Phi P' = s^{(t)} P \Phi</math>'''。 |
| − | #满足交换律；
| |
| − | #Hard Partitioning，即存在分组矩阵<math>V_{i, j} = 1\ if\ s_i \in s_j'\ and\ 0\ otherwise</math>；
| |
| − | #<math>V</math>是一个lumpable分组。
| |
| | | | |
| | + | 证明如下： |
| | | | |
| | + | 对于一个成块的<math>P</math>，和它的成块划分<math>\Phi</math>，我们针对<math>\Phi = \left ( \begin{array}{cc} 1 & 0 \\ 0 & 1 \\ 0 & 1 \\ 0 & 1 \end{array} \right )</math>的例子，其他情况类似。 |
| | | | |
| | + | 对于这个<math>\Phi</math>，我们知道<math>P_{11}=A_{11}</math>，<math>P_{12}+P_{13}+P_{14}=A_{12}</math>，<math>P_{21}=P_{31}=P_{41}=A_{21}</math>，<math>P_{22}+P_{23}+P_{24}=P_{32}+P_{33}+P_{34}=P_{42}+P_{43}+P_{44}=A_{22}</math>。 |
| | | | |
| − | ==Lumpable Partition粗粒化的一致性Consistency== | + | 由于<math>A_{21}</math>和<math>A_{22}</math>的等于关系，<math>P \Phi = \left ( \begin{array}{cc} P_{11}' & P_{12}' \\ P_{21}' & P_{22}' \\ P_{21}' & P_{22}' \\ P_{21}' & P_{22}' \end{array} \right )</math>。这相当于将<math>P</math>的每一行按照划分进行加总，而<math>P \Phi</math>中同一组的行是相同的。 |
| | | | |
| − | 这一小节里我们讨论一下，对一个马尔科夫链的'''lumpable partition''' 与 HOM（Higher-order Macronodes，详情请参考[[复杂网络中的因果涌现]]），和Consistency之间的关联。
| + | 另一方面，<math>\Phi P'</math>的含义是将<math>P'</math>的每一行按照<math>\Phi</math>复制到对应的微观状态的行中。所以，我们会发现<math>\Phi P'</math>和<math>P \Phi</math>的结果是一样的。 |
| | | | |
| | | | |
| | | | |
| − | Higher-order Macronodes，是由Jian Xu<ref>J. Xu, T. L. Wickramarathne, and N. V. Chawla， 'Representing higher-order dependencies in networks,' Science Advances, vol. 2, Article ID el600028, 2016.a</ref>提出，根据给定的微观马尔科夫链和节点的聚类方案，得出一个和微观转移矩阵保持一致的宏观转移矩阵的方法。
| + | ===一致性Consistency=== |
| | | | |
| − | 我们这里使用一个简单的lumpable partition例子，来显示lumpability的粗粒化跟HON是对应的。
| + | 这一小节里讨论马尔科夫链的成块划分 与 HOM（Higher-order Macronodes，详情请参考[[复杂网络中的因果涌现]]）之间的关系，以及它们与一致性的联系。 |
| | | | |
| − | [[文件:Lumpability例子示意图.png|缩略图|图4：例子示意图|替代=]] | + | 以下关于[[动力学的一致性检验]]的描述节选自[[复杂网络中的因果涌现]]： |
| | | | |
| − | <math> | + | 定义微观网络<math>G </math>与宏观网络<math>G_M </math>，分别在两个网络上进行[[随机游走]]。在某个时间<math>t</math>，<math>G</math>上的预期分布为<math>P_m(t)</math>，而<math>G_M </math>上的预期分布为 <math>P_M(t)</math>。 |
| − | \begin{aligned}
| |
| − | P = P_{s_i \rightarrow s_j} = \left [
| |
| − | \begin{array}{c:c:cc:c:c}
| |
| − | 0 & 0 & 0.3 & 0.1 & 0.6 & 0\\
| |
| − | \hdashline
| |
| − | 0 & 0 & 0.2 & 0.3 & 0 & 0.5\\
| |
| − | \hdashline
| |
| − | 0 & 0 & 0 & 0.7 & 0.2 & 0.1\\
| |
| − | 0 & 0 & 0.7 & 0 & 0.2 & 0.1\\
| |
| − | \hdashline
| |
| − | 1.0 & 0 & 0 & 0 & 0 & 0\\
| |
| − | \hdashline
| |
| − | 0 & 1.0 & 0 & 0 & 0 & 0\\
| |
| − | \end{array}
| |
| − | \right ]
| |
| − | \end{aligned}
| |
| − | </math> | |
| | | | |
| − | 对于这个转移概率矩阵，<math>\{1, 2, \{34\}, 5, 6\}</math>是一个lumpable partition。
| + | 将<math>P_m(t) </math>分布叠加到宏观宏观<math>G_M </math>的相同节点上，得到<math>P_{M|m}(t) </math>分布。通过计算<math>P_M(t) </math>和<math>P_{M|m}(t) </math>之间的KL散度来衡量其不一致性（inconsistency）。如果结果为零，则表示动力学一致。公式如下： |
| | | | |
| | + | <math>inconsistency=\sum_{t=0}^T D_{KL}[P_M(t)||P_{M|m}(t)]</math> |
| | | | |
| | + | 也就是说，不一致性 表示了 宏观和微观网络节点在不同时刻的概率分布的[[KL散度]]之和。 |
| | | | |
| − | 首先，我们先按照lumpability的粗粒化定义，计算对应的宏观转移概率：
| + | 我们在[[马尔科夫链的成块性]]中推导了结论：'''基于成块性划分的粗粒化方法构建的宏观网络与微观网络是一致的。''' |
| − | <math>
| |
| − | \begin{aligned}
| |
| − | \left [
| |
| − | \begin{array}{c:c:c:c:c}
| |
| − | 0 & 0 & 0.4 & 0.6 & 0\\
| |
| − | \hdashline
| |
| − | 0 & 0 & 0.5 & 0 & 0.5\\
| |
| − | \hdashline
| |
| − | 0 & 0 & 0.7 & 0.2 & 0.1\\
| |
| − | \hdashline
| |
| − | 1.0 & 0 & 0 & 0 & 0\\
| |
| − | \hdashline
| |
| − | 0 & 1.0 & 0 & 0 & 0\\
| |
| − | \end{array}
| |
| − | \right ]
| |
| − | \end{aligned}
| |
| − | </math>
| |
| − | | |
| − | | |
| − | | |
| − | 然后，我们来简单介绍一下的构建宏观HOM转移概率矩阵的计算方法。
| |
| − | | |
| − | 在图4中，我们看到3和4为待合并节点<math>A</math>。
| |
| − | | |
| − | 1. 对于其他节点到待合并节点<math>A</math>的连边，即待合并节点的入流（图4中绿色的连边），我们直接加和即可，即<math>p_{s_1 \rightarrow A} = 0.3+0.1=0.4</math>，<math>p_{ s_2 \rightarrow A} = 0.2+0.3=0.5</math>
| |
| − | | |
| − | 2. 对于待合并节点<math>A</math>到其他节点的连边，即待合并节点的出流（图4中棕色的连边），我们需要考虑三种情况：
| |
| − | #当待合并节点<math>A</math>间存在连边时；
| |
| − | #当待合并节点<math>A</math>指向同一个输出节点时；
| |
| − | #当待合并节点<math>A</math>指向不同输出节点时；
| |
| − | | |
| − | 待合并节点<math>A</math>的出流的计算方式都不一样，如图5所示。
| |
| − | | |
| − | [[文件:网络节点边权合并示意图.png|替代=|411x411像素]] | |
| | | | |
| − | '''但是'''，我们可以注意到，这三种计算方式都是待合并节点<math>A</math>中的各节点的出流的<math>W_i^{out}</math>加权，而我们知道，lumpability的特性决定了，群组里的各节点到其他群组的出流<math>W_i^{out}</math>都是一样的，对相同的<math>W_i^{out}</math>做任意加权平均的结果都等于<math>W_i^{out}</math>。也就是说，任意的加权方法对于lumpable partition来说都能得出相同的结果。
| |
| | | | |
| − | 由此，我们总结，'''lumpable partition的聚合方式和HOM的计算方式，无论入流还是出流都完全一致。'''
| |
| | | | |
| | | | |
| | | | |
| − | 我们得出这个结论的目标是，借助HOM方法的consistency的性质，说明lumpable partition的聚合方式，也有consistency的性质。
| |
| | | | |
| − | 以下关于'''网络动力学的一致性'''的描述节选自[[复杂网络中的因果涌现]]：
| + | ==成块性和粗粒化== |
| | | | |
| − | 定义微观网络<math>G </math>与宏观网络<math>G_M </math>，在两个网络上[[随机游走]]，在未来某个时间<math>t </math> ， <math>G </math>上的预期分布为 <math>P_m(t) </math>， <math>G_M </math>上的预期分布为 <math>P_M(t) </math>。
| + | ===基于成块性的粗粒化方法（未给定成块的划分的情况）=== |
| | | | |
| − | 将<math>P_m(t) </math>分布叠加到宏观上<math>G_M </math>的相同节点上，得到<math>P_{M|m}(t) </math>分布。用<math>P_M(t) </math>和<math>P_{M|m}(t) </math>之间的KL散度来衡量其不一致性（inconsistency），若结果为零则动力学一致。公式为：
| + | 从前面的成块性公式（2）和例子中，我们可以直观地理解：当马尔科夫矩阵存在块状结构，或者状态明显可以被划分为几类时，根据这样的划分，该矩阵就是成块的。对于简单的<math>P</math>，如图6中的<math>\bar{P}</math>所示，我们能够根据上面的定理（1）很快的找出它的成块划分<math>\Phi</math>，并通过定义（3）迅速计算出对应的<math>P'</math>。 |
| | | | |
| − | <math>inconsistency=\sum_{t=0}^T D_{KL}[P_M(t)||P_{M|m}(t)]</math>
| + | [[文件:Lump fig1.png|缩略图|398x398像素|图6：Zhang<ref name=":4" /> 文章中的示意图。图中左面四个矩阵都是成块的马尔科夫矩阵，而右面的P_2是一个噪声矩阵，(P_1)^T P_2 = 0|替代=]] |
| | | | |
| − | 也就是说，Inconsistency 等于 宏观和微观网络节点在不同时刻的概率分布的[[KL散度]]之和。
| + | 然而，在实际应用中，我们经常遇到的矩阵可能并不完美。例如，成块的矩阵的状态排序可能被打乱（如图（6）中的<math>P_1</math>），或者矩阵包含了如<math>P_2</math>的噪声（如图6中的<math>P</math>，<math>P = P_1 + P_2</math>，<math>P_1^TP_2 = 0</math>）。 |
| | | | |
| − | 实验发现，对不同节点规模以及参数下的微观网络，使用HOM粗粒化后的宏观网络的不一致性随着迭代步数的增加都会收敛到0。这说明，HOM构建的宏观网络和微观网络是保持一致的。
| + | 在这种情况下，我们通常面临的是像<math>P</math>这样的矩阵。我们既无法确定它是否成块，也无法决定它的划分，甚至不知道它的马尔科夫秩。 |
| | | | |
| − | 回到上面lumpable partition 等于HOM的推断，我们就能得出，'''根据lumpability而做的粗粒化，构建的宏观网络和微观网络也是保持一致的。'''
| + | 针对这一问题，Anru Zhang<ref name=":4">Zhang, Anru, and Mengdi Wang. "Spectral state compression of markov processes." ''IEEE transactions on information theory'' 66.5 (2019): 3202-3231.</ref><ref name=":4" />提出了一种寻找最优划分的方法。通过这种方法，我们可以找到最优的划分，并基于这个划分判断一个马尔科夫矩阵是否成块。具体步骤如下： |
| | | | |
| − | | + | #获取一个n*n维的马尔科夫矩阵P，或者是马尔科夫链的频率采样； |
| − | ==基于Lumpability的粗粒化方法（未给定lumpable partition的情况）==
| + | #获取<math>r<n</math> 的马尔科夫秩，或指定一个<math>r</math>； |
| − | | |
| − | [[文件:Lump fig1.png|缩略图|398x398像素|图6：Zhang<ref name=":0" /> 文章中的示意图。图中左面四个矩阵都是lumpable马尔科夫矩阵，而右面的P_2是一个噪声矩阵，(P_1)^T P_2 = 0|替代=]]
| |
| − | | |
| − | 由上面的lumpability公式(4)和例子中我们能获得一个直观上的说法：当马尔科夫矩阵存在block结构，或者状态明显可被分成几类的时候，根据这样的partition，该矩阵就会lumpable，如图6中的<math>\bar{P}</math>所示，把相同的状态（行向量）分成一类的partition显然lumpable。
| |
| − | | |
| − | 但是，有时候有些lumpable的矩阵的状态排序被打乱了（如图6中的<math>P_1</math>），或者矩阵包含了如<math>P_2</math>的噪声（如图6中的<math>P</math>，<math>P = P_1 + P_2</math>，<math>P_1^TP_2 = 0</math>）。
| |
| − | | |
| − | 我们在实际问题中很多时候要面对的是像<math>P</math>这样的矩阵，我们既无法确定它是否lumpable，也无法决定它的partition，我们甚至不知道它的马尔科夫秩。
| |
| − | | |
| − | 在这种情况下，Anru Zhang<ref name=":0" />的文章中提供了一种寻找最优partition的方法。通过此方法我们能找到最优的partition，代入这个partition我们就能通过上面的充分必要条件来决定一个马尔科夫矩阵是否lumpable。具体步骤如下：
| |
| − | | |
| − | #先获取一个n*n维的马尔科夫矩阵P，或者是马尔科夫链的频率采样；
| |
| − | #获取r<n 的马尔科夫秩，或指定一个r；
| |
| | #对P进行SVD分解，<math>P = U \Sigma V^T</math>，其中U为左奇异向量，V为右奇异向量。 | | #对P进行SVD分解，<math>P = U \Sigma V^T</math>，其中U为左奇异向量，V为右奇异向量。 |
| − | #通过下列公式得到最优partition <math>\Omega_1, \Omega_2, ... , \Omega_r</math> | + | #通过下列公式得到最优划分 <math>\Omega_1, \Omega_2, ... , \Omega_r</math> |
| | | | |
| | <math> | | <math> |
| 第497行： |
第312行： |
| | 其中，<math>v_s</math>是第<math>s</math>类<math>\Omega_s</math>的特征向量。 | | 其中，<math>v_s</math>是第<math>s</math>类<math>\Omega_s</math>的特征向量。 |
| | | | |
| − | 这个算法的意思是在最优的partition中，<math>\Omega_s</math>中的状态<math>i</math>的右奇异向量会和<math>v_s</math>距离最小，也就是说，让每个微观态的右特征向量和它对应的宏观态的右特征向量尽可能接近。
| + | 这个算法的核心思想是：在最优的划分中，<math>\Omega_s</math>中的状态<math>i</math>的右奇异向量会和<math>v_s</math>距离最小，也就是说，让每个微观态的右特征向量和它对应的宏观态的右特征向量尽可能接近。 |
| | | | |
| | | | |
| | | | |
| | | | |
| − | 这个看起来非常眼熟，其实它就是在做kMeans聚类算法。让<math>v_s</math>和组里的<math>V[i:r]</math>距离最小的方法，就是让<math>v_s</math>成为<math>V[i:r]</math>这若干个点的中心。
| + | 这个算法看起来非常熟悉，实际上它与 k-Means 聚类算法非常相似。让<math>v_s</math>和组里的<math>V[i:r]</math>距离最小的方法，就是让<math>v_s</math>成为<math>V[i:r]</math>这若干个点的中心。 |
| | | | |
| − | 回顾一下kMeans算法把n个点聚成r类的目标函数，其中第<math>i</math>个点被归到第<math>c^i</math>类，而<math>\mu_j</math>为第<math>j</math>类点的中心点：
| + | 回顾一下k-Means算法把n个点聚成r类的目标函数，其中第<math>i</math>个点被归到第<math>c^i</math>类，而<math>\mu_j</math>为第<math>j</math>类点的中心点： |
| | | | |
| | <math>J(c^1, ... , c^n, \mu_1, ... , \mu_r) = \sum_{i=1}^n || x_i - \mu_{c^i} ||^2 </math> | | <math>J(c^1, ... , c^n, \mu_1, ... , \mu_r) = \sum_{i=1}^n || x_i - \mu_{c^i} ||^2 </math> |
| | | | |
| − | 我们看到这两个目标函数是非常相似的。所以，我们就可以通过上述算法或者kMeans来获取最优partition，然后根据这个partition来判断马尔科夫矩阵的lumpability。
| + | 我们看到这两个目标函数非常相似。因此，我们可以通过上述算法或 k-Means 聚类来获取最优的状态划分，进而判断马尔科夫矩阵的成块性。 |
| − | | |
| − | | |
| | | | |
| | =因果涌现= | | =因果涌现= |