“马尔科夫链的粗粒化”的版本间的差异

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索
第1行： 第1行：
 
我们先简单回顾一下马尔科夫矩阵是什么。它是一种square matrix，行列数一样，且满足每一行和为1的条件。
 
我们先简单回顾一下马尔科夫矩阵是什么。它是一种square matrix，行列数一样，且满足每一行和为1的条件。
  
−
而马尔科夫链指的是一个n维的状态的序列[math]\{x_t\ = 1, ..., n\}_{t}[/math]，每一步的状态转换都有马尔科夫矩阵[math]M[/math]决定，即[math]x_{t+1} = M x_t[/math].
+
而马尔科夫链指的是一个n维的状态的序列<math>\{x_t\ = 1, ..., n\}_{t}</math>，每一步的状态转换都有马尔科夫矩阵<math>M</math>决定，即<math>x_{t+1} = M x_t</math>.
  
−
[math]M[/math]的每一行对应的每个状态转移到其他状态的概率。比如当[math]x_t[/math]等于第一个状态的时候，M的第一行展示了[math]x_{t+1}[/math]状态的概率。
+
<math>M</math>的每一行对应的每个状态转移到其他状态的概率。比如当<math>x_t</math>等于第一个状态的时候，M的第一行展示了<math>x_{t+1}</math>状态的概率。
  
 
那对马尔科夫链做粗粒化做粗粒化的意义是什么呢？我们看到文献中着重强调这两点：
 
那对马尔科夫链做粗粒化做粗粒化的意义是什么呢？我们看到文献中着重强调这两点：
第26行： 第26行：
 
这里的秩的意思是，我们能多大程度上压缩信道，使得信息在宽度为秩的信道中无损传递。（笔者个人理解）
 
这里的秩的意思是，我们能多大程度上压缩信道，使得信息在宽度为秩的信道中无损传递。（笔者个人理解）
  
−
在n个离散状态的马尔科夫矩阵中，[math]f_1, ... , f_r, g_1, ... , g_r[/math] 是维度为n的矩阵。
+
在n个离散状态的马尔科夫矩阵中，<math>f_1, ... , f_r, g_1, ... , g_r</math> 是维度为n的矩阵。
  
−
而我们能定义r × r的markov kernel [math]C = \{Cij = \sum_{p=1}^k f_j(k)g_i(k)\}[/math]
+
而我们能定义r × r的markov kernel <math>C = \{Cij = \sum_{p=1}^k f_j(k)g_i(k)\}</math>
  
−
而且[math]f_1, ... , f_r[/math] 为 left Markov features，[math]\{g1, . . . , gr\}[/math] 为 right Markov features.
+
而且<math>f_1, ... , f_r</math> 为 left Markov features，<math>\{g1, . . . , gr\}</math> 为 right Markov features.
  
 
这个定义可以想象成可压缩的程度，也会是下面的hard partitioning的分组的数量。
 
这个定义可以想象成可压缩的程度，也会是下面的hard partitioning的分组的数量。
  
−
Lumpability
+
=Lumpability=
  
 
Lumpability是一种用于分类的定义，笔者暂时还没找到一个正式的中文翻译，而不同文献对于这个概念的解释也有所不同。
 
Lumpability是一种用于分类的定义，笔者暂时还没找到一个正式的中文翻译，而不同文献对于这个概念的解释也有所不同。
第40行： 第40行：
 
这个概念最早出现在Kemeny, Snell 1976. Finite Markov Chains中。书中的定义是这样的
 
这个概念最早出现在Kemeny, Snell 1976. Finite Markov Chains中。书中的定义是这样的
  
−
给定一个partition [math]A=\{A1, A2, ... ,Ar\}[/math]，我们能够用下列公式描述一个粗粒化后的马尔科夫链(lumped process)，且这个转移概率对任何初始状态(starting vector) [math] \pi [/math] 都是一样的：
+
给定一个partition <math>A=\{A1, A2, ... ,Ar\}</math>，我们能够用下列公式描述一个粗粒化后的马尔科夫链(lumped process)，且这个转移概率对任何初始状态(starting vector) <math> \pi </math> 都是一样的：
  
−
[math]
+
<math>
 
Pr_{\pi}[f_0 \in A_i]
 
Pr_{\pi}[f_0 \in A_i]
 
Pr_{\pi}[f_1 \in A_j | f_0 \in A_i]
 
Pr_{\pi}[f_1 \in A_j | f_0 \in A_i]
 
Pr_{\pi}[f_n \in A_t |f_{n-1} \in A_s  f_0 \in A_i]
 
