計算吸收馬爾可夫鏈基本矩陣的最佳方法是什麼？

我有一個非常大的吸收馬爾可夫鏈（從10個州到數百萬個規模的問題）非常稀疏（大多數州只能對4或5個其他州作出反應）。計算吸收馬爾可夫鏈基本矩陣的最佳方法是什麼？

我需要計算這條鏈的基本矩陣的一行（起始狀態中的每個給定狀態的一個平均頻率）。

通常情況下，我會通過計算(I - Q)^(-1)做到這一點，但我一直沒能找到實現稀疏矩陣求逆算法一個好的圖書館！我看過幾篇論文，其中大部分是P.h.D.水平的工作。

我的谷歌搜索結果大部分指向我的帖子談論如何解決線性（或非線性）時，方程組的一個不應使用矩陣求逆...我沒有找到特別有幫助。基本矩陣的計算是否類似於求解一個方程組，我只是不知道如何用另一個的形式表達一個矩陣？

所以，我提出了兩個具體的問題：

什麼是計算一個稀疏矩陣的逆的行（或所有行）的最好方法？

什麼是計算大量吸收馬爾可夫鏈的基本矩陣的行的最佳方式是什麼？

Python解決方案將會非常棒（因爲我的項目目前還是一個概念驗證），但是如果我必須用一些好的Fortran或C來弄髒我的手，那不是問題。

編輯：我剛剛意識到矩陣A的逆矩陣B可以被定義爲AB = I，其中I是單位矩陣。這可能允許我使用一些標準的稀疏矩陣解算器來計算反算......我必須跑掉，所以請隨時完成我的思路，我開始認爲這可能只需要一個真正的基本矩陣財產...

來源

2012-07-29 Ryan Marcus

數量的變化。如果你想要一個Python的解決方案，請貼上標籤'python'。還有其他的堆棧交換也可能或多或少有用。 – 2012-07-29 00:38:04

我正在通過PGM上的一些東西，並想知道是否有一種方法來計算這一般 - 沒有稀疏矩陣的想法，所以祝你好運！ – argentage 2012-08-20 20:50:12

假設你正在試圖做的是找出什麼是expected number of steps before absorbtion，從「有限馬爾可夫鏈」（凱梅尼和Snell），方程式這是維基百科上轉載是：

t=N1

或擴大基礎矩陣

t=(I-Q)^-1 1

花事：

(I-Q) t = 1

這是標準格式，使用功能求解線性方程組

A x = b

把這個付諸實踐的系統來演示性能上的差異（甚至比你小得多系統」重新描述）。

import networkx as nx 
import numpy 

def example(n): 
    """Generate a very simple transition matrix from a directed graph 
    """ 
    g = nx.DiGraph() 
    for i in xrange(n-1): 
     g.add_edge(i+1, i) 
     g.add_edge(i, i+1) 
    g.add_edge(n-1, n) 
    g.add_edge(n, n) 
    m = nx.to_numpy_matrix(g) 
    # normalize rows to ensure m is a valid right stochastic matrix 
    m = m/numpy.sum(m, axis=1) 
    return m

提出了兩種可供選擇的方法來計算預期步數。

def expected_steps_fundamental(Q): 
    I = numpy.identity(Q.shape[0]) 
    N = numpy.linalg.inv(I - Q) 
    o = numpy.ones(Q.shape[0]) 
    numpy.dot(N,o) 

def expected_steps_fast(Q): 
    I = numpy.identity(Q.shape[0]) 
    o = numpy.ones(Q.shape[0]) 
    numpy.linalg.solve(I-Q, o)

採摘這是大到足以證明問題，在計算基本矩陣時發生的類型的例子：

P = example(2000) 
# drop the absorbing state 
Q = P[:-1,:-1]

產生如下時序：

%timeit expected_steps_fundamental(Q) 
1 loops, best of 3: 7.27 s per loop

和：

%timeit expected_steps_fast(Q) 
10 loops, best of 3: 83.6 ms per loop

需要進一步的實驗來測試稀疏矩陣的性能影響，但很顯然，計算反函數要比您期望的慢得多。

類似的方法這裏介紹的一個，也可以用於步驟

來源

2014-07-15 13:38:02

原因你得到的建議不使用逆矩陣的解方程是因爲數值穩定性。當矩陣的特徵值爲零或接近零時，由於缺少反比（如果爲零）或數值穩定性（如果接近於零），就會出現問題。然後，解決問題的方法是使用不需要存在逆的算法。解決方案是使用Gaussian elimination。這並沒有提供完全相反的結果，而是讓你看到上行三角形式的泛化形式 - 行梯形式。如果矩陣是可逆的，則結果矩陣的最後一行包含一行逆。所以只要安排你消除的最後一行是你想要的行。

我要把它留給你理解爲什麼I-Q始終是可逆的。

來源

2012-11-08 15:34:01 eh9

計算吸收馬爾可夫鏈基本矩陣的最佳方法是什麼？

回答

相關問題