更改

[[马尔科夫链]]是一类特殊的随机过程：在给定当前状态后，对未来状态的预测不再依赖更早的过去状态。一般的[[马尔科夫链]]包括 <math>N</math> 个状态，所有状态之间的概率转移构成一个转移概率矩阵 <math>P</math>。该矩阵有 <math>N</math> 行 <math>N</math> 列，且满足概率归一化条件（所有元素位于 0 到 1 之间，所有行的和为 1）。本词条限定在 '''平稳马尔科夫链''' 上讨论，也就是 [math]P[/math] 不随时间和状态而变。

[[马尔科夫链]]是一类特殊的随机过程：在给定当前状态的信息后，对未来状态的预测不依赖更早的过去状态。对于一个包括 <math>N</math> 个状态的 [[马尔科夫链]]，所有状态之间的概率转移构成一个转移概率矩阵 <math>P</math>。该矩阵有 <math>N</math> 行 <math>N</math> 列，且满足概率归一化条件（所有元素位于 0 到 1 之间，所有行的和为 1）。本词条限定在 '''平稳马尔科夫链''' 上讨论，也就是 [math]P[/math] 不随时间和状态而变。

所谓马尔科夫链的粗粒化，是指找到一个新的马尔科夫链，它具有 <math>1<M<N</math> 个状态，其对应的 <math>M</math> 行 <math>M</math> 列概率转移矩阵为<math>P'</math>。它同样满足概率归一化条件，可以看作对 <math>P</math> 所描述动力学过程的一种抽象近似约简。

所谓马尔科夫链的粗粒化，是指找到一个新的马尔科夫链，它具有 <math>1<M<N</math> 个状态，其对应一个 <math>M</math> 行 <math>M</math> 列概率转移矩阵 <math>P'</math>。它同样满足概率归一化条件，可以看作对 <math>P</math> 所描述动力学过程的一种近似的抽象、聚合和约简。

# 当我们研究一个状态极多的[[复杂系统]]时，往往并不会关注每一个微观状态。在粗粒化中，我们希望过滤掉不感兴趣的噪声和异质性，从微观尺度中总结出一些中尺度或宏观尺度的规律；

# 当我们研究一个状态极多的[[复杂系统]]时，往往不能关注每一个微观状态。在粗粒化中，我们希望过滤掉微观尺度中不感兴趣的噪声和异质性，从中总结出一些中尺度或宏观尺度的规律；

# 有些状态的转移概率非常相似，所以可以被看成同一类状态。对这些状态进行划分和归并可以减少马尔科夫链的冗余性，得到一个更简洁有效的表示；

# 有些状态的转移概率非常相似，所以可以被看成同一类状态。对这些状态进行划分和归并可以减少马尔科夫链的冗余性，得到一个更简洁有效的表示；

# 在用到[[马尔科夫决策过程]]的[[强化学习]]算法中，对马尔科夫链做粗粒化可以减少[[状态空间]]的大小，提高训练过程的样本效率和任务表现<ref name=":10">Hafner, Danijar, et al. "Mastering atari with discrete world models." arXiv preprint arXiv:2010.02193 (2020).</ref>。

# 在用到[[马尔科夫决策过程]]的[[强化学习]]算法中，对马尔科夫链做粗粒化可以减少[[状态空间]]的大小，提高训练过程的样本效率和任务表现<ref name=":10">Hafner, Danijar, et al. "Mastering atari with discrete world models." arXiv preprint arXiv:2010.02193 (2020).</ref>。

对任意马尔科夫链的转移概率矩阵做约简，都存在无穷多种可能的方法。然而在实际粗粒化过程中，我们必须从这些方法中做筛选，使约简后的矩阵[math]P'[/math]尽可能保留原矩阵的主要特征。为刻画这些特征是否被保留，人们提出了不同的标准，包括：

对任意马尔科夫链的转移概率矩阵做约简，存在无穷多种可能的做法。然而在实际粗粒化过程中，我们必须从这些方法中做筛选，使约简后的矩阵 [math]P'[/math] 尽可能保留原矩阵的主要特征。为刻画这些特征是否被保留，文献中提出了不同的标准。总体原则包括：

# 首先，我们想尽量'''降低'''动力学在压缩后的'''维度'''；

# 首先，我们想尽量'''降低'''动力学在压缩后的'''维度'''；

# 最后，我们希望压缩后的过程和原本的过程尽量'''保持一致'''。

# 最后，我们希望压缩后的过程和原本的过程尽量'''保持一致'''。

对马尔科夫链做粗粒化并没有统一定义，目前该主题也没有完整的文献综述。在许多文献中，粗粒化（coarse-graining）、聚类/聚合（partitioning/lumping/clustering/aggregation）和降维（dimension reduction）往往是重叠乃至近似等价的。

对马尔科夫链做粗粒化并没有统一定义，目前该主题也没有完整的文献综述。在许多文献中，粗粒化（coarse-graining）、聚类/聚合（partitioning/lumping/clustering/aggregation）和降维（dimension reduction）往往是重叠乃至近似等价的。

