機械学習とかコンピュータビジョンとか

CVやMLに関する勉強のメモ書き。

ボルツマンマシンについて勉強した その2

はじめに

ボルツマンマシンについて勉強したのでメモその2.主にボルツマンマシンの学習におけるサンプリングについて. 教科書は以下.機械学習プロフェッショナルシリーズの深層学習に比べてサンプリングに関わる説明が手厚くサンプリングを初めて学ぶ身としてはありがたい.

サンプリングについて

基本的にはサンプリングを使う意味として,ボルツマンマシンの学習時に期待値計算がしんどいので,分布からサンプリングしてその平均を期待値とすれば計算量が減って嬉しいというもの. サンプリングで得られたサンプルの平均を期待値として使うには各サンプルがi.i.dに所望の分布からサンプルされてないと真の期待値から大きく外れて役に立たないのでそのようなサンプルを生成するうまいやり方がないかというのがサンプリング手法のポイントとなるところ. 基本的にサンプルがi.i.dに得られていたら大数の法則からサンプル数が無限大の時に真の期待値に収束する.

マルコフ連鎖

ここではモンテカルロ法の一種のマルコフ連鎖モンテカルロ法(Markov Chain Monte Carlo method, MCMC)について考える.

まずMCMCで重要なマルコフ連鎖について.マルコフ連鎖マルコフ性を満たす確率過程のことで,現在の状態が1時刻前の状態だけから決定されるというもの.つまりP(x_t|x_{t-1},...,x_1)=P(x_t|x_{t-1})というもの. マルコフ過程においてある時刻tの確率分布P(x_t)は周辺化を用いてP(x_t)=\sum_{x_{t-1}}P(x_t|x_{t-1})P(x_{t-1})と表現できる.さらに同時分布はマルコフ性からP(x_t,...x_1)=P(x_t|x_{t-1})...P(x_2|x_1)P(x_1)と表される.

教科書ではマルコフ連鎖の応用としてページランクが紹介されていたが今回の勉強目的とは関係ないのでここでは割愛.

ここで,確率変数xが取りうる状態を\alpha\in\{1,2,..\}とすると,\mathbf{\pi}_t=\left(P(x_t=1),P(x_t=2),...\right)のように時刻tにおける各状態の実現確率P(x_t=1),P(x_t=2),...を並べたベクトルを考える.このベクトルを状態確率分布と呼ぶ.同様に状態aから状態bへの遷移確率P(x_t=a|x_{t-1}=b)ab成分とする行列を遷移確率行列\mathbf{T}と呼ぶ.すると時刻tの状態確率分布はt-1の状態分布を用いて,

 \displaystyle
\mathbf{\pi}_t=\mathbf{T}\mathbf{\pi}_{t-1}

と表現できる.ここで均一なマルコフ連鎖(遷移確率行列が時刻tによらない)を考えれば,ある時刻tにおける状態確率分布は\mathbf{\pi}_t=\mathbf{T}^t\mathbf{\pi}_0となる.ここでt\rightarrow\inftyの時,もはや遷移確率行列により状態確率分布が変化しなくなった場合,その分布を平衡分布と呼ぶ.マルコフ連鎖は必ず平衡分布に収束するわけではなく規約性と非周期性を満たす時に収束する(詳細は教科書参照).収束の条件式として以下の詳細つり合い条件が与えられる.

\displaystyle
T_{ba}P(x=a)=T_{ab}P(x=b) \\ \displaystyle
P(x=a)=\sum_bT_{ab}P(x=b)

2行目は1行目の両辺をbについて和を取ることで\sum_bT_{ba}=1の関係を用いて得られる.

マルコフ連鎖モンテカルロ

ようやく本題のMCMCMCMCはサンプリングしたい分布P(x)が複雑でサンプリングが難しい時に,P(x)に収束するマルコフ連鎖からサンプリングしようというもの.そうすればマルコフ連鎖が収束した時には,欲しい分布からサンプリングしているのと同じとみなせる.問題はマルコフ連鎖をどう設計するかで,収束が早いほど嬉しいのは言うまでもない.ここでは例としてギブスサンプリングを考える.

ギブスサンプリングは簡素な方法でマルコフ連鎖を設計するため,アルゴリズムも単純で汎用性が非常に高い.いまボルツマンマシンの確率変数が\mathbf{x}=(x_1,...,x_M)と定義されている時,ギブスサンプリングでは以下の条件つき分布からサンプリングを行う.

\displaystyle
P(x_i|x_1,...,x_{i-1},x_{i+1},...,x_M)

要は,全ての確率変数を一気にサンプリングするのではなく,他の確率変数を条件として一つの確率変数のみをサンプリングしようというもの.全ての変数を一気にサンプリングするのは難しいが,一つずつなら楽にできるというのがギブスサンプリングのいいところ.この時サンプリングする順番は任意.

