終末 A.I.

Deep Learning を中心に、週末に機械学習するエンジニアのブログ

ベイズ統計を理解する(3) 〜 グラフィカルモデル 〜

Computer Vision Modelsのテキストとベイズ推定とグラフィカルモデル:コンピュータビジョン基礎1 | Udemyを使用して、ベイズ統計について説明するコーナーの第三弾は、グラフィカルモデルについてです。

グラフィカルモデルとは、確率変数同士の関係をグラフの形で表現したものとなります。 グラフなので、有向グラフと無向グラフが存在し、それぞれベイジアンネットワーク、マルコフネットワークと呼ばれています。

ベイジアンネットワーク

それでは、それぞれのグラフが表す確率分布を見ていきましょう。 まず、ベイジアンネットワークですが、下記のような式を満たす同時分布を表す事ができます。

 { Pr(x_1...x_N) = \prod_{n=1}^N Pr(x_n|x_{pa(n)})}

確率変数{x_1}から{x_N}までの同時分布は、それぞれの変数間の条件付き分布の積で表現できるという意味です。{pa(n)}は、変数{x_n}の親要素(tail部分が接続されている矢印のhead部にあたる変数)を表しています。

とは言うものの、字面だけで説明してはよくわからないので、例で見てみましょう。下記は、変数A,B,C,Dの関係を示したベイジアンネットワークになります。

f:id:KSKSKSKS2:20160605124056p:plain

このグラフで表されている同時分布は下記のように書くことができます。

{Pr(A,B,C,D) = Pr(A)Pr(C|A)Pr(B)Pr(D|B,C)}

対応関係は見ての通り、親がいない(入ってくる矢印のない)要素の確率分布は{Pr(A)}のようにそのまま使用されます。また、親がいる(入ってくる矢印のある)要素の確率分布は{Pr(C|A)}のように、親要素の条件付き分布として表現されます。

また、ある変数Aとある変数Bが条件付き独立であるかどうかをグラフで表現することができます。A,Bが変数Cで条件付き独立となるのは、A,B間にCがある場合(head-to-tail)、A,Bの親要素がCである場合(tail-to-tail)、CがA,Bの子要素もしくは子要素の子孫要素でない場合(head-to-head)です。ちなみに、head-to-headの場合は条件付きでない場合は独立になりますので注意してください。

ベイジアンネットワークでは、下記のように添字付き変数をプレートで表現したり、確率変数以外の変数との関係を表す事ができます。

f:id:KSKSKSKS2:20160605130002p:plain

上記の図は、混合正規分布ベイジアンネットワークで表現したグラフになります、青枠で囲まれた部分をプレートと呼び、添字付き変数同士の関係を示すものです。図では、{h_i}{x_i}の間に依存関係があり、他の添字の変数とは依存しないということが表現されています。また、黒丸で表現されている変数は確率変数でない変数で、正規分布のパラメーターや重みが表現されています。

マルコフネットワーク

次にマルコフネットワークです。マルコフネットワークは、確率変数間の関係を何らかの関数で表現し、その積で同時分布を表現したグラフとなります。式で表すと下記のようになります。

{Pr(x_1...x_N) = \frac{1} {Z} \prod_{c=1}^C \phi_c(x_1...x_N)}

Z は partition function と呼ばれ、確率分布にするための正規化項です。{\phi_c}は potential function と呼ばれ、必ず正の値を取る関数です。マルコフネットワークは、一般的に下記のように対数を取りギブズ分布の形で表されます。

{Pr(x_1...x_N) = \frac{1} {Z} exp(-\sum_{c=1}^C \psi_c(x_1...x_N))}

{\psi_c(x_1...x_N) = -log(\phi_c(x_1...x_N))} と定義しコスト関数と呼ばれ、定義からわかるように実数値を返します。こちらもグラフの例を見てみましょう。

f:id:KSKSKSKS2:20160605131746p:plain

このグラフで表現される同時分布は、下記の通りです。

{Pr(x_1...x_N) = \frac{1} {Z} \phi_1(A,B,C)\phi_2(B,E)\phi_3(C,D)\phi_4(D,E)}

グラフ理論では、完全部分グラフのことをクリークと呼びます。マルコフネットワークでは、クリークごとに一つポテンシャル関数やコスト関数を定義し、その積で同時分布を表現します。ただし、実装上はエッジごとにポテンシャル関数やコスト関数を定義するようになっている場合が普通です。

マルコフネットワークの場合もグラフから条件付き独立かどうか判定することができます。ベイジアンネットワークの時と比べその判断は非常に簡単で、変数間にエッジがない場合は条件付き独立となります。

ベイジアンネットワークとマルコフネットワーク、どちらも確率変数同士の関係をグラフで表す手法であり、どちらで表現するのが良いかは難しい問題です。一つの判断基準としては、表現可能な条件付き独立の関係があります。

例えば、変数AとBは通常は独立だが変数Cが観測されている場合は条件付き従属となる関係を表現したい場合、ベイジアンネットワークでしか表現することができません。一方、変数A,Bは変数C,Dの元で条件付き独立であり、変数C,Dは変数A,Bの元で条件付き独立であるような関係は、マルコフネットワークでしか表現することができません。このようにグラフの特性を把握して、モデリングしていく必要があります。

内部状態の推定とサンプリング

