確率と論理の統合(1) ベイジアンネットとKBMCとPRMとSRL

ベイジアンネット

岩波データサイエンスvol2より。

以前述べたベイズ推定の応用としてベイジアンネットがある。ベイジアンネットは様々な事象間の因果関係（厳密には確率的な依存関係）をグラフ構造で表現するモデリング手法の一つで、故障診断や気象予測、医療的意思決定支援、マーケティング、レコメンドシステムなど様々な分野で利用や研究が行われている。

これを数学的に表現すると、有限個の確率変数X₁,..X_Nをノードとする有効グラフと各ノードに付随する条件付き確率表(conditional probability table:CPT)からなり、X₁,..,X_Nの同時分布 P(X₁=x₁,..X_N=x_n) を以下のようなグラフ構造で表す。

これらを用いた学習としては、CPTの確率値を推定するものから、グラフ構造を学習する構造学習まで様々なものが研究されている。

著名なものとしては、電車の混雑状況や、津波・地震などの災害・株価のリアルタイム処理・スパムメールの分類・レコメンドシステム・センチメント分析等で使われるナイーブベイズ(データが与えられたときの全ての推定の確率を計算し、最も確率の高いものを推定結果として出力するアルゴリズム)や、音声認識、バイオインフォマティクス、形態素解析（自然言語処理）、楽譜追跡、部分放電など、時系列パターンの認識に応用される隠れマルコフモデル等があり、データマイニングを支える標準的な確率モデリング技術となっている。

KBMCによるベイジアンネットの自動生成

ベイジアンネットには、似たようなものがあってもまとめて記述ができず、変数が異なると別々のベイジアンネットを作らなければならない等作成の為の課題があり、複雑で巨大なモデルの記述は困難となる。

この問題を解決するために、知識ベースモデル構築(KBMC)と呼ばれるベイジアンネットの自動生成の研究がおこなわれた。KBMCは述語論理が用いられ、prolog的な宣言的なプログラミング言語等を用いて、知識ベースを参照しつつ後ろ向き推論を行い、質問に回答する為のベイジアンネット動的に生成して、それを使って確率を計算して質問に答えるしくみが用いられた。これによりすべての可能性のある質問に対する巨大なベイジアンネットを作成するという問題が回避できた。

このKBMCは、エキスパートシステムの確率的な応用として捉えられるが、エキスパートシステムが持っていた課題をそのまま引き継いでいた為、フレーム問題という課題を持っていた。

確率的関係モデル(probabilistic relational model;PRM)

PRMは有向グラフィカルモデルであるベイジアンネットの発展形であり、SRLの先駈となったものとなる。単純化していうとPRMは、関係データベース(relational database;RDB)からベイジアンネットを作り出す。従来のベイジアンネットが一つの表として表現されるデータを扱い、属性を確率変数とみなして属性間の確率的依存関係をモデル化するのに対し、PRMは、関係データベースの複数の表を扱い、表の間の参照関係を利用して、同一のもしくは別々の表にある属性間の確率的依存関係を関係データベースの行であるタプル(レコード)ごとに定め、それらを集めて一つのベイジアンネットとして表現する。

すなわち、PRMは複数の表を扱うことと、タプルごとに確率をモデル化することかで特徴となる。と違って確率計算はその分大変になるが、従来のベイジアンネットより複雑できめ細やかな確率的依存関係を表現できる。

学習面も異なる。従来のベイジアンネットは表のタプルを独立同一分布からのサンプルと仮定し確率を学習するが、PRMの確率学習ではデータベースがただ一つのサンプルであり、その一例から確率を学習する。したがって独立同一分布の過程とは無縁であるが、別途実質的に確率計算上同等の効果を持つような仮定をおく。

もう少し具体的にいうと、PRMではオブジェクト指向風の考え方を使い、個々の表をクラス、表に属するタプルをクラスのオブジェクト(個体、インスタンス)とみなす。以下、表とクラス、タプルとオブジェクトを同じものとして扱う。タプルは複数の属性を持ち、属性は、表の中のオブジェクトを識別するためのIDや、他の表との参照関係を表すための値のような非確率的属性と個体の性質を表す通常の確率的記述属性とに分かれる。

例として映画に関するデータを関係データベースにしたものを考える。下図に示すように、この関係データベースには、俳優、出演、映画の3つの表がある。