Pr_{\pi}[f_n \in A_t |f_{n-1} \in A_s  f_0 \in A_i]
−
[/math]
+
</math>
 
[[文件:Lump fig1.png|缩略图|398x398像素|图1：Zhang<ref name=":0" /> 文章中的示意图。图中左面四个矩阵都是lumpable马尔科夫矩阵，而右面的P_2是一个噪声矩阵，(P_1)^T P_2 = 0]]
 
[[文件:Lump fig1.png|缩略图|398x398像素|图1：Zhang<ref name=":0" /> 文章中的示意图。图中左面四个矩阵都是lumpable马尔科夫矩阵，而右面的P_2是一个噪声矩阵，(P_1)^T P_2 = 0]]
  
  
−
作者提出了判断一个马尔科夫链对给定partition [math]A=\{A1, A2, ... ,Ar\}[/math]是否lumpable的充分必要条件为
+
作者提出了判断一个马尔科夫链对给定partition <math>A=\{A1, A2, ... ,Ar\}</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]p_{k A_j} = \sum_{s_m \in A_j} p_{k m} = p_{A_i A_j} = p_{k A_j}, k \in A_i[/math]
+
也就是说<math>p_{k A_j} = \sum_{s_m \in A_j} p_{k m} = p_{A_i A_j} = p_{k A_j}, k \in A_i</math>
  
−
直观上来说，当马尔科夫矩阵存在block结构，或者状态明显可被分成几种partition的时候，该矩阵就会lumpable，如图一中的[math]\bar{P}[/math]所示。
+
直观上来说，当马尔科夫矩阵存在block结构，或者状态明显可被分成几种partition的时候，该矩阵就会lumpable，如图一中的<math>\bar{P}</math>所示。
  
−
但是，有时候有些lumpable的矩阵的状态排序被打乱了（如图一中的[math]P_1[/math]），或者矩阵包含了如[math]P_2[/math]的噪声（如图一中的[math]P[/math]，[math]P = P_1 + P_2, P_1^TP_2 = 0[/math]）。
+
但是，有时候有些lumpable的矩阵的状态排序被打乱了（如图一中的<math>P_1</math>），或者矩阵包含了如<math>P_2</math>的噪声（如图一中的<math>P</math>，<math>P = P_1 + P_2, P_1^TP_2 = 0</math>）。
  
−
我们在实际问题中很多时候要面对的是像[math]P[/math]这样的矩阵，我们既无法确定它是否lumpable，也无法决定它的partition，我们甚至不知道它的马尔科夫秩。
+
我们在实际问题中很多时候要面对的是像<math>P</math>这样的矩阵，我们既无法确定它是否lumpable，也无法决定它的partition，我们甚至不知道它的马尔科夫秩。
  
 
在这种情况下，Anru Zhang<ref name=":0" />的文章中提供了一种寻找最优partition的方法，通过此方法我们能找到最优的partition，代入这个partition我们就能通过上面的充分必要条件来决定一个马尔科夫矩阵是否lumpable。具体步骤如下：
 
在这种情况下，Anru Zhang<ref name=":0" />的文章中提供了一种寻找最优partition的方法，通过此方法我们能找到最优的partition，代入这个partition我们就能通过上面的充分必要条件来决定一个马尔科夫矩阵是否lumpable。具体步骤如下：
第66行： 第66行：
 
#先获取一个n*n维的马尔科夫矩阵P，或者是马尔科夫链的频率采样；
 
#先获取一个n*n维的马尔科夫矩阵P，或者是马尔科夫链的频率采样；
 
#获取r<n 的马尔科夫秩，或指定一个r；
 
#获取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
+
#通过下列公式得到最优partition<math>
 +
\Sigma_1, \Sigma_2, ... , \Sigma_r
 +
</math>
 
#
 
#
 +
 +
<math>
 +
\Sigma_1, \Sigma_2, ... , \Sigma_r = argmin_{\Sigma_1, \Sigma_2, ... , \Sigma_r} min_{v_1, v_2, ... , v_r} \sum_{s=1}^r \sum_{i \in \Sigma_s} || V[i:r] - v_s ||_2^2
 +
</math>
 +
 +
其中，<math>v_s</math>是第s类<math>\Sigma_s</math>的特征向量。
 +
 +
这个算法的意思是在最优的partition中，<math>\Sigma_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>这若干个点的中心。
 +
 +
回顾一下Kmeans算法把n个点聚成r类的损失函数：
 +
 +
