Hiroki Naganuma

2020 Hiver Q3

Answer

• Answer

Materials

MRF

Reference

• MRF (Markov Random Field)

• Ising Model

• RMF PRML Sec8

• Prml Reading Group 10 8.3

• [DL輪読会]Deep Learning 第16章 深層学習のための構造化確率モデル

Gibbs Sampling

• MCMC の代表的なアルゴリズムギブス・サンプリング: 端的、 t+1 に update されていかないのが気になる
• PRML 11章 二変量正規分布からのギブスサンプリング
• Gibbs Sampler を用いたベイズ推定法によるオプション評価の方法

Mixing Time

• Lecture 9: Eigenvalues and mixing time

• Lecture 10: Mixing time and eigenvalues

• 来嶋秀治「MCMC法と近似精度保証」（RAMP 2007）: わかりやすい！
  • 旧論文URL: http://www.econ.nagasaki-u.ac.jp/RAMP2007/paper/1-1.pdf（2026-09-30: HTTP/HTTPSとも404、論文の移転先未確認）
  • 同じ講演の著者公開スライド（論文本体とは別資料）

MCMC

PRML

DL Book

• [DL輪読会]Deep Learning 第17章 モンテカルロ法

Other Reference

• 文教大 マルコフ連鎖

• MCMC チュートリアル 入門から多峰性分布の扱いとその応用まで

• 確率と計算 Mixing Time

• マルコフ連鎖入門: めちゃくちゃ詳しい、 OverKill

• 駒澤大学 マルコフ連鎖

• 確率過程の基礎-マルコフ連鎖

• マルコフ連鎖

• 理科大の資料

わかりやすいブログ記事

• マルコフ連鎖の収束のための条件とMCMCとの関係

  収束するための条件として、どの状態からでも有限回のステップで他のどの状態にでもいけるという性質を持つ必要があります。これを既約性と呼びます。 元の状態に戻るために必要なステップ数の最大公約数を周期と呼び、全ての状態での周期が1であるようなマルコフ連鎖は非周期性を持つと言います。

収束条件 そして、次のような話が成り立ちます。既約かつ非周期なマルコフ連鎖は不変分布に収束する。

• 分布の距離と混合時間

適当な条件の下で確率行列Pnは時間nを大きくしていくと不変確率分布Πに収束するというわけでした。 混合時間 全変動ノルムを用いて2つの分布の距離を評価することが出来る PnはΠに収束する ここから、どれくらいnを大きく取るとおおよそ収束したとみなせるかという考え方が必要になってきます。これが混合時間です。

エルゴード性

ref 定常分布があるかどうかは次の3条件が必要です。

• 任意の状態から他の任意の状態へ到達可能(accessible)
• 周期性を持たない
• 状態数が有限 この3つの性質を満たすとき、そのマルコフモデルはエルゴード性(ergodicity)を持つといい、同時に定常分布も存在します。