97
个编辑
更改
跳到导航
跳到搜索
第4行：
第4行： + + 第9行：
第11行： + + 第30行：
第34行： − + − − 而且<math>f_1, ... , f_r</math> 为 left Markov features，<math>\{g1, . . . , gr\}</math> 为 right Markov features. 第42行：
第44行： − + + + + − + + + + − + 第71行：
第79行： − + − − − # − + − + − + 第88行：
第93行： − + 第124行：
第129行： − +
无编辑摘要
<math>P</math>的每一行对应的每个状态转移到其他状态的概率。比如当<math>x_t</math>等于第一个状态的时候，<math>P</math>的第一行展示了<math>x_{t+1}</math>状态的概率。
<math>P</math>的每一行对应的每个状态转移到其他状态的概率。比如当<math>x_t</math>等于第一个状态的时候，<math>P</math>的第一行展示了<math>x_{t+1}</math>状态的概率。
那对马尔科夫链做粗粒化做粗粒化的意义是什么呢？我们看到文献中着重强调这两点：
那对马尔科夫链做粗粒化做粗粒化的意义是什么呢？我们看到文献中着重强调这两点：
# 有些状态的转移概率非常相似，所以可以被看成同一类状态，对这种马尔科夫链做partitioning可以减少系统表示的冗余性；
# 有些状态的转移概率非常相似，所以可以被看成同一类状态，对这种马尔科夫链做partitioning可以减少系统表示的冗余性；
# 在用到马尔科夫决策过程的强化学习里，对马尔科夫链做粗粒化可以减少状态空间的大小，提高训练效率。
# 在用到马尔科夫决策过程的强化学习里，对马尔科夫链做粗粒化可以减少状态空间的大小，提高训练效率。
马尔科夫链的粗粒化可以分成Hard partitioning和Soft partitioning。Hard partitioning是指把若干个微观状态分成一个宏观状态类，且一个微观状态不能同时属于多个宏观状态类，而soft partitioning则会有可能出现这种情况。
马尔科夫链的粗粒化可以分成Hard partitioning和Soft partitioning。Hard partitioning是指把若干个微观状态分成一个宏观状态类，且一个微观状态不能同时属于多个宏观状态类，而soft partitioning则会有可能出现这种情况。
在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 = \{C_{ij} = \sum_{k=1}^n f_j(k)g_i(k)\}</math>，<math>f_1, ... , f_r</math> 为 left Markov features，<math>g_1, . . . , g_r</math> 为 right Markov features.
这个定义可以想象成可压缩的程度，也会是下面的hard partitioning的分组的数量。
这个定义可以想象成可压缩的程度，也会是下面的hard partitioning的分组的数量。
这个概念最早出现在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=\{A_1, A_2, ... ,A_r\}</math>，我们能够用下列公式描述一个粗粒化后的马尔科夫链(lumped process)，且这个转移概率对任何初始状态(starting vector) <math> \pi </math> 都是一样的：
<math>
<math>
Pr_{\pi}[f_0 \in A_i]
Pr_{\pi}[f_0 \in A_i]
</math>
<math>
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]
</math>
<math>
Pr_{\pi}[f_n \in A_t |f_{n-1} \in A_s f_1 \in A_j 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=\{A_1, A_2, ... ,A_r\}</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>都是一样的。
#获取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<math>
#通过下列公式得到最优partition <math>\Omega_1, \Omega_2, ... , \Omega_r</math>
\Sigma_1, \Sigma_2, ... , \Sigma_r
</math>
<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
\Omega_1, \Omega_2, ... , \Omega_r = argmin_{\Omega_1, \Omega_2, ... , \Omega_r} min_{v_1, v_2, ... , v_r} \sum_{s=1}^r \sum_{i \in \Omega_s} || V_{[i,:r]} - v_s ||_2^2
</math>
</math>
其中，<math>v_s</math>是第s类<math>\Sigma_s</math>的特征向量。
其中，<math>v_s</math>是第s类<math>\Omega_s</math>的特征向量。
这个算法的意思是在最优的partition中，<math>\Sigma_s</math>中的状态<math>i</math>的右奇异向量会和<math>v_s</math>距离最小，也就是说，让每个微观态的右特征向量和它对应的宏观态的右特征向量尽可能接近。
这个算法的意思是在最优的partition中，<math>\Omega_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聚类算法。让<math>v_s</math>和组里的<math>V[i:r]</math>距离最小的方法，就是让<math>v_s</math>成为<math>V[i:r]</math>这若干个点的中心。
回顾一下Kmeans算法把n个点聚成r类的损失函数,其中第<math>i</math>个点被归到第<math>c^i</math>类，而<math>\mu_j</math>为第<math>\j</math>类点的中心点：
回顾一下Kmeans算法把n个点聚成r类的损失函数,其中第<math>i</math>个点被归到第<math>c^i</math>类，而<math>\mu_j</math>为第<math>j</math>类点的中心点：
<math>J(c^1, ... , c^n, \mu_1, ... , \mu_r) = \sum_{i=1}^n || x_i - \mu_{c^i} ||^2 </math>
<math>J(c^1, ... , c^n, \mu_1, ... , \mu_r) = \sum_{i=1}^n || x_i - \mu_{c^i} ||^2 </math>
#Lumpability最优的partition不等于可逆性最优的partition。
#Lumpability最优的partition不等于可逆性最优的partition。
#Lumpability的分组数量是基于马尔科夫秩的，而可逆性的分组数量是对奇异值谱的截断位置。