马尔科夫链的粗粒化

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
Liangjh讨论 | 贡献2024年8月27日 (二) 16:41的版本
跳到导航 跳到搜索

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

而马尔科夫链指的是一个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]状态的概率。

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

  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]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]

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

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

Lumpability

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

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

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

[math] 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]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]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]所示。

但是,有时候有些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,我们甚至不知道它的马尔科夫秩。

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

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


(未完待续)

  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.