集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织

更改

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

2024年10月23日 (三) 23:32的版本

删除325字节 、 2024年10月23日 (星期三)
→‎Lumpability
第113行： 第113行：     
这个概念最早出现在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>中。
 
这个概念最早出现在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的充分必要条件'部分。
    
首先定义<math>s^{(t)}</math>表示系统在<math>t</math>时刻的微观状态，微观状态空间为<math>S=\{s_1, s_2, ... ,s_n\}</math>。
 
首先定义<math>s^{(t)}</math>表示系统在<math>t</math>时刻的微观状态，微观状态空间为<math>S=\{s_1, s_2, ... ,s_n\}</math>。
   −
给定一个state partition <math>A=\{A_1, A_2, ... ,A_r\}</math>，也可以把其理解为宏观的状态空间，<math>S \rightarrow A</math>是Hard Partition的映射关系，定义<math>A^{(t)}</math>表示系统在<math>t</math>时刻的宏观状态。
+
给定一个任意state partition <math>A=\{A_1, A_2, ... ,A_r\}</math>，也可以把其理解为宏观的状态空间。
 +
 
 +
<math>S</math>和<math>A</math>之间的Hard Partition映射关系为：<math>A_i \in S, A_i \neq \empty, A_i \cap A_j = \empty , \forall i, j, \cup_i A_i = S</math>
 +
 
 +
对于任意state partition <math>A=\{A_1, A_2, ... ,A_r\}</math>，我们能够定义一个lumped process，即把微观的动力学轨迹<math>s^{(t)}</math>投影到<math>A</math>的空间上。
   −
对于一个给定的state partition <math>A</math>，当下列公式对任何微观初始状态(starting vector) <math> \pi </math> 都保持一致时，<math>A</math>是一个lumpable partition：
+
这种轨迹的投影可以写作下列公式：
    
{{NumBlk|:|
 
{{NumBlk|:|
第124行： 第132行：  
\begin{aligned}
 
\begin{aligned}
 
&Pr_{\pi}[s^{(0)} \in A_i] \\
 
&Pr_{\pi}[s^{(0)} \in A_i] \\
−
&Pr_{\pi}[s^{(t)} \in A_m | s^{(t-1)} \in A_k, ... ,  s^{(1)} \in A_j,  s^{(0)} \in A_i] = Pr_{\pi}[s^{(t)} \in A_m | s^{(t-1)} \in A_k]
+
&Pr_{\pi}[s^{(1)} \in A_j | s^{(0)} \in A_i] \\
 +
&Pr_{\pi}[s^{(t)} \in A_m | s^{(t-1)} \in A_k, ... ,  s^{(1)} \in A_j,  s^{(0)} \in A_i]
 
\end{aligned}
 
\end{aligned}
 
</math>
 
</math>
 
|{{EquationRef|3}}}}
 
|{{EquationRef|3}}}}
   −
这两个公式描述了：
+
其中，<math> \pi </math>为初始微观状态。
   −
# 系统在时间<math>t</math>的微观状态<math>s^{(t)}</math>属于某个宏观状态<math>A_k</math>的概率；
+
这些公式描述了：
−
# 已知在时间<math>t</math>的微观状态<math>s^{(t)}</math>属于某个宏观状态<math>A_k</math>，那么在时间<math>t+1</math>的微观状态<math>s^{(t+1)}</math>属于某个宏观状态<math>A_m</math>的概率；
  −
# 马尔可夫性。
     −
这两个公式暗示了两种不同的从微观状态到宏观状态的路径：(1) 微观状态->聚类->宏观动力学->宏观状态 和 (2) 微观状态->微观动力学->聚类->宏观状态
+
# 式子3.1：系统在<math>t=0</math>的微观状态<math>s^{(0)}</math>属于某个宏观状态<math>A_i</math>的概率；
 +
# 式子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+1</math>的微观状态<math>s^{(t+1)}</math>属于某个宏观状态<math>A_m</math>的概率；
   −