グラフィカルモデルでの目的は、一般的なベイズモデルと同じく、観測変数{x_1...x_N}を与えられた時に、状態{w_1...w_N}を事後分布から推定することにあります。しかしながら、複雑なグラフィカルモデルにおいて事後分布を求めることはほぼ不可能です。そこで代替案として用いられるのが、MAP推定値、周辺事後分布、周辺事後分布の推定値、そしてサンプリングです。

サンプリング以外の方法は、事後分布と同様、計算が難しく、またそれぞれ推定結果に制約が与えられてしまいます。一方、サンプリングは代表値を取得するだけでなく、複数回サンプリングを行い事後分布の近似を作成することもでき、演算も高速であることからよく使われています。HMMなどのチェインモデルやツリーモデルのようにMAP推定値を計算できるような特殊な形のネットワークを除いては、サンプリングにより推定値を求めることが一般的です。

ベイジアンネットワークでは、サンプリングとして伝承サンプリング(Ancestral sampling)が用いられます。このサンプリング方法は、ベイジアンネットワークの一番起点となる変数から1つずつサンプリングしていき、全ての変数の値をサンプリングするという方法です。

マルコフネットワークでは、サンプリングとしてMCMC(マルコフ・チェーン・モテカルロ)が用いられます。このサンプリング方法には、いろいろとアルゴリズムがあるのですが、よく使われる Gibbs Smapling について説明します。Gibbs Smapling では、一つの変数以外の変数を固定し、その変数をサンプリングするという作業を繰り返し行い、変数セット全てをサンプリングします。

サンプリング時に気をつけることは、変数の初期値にサンプリング結果が影響されないように、Burn-in と呼ばれる、十分なサンプリングをした後に実際に使用するサンプリング点を取得する方法を行う必要がある点と、複数のサンプル点を使用する場合は、それらの間に相関関係が発生しないように、十分にサンプリング間隔をあけたサンプル点を使用する必要があるという2点です。

Gibbs Smaplingでは、サンプリングしたい変数を他の変数で条件付けした条件付き分布を求める必要がありますが、マルコフネットワークでは直接接続されているノード以外とは条件付き独立であるため、条件付き分布を簡単に利用することができます。しかし、MCMCは伝承サンプリングに比べ計算回数が圧倒的に多いため、リソースや計算時間を必要とするといった欠点もあります。また、条件付き分布を求めることが容易でないケースもあり、その場合は条件付き分布を近似した分布を用いてサンプリングを行う、メトロ・ポリス法などがあります。

グラフィカルモデルの学習

さて、上記ではグラフィカルモデルを使用してどのように未知変数を推定するかについて説明しましたが、グラフィカルモデルを使用するにはご多分にもれず学習をしてパラメーターの推定、もしくはパラメーター分布の推定を行う必要があります。もちろん、学習を一切行わず、利用者が決めた確率分布に従って推定を行うようにすることもできますが、ノードの数が多くなればなるほどそれは現実的ではありません。

とはいうものの、複雑な構造をしていますので、パラメーター学習も一般的に難しいものとなります。テキストでもあまり触れられていませんので、また別の機会に詳細を書きたいと思います。

有名なグラフィカルモデル

グラフィカルモデルの形として有名なものに、チェインモデル(HMM)、ツリーモデル、グリッドモデルがあります。

HMMは、観測できない状態wによって観測変数xが生成され、次状態{w_{n+1}}は現状態{w_n}に依存するという形をモデル化したもので下記のような形となります。

f:id:KSKSKSKS2:20160605154000p:plain

このHMMや前状態が複数あるツリーモデルにて、状態wを推定するのに用いられる方法はいくつかあり、MAP推定を行う場合は動的計画法が用いられ、周辺事後分布を推定する場合はForword-BackwordアルゴリズムやSum-productアルゴリズムなどが用いられます。

HMMの学習は、学習セットとして内部状態も与えられている(Supervisedな)場合と、与えられていない(Unsupervisedな)場合とで分けて考える必要があります。Supervisedな場合は、ML推定、MAP推定、ベイズ推定などを用いて比較的容易に学習することができます。Unsupervisedな場合は、内部状態wを隠れ変数として扱いEMアルゴリズムで学習を行うのが一般的です。

マルコフネットワークでよく使われるグリッドモデルは、その中でもマルコフ確率場(MRF)と呼ばれるモデルが良く使われます。MRFでは、ノードが格子状に接続された無向グラフで、ノードは内部状態を表す未観測の確率変数として扱います。そして、その状態に応じてノードごとに1つずつ観測変数が現れるという形をモデル化したものです。

f:id:KSKSKSKS2:20160605154406p:plain

MRFで状態wをMAP推定するために、グラフカットやα-拡張という手法が用いられます。この手法では、劣モジュラであれば厳密解を劣モジュラでなくても良い近似解を得ることができます。

上記で説明した推定方法はここでは詳しく説明しませんが、テキストには詳細が記載されていますので興味がある方はぜひ読んでみてください。

終わりに

この記事では、グラフィカルモデルについて説明しました。ベイジアンネットワーク、マルコフネットワークそれぞれで未観測変数がどのように推定されるのかを説明しました。

そして、全3回とだいぶ長々と書いてきましたが、ひとまずベイズ統計およびそれを利用した機械学習の基本の説明記事は今回にて終了です。変分ベイズ法とか、グラフィカルモデルの学習手法とか、ベイズによる教師なし学習手法とか、まだまだ抑えておきたい部分はありますが、今までの3記事の内容を理解しておけば、とりあえずベイズが分からないせいで何を言っているか分からないということにはならないだろうと思います。

来週からは、また Deep Learning 周りの話に戻りたいと思います。