“马尔科夫链的粗粒化”的版本间的差异
| 第1行： | 第1行： | ||
我们先简单回顾一下马尔科夫矩阵是什么。它是一种square matrix，行列数一样，且满足每一行和为1的条件。 | 我们先简单回顾一下马尔科夫矩阵是什么。它是一种square matrix，行列数一样，且满足每一行和为1的条件。 | ||
| − | 而马尔科夫链指的是一个n维的状态的序列[math]\{x_t\ = 1, ..., n\}_{t}[ | + | 而马尔科夫链指的是一个n维的状态的序列[math]\{x_t\ = 1, ..., n\}_{t}[/math]，每一步的状态转换都有马尔科夫矩阵[math]M[/math]决定，即[math]x_{t+1} = M x_t[/math]. |
| − | [math]M[ | + | [math]M[/math]的每一行对应的每个状态转移到其他状态的概率。比如当[math]x_t[/math]等于第一个状态的时候，M的第一行展示了[math]x_{t+1}[/math]状态的概率。 |
| 第21行： | 第21行： | ||
大家理解的线代里的rank秩的定义是看矩阵中的线性无关的行向量的数量，但是这里对秩的理解是从一种类似于信道的概念。 | 大家理解的线代里的rank秩的定义是看矩阵中的线性无关的行向量的数量，但是这里对秩的理解是从一种类似于信道的概念。 | ||
| − | 秩的定义为我们能找到的一组概率密度函数 [math]f_1, ... , f_r, g_1, ... , g_r[ | + | 秩的定义为我们能找到的一组概率密度函数 [math]f_1, ... , f_r, g_1, ... , g_r[/math]，使得r在下列公式里最小。 |
[math] | [math] | ||
| 第27行： | 第27行： | ||
P(X_{t+1} | X_{t}) = \sum^r_{k=1} f_k(X_t) g_k(X_{t+1}) | P(X_{t+1} | X_{t}) = \sum^r_{k=1} f_k(X_t) g_k(X_{t+1}) | ||
| − | [ | + | [/math] |
| 第33行： | 第33行： | ||
这里的秩的意思是，我们能多大程度上压缩信道，使得信息在宽度为秩的信道中无损传递。（笔者个人理解） | 这里的秩的意思是，我们能多大程度上压缩信道，使得信息在宽度为秩的信道中无损传递。（笔者个人理解） | ||
| − | 在n个离散状态的马尔科夫矩阵中，[math]f_1, ... , f_r, g_1, ... , g_r[ | + | 在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)\}[ | + | 而我们能定义r × r的markov kernel [math]C = \{Cij = \sum_{p=1}^k f_j(k)g_i(k)\}[/math] |
| − | 而且[math]$f_1, ... , f_r$[ | + | 而且[math]$f_1, ... , f_r$[/math] 为 left Markov features，[math]\{g1, . . . , gr\}[/math] 为 right Markov features. |
2024年8月26日 (一) 21:37的版本
我们先简单回顾一下马尔科夫矩阵是什么。它是一种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]状态的概率。
那对马尔科夫链做粗粒化做粗粒化的意义是什么呢？我们看到文献中着重强调这两点：
- 有些状态的转移概率非常相似，所以可以被看成同一类状态，对这种马尔科夫链做partitioning可以减少系统表示的冗余性；
- 在用到马尔科夫决策过程的强化学习里，对马尔科夫链做粗粒化可以减少状态空间的大小，提高训练效率。
马尔科夫链的粗粒化可以分成Hard partitioning和Soft partitioning。Hard partitioning是指把若干个微观状态分成一个宏观状态类，且一个微观状态不能同时属于多个宏观状态类，而soft partitioning则会有可能出现这种情况。
我们这里主要讨论hard partitioning，主要参考的是Anru Zhang and Mengdi Wang的Spectral State Compression of Markov Processes。
首先讨论的是一个马尔科夫矩阵的rank秩。
大家理解的线代里的rank秩的定义是看矩阵中的线性无关的行向量的数量，但是这里对秩的理解是从一种类似于信道的概念。
秩的定义为我们能找到的一组概率密度函数 [math]f_1, ... , f_r, g_1, ... , g_r[/math]，使得r在下列公式里最小。
[math]
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.
（未完待续）