Hamillton dynamics PRML
- 1. 11.5 HyBrid Monte Carlo Algorithm metropolis algorithmでは、 状態空間の移動には非常に非効率である Random walk との類似性が 指摘されている random walk は以下で定義され、 移動距離が大きくなるほど、遷移確率が等比級数的に減少する。 この節では、物理システムを導入し、 棄却確率を小さく保ったままで、z の移動距離を大きくとり、 zの構成する状態空間を自由に満遍なく行きわたるような遷移方法について述べる。 log p(z)のz微分が計算できる系（ほとんどの系）で適用可能だ 物理システムの導入に入る前に少し 話をわかりやすく整理しておく
- 2. いま、 そもそもの機械学習の使用目的として、 Object Recognition を考える。 白地の背景にあるくだものを 一定の距離から撮影した写真の 機械学習による物体認識を行う これを行うためにわれわれは 三つの隠れ変数をあらかじめ想定する すなわち object position orientation のみっつだ 10*10の画像を想定し、 position?z1 は1~100の変数をとる orientation?z2 は平面角を考え、1~360の値をとるものとする object は、りんご、みかん、れもんで z3 は 1~3の値をとるものとする この非常に単純な例の すべての場合を考えると、 100*360*3 = 108000通りかんがえなくてはならず、 サンプリングが必要となることはすでに述べた。 適切なサンプリングを行うことによって、 少ないサンプルでも サンプルのimageの期待値 は 純粋な期待値 E(f) とほぼ同じ値を得ることができることは章のはじめに述べた
- 3. 状態空間は、 z1~z3のはるユークリッド空間と考えることができる われわれのもくてきはこの３つのベクトルがはる空間内を 万遍なく行きわたることである。 この状態空間を万遍なく散歩するために ハミルトン力学を導入する。 Phase Space と呼ばれる一般的な物理空間上で 存在確率が正準分布(ボルツマン分布)に従う 集合 を考える。 で表される。 このzの集合は、位置変数を表すものとする。 つぎにZに一対一で対応する 集合 を同様に正準分布から取得する。 が存在確率となる 適切に Text
- 5. E(z) はPotential Energy そのものである 高校のニュートン力学でいうところの位置エネルギーであり 運動エネルギーである K(r) を導入しよう rはzの時間微分をあらわすが、 ハミルトン系では、zと独立に あらかじめ定義しており、 zとrは独立変数として扱うことができることに注意しよう。 すると系の全エネルギーTotal Energy Potential として、 ハミルトニアンが描写できる。 ここで、 とても重要な事実がある、
- 7. 実際に書いてみると次のようになる ニュートンの運動方程式では zの２次の微分が式に現れてくるが、 ハミルトニアンでは zに加えて、rを導入することで 計算が容易な?1次微分?で表すことができる という点でハミルトン力学はコンピュータに優しい。 さて、実際の計算の設計方法として、 Leap Frog の話に移ろう 一回のステップサイズ?を?ε?として 片方の変数でε/2 の状態を考え、 蛙跳びをするように、交互に積分していくことで、 精密な近似ができる。 ここで、さきほどのハミルトニアンの 重要な式が活躍する εあるいはε/2すすんだ状態を １次のテイラー展開で近似しているわけだが、 rの時間微分などというものは 実際の値として、得ることができない。 しかし、 さきほどの式よりrの時間微分は、 ハミルトニアンのz微分すなわち エネルギー関数の勾配と同じ値である
- 8. HyBrid Monte Carlo しかしながら 誤差はつきものである。 ハミルトニアンが系に固有な値をとる( constant ) であるという事実をもちいて、 HyBrid Monte Carlo の話に移る 私は感動しました！ ハミルトニアンは、 誤差の発生しない状態では 時間変化しないのです。 つまり、初期値におけるハミルトニアンが、常にシステムを修正してくれるのです ! 具体的には 1. 乱数取得による r の更新 2. 改良版リープフロッグによる z, r の更新 を交互に行う。 DEVELOPPED LEAP FROG where : STEP SIZE = ε0 # of STEPs = L 1. SELECT Direction , FOWARD Or BACK, ? letting variable λ= { -1, +1 } 2. LEAP FROG L step Let STEPsize of ε = λε0 Let（ z , r ) = ( z(0) , r(0) ) : starting state ↓L step ( z* , r*) = ( z(εL ) , r(εL ) ) 3. IF Approve(z , r , z* ,r*) > u THEN APPROVE !! OTHERWISE ( z*,r*) <- ( z , r )
- 9. この部分の説明を、教科書で、読むときに注意してほしいのだが このλの設定があたかも、 「詳細釣り合いを満たすために導入する」かのような 邦訳の文章構造になっているが、 これはおかしな話で、 詳細釣り合いを満たすには ただ、ハミルトニアンが変化しないことが十分条件であり、 λを導入する理由とはならない。 他の本をみてもそのように書かれていない。 ハイブリッドモンテカルロは 詳細釣り合いを満たす必要があるが、 以下の式が、 詳細釣り合いそのものであることから ハミルトニアンの変化がなければ、 ハイブリッドモンテカルロを適用できる ここでRはz、rのはる空間を表し δVはそのVolume (体積) を表す 1/2 はλ=-1の場合を除いたことを意味する rの乱数取得だけでは、 エルゴード性を保証する すなわち、 zの状態空間をまんべんなく行きわたることを保証するには十分でないので、 ステップサイズεを小さな値の範囲内で乱数取得してやると良い。
- 10. 多変量ガウス分布への適用を考えることで Hybrid Monte Carlo の振る舞いについての洞察を得ることができる. 簡単のため,独立な要素を持つガウス分布p ( z ) を考える ハミルトン関数は, で与えられる。 HyBrid Monte Carloはどの回転等方性を持つので、 (どの方向に進んでも同じアルゴリズムが適用できる) 等方性： 水やガラスは光学的性質に関して向きによらないので等方的であるが、 液晶や結晶は向きによって異なる偏光応答をするので異方的である 相関がある要素を持つgauss分布においても同様にあてはまる。 つまりLeapFrog積分の間 z i , r i の組は独立に時間発展する。 このことはハミルトン力学の観点からすでに述べた。 しかし,候補点の受理、棄却は、 H の値に基づいて行われる. よっ て,ある1 つの変数にも大きな積分誤差があると,高い棄却率を招く. 離散Leap Frog積分か 真の連続時間力学の十分に良い近似であるためには, Leap Frog積分のスケールεは、 potential が有意に変化する最も短い長さスケールより小さい必要がある. これはσmin つまり σ i の最小値に支配される Hybrid Monte CarloにおけるLeap Frog積分の目的は, Phase Space 内を初期状態から比較的独立な新しい状態へ大きく移動させつつ, 高い受理 確率を実現させることであったことを思い出して欲しい. これを実現するには,Leap Frog積分を O( σmax / σmin ) のオーダーの繰り返し回数だけ続ける必要がある 対照的に,以前にも考えた,分散s^2の等方Guass分布を提案分布とする 単純な Metropolis Algorithmの振る舞いを考えてみよう. 高い棄却率を避けるために, sの値はσminのオータ ーである必要があった. よって,状態空間の探索はRandom walkで進み, おおよそ独立な状態に達するまて O (( σmax / σmin )^2) のステップが?か かる. 参考文献：wikipedia ボルツマン分布（正準分布） probability interface