12

私は非常にスパースな非常に大きな吸収マルコフ連鎖（問題のサイズに合わせてスケール-10状態から数百万）を持っています（ほとんどの状態は他の4つまたは5つの状態にしか反応できません）。

このチェーンの基本行列の1行を計算する必要があります（1つの開始状態が与えられた場合の各状態の平均頻度）。

通常、これは計算によって行います(I - Q)^(-1)が、スパース行列の逆アルゴリズムを実装する優れたライブラリを見つけることができませんでした。私はそれに関するいくつかの論文を見ました、それらのほとんどは博士号レベルの仕事です。

私のGoogleの結果のほとんどは、線形（または非線形）連立方程式を解くときに逆行列を使用するべきではないという投稿を示しています...特に役立つとは思いません。基本行列の計算は連立方程式を解くのと似ていますか？私は単に一方を他方の形で表現する方法がわかりませんか？

それで、私は2つの特定の質問を提起します：

スパース行列の逆行列の行（またはすべての行）を計算するための最良の方法は何ですか？

また

大きな吸収マルコフ連鎖の基本行列の行を計算するための最良の方法は何ですか？

Pythonソリューションは素晴らしいでしょう（私のプロジェクトは現在も概念実証であるため）が、古き良きFortranまたはCで手を汚さなければならない場合でも、それは問題ではありません。

編集：行列Aの逆行列はAB = Iとして定義できることに気づきました。ここで、Iは単位行列です。これにより、いくつかの標準的なスパース行列ソルバーを使用して逆行列を計算できるようになる可能性があります...逃げる必要があるので、自由に思考の列を完成させてください。財産...

4

2 に答える 2

4

あなたがやろうとしていることが吸収までの予想歩数であると仮定すると、ウィキペディアで再現されている「有限マルコフ連鎖」（ケメニーとスネル）からの方程式は次のとおりです。

t = N1

または基本行列を拡張する

t =（IQ）^-1 1

再配置：

（IQ）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

予想されるステップ数を計算するための2つの代替アプローチを提示します。

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-15T13:38:02.380 に答える
3

方程式を解くために逆行列を使用しないというアドバイスを得る理由は、数値の安定性のためです。行列の固有値がゼロまたはゼロに近い場合、逆行列（ゼロの場合）または数値安定性（ゼロに近い場合）がないために問題が発生します。したがって、問題に取り組む方法は、逆数が存在することを必要としないアルゴリズムを使用することです。解決策は、ガウスの消去法を使用することです。これは完全な逆行列を提供するのではなく、上三角形の一般化である行階段形になります。行列が反転可能である場合、結果行列の最後の行には逆行列の行が含まれます。したがって、削除する最後の行が目的の行になるように配置するだけです。

I-Qなぜ常に可逆であるかを理解するのはあなたに任せます。

于 2012-11-08T15:34:01.150 に答える