<math>J(c^1, ... , c^n, \mu_1, ... , \mu_r) = \sum_{i=1}^n || x_i - \mu_{c^i} ||^2 </math>
 +
 +
其中，第<math>i</math>个点被归到第<math>c^i</math>类，而<math>\mu_j</math>为第<math>\j</math>类点的中心点。
 +
 +
（注：文章中并没有提到可以用KMeans来实现这个算法，但笔者认为它们是等价的）
 +
 +
 +
 +
所以，我们就可以通过上述算法或者kMeans来获取最优partition，然后根据这个partition来判断马尔科夫矩阵的lumpability。
 +
 +
  
  

2024年8月27日 (二) 17:22的版本

我们先简单回顾一下马尔科夫矩阵是什么。它是一种square matrix，行列数一样，且满足每一行和为1的条件。

而马尔科夫链指的是一个n维的状态的序列[math]\displaystyle{ \{x_t\ = 1, ..., n\}_{t} }[/math]，每一步的状态转换都有马尔科夫矩阵[math]\displaystyle{ M }[/math]决定，即[math]\displaystyle{ x_{t+1} = M x_t }[/math].

[math]\displaystyle{ M }[/math]的每一行对应的每个状态转移到其他状态的概率。比如当[math]\displaystyle{ x_t }[/math]等于第一个状态的时候，M的第一行展示了[math]\displaystyle{ x_{t+1} }[/math]状态的概率。

那对马尔科夫链做粗粒化做粗粒化的意义是什么呢？我们看到文献中着重强调这两点：

  1. 有些状态的转移概率非常相似，所以可以被看成同一类状态，对这种马尔科夫链做partitioning可以减少系统表示的冗余性；
  2. 在用到马尔科夫决策过程的强化学习里，对马尔科夫链做粗粒化可以减少状态空间的大小，提高训练效率。

马尔科夫链的粗粒化可以分成Hard partitioning和Soft partitioning。Hard partitioning是指把若干个微观状态分成一个宏观状态类，且一个微观状态不能同时属于多个宏观状态类，而soft partitioning则会有可能出现这种情况。

我们这里主要讨论hard partitioning，主要参考的是Anru Zhang和Mengdi Wang的Spectral State Compression of Markov Processes[1]。

首先讨论的是一个马尔科夫矩阵的rank秩。

大家理解的线代里的rank秩的定义是看矩阵中的线性无关的行向量的数量，但是这里对秩的理解是从一种类似于信道的概念。

秩的定义为我们能找到的一组概率密度函数 [math]\displaystyle{ f_1, ... , f_r, g_1, ... , g_r }[/math]，使得r在下列公式里最小：

[math]\displaystyle{ P(X_{t+1} | X_{t}) = \sum^r_{k=1} f_k(X_t) g_k(X_{t+1}) }[/math]

这里的秩的意思是，我们能多大程度上压缩信道，使得信息在宽度为秩的信道中无损传递。（笔者个人理解）

在n个离散状态的马尔科夫矩阵中，[math]\displaystyle{ f_1, ... , f_r, g_1, ... , g_r }[/math] 是维度为n的矩阵。

而我们能定义r × r的markov kernel [math]\displaystyle{ C = \{Cij = \sum_{p=1}^k f_j(k)g_i(k)\} }[/math]

而且[math]\displaystyle{ f_1, ... , f_r }[/math] 为 left Markov features，[math]\displaystyle{ \{g1, . . . , gr\} }[/math] 为 right Markov features.

这个定义可以想象成可压缩的程度，也会是下面的hard partitioning的分组的数量。

Lumpability

Lumpability是一种用于分类的定义，笔者暂时还没找到一个正式的中文翻译，而不同文献对于这个概念的解释也有所不同。

这个概念最早出现在Kemeny, Snell 1976. Finite Markov Chains中。书中的定义是这样的

给定一个partition [math]\displaystyle{ A=\{A1, A2, ... ,Ar\} }[/math]，我们能够用下列公式描述一个粗粒化后的马尔科夫链(lumped process)，且这个转移概率对任何初始状态(starting vector) [math]\displaystyle{ \pi }[/math] 都是一样的：

[math]\displaystyle{ Pr_{\pi}[f_0 \in A_i] Pr_{\pi}[f_1 \in A_j | f_0 \in A_i] Pr_{\pi}[f_n \in A_t |f_{n-1} \in A_s f_0 \in A_i] }[/math]

图1：Zhang[1] 文章中的示意图。图中左面四个矩阵都是lumpable马尔科夫矩阵，而右面的P_2是一个噪声矩阵，(P_1)^T P_2 = 0


