エピソード
MCMCと信念伝達の合成
代入 Sung-Soo Ahn
Markov Chain Monte Carlo (MCMC) と Belief Propagation (BP) は、グラフィカル モデル (GM) の計算推論に最も一般的なアルゴリズムです。 原則として、MCMCは正確な確率論的方法であり、しかし、しばしば指数関数的に遅い混合に苦しむ。 これに対し、BP は決定論的な方法であり、通常は高速で経験的に非常に成功していますが、一般的にループグラフに対する精度の制御が欠けています。 本論文では,BPの近似誤差を補正するMCMCアルゴリズムを紹介する. このフレームワークは、BP 誤差を重み付けされた一般化されたループの合計として表現できるループ微積分 (LC) アプローチに基づいています。 完全な系列は計算的に難解ですが、2 つの正規ループをすべて合計した切り捨てられた系列は、平面的なペアワイズバイナリ VM の多項式時間で計算可能であり、経験的に非常に正確な近似を提供することも知られています。 そこで、まず、一般(非平面)ペアワイズ二項モデルの切り捨てられた一連の多項式時間近似MCMCスキームを提案します。 ここでの主な考え方は、他の(関連する)問題で高速混合を提供することが知られているワームアルゴリズムを使用し、2標準ループをサンプリングするための適切な拒否スキームを設計することです。 さらに、完全なシリーズを近似するための効率的な拒否フリーMCMCスキームも設計しています。 私たちの設計の基になる主な新規性は、一般化されたループの効率的な分解を提供するサイクルベースの概念を利用することです。 基本的に、提案されたMCMCスキームは、非自明なBPソリューションに基づいて構築された変換されたGM上で実行され、我々の実験は、BPとMCMCのこの合成が直接MCMCスキームとベアBPスキームの両方を上回っていることを示している。
Markov Chain Monte Carlo (MCMC) と Belief Propagation (BP) は、グラフィカル モデル (GM) の計算推論に最も一般的なアルゴリズムです。 原則として、MCMCは正確な確率論的方法であり、しかし、しばしば指数関数的に遅い混合に苦しむ。 これに対し、BP は決定論的な方法であり、通常は高速で経験的に非常に成功していますが、一般的にループグラフに対する精度の制御が欠けています。 本論文では,BPの近似誤差を補正するMCMCアルゴリズムを紹介する. このフレームワークは、BP 誤差を重み付けされた一般化されたループの合計として表現できるループ微積分 (LC) アプローチに基づいています。 完全な系列は計算的に難解ですが、2 つの正規ループをすべて合計した切り捨てられた系列は、平面的なペアワイズバイナリ VM の多項式時間で計算可能であり、経験的に非常に正確な近似を提供することも知られています。 そこで、まず、一般(非平面)ペアワイズ二項モデルの切り捨てられた一連の多項式時間近似MCMCスキームを提案します。 ここでの主な考え方は、他の(関連する)問題で高速混合を提供することが知られているワームアルゴリズムを使用し、2標準ループをサンプリングするための適切な拒否スキームを設計することです。 さらに、完全なシリーズを近似するための効率的な拒否フリーMCMCスキームも設計しています。 私たちの設計の基になる主な新規性は、一般化されたループの効率的な分解を提供するサイクルベースの概念を利用することです。 基本的に、提案されたMCMCスキームは、非自明なBPソリューションに基づいて構築された変換されたGM上で実行され、我々の実験は、BPとMCMCのこの合成が直接MCMCスキームとベアBPスキームの両方を上回っていることを示している。
ご意見およびご提案がある場合は、 こちらから問題を送信してください。