首先，公式整体可以看作是路径1的宏观动力学，描述了系统的宏观状态的转移概率。
+
回想一下图(1)的交换律。我们现在有了微观动力学，也有了微观到宏观的粗粒化过程。所以式子(3)描述的是 微观状态->微观动力学->粗粒化->宏观状态这一条 路径。
   −
“系统的微观状态<math>s^{(t)}</math>属于<math>A_k</math>”里包含了“系统的宏观状态<math>A^{(t)}</math>等于<math>A_k</math>”这个概念，所以<math>Pr_{\pi}[s^{(t)} \in A_m | s^{(t-1)} \in A_k] = Pr_{\pi}[A^{(t)} = A_m | A^{(t-1)} = A_k]</math>。
+
需要注意的是，虽然任意一个state partition <math>A</math>都能走这样的路径，并形成lumped process。但不是所有的这些lumped process都是有意义且满足交换律的。
   −
同时，这个表达式也表达了，当<math>s^{(t)}</math>属于某个宏观状态<math>A_k</math>时，<math>s^{(t+1)}</math>属于哪个宏观状态的意思。从这个角度来看，它走的是路径2的微观动力学，其中<math>\pi</math>为微观初始状态，<math>\{s^{(0)},\ s^{(1)},\ ...\ ,\ s^{(t)}\}</math>为微观动力学（微观动力学的演化过程在这里被省略了），而<math>s^{(t)} \in A_m</math>代表了从微观状态到宏观状态的聚类过程。
+
书中接下来就定义了什么叫做lumpable partition：
   −
强调考虑所有初始状态<math>\pi</math>的目的是确保这两种路径在任何时间点给出的微观状态和宏观状态之间的关系是一致的。
+
对于一个给定的state partition <math>A</math>，当
   −
无论我们从哪个微观状态<math>s^{(t)}</math>出发，对该<math>s^{(t)}</math>来说，
+
# 式子(3)对任何微观初始状态(starting vector) <math> \pi </math> 都保持一致时，
 +
# 定义<math>A^{(t)} = A(s^{(t)})</math>表示系统在<math>t</math>时刻的宏观状态，<math>\{A^{(0)}, ... , A^{(t-1)} \}</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] = Pr_{\pi}[s^{(t)} \in A_m | s^{(t-1)} \in A_k]</math>时，
   −
<math>
+
<math>A</math>是一个lumpable partition。
−
\begin{aligned}
  −
&Pr_\pi [s^{(t)} \in A_m | s^{(t-1)}\in A_k] \\
  −
&=Pr⁡[A^{(t)} = A_m | A^{(t-1)} = A_k], \forall A_k \in A  \text{（路径1）} \\
  −
&=Pr⁡[s^{(t)}\in A_m | s^{(t-1)}=s_i \in A_k], \forall s_i \in A_k  \text{（路径2）}
  −
\end{aligned}
  −
</math>
     −
无论是走宏观动力学(路径1)还是微观动力学(路径2)，系统的微观状态和宏观状态的对应关系都是相同的，也会以相同的概率到达宏观状态<math>A^{(t+1)}</math>，也就是'''满足了交换律'''。
+
不满足上述两个条件的，都不被定义为lumpable partition。
   −
下一个小节我们会给出反例，说明non-lumpable的情况下，式子(3)并不是对所有的<math>\pi</math>都成立。
         +
===lumpable partition的充分必要条件===
    
作者提出了判断一个马尔科夫链对'''给定partition <math>A=\{A_1, A_2, ... ,A_r\}</math>''' 是否lumpable的充分必要条件为：
 
作者提出了判断一个马尔科夫链对'''给定partition <math>A=\{A_1, A_2, ... ,A_r\}</math>''' 是否lumpable的充分必要条件为：
Liangjh
97

个编辑

取自“https://wiki.swarma.org/index.php/特殊:移动版差异/38885”