確率と論理を融合したモデリング(2) PLL(確率論理的学習)

確率と論理を融合したモデリング(2) PLL(確率論理的学習)

岩波データサイエンスvol3「確率と論理を融合した確率モデリング」より。

述語論理とPLL

前回は北米で発達したSRL(stastical relational learning 統計的関係学習)について述べた。今回はヨーロッパの対抗馬であるPLL(probabilistic logic learning;確率論理学習)について述べる。

前述したPRM(probabilistic relational model 確率的関係モデル)やMLN(Markov logic network;マルコフ論理ネットワーク)等のSRLは関係式や論理式を使い確率モデルを豊かにしようという発想に基づいており、関係式や論理式を使うものの、術後論理を確率によって豊かにすることは直接の目的ではない。一方、人工知能の分野では術後論理による知識表現が古くから研究されており、そこに確率を取り入れて、常に成り立つ論理的知識だけでなく確率的な知識も表現しようとする試みが統計的機械学習がブームになる以前からあった。

人工知能研究における論理から確率への接近は、おそらく1986年のNilsonの研究に始まる。Nilsonは確率付きの論理式からなる知識ベースを考え、それを可能世界-知識ベースのモデル-の生起確率の制約として捉えて、知識ベースから定理として導かれる論理式の確率の上限値と下限値からなる区間を計算してみせた。その後1990年第二入り、論理プログラミング(logic programming)に確率を導入する確率的論理プロクラミングの研究が盛んになる。

論理プログラミングとは定節をプログラムコードとして使うプログラミング方式で、言語としてPrologが代表的であり、それに影響を与えた遠縁の関数型言語としてはLispやErlangがある。

論理プログラミングに対しては、大別して2種類の確率化方式が提案されている。一つはNilsonのように論理式に確率の区間を与える方法で、もう一つは論理式に確率値を与える方式となる。後者の方式については、Pooleにより離散ベイジアンネットが論理式で表現できることが示された。しかし、どちらの方式でも確率は天下り式に与えられることが仮定され、確率をデータから学習することは想定されていなかった。

その後Satoにより確率化された最小モデル意味論に沿ってデータから確率を統計的に学習する方式が提案され、隠れマルコフモデルや確率文脈自由文法の統計的学習が可能となった。一方で、論理プログラミングから派生した論理に基づき構造学習を行うILP(inductive logic programming;帰納的論理プログラミング)の研究でも、1990年第二ベイジアンネットとの融合研究が始まった。ILPは正例、負例から論理式の形でデータの規則性を抽出するが、ベイジアンネットを取り込むことにより術後論理の高い表現力を保ったまま、現実データのノイズや欠損などの不確実性を扱えるようになると期待された。現在ではこれらの研究は、先述した確率論理プログラミングと併せてPLLと呼ばれている。

PLLは主として西ヨーロッパで研究されていたが、2000年代に入ると確率と論理への共通の関心を背景に北米のSRLと西ヨーロッパのPLLとの交流が始まり、大西洋を挟んで穏やかなコミュニティが形成された。その後順調に研究の発展が続き、例えばPLLではlifted inferenceと言われる。論理式の対称性などを利用した確率計算の効率化が熱心に研究されたが、2010年までにはSRLもPLLも研究が一段落した。

それと同時にSRL/PLLの流れに沿い、その初志とねいえるAIにおける高級言語による機械学習の実現を目指す「確率プログラミング」(probabilistic programming;PP)の動きが出て、米国DARPAのPPAML(probabilistic programming for advanced machine learning)プロジェクトに引き継がれている。確率プログラミングはグラフィカルモデルや確率文法の枠を超えたTuring completeな汎用プログラミング言語を用い、高級言語による自由度の高い確率モデリングを目指すもので、Schemaに基づくChurchやClojureに基づくAnglicanなどはノンパラメトリック・ベイズモデルを非専門家にも比較的気軽に扱えるようにしている。

SRLもPLLもどちらも確率モデルを投じて論理と確率を結びつけようとしたが、まだ道半ばである。両者の結びつけ方も単に確率と呼ぶ数値を論理式に与えるようなアドホックなものもあり、(離散的な)確率モデリングとして両者を厳密に統合した試みは少ない。

帰納論理プログラミング(ILP;inductive logic programming)と確率