今,確率変数i以外の変数の値を\mathbf{x}_{-i}=(x_1,..,x_{i-1},x_{i+1},...,x_M)とすると,ギブスサンプリングで必要な条件つき分布は

\displaystyle
P(x_i|\mathbf{x}_{-i},\theta) \\ \displaystyle
=\frac{P(\mathbf{x},\theta)}{\sum_{x_i=0,1}P(\mathbf{x},\theta)} \\ \displaystyle
=\frac{\exp(-\Phi(\mathbf{x},\theta))}{\sum_{x_i=0,1}\exp(-\Phi(\mathbf{x},\theta))}

となる.ただし分母はx_iについての周辺化を表している.この式を陽に書くと

\displaystyle
\frac{\exp(-\Phi(\mathbf{x},\theta))}{\sum_{x_i=0,1}\exp(-\Phi(\mathbf{x},\theta))}\\ \displaystyle
=\frac{\exp(\sum b_ix_i + \sum w_{ij}x_ix_j)}{\sum_{x_i=0,1}\exp(\sum b_ix_i + \sum w_{ij}x_ix_j)} \\ \displaystyle
=\frac{\prod_i\exp(b_ix_i)\prod_{i.j}\exp(w_{ij}x_ix_j)}{\sum_{x_i=0,1}\prod_i\exp(b_ix_i)\prod_{i,j}\exp(w_{ij}x_ix_j)} \\ \displaystyle
=\frac{\exp(b_i)\prod_j\exp(w_{ij}x_ix_j)}{\sum_{x_i=0,1}\exp(b_ix_i)\prod_j\exp(w_{ij}x_ix_j)} \\ \displaystyle
=\frac{\exp(b_ix_i+\sum_jw_{ij}x_ix_j)}{1+\exp(b_i+\sum_jw_{ij}x_j)}

と変形ができる.3行目から4行目はx_iと関係ない項を約分しており,最後の行はx_i=0,1を代入することで求まる.ここで,両辺の\sum_jはノードiに隣接しているノードのみでの足し合わせになっているため,ノードiに隣接するノードの状態からx_iが決まることがわかる.すなわちボルツマンマシンの局所マルコフ性のおかげで,\mathbf{x}_{-i}を知らなくても周辺のノードのみでx_iを求めることができ,それにより効率的に計算が可能である.また,ここで上記の式をよく見ると,x_i=0,1であることからシグモイド関数の形になっていることがわかる.そのため,サンプリングも非常に単純に行うことができ,区間[0,1]から発生させた一様乱数がP(x_i=1|\mathbf{x}_{-i},\theta)より大きければ,x_i=1を,それ以外にはx_j=0をサンプリング値とすればいい.

ギブスサンプリングの問題点

サンプリングのための条件つき分布とそのサンプリング方法がわかったので,あとはギブスサンプリングの枠組みに当てはめて全ての確率変数をサンプリングすれば良い.また,簡単な計算で連鎖が定常状態になれば元の分布になることを示せる(教科書に丁寧な証明があるので割愛).ただし,ギブスサンプリングには一つ問題がある.当然,一番最初の変数をサンプリングする際には他の値はわからないため適当な値で初期化を行う.そこから平衡状態になるまで(初期値の影響が完全に消え去るまで)サンプリングを繰り返す必要があるが(この繰り返しをburn-inと呼ぶらしい),どれくらいサンプリングを繰り返せば平衡状態になるかを見積もる明確な方法がない.もう一つ問題として,burn-inをしたのち1つサンプルを得た直後に別なサンプルを得るとそのサンプルは直前のサンプルと強い相関を持つため独立なサンプルとして使うことができない.そのため,ある程度時間をあけてサンプルを取得する必要があるため,全てのサンプルが得られるまでに時間が必要となる.

実践的なサンプリング方法

上記の最後に挙げたように,ギブスサンプリングにはサンプルを連続して取得すると相関を持ってしまう問題がある.そこで連鎖を複数作ってそれぞれの連鎖からサンプリングする方法を考える.これは,サンプリングしたい数だけ連鎖を用意すればサンプル間の独立性を保証できる.ただし,連鎖の数だけburn-inが必要なので計算コストはかかる(処理を並列化すれば解決は可能?).そのため実践的には,連鎖の本数と計算時間のトレードオフを考えて,複数の連鎖を使って各連鎖から複数のサンプルを取得する方法が取られる.

まとめ

ギブスサンプリングにより分布の期待値を近似する方法を勉強した.これでボルツマンマシンの学習に必要な期待値を近似的に求めることができる.ただし,隠れ変数が入ってくるとモデルだけでなくデータに関する期待値の計算が困難なってくるためサンプリングが必要になり嬉しくない.そこで構造に制約を加えて計算をしやすくしようということで制約ボルツマンマシンができたようなので次回はそこら辺を勉強予定.

ちなみに教科書にはギブスサンプリングではなく平均場近似を使って近似する方法についての解説があったのでそっちも勉強してまとめたい.