俳優の表は、俳優のID(俳優を一意に識別する属性)と俳優の性別を属性として持つ。このうち俳優を一意に識別する属性は、関係データベースの用語で主キーと呼ばれる。俳優の性別は記述属性となる。同様に、映画の表は映画のIDと、映画ジャンルを属性として持つ。さらに、出演の表は、出演のID、俳優のID、映画のIDと、ある俳優がある映画で演じた役柄を属性として持つ。このうち、出演のIDは主キーであり、俳優のIDと映画のIDは他の表を参照するためのものであり、外部キーと呼ばれる。

クラスXの属性AをX.A、外部キーσにより最小されるクラスをX.σで表す。例えば、上の例では、俳優.性別、出演.俳優などとなる。表の参照関係はさらに一般化することがかのうで、τにより外部キーを順方向・逆方向まぜて0回以上たどる参照の連鎖を表すことにして、クラスXからの参照の連鎖τにより参照される(たどりつく)クラスをX.τと書く。このとき、クラスXの確率的記述属性Aは参照の連鎖τにより参照されるクラスX.τの確率的記述属性Bと確率的依存関係にある可能性がある。例えば、出演.役柄は、俳優.性別や、映画.ジャンルと確率的依存関係にある。

以後簡単のためにキーと確率的記述属性を区別し、後者を単に属性と呼ぶ。PRMではクラスXの各属性Aに対し、Aが確率的に依存する属性の集合(親ノードの集合)Pa(X.A)と付随する条件付き分布(CPT)P(X.A|Pa(X.A))が定められている。関数名、属性、属性の定義からなる関係スキーマ、及び属性の局所的な確率的依存関係を表すPa(X.A)と付随するP(X.A|Pa(X.A))を合わせたものをPRMスキーマと呼ぶ。

RDBからタプルの属性値をすべて抹消したRDBはキーによるタプル間の参照関係だけを表している。それをスケルトン(skelton)と呼ぶ。PRMとはPRMスキーマとスケルトンσの組を言い、属性間の確率的依存関係を表すPRMスキーマをスケルトンによりタプルレベルに具体化したものとなる。すなわち、PRMはRDBの表Xのタプルx∈Xの属性x.Aとスケルトンσから導かれる参照の連鎖τによりxから辿り着けるタプルy=x.τの属性B、すなわちx.τ.Bとの間の確率的依存関係を定める。

そしてこれらの確率的依存関係は(確率的依存関係がループしないなどといった条件のもとに)一つのベイジアンネットを成すことを仮定する。このベイジアンネットでは、通常のベイジアンネットと異なりタプルごとの属性、すなわちx.Aが確率変数であり、グラフのノードを成す。x.Aに付随するCPTはP(X.A|Pa(X.A))を使う。言い換えるとPRMではクラスと属性が同じならばタプルが異なっていても同一のCPTを共有する。このしくみにより、PRMでは、確率計算上あたかも独立同一分布からのサンプルであるように扱われる。

下図に、出演.役割の親ノードが俳優.性別、映画.ジャンルであることを表すPRMスキーマ、PRMスケルトン、それらによって定義されるPRMと等価なベイジアンネットの一部を示している。

俳優、映画、出演の行(タプル)の数が増えれば、非常にたくさんのノードを持つベイジアンネットが構成されるのが確認できる。

元の関係データベースRDBは、スケルトンσに対し、それを作る際に抹消したタプルの属性値を埋め戻したものとなる。それはちょうどこのベイジアンネットの各ノードに値を与えたものに相当する。言い換えるとRDBはこのベイジアンネットの一つのインスタンスI(実現値)になっている。xを表Xのタプル、Iにおけるx.Aの実現値をI_x.A、PRMスキーマSで与えられているXの属性Aの親属性等Pa(X.A)の実現値をI_Pa(x.A)と記す。確率P(I_x.A|I_Pa(x.A))をパラメータと呼び、パラメータの全体集合をθで表す。さらにXにより表の全体をA(X)により表X∈Xの属性の全体を表す。するとインスタンスIの確率、言い換えるとPRMが定めるRDBの尤度は以下により与えられる。