ILPは90年代初頭に英国のMuggletonにより提唱された知識獲得の方法で、規定アトム(ground atom)により、正例、負例を表し、これらの例から確定節(define clause)の形で例に潜む規則性を取り出そうというものになる。その後発展と分化を繰り返しつつ主として黄酒に広まり、現在は機械学習における構造学習の一種として定着している。

一方ILPに確率を導入するPLLの動きは90年代半に始まり現在に続いている。例えばMuggletonは確定節とCFG規則の類似性に着目し、丁度CFG規則に確率を付与してPCFGができるように、確定節に確率を付与することにより、証明されるアトムに確率を付与する方式を提案し、SLP(stochastic logic programming;確率論理プログラミング)と呼んだ。2000年代に入るとベルギーのDe Raedtを中心とするILPのグループによりMuggletonとは別の方法でILPに確率を導入する研究が盛んになったが、書紀には確定節を使ってベイジアンネットワークを定義するものが多く、確率計算と学習はベイジアンネットワーク依存であった。

MuggletonにしてもDe Raedtにしても述語論理式から出発し、そこに確率を付与する道を辿ったが、彼らはデータマイニングへの応用の意識が強く、無限を扱う道具として述語論理を選んだわけではない。論理式は(変数を含んで便利ではあるが)複雑な名前として便宜的に使われことが多く、論理式に確率を割り当てているにもかかわらず、可能世界上の確率測度との関連に関する意識は薄かった。

ILPに関しては現在でも活発に研究が行われており、学会も開催されている。

確率と論理を結びつける

SRL/PLLは述語論理で表現された知識と確率計算や学習を確率モデルを通じて結びつけようとするものとなる。しかし、論理や確率は互いに独立した学問であり、単に論理式を確率モデルで使ったからと言って両者を矛盾なく融合させたことにはならない。確率と論理を矛盾なく数学的に結びつける定理としてFenstradの表現定理がある。

この定理は論理的に確率を矛盾なく割り当てられるためには可能世界に確率測度P(*)を定義し、論理式φに対し、それを真にする可能世界ωの全体(ω|ω⊨φ)をφの確率にしなさいと言っている。この定理から、計算可能な可能多世界を計算機に実装し、その上に確率測度を定義すれば、数学的に矛盾のない論理式の確率計算及び学習が可能となるであろうということが示唆される。

またFenstadの表現定理に基づき人工的に確率測度を持つ有限の可能多世界(エルブラン解釈{ω1,ω2,…,ωn})を作って確率計算のシミュレーションを行うことができる。具体的にはそれぞの可能世界の生起確率\(\lambda(\omega_1),\dots,\lambda(\omega_n)(\sum_{i=1}^n\lambda(\omega_i)=1)\)を定め、閉論理式φに対してはφを真にする可能世界の生起確率の和をφの関数とすれば良い。

\[P(\phi)=\displaystyle\sum_{\omega⊨\phi,1≤i≤n}\lambda(\omega_i)\]