本词条只讨论离散时间马尔科夫链，且动力学 <math>P</math> 是时齐（不随时间变化）的，不讨论连续马尔科夫过程。我们定义微观状态空间为<math>S=\{s_1, s_2, ... ,s_n\}</math>，微观转移函数<math>P \in \mathcal{R}_{n \times n}</math>是一个大小为 n 的马尔科夫矩阵。同样，粗粒化后的宏观状态空间为<math>S'=\{s'_1, s'_2, ... ,s'_r\}</math>，宏观转移函数<math>P' \in \mathcal{R}_{r \times r}</math>。

本词条只讨论离散时间马尔科夫链，且动力学 <math>P</math> 是时齐（不随时间变化）的，不讨论连续马尔科夫过程。我们定义微观状态空间为<math>S=\{s_1, s_2, ... ,s_n\}</math>，微观转移函数<math>P \in \mathcal{R}_{n \times n}</math>是一个大小为 n 的马尔科夫矩阵。同样，粗粒化后的宏观状态空间为<math>S'=\{s'_1, s'_2, ... ,s'_r\}</math>，宏观转移函数<math>P' \in \mathcal{R}_{r \times r}</math>。多数文献中会出现如图1的定义<ref name=":7" />：

多数文献中会出现如图1的定义<ref name=":7" />：

[[文件:马尔科夫链的粗粒化定义.png|无|图1：马尔科夫链一步状态转移过程与粗粒化过程示意图|缩略图|400x400像素]]

[[文件:马尔科夫链的粗粒化定义.png|无|图1：马尔科夫链一步状态转移过程与粗粒化过程示意图|缩略图|400x400像素]]

# '''划分'''（对状态空间进行粗粒化）：对状态进行分组，得出<math>\Phi</math>，决定 <math>S</math> 空间中的状态要如何被投影到 <math>S'</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）。硬划分是指把若干个微观状态分成一个宏观状态类，且一个微观状态不能同时属于多个宏观状态类；软划分则可能出现一个微观状态同时属于多个宏观类的情况。

马尔科夫链的粗粒化可以分成硬划分（hard partitioning）和软划分（soft partitioning）。硬划分是指把若干个微观状态分成一个宏观状态类，且一个微观状态不能同时属于多个宏观状态类；软划分则可能出现一个微观状态同时属于多个宏观类的情况。

在硬划分的情况下，<math>\Phi_{i, j} = \begin{cases} 1\text{, if}\ s_i \in s_j', \\ 0\text{, otherwise} \end{cases}</math>，即一个表示 <math>i</math> 属于 <math>j</math> 类的零一分组矩阵。如果是软划分，<math>\Phi</math> 则不一定是零一矩阵<ref name=":12" />。

在硬划分的情况下，<math>\Phi_{i, j} = \begin{cases} 1\text{, if}\ s_i \in s_j', \\ 0\text{, otherwise} \end{cases}</math>，即一个表示 <math>i</math> 属于 <math>j</math> 类的零一分组矩阵。如果是软划分，<math>\Phi</math> 则不一定是零一矩阵<ref name=":12" />。

|{{EquationRef|1}}}}

|{{EquationRef|1}}}}

其中 <math>W \in \mathbb{R}^{r \times n}</math>，其中[math]W[/math]的任意元素满足：[math]W_{ij}\geq 0, \forall i,j\in\{1,2,\cdots,n\}[/math]，并要求转换后的[math]P'[/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>，其中 <math>W</math> 的任意元素满足：<math>W_{ij}\geq 0, \forall i,j\in\{1,2,\cdots,n\}</math>，并要求转换后的 <math>P'</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]t[/math] 到 [math]t+1[/math] 时刻的过程<math>P'</math>，可以表达为从图1左上角的[math]t[/math] 时刻宏观状态出发，先经过一个“逆向粗粒化”操作 <math>W</math> 得到[math]t[/math] 时刻微观状态，再经微观动力学 <math>P</math> 得到 [math]t+1[/math] 时刻的微观状态，最后经粗粒化 <math>\Phi</math> 得到 [math]t+1[/math] 时刻的宏观状态。

我们可以这样理解这个公式：宏观状态从 <math>t</math> 到 <math>t+1</math> 时刻的过程 <math>P'</math>，可以表达为从图1左上角的 <math>t</math> 时刻宏观状态出发，先经过一个“逆向粗粒化”操作 <math>W</math> 得到 <math>t</math> 时刻微观状态，再经微观动力学 <math>P</math> 得到 <math>t+1</math> 时刻的微观状态，最后经粗粒化 <math>\Phi</math> 得到 <math>t+1</math> 时刻的宏观状态。

从式子{{EquationRef|1}}可以看到，<math>\Phi</math> 和 <math>P</math> 都是给定的，所以这一步要做的是决定 <math>W</math>。<math>W</math> 的基本限制是使 <math>P'</math> 符合马尔科夫矩阵定义；在此基础上，<math>W</math> 仍有无限多种选项，我们可以从中挑出更符合目标特征的方案。

从式子{{EquationRef|1}}可以看到，<math>\Phi</math> 和 <math>P</math> 都是给定的，所以这一步要做的是决定 <math>W</math>。<math>W</math> 的基本限制是使 <math>P'</math> 符合马尔科夫矩阵定义；在此基础上，<math>W</math> 仍有无限多种选项，我们可以从中挑出更符合目标特征的方案。