\[P(I|\sigma,\mathbf{S},\theta)=\displaystyle\prod_{X\in\mathbf{X}}\prod_{A\in \mathbf{A}(X)}\prod_{x¥in\sigma(X)}P(I_{x.A}|I_{Pa(x.A)})\]

モデルのパラメータである条件付き確率値の計算は最尤推定により、すなわち、上記の尤度を最大にすることにより行われる。観測値に欠損がある場合もEMアルゴリズムなどを使い最尤推定によりパラメータ学習が行われる。構造学習について言えば、RDBにおける表Xの興味ある属性X.Aに対し、その親となる属性Pa(X.A)をデータから求めるのがPRMの構造学習となる。各変数の親となる変数を決めるという意味で通常のベイジアンネットの構造学習と同じとなるが、探索空間を狭めるため、探索する参照の連鎖τの長さを制御する必要がある。PRMは推薦システムなどに応用され、またその後、構造的不確定性を取り入れたり、実態関連モデル(entity-relationship model;ERモデル)と組み合わせるなどの発展があった。

マルコフ確率場とSRLとMLN,PSL

PRMを術後論理の立場から振り返ってみると、表の関係を表す術後、表のタプルを固体と思えば、固体とそれらの関係を扱っていることになる。表Xにタプルt₁,…,t_nがあることをX(t₁,…,t_n)という術後論理のアトムにより表す。ここでXは述語記号、tiは項と呼ばれる。この式は「t1,…,tnはXという関係にある」という命題(proposition)を表す。すると、関係データベスは変数を持たないアトム(基底アトム(groud atom)と呼ばれる)の有限集合と等価であり、PRMは、たとえばX(t₁,…,t_n)の項tiとY(s₁,…,s_m)の項sjの確率的依存関係を記述できる。しかしX(t₁,…,t_n)⇒Y(s₁,…,s_m)のような論理的依存関係はたとえ成り立っていたにしても記述することも利用することもできない。まして∀x bird(x)⇒can_fly(x)のような普遍限量子によって表現される一般法則の扱いは考慮の外となる。

述語論理においては、項はx,y,z,…のような変数、もしくは0,1,2,…のような定数、あるいはさらに複雑なfather_of(x)のような関数であり、個体を表す。アトムあるいはその否定をリテラル(literal)、リテラルの選言(disjunction)を節(clause)と呼ぶ。節に変数がある場合には∀により縛られているものとみなす。節の部分クラスとしてA⇐B1∧…∧Bn、あるいは同じものであるがB1∧…∧Bn⇒A(n≥0<A,Biはアトム)の形をした定節があり、n=0の場合は(アトムと一致する)特に単節(unit clause)と呼ばれる。bird(x)⇒can_fly(x)は定節の例であり、(変数は∀に縛られているとみなすので)すべてのxについて、もしxがbirdならばxは飛べる(can_fly)ことを言っている。節は単節の集合としての関係データベースも表せるし、友達の友達はまた友達である(friend(x,y)∧friend(y,z)⇒friend(x,z))のような再帰的推移則も表せる、知識表現にとって強力な表現形式となる。

したがって、関係データベースよりも強力な記述力を持つ術後論理の節を使って個体及び個体艦の関係に基づく確率モデルを構築することも当然考えられる。SRLでは種々の試みがなされており、一つの代表例が重み付き節集合によりマルコフ確率場(MArkov random field)を定義するマルコフ論理ネットワーク(Markov logic network;MLN)となる。

MLNについて語るためには可能世界という概念が便利となる。一般に論理式の真偽については領域(集合)を定め、その上での基底アトムの真偽を定め、順次より複雑な式の真偽を定めることによりその領域におけるすべての論理式の真偽を定める。節の場合、領域として基底項(変数を持たない項,ground term)の全体の集合、すなわちエルブラン領域(Herbrand universe)を使うのが通例となる。エルブラン領域におけるすべての規定アトムの真偽値を定めるものをエルブラン解釈(Herbrand interpretation)と呼ぶ。以後エルブラン解釈を可能世界と呼ぶ。MLNは実数の重みがついた節集合により可能世界の確率分布を与える。例としては以下のものとなる。

これは喫煙と友人関係に関するMLNを定める重み付き節集合となる(A⇒Bは¬A∨BとA⇔Bは(A⇒B)∧(B⇒A)と等価なので、上の2式は節集合に書き換えられる)。節の重みが大きいほど、その節は可能世界で真になる確率が高い。

