Forward/backward 简单（非隐藏）马尔可夫链算法

Question

给定初始转移矩阵

其中 x 是随机游走者开始行走的初始节点。

然后我们可以计算数量：

表示边 (i, j) 的预期访问次数，同时在 x 中开始行走，假定行走长度为 L。

因为像Q^(L-1)这样的一些矩阵幂，所以上面数量的计算非常耗时我想知道是否有类似的算法来计算HMM的前向后向算法那个简单（可见）马尔可夫链的数量。

Answer 1

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

在你的情况下，我假设你想要 访问特定边 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

Forward/backward 简单（非隐藏）马尔可夫链算法

Forward/backward algorithms for simple (non Hidden) Markov Chain

algorithm

markov-chains