作者提出了判断一个马尔科夫链对给定partition [math]\displaystyle{ A=\{A1, A2, ... ,Ar\} }[/math]是否lumpable的充分必要条件为

对于任意一对[math]\displaystyle{ A_i, A_j }[/math]，每一个属于[math]\displaystyle{ A_i }[/math]的状态[math]\displaystyle{ s_k }[/math]的[math]\displaystyle{ p_{kA_j} }[/math]都是一样的。

也就是说[math]\displaystyle{ p_{k A_j} = \sum_{s_m \in A_j} p_{k m} = p_{A_i A_j} = p_{k A_j}, k \in A_i }[/math]

直观上来说，当马尔科夫矩阵存在block结构，或者状态明显可被分成几种partition的时候，该矩阵就会lumpable，如图一中的[math]\displaystyle{ \bar{P} }[/math]所示。

但是，有时候有些lumpable的矩阵的状态排序被打乱了（如图一中的[math]\displaystyle{ P_1 }[/math]），或者矩阵包含了如[math]\displaystyle{ P_2 }[/math]的噪声（如图一中的[math]\displaystyle{ P }[/math]，[math]\displaystyle{ P = P_1 + P_2, P_1^TP_2 = 0 }[/math]）。

我们在实际问题中很多时候要面对的是像[math]\displaystyle{ P }[/math]这样的矩阵，我们既无法确定它是否lumpable，也无法决定它的partition，我们甚至不知道它的马尔科夫秩。

在这种情况下，Anru Zhang[1]的文章中提供了一种寻找最优partition的方法，通过此方法我们能找到最优的partition，代入这个partition我们就能通过上面的充分必要条件来决定一个马尔科夫矩阵是否lumpable。具体步骤如下：

  1. 先获取一个n*n维的马尔科夫矩阵P，或者是马尔科夫链的频率采样；
  2. 获取r<n 的马尔科夫秩，或指定一个r；
  3. 对P进行SVD分解，[math]\displaystyle{ P = U \Sigma V^T }[/math]，其中U为左奇异向量，V为右奇异向量。
  4. 通过下列公式得到最优partition[math]\displaystyle{ \Sigma_1, \Sigma_2, ... , \Sigma_r }[/math]

[math]\displaystyle{ \Sigma_1, \Sigma_2, ... , \Sigma_r = argmin_{\Sigma_1, \Sigma_2, ... , \Sigma_r} min_{v_1, v_2, ... , v_r} \sum_{s=1}^r \sum_{i \in \Sigma_s} || V[i:r] - v_s ||_2^2 }[/math]

其中，[math]\displaystyle{ v_s }[/math]是第s类[math]\displaystyle{ \Sigma_s }[/math]的特征向量。

这个算法的意思是在最优的partition中，[math]\displaystyle{ \Sigma_s }[/math]中的状态[math]\displaystyle{ i }[/math]的右奇异向量会和[math]\displaystyle{ v_s }[/math]距离最小，也就是说，让每个微观态的右特征向量和它对应的宏观态的右特征向量尽可能接近。


这个看起来是不是非常眼熟。其实它就是在做kMeans聚类算法。让[math]\displaystyle{ v_s }[/math]和组里的[math]\displaystyle{ V[i:r] }[/math]距离最小的方法，就是让[math]\displaystyle{ v_s }[/math]成为[math]\displaystyle{ V[i:r] }[/math]这若干个点的中心。

回顾一下Kmeans算法把n个点聚成r类的损失函数：

[math]\displaystyle{ J(c^1, ... , c^n, \mu_1, ... , \mu_r) = \sum_{i=1}^n || x_i - \mu_{c^i} ||^2 }[/math]

其中，第[math]\displaystyle{ i }[/math]个点被归到第[math]\displaystyle{ c^i }[/math]类，而[math]\displaystyle{ \mu_j }[/math]为第[math]\displaystyle{ \j }[/math]类点的中心点。

（注：文章中并没有提到可以用KMeans来实现这个算法，但笔者认为它们是等价的）


所以，我们就可以通过上述算法或者kMeans来获取最优partition，然后根据这个partition来判断马尔科夫矩阵的lumpability。



（未完待续）

  1. ↑ 1.0 1.1 1.2 Zhang, Anru, and Mengdi Wang. "Spectral state compression of markov processes." IEEE transactions on information theory 66.5 (2019): 3202-3231.
取自“https://wiki.swarma.org/index.php?title=马尔科夫链的粗粒化&oldid=37064”