エルブラン領域が有限で{a,b}の2個体からなる場合を考える。節の可能な基底代入例(節のすべての変数に基礎項を代入したもの)の全体を考え、同一の節の基底代入例に出現する基底アトムを辺で結ぶことにより図のような無向グラフが得られる。

たとえばfreind(x,y)⇒(smokes(x)⇔smokes(y))のxにa、yにbなる基底代入を行えばfriends(a,b)⇒(smokes(a)⇔smokes(b))基底代入例が得られ、ここに出現する基底アトムfriends(a,b),smokes(a),smokes(b)は辺で結ばれてクリークとなる。

この無向グラフにおいて基底アトムは1(真)、0(偽)を取る確率変数であり、グラフは基底アトムの確率的依存関係を定めるマルコフ確率場を表す。節Cの基底代入例に対応したクリークは節に付随した重みWcが与えられている。可能世界ωの生成確率は大数線形(log-linear)モデル\(p(\omega)\propto exp\left(\displaystyle\sum_C W_C\cdot N_c(\omega)\right)\)により与えられる。ただし、Nc(ω)はωが真とする節Cの基底代入列の数となる。

MLNは従来の対数線形モデルの素性として1,0の値を取る基底節を使ったものと捉えることもできる。単純な仕掛けであるが、基底を素性として使うことにより、命題間の論理的依存関係を節として記述するだけでなく、その依存関係が成り立つ程度を計算できる確率として与えることに成功している。MLNは推薦システムを始め、自然言語処理など広範囲に適用が試みられている。

MLN以外の比較的最近提案されたマルコフ確率場のクラスとして確率的ソフトロジック(probabilistic soft logic;PSL)がある。MLNと同じく0.3 : friend(B,A) ∧ votesFor(A,P) → votesFor(B,P)のような重み付き節からなるプログラムを使うが、命題の確率値が連続値を取るところが根本的に異なり、そのおかけでMLNより計算上有利な点がある。具体的にみるとPSLにおいて真偽値は区間[0,1]の連続血をとり、基底アトムにそのような値をパラメータとして割り当てた後、基底アトムからからなる任意のブール式の確率値が以下のように再帰的に計算される。

\begin{eqnarray}\omega(A∧B)&=&max(0,\omega(A)+\omega(B)-1)\\\omega(A∨B)&=&min(1,\omega(A)+\omega(B))\\\omega(¬A)&=&1-\omega(A)\end{eqnarray}

プログラムの重み付き節r=λ:B→Hに対し、この節の「真になることからの距離」をd_r(ω)=max(0,ω(B)-ω(H))により定義する。d_r(ω)=0はω(B)≤ω(H)と同値であり、これはB→H(ブール代数を一般化した)ハイティング代数における真値を扱っていることと同値となる。

可能世界ωの生起確率は\(P(\omega)\propto exp\left(-\displaystyle\sum_{r\in R}\lambda_r\cdot d_r(\omega)\right)\)で与えられる。ここでRはPSLプログラムの重み付き節の基底代入例の集合であって、今問題となっている確率モデリングに関係する基底アトムだけからなるものとなる。多くのrに対しdr(ω)=0が成り立つようなωの生起確率が高いことがわかる。

MLNに比べPSLの有利な点として、最尤の説明(most probable explanation;MPE)問題を高速に解けることが挙げられる。MPE問題は世界ωの一部が観測され真偽が固定されている時、P(ω)の最大値を与える残りの基底アトムの真偽値(パラメータ)を求める問題となる。

PSLの場合MPEを解くには\(\phi=\displaystyle\sum_{r\in R}\lambda_r\cdot d_r(\omega)\)の最小値を与えるパラメータを求めるのであるが、φがパラメータの関数として凸であり、またdr(ω)もパラメータの線形関数から行為せされているので、高速にこのMPEを解ける。

以上SRLについて述べた。総じてSRLは、ベイジアンネットの記述力を向上させるために論理式を導入したものの、ある種の便利な(マクロのような)関数として利用するだけで、論理学との繋がりは弱い。

次回はヨーロッパで発展したPLL(probabilistic logic learning;確率論理学習)について述べる。