具体例として、エルブラン領域は2つの定数(a,b)からなり、言語𝓛は述語記号としてR(*,*)しかもたないものとする。4つの基底アトム(変数を持たないアトム){R(a,a),R(a,b),R(b,a),R(b,b)}が存在しそれらの真偽値を決める可能世界(エルブラン解釈は全部で24=16個存在する。今可能世界の生起確率の和が1となるように次のように可能世界の正規確率を決める。

すると以下のように確率が計算される。

\begin{eqnarray}P(∃x_1R(x_1,a))&=&\lambda(\omega_1)+\lambda(\omega_2)=0.2+0.3=0.5\\P(∀x_1R(x_1,a))&=&\lambda(\omega_2)=0.3\\P(∀x_1∃x_2R(x_1,x_2))=&=&\lambda(\omega_1)+\lambda(\omega_2)+\lambda(\omega_3)=1.0\end{eqnarray}

これらを使い最終的にP(R(x1,x2))=0.2・0.5+0.3・0.9+0.5・0.4=0.57を得て、この可能世界では述語R(x1,x2)は平均0.57の確率で真となる。

論理に基づく確率モデリング

前回はFenstadの表現定理に基づき人工的に確率測度を持つ有限の可能多世界を作って確率計算のシミュレーションをおこなった。言い換えると確率モデルを作ったものとなる。この試みを一般化して実装すれば、論理に基づく確率モデルが実現できるはずで、今回はそれらについて述べる。

以後は簡単のため確率は閉論理式の確率だけを考える。この場合Fenstadの表現定理によれば可能多世界上の確率測度を定めればよく、各可能世界ごとの確率測度は考える必要はない。従って論理に基づく確率モデリングがなすべきことは以下の3つとなる。

• 定義: 可能多世界の確率測度を定義する。
• 定義計算: 論理式の確率の計算を行う
• 定義学習:データから確率を学習する。

最初の課題は可能多世界の確率測度を定義することとなるが、可能世界が無限の場合は難しくなる。簡単のために我々が使う一階言語𝓛の基底アトムの全体をBで表し、エルブラン基底と呼ぶ。可能世界はエルブラン基底から{1(真)、0(偽)}へのマップであり、従って可能世界は2^|B|個ある(|B|はBの濃度)。関数記号がない場合Bは有限集合なので、前回のシミュレーションのとおり可能世界を数え上げ、各世界に和が1になるように確率を割り振れば良い。

しかし、関数記号がある場合、Bは加算無限となり、可能世界は2^|B|、すなわち実数の数と同じだけある。従って全部を数え上げて確率を割り振ることは不可能となる。

純粋に数学的な観点から言えば、実数濃度を持つ可能多世界上に確率測度を定義することは可能である。しかし、機械学習を目指す立場から言うと2番目の課題が重要で、この確率測度は計算できるものでなければならないし、さらに効率良く計算可能であってほしいという工学的要求もある。また、3番目の課題に関連して、確率モデルとしては統計学習が可能なようにパラメータ化されている必要がある。

分布意味論

Fenstadの表現定理が機械学習にもたらす可能性を最大限に活かすには、有限のグラフィカルモデルを超えてプログラミング言語のレベルで確率モデリングを実現する必要がある。無限の世界を扱う確率モデルはマルコフ連鎖(Markov chain)やPCFG(確率文脈自由文法)など多数あり、それぞれ別々の分野として研究がなされているが、グラフィカルモデルを含め、有限なモデルであろうと、無限なモデルであろうとそれらをすべて論理に基づく確率モデリングにより吸収する。

論理の世界にはPrologという論理に基づいたプログラミング言語が昔から存在し、多様な処理系も開発維持されているので、Prologのプログラミング機能をすべて保持しつつPrologを確率プログミングげんこせに拡張することを考える。

まずプログラミング言語の確率化だけが目的ならばプログラムに確率的要素をトノ入れれば良い。プログラミング言語の基礎であるTuring機械を考えれば、状態遷移は非決定性であり、それを確率的選択に置き換えれば確率的Tuting機械を得る。同じくPrologの呼び出し節の選択を確率的に行えば、確率的Prologを得ることができる。

しかし、これは単に計算を確率化するだけに留まる。Fenstadの定理が示すところの確率空間につながるためには確率的論理プログラムが可能多世界上の確率測度を定義しなければならないが、この立場を「分布意味論」という。分布意味論はプログラムの数学的意味を定める表示意味論(denotational semantics)の一種であり、現在確率論的論理プログラムの標準的意味論となっている。

分布意味論はサイコロによる確率的選択、すなわちカテゴリカル分布から出発する。加算個のカテゴリカル分布の直積分布を基本分布と呼ぶ。たとえばカテゴリカル分布がベルヌーイ分布のとき基本分布は0,1の無限列の全体{0,1}^∞の上の確率測度になる。分布意味論ではこの固定された基本分布を論理プログラムで加工することにより現実世界を近似するより複雑な分布を作り出す。

技術的には通常の非確率的論理プログラムの標準的意味論である最小モデル意味論(least model semantics)とKolmogorovの拡張定理を利用して基本分布を可能多世界上の分布に拡張するが、その結果論理プログラムを書くことによりいくらでも複雑な分布が表現可能となり、実際にBN(ベイジアンネット)、LDA、HMM(隠れマルコフモデル)あるいはPCFGなど現在の標準的確率モデルを含む非常に広範囲の生成的確率モデルが分布意味論により表現可能となる。