812
个编辑
更改
→粗粒化
[[文件:马尔科夫链的粗粒化定义.png|替代=|图1：粗粒化定义]]
[[文件:马尔科夫链的粗粒化定义.png|替代=|图1：粗粒化定义]]
对状态空间<math>S</math>和转移函数<math>P(t):S \rightarrow S</math>，我们需要'''一个投影函数<math>\Phi:S \rightarrow S'</math>'''，和'''一个新的转移函数<math>P'(t):S' \rightarrow S'</math>'''，而且<math>S'</math>和<math>P'</math>要符合马尔科夫链定义。
对状态空间 <math>S</math> 和转移函数 <math>P(t):S \rightarrow S</math>，我们需要'''一个状态分组的投影函数 <math>\Phi:S \rightarrow S'</math>'''，和'''一个在新状态空间上的转移函数 <math>P'(t):S' \rightarrow S'</math>'''，而且 '''<math>S'</math> 和<math>P'</math> 要符合马尔科夫链定义'''。
如果我们对这个降维/粗粒化过程进行分解的话，我们可以看到这个过程可以被分为三步。
# '''划分'''（对状态空间进行粗粒化）：对状态进行分组，决定<math>S</math>空间中的状态要如何被投影到<math>S'</math>空间上，也就是得出<math>\Phi</math>。
# '''划分'''（对状态空间进行粗粒化）：对状态进行分组，得出<math>\Phi</math>，决定 <math>S</math> 空间中的状态要如何被投影到 <math>S'</math> 空间上。
# '''聚合'''（对转移概率进行粗粒化）：基于分组函数<math>\Phi</math>，我们要决定如何把原来的状态转移矩阵<math>P</math>降维成新的<math>P'</math>。
# '''聚合'''（对转移概率进行粗粒化）：基于分组函数 <math>\Phi</math>，我们要决定如何把原来的状态转移矩阵<math>P</math>降维成新的<math>P'</math>。
# 判断粗粒化方案<math>\Phi</math>和<math>P'</math>符合什么样的性质。
# 判断粗粒化方案 <math>\Phi</math> 和 <math>P'</math> 符合什么样的性质。
===划分：对状态空间进行粗粒化===
===划分：对状态空间进行粗粒化===
我们假设投影函数<math>\Phi</math>是一个<math>n \times r</math>的线性投影矩阵，且符合下列两个条件：'''(1)所有元素非负；(2)每行加和等于1。'''
我们假设投影函数 <math>\Phi</math> 是一个 <math>n \times r</math> 的线性投影矩阵，且符合下列两个条件：'''(1)所有元素非负；(2)每行加和等于1。'''
马尔科夫链的粗粒化可以分成硬划分（Hard partitioning）和软划分（Soft partitioning）。硬划分是指把若干个微观状态分成一个宏观状态类，且一个微观状态不能同时属于多个宏观状态类，而软划分则会有可能出现一个微观状态被分在属于多个宏观类的情况。
在硬划分的情况下，<math>\Phi_{i, j} = \begin{cases} 1\text{, if}\ s_i \in s_j', \\ 0\text{, otherwise} \end{cases}</math><ref name=":12" />，即一个表示<math>i</math>属于<math>j</math>列的零一分组矩阵。如果是软划分的话，<math>\Phi</math>则不一定会是零一矩阵。
在硬划分的情况下，<math>\Phi_{i, j} = \begin{cases} 1\text{, if}\ s_i \in s_j', \\ 0\text{, otherwise} \end{cases}</math><ref name=":12" />，即一个表示<math>i</math>属于<math>j</math>列的零一分组矩阵。如果是软划分的话，<math>\Phi</math>则不一定会是零一矩阵。
===聚合：对转移概率进行粗粒化===
===聚合：对转移概率进行粗粒化===
得出<math>\Phi</math>后，对微观马尔科夫矩阵<math>P</math>的降维可以表示为
得出 <math>\Phi</math> 后，对微观马尔科夫矩阵 <math>P</math> 的降维可以表示为
{{NumBlk|:|
{{NumBlk|:|
|{{EquationRef|1}}}}
|{{EquationRef|1}}}}
其中<math>W \in \mathbb{R}^{r \times n}</math>。Buchholz<ref name=":12">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>\Phi \in \mathbb{R}^{n \times r}</math>称作collector matrix。
其中 <math>W \in \mathbb{R}^{r \times n}</math>。Buchholz<ref name=":12">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>\Phi \in \mathbb{R}^{n \times r}</math> 称作collector matrix。
我们假设了<math>W, \Phi, P, P'</math>都是线性的，所以我们可以看到这个公式描述了图1中从左上角的t时刻宏观状态出发，经过逆向粗粒化<math>W</math>得到了t时刻微观状态，走微观动力学<math>P</math>得到了t+1时刻的微观状态，再经粗粒化<math>\Phi</math>得到t+1时刻的宏观状态。
我们假设了<math>W, \Phi, P, P'</math>都是线性的，所以我们可以这样理解这个公式：从图1中从左上角的t时刻宏观状态出发，经过了一个‘逆向粗粒化’操作<math>W</math>，得到了 t 时刻微观状态，走微观动力学 <math>P</math> 得到了 t+1 时刻的微观状态，再经粗粒化 <math>\Phi</math> 得到 t+1 时刻的宏观状态。
式子{{EquationRef|1}}中我们发现，<math>\Phi</math> 和 <math>P</math> 都是给定的，所以我们在这一步要做的是决定 <math>W</math>。<math>W</math> 的基础限制是要使得 <math>P'</math> 符合马尔科夫矩阵定义，所以有无限多种 <math>W</math> 的选项。从这些选项中，我们也能挑出某些符合我们想要的特征的 <math>W</math>。
式子{{EquationRef|1}}中我们发现，<math>\Phi</math>和<math>P</math>都是给定的，所以我们在这一步要做的是决定<math>W</math>。<math>W</math>的基础限制是要使得<math>P'</math>符合马尔科夫矩阵定义，所以有无限多种<math>W</math>的选项。从这些选项中，我们也能挑出某些符合我们想要的特征的<math>W</math>。
<br/>
<br/>
===判断粗粒化方案符合的性质===
==粗粒化方案符合的性质==
最基本的粗粒化方法的约束是要确保粗粒化后的新的<math>S'</math>和<math>T'</math>要符合马尔科夫链定义。除此之外也有一些其他的规则，比如：
最基本的粗粒化方法的约束是要确保粗粒化后的新的<math>S'</math>和<math>T'</math>要符合马尔科夫链定义。除此之外也有一些其他的规则，比如：