algorithm - 简单（非隐藏）马尔可夫链的前向/后向算法

对于这类问题，马尔可夫模型有一些技巧。

在您的情况下，我假设您希望在给定的情况下访问特定边缘 i,j 的预期次数

转移概率矩阵P ,
所有链都从x开始，并且
所有链的长度为L

我会忽略任何像你这样的特殊形式的 P 可能会进一步提高速度。一般的想法（可以扩展到有关马尔可夫系统的其他问题）是这样的：

首先我们意识到，如果我们知道对边缘开始状态的实际访问次数，我们可以使用转移矩阵P来推断特定边缘的实际计数。

示例：假设在长度为 50 的链中，我们知道平均有 10 次我们处于状态 1。在 P 中，从 1 -> 2 跳跃的机会是 50%。然后在长度为 50 + 1 的链中，我们发现 10 * 50% = 5 的所有边平均为 1 -> 2。（注意状态访问和边访问之间的区别！）

幸运的是，处于某种状态的期望可以写成转换矩阵的几何级数。只要分母可以反转，您就可以对几何级数使用通常的技巧，不幸的是，转移矩阵并非如此。至少不是微不足道的，但这可以解决。

让我用 LaTeX 写出状态访问次数向量

E_c{x_0,L} = \sum_{i=0}^{L-1} P^i x_0 = (\sum_{i=0}^{L-1} P^i) x_0

其中 x_0 是向量，在您的情况下初始分布处处为零，但您选择的一种状态。

请注意，x_0 之前的总和是一个矩阵，其中包含所有可能的初始状态的所有状态计数。现在来计算这个矩阵。使用我们得到的几何级数

\sum_{i=0}^{L-1} P^i = \frac{P^L - Id}{P - Id}

Id 是单位矩阵。分母是单数，所以我们有问题。幸运的是，分子有同样的问题，所以我们可以解决这个问题。使用特征值分解并使用左右特征向量矩阵和特征值对角矩阵 evD 重写 P

P = evR evD evL

\sum_{i=0}^{L-1} P^i = \sum_{i=0}^{L-1} (evR evD evL)^i 
                     = evR (\sum_{i=0}^{L-1} evD^i ) evL

现在我们为每个特征值留下了简单的几何级数。一个特征值是 1，这会导致问题。但在这种情况下，我们只是总结一下。从 0 到 L-1 求和 1 就是 L。其他几何级数定义明确。

优点：您现在可以立即计算 x_0 或 L 的任何选择的边缘。

缺点：你总是必须做特征分解，但如果你有很大的矩阵，这是一个问题。

例子：

一个简单的偶对称矩阵

P = {{0.8,   0.15, 0.05}, 
     {0.075, 0.85, 0.075}, 
     {0.05,  0.15, 0.8}}

我们选择了L = 51（50 个转换）和x_0 = {1, 0, 0}

evD = {{1., 0., 0.}, {0., 0.75, 0.}, {0., 0., 0.7}}
evR = {{-0.612372, -0.707107, 0.612372}, {-0.612372, 0, -0.612372}, {-0.612372, 0.707107, 0.612372}}
evL = {{-0.408248, -0.816497, -0.408248}, {-0.707107, 0, 0.707107}, {0.408248, -0.816497, 0.408248}}

GeometricSeries(evD,50) = {{50., 0., 0.}, {0., 4., 0.}, {0., 0., 3.33333}}

E_c(x_0 = 1) = evR GeometricSeries(evD,50) evL {1, 0, 0}
             = {15.3333, 11.6667, 11.3333}

对于转换 1 -> 2 (15%)，我们得到 15.3333 * 15% = 2.3

algorithm - 简单（非隐藏）马尔可夫链的前向/后向算法

问题描述

解决方案

推荐阅读