1

機械学習アルゴリズムのトレーニングの側面を並列化できるかどうかを調べようとしています。トレーニングの計算コストの高い部分には、正定値行列 (共分散行列) のコレスキー分解が含まれます。純粋に行列代数の観点から問題を組み立ててみます。さらに情報が必要な場合はお知らせください。

ブロック行列があるとしましょう（共分散行列ですが、それは問題には関係ありません）

 
M = AB  
    B* C

ここで、A と C は 2 つの異なるセットからのトレーニング データに関連しています。A と B は両方とも正定です。簡単にするために、A と C のサイズが nxn であると仮定します。

ブロックコレスキー分解を行う式があります。http://en.wikipedia.org/wiki/Block_LU_decompositionを参照してください。要約すると、次の結果が得られます。

M = ル

ここで (* は転置を示します)

L = A^{1/2} 0
    B*A^{-*/2} Q^{1/2}

どこ

Q = C - B*A^{-1}B

ここで、行列 A と C に関連するトレーニングが既に実行されているとしましょう。したがって、A のコレスキー分解を実行し、C は A^{1/2} と C^{1/2} を与えます (したがって、前方置換を使用して、逆数 A^{-1/2} および C^{-1/2} を簡単に計算できます)。

Q をこれらの量で書き直します。

Q = Q^{1/2} Q^{*/2} = C^{1/2} C^{*/2} - B* A^{-*/2}A^{-1/2} B

私の質問は次のとおりです。この設定を考えると、コレスキー分解を Q に適用することなく、代数的に Q^{1/2} を計算することが可能です。つまり、C^{1/2} を使用してQ^{1/2}の計算。これが可能であれば、トレーニングを簡単に並列化できます。

返信ありがとうございます。マトリックスの組版について申し訳ありません。特に数学や行列をタイプセットする賢明な方法はありますか?

マット。

4

2 に答える 2

3

一連のコレスキー ダウンデートでこれを行うことができます。

(以下では、乗算との混同を避けるために転置に ' を使用します)

A のコレスキー係数が a で、C のコレスキー係数が c の場合、Q の方程式は次のように記述できます。

Q = c*c' - beta'*beta ここで、beta = inverse(a) B (つまり、 beta = B を beta に対して解く)

beta の i 番目の列を b[i] と書くと、

Q = c*c' - 合計 b[i]*b[i]'

のコレスキー分解を求める

c c' - x x' (x はベクトル、c は下三角)

ランク 1 コレスキー ダウンデートとして知られています。Golub と van Loanには安定したアルゴリズムがあります。

于 2010-07-14T19:46:06.417 に答える
1

思った通りではありませんが、答えが出たと思います。

機械学習のコンテキストを削除すると、私の質問は、C^{1/2}を知ることがQ^{-1/2}の計算に役立つかどうかに要約されます。以下でさらに詳しく説明しますが、追跡を断ち切るために、答えは「はい」ですが、安定性に関してのみであり、計算ではありません（現在、これが当てはまると証明することはできませんが、かなり確実です）。

安定性に対する答えが「はい」である理由については、元の質問の定義Qを次のように再配置しました。

Q = C-B * A ^ {-1} B =（C ^ {1/2} + B * A ^ {-* / 2}）（C ^ {1/2}-B * A ^ {-* / 2}）*

事前にC^{1/2}を知ることにより、Aを直接反転させることなくQを計算できます。直接反転は数値的に安定していません。

残念ながら、私はこのテーマについてかなりの量の調査を行いましたが、$ C ^{1/2}$がQ^{-1/2}の正確な計算でwrtの計算に役立つようには見えません。最善のアプローチは、上記のようにC ^ {1/2}を使用してQを計算し、次にコレスキーを使用してQをQ ^ {1/2}に分解し、次に前方置換を使用してQ^{-1/2}を計算することです。

さらなる研究

私があまり詳しく調べなかった領域の1つは、C^{1/2}を使用してQ^{-1/2}を近似できるかどうかでした。開始点としてC^{1/2}を使用する反復法の線に沿った何か。そのような反復近似プロセスについては知りませんが、検索を続けます。それを中心に新しい質問を始めるかもしれません。

大きな進歩があれば、皆さんに更新します。

于 2010-07-07T18:20:12.080 に答える