Inverse Entailment and Progol Stephen Muggleton 1995年，Muggletonによって、New Generation Computing で発表された論文です。 帰納論理プログラミングの１つProgolについての論文です。 有川研究室　修士1年 坂東　恭子

発表の流れ ・はじめに ・帰納論理プログラミング（ILP）とは ・Progolの説明 ・まとめ

はじめに 機械学習：決定木 帰納論理プログラミング（ILP） 一階述語論理式を学習しよう 背景知識を使おう 機械学習：帰納推論、PAC学習がある。　命題論理上の学習、複雑な学習ができない 一階論理式を学習しよう。より複雑な学習のために背景知識を使おう。 帰納論理プログラミング　Inductive Logic Programming この名前もMuggletonによってつけられた 帰納論理プログラミング（ILP）

帰納論理プログラミングとは？ 背景知識、正例、負例 負例を説明せず、正例を説明する仮説をみつける 帰納論理 プログラミング 機械学習 logic programming 機械学習 　machine learning 帰納論理プログラミングの位置付け 機械学習を一階論理式に拡張したということで、 論理プログラミングと機械学習のintersection 背景知識について説明 背景知識、正例、負例 負例を説明せず、正例を説明する仮説をみつける

ILP システムの例 ・GOLEM ：92年、Muggletonらによって開発された 　　　　　　　　　RLGG(Relative Least General Generalization) 　に基づくILPシステム ・Progol　:95年、Muggletonらによって開発された 　　　　　　　逆伴意（inverse entailment）に基づくILP 　　　　　　　システム ・FOIL　:90年、Quinlanによって開発されたILPシステム ・GKS　：95年、溝口によって開発されたILPシステム RLGG＝相対最小汎化 Muggleton　：York大学 Quinlan:　　シドニー大学

Progol とは？ ・95年、Muggletonによって開発されたILP システム ・C, Prologで作られたシステム ・逆伴意（inverse entailment）の考えを使う Prolog　論理プログラミングでよく使われる まず、伴意の説明

伴意(entailment)とは？ A ⊨ B ・伴意 ＝ 論理的帰結 ・記号 ⊨ を使う ・BはAの伴意である ・BはAの論理的帰結である ＝　 論理的帰結 ・記号 ⊨ を使う A　⊨　B ・BはAの伴意である ・BはAの論理的帰結である 論理的帰結とは Aのすべてのモデルが、Bのモデルである Aを真とするような解釈はすべて、Bも真とする。 ・背景知識＋仮説　⇒　例 記号を使って表すと B(背景知識)　∧　H（仮説）　⊨　E（例）

逆伴意(inverse entailment)とは？ 伴意：B(背景知識)　∧　H（仮説）　⊨　E（例） 演繹定理より 　H（仮説）　⊨　 B(背景知識) → E（例） 逆伴意： 伴意を逆向きに読む　　　　　　 　　　　　　背景知識と例から仮説を得る

Progolの仮説生成プロセス 逆伴意に基づき最も特殊な節（最弱仮説）を構成 最も特殊な節を包摂する空間（最弱仮説空間） において、最良優先探索 最良な仮説をみつける

仮説と最弱仮説の関係 正例 仮説 仮説 正例 最弱仮説 最弱仮説 仮説 一般的 特殊化 特殊化 特殊化 正例 特殊 ここを求める 探索空間が 縮小される 正例 仮説 特殊化 仮説 最弱仮説 特殊化 ここを求める 仮説を特殊化することによって正例は求められる 正例から仮説を求めるには考慮すべき空間が大きい 最弱仮説を求めると考慮する空間が縮小される 最弱仮説 正例 特殊化 特殊 正例

最弱仮説の生成    なぜ？ Hから伴意されることを示す。 ・B  ￢ Eから最弱仮説を演繹的に計算可能 対偶をとって ￢（B → E）　⊨　￢ H  すべてのモデルで真な基底 リテラルの連言（）：bot(B,E) B  ￢ Eから演繹に計算される節が，Hの最弱仮説となることをしめす Hから伴意されることを示す。 もし、Hがbot(B、E)の部分連言じゃなかったら もし、bot(B,E)以外の基底リテラルを含めば，その余分なリテラルを 含まないモデルが存在 　　　　 　　B  Eのすべてのモデルで真とはならない B  ￢ E　⊨　￢ H なぜ？ B  ￢ E　⊨　￢　bot(B,E)  ￢ Hは￢　bot(B,E) 　の部分連言（）

証明：￢ Hは￢ bot(B,E)の部分連言（） ￢　bot(B,E) = l1 ・・・  ln ￢　H = l1 ・・・  ln  lk  lk+1 B  ￢ E　にはlk , lk+1を 含まないモデルが存在 矛盾 B  ￢ E　 ⊭　￢ H

H ⊨ bot(B,E) B  ￢ Eから最弱仮説を演繹的に計算可能 B  ￢ E ⊨　￢　bot(B,E) 　⊨　￢ H 対偶をとって H 　⊨　 bot(B,E) 　 最弱仮説MSH 連言だと部分連言は伴意される Bと￢ E から伴意されるなかで一番特殊 最弱仮説は仮説から伴意されるから B  ￢ Eから最弱仮説を演繹的に計算可能

正例：　　　　　　　　　　負例： gf（波平，タラオ）　　　　　　gf（波平 ，カツオ） gf（洋平，カツオ） 　　　　　gf（舟，タラオ）　 gf（洋平，サザエ）　　 　　　gf（洋平，タラオ） gf（洋平，ワカメ） 背景知識：f（波平，サザエ）， m（舟，ワカメ）， f（波平， カツオ），f（波平，ワカメ）， 　　　　　 m（サザエ，タラオ），f（洋平，波平） 　　　　　　 p（A，B）:- f（A，B），p（A，B）:- m（A，B）

母 洋平 海平 妹 波平 舟 ワカメ カツオ サザエ マスオ タラオ

 f（波平，サザエ） m（舟，サザエ） f（波平，カツオ）  f（波平，ワカメ） m（サザエ，タラオ）  f（洋平，波平） 正例E+： gf（波平，タラオ）について B　　 　￢E　　⊨　　 ￢MSH ￢MSHはB  ￢Eのすべてのモデルで真 B　　 　￢E = ￢ gf（波平，タラオ） 　　  f（波平，サザエ） m（舟，サザエ） f（波平，カツオ） 　　  f（波平，ワカメ） m（サザエ，タラオ）  f（洋平，波平） 　　  p（A，B）:- f（A，B）  p（A，B）:- m（A，B） ￢MSH は基底リテラルの連言 = ￢ gf（波平，タラオ） 　 f（波平，サザエ） m（舟，サザエ） f（波平，カツオ）  f（波平，ワカメ） m（サザエ，タラオ）  f（洋平，波平） 　 p（波平，サザエ） p（舟，サザエ） p（波平，カツオ） 　 p（波平，ワカメ） p（サザエ，タラオ）  p（洋平，波平） ￢MSHは連言なので，B　　 　￢Eの部分集合 部分集合だったらいいので， B　　 　￢Eごとを最弱仮説とする

 f（波平，サザエ） m（舟，サザエ） f（波平，カツオ）  f（波平，ワカメ） m（サザエ，タラオ）  f（洋平，波平） MSH ＝￢ (￢ gf（波平，タラオ） 　 f（波平，サザエ） m（舟，サザエ） f（波平，カツオ）  f（波平，ワカメ） m（サザエ，タラオ）  f（洋平，波平） 　 p（波平，サザエ） p（舟，サザエ） p（波平，カツオ） 　 p（波平，ワカメ） p（サザエ，タラオ）  p（洋平，波平）) と同じ意味 ＝gf（波平，タラオ）:- f（波平，サザエ）, m（舟，サザエ）, 　　　　　　　　　　　　 f（波平，カツオ）, f（波平，ワカメ）, 　　　　　　 m（サザエ，タラオ）,f（洋平，波平）, 　　　　　　　　　　　　　 p（波平，サザエ）, p（舟，サザエ）, 　　　　　　　　　　　　 p（波平，カツオ）, p（波平，ワカメ）, 　　　　　　 p（サザエ，タラオ）,p（洋平，波平）

最弱仮説から仮説を求める 最弱仮説を伴意する 最良な仮説を求める 伴意を包摂で近似し、 仮説空間を探索しよう H（仮説）　⊨　 MSH（最弱仮説） 一般的 最弱仮説を伴意する 最良な仮説を求める 伴意を機械的 に行うのは困難 最弱仮説と仮説にも節の関係が適応され 仮説を特殊化したものが最弱仮説 最弱仮説は仮説によって伴意されるから 最弱仮説を伴意するような仮説を求めればいい でも、伴意を機械的にやることは困難 伴意を包摂で近似し、 仮説空間を探索しよう 特殊 最弱仮説

Progolの仮説生成プロセス 逆伴意に基づき最も特殊な節（最弱仮説）を構成 最弱仮説を包摂する空間（最弱仮説空間） において、最良優先探索 最弱仮説を包摂するような節はたくさんあるので探索が必要 最良な仮説をみつける

A*-like 探索 ・Progolで使われている探索方法 ・最弱仮説空間（最弱仮説を包摂する空間）を 探索し、最良仮説を得る

A* 探索 ・グラフにおける最良優先探索 ・評価関数 f(n) を最小にするパスをみつける。 f(n)＝g(n)＋h(n) : n経由の最短解の見積りコスト g(n):出発接点から接点nまでの経路のコスト h(n):ヒューリスティック関数 nからゴールまでの見積りコスト 最良優先探索とは，最良に見える接点を選択する

S 14 B I 10 10 8 21 A H 18 E 9 10 C 14 G 7 13 12 D F

ヒューリスティック関数（ゴールとの直線距離） S : 36 A : 32 B : 25 C : 24 D : 23 E : 19 F : 16 H : 10 I : 18 G : 0 S f=36 A B f=10+32=42 f=14+25=39 S E I f=24+36=60 f=22+19=41 f=24+18=42

よって、最良経路は、S  B  E  H  G E f=22+19=41 B F H f=31+10=41 f=38+16=54

S 14 B I 10 10 8 21 A H 18 E 9 10 C 14 G 7 13 12 D F

A*-like 探索グラフの生成 ・探索空間・・・最弱仮説（MSH）を包摂する空間 ・（empty set）からはじまるグラフを作り、そのグラフ 　について最良優先探索を行う。 A*探索はグラフにおける最良優先探索なので、まずグラフを作る

MSH(最弱仮説) ＝gf（波平，タラオ）:- f（波平，サザエ）, m（舟，サザエ）, f（波平，カツオ）, f（波平，ワカメ）, 　　　　　　　　　　　　　 p（波平，サザエ）, p（舟，サザエ）, 　　　　　　　　　　　　 p（波平，カツオ）, p（波平，ワカメ）, 　　　　　　 p（サザエ，タラオ）,p（洋平，波平）

 gf（A，B） 最も特殊な節 gf(A,B):-f(A,C),m(D,C),f(A,E),m(C,B),f(F,A), -m(C,D) -m(C,B) -f(C,A) -p(A,C) -p(C,D) -p(C,B) gf（A,B）： -f(A,C), m(D,C) m(C,B) f(D,A) p(A,C) p(D,C) p(C,B) p(D,A) ・・・・・・ まず、empty　set 次に、headだけからなる節 その後は，リテラルを1つづつ追加していく 追加するリテラルは、最弱仮説を包摂するもの そうすると最後には、最弱仮説の基礎アトムを変数に変えてあげたのになる 最も特殊な節 gf(A,B):-f(A,C),m(D,C),f(A,E),m(C,B),f(F,A), p(A,C),p(D,C),p(A,E),p(C,B),p(F,A)

グラフ内A*-like探索 －(｛仮説のリテラル長｝＋ ｛説明される負事例の数｝) ・評価関数として記述長最小原理を使う。 ・compression gainが最も大きいものが最良 compression gain＝ 　 －(｛仮説のリテラル長｝＋ ｛説明される負事例の数｝) {説明される正事例の数} A ｛仮説のリテラル長｝＝ ｛その時点の仮説のリテラル長｝＋｛追加されるリテラル長｝ g(n) ＝ ｛仮説のリテラル長｝＋｛説明される負事例｝

・｛追加されるリテラルの最小値｝をヒューリスティック 関数で与える 　関数で与える ・　f(n)＝説明される正事例の数－｛ g(n) ＋ h(n)｝　 　が最大になる仮説を見つける ・全解探索（仮説空間すべて考慮） h(n)＝ head部の出力変数がすべて、body部の入力変数 　　　　として存在しない時に追加するリテラルの最小値 gf（A,B）： -f(A,C) Bについてのリテラルを追加 p(A,B,C): -q(A,D) B, Cについてのリテラルを追加

 gf（A，B） 最良な仮説 4 － (10+0)= ｰ6 ｰ3 ｰ1 ｰ3 ｰ1 ｰ3 2 ｰ3 例 4 － (0+3+2)= －1 4 － (1+2+1) = 0 gf（A,B）： -f(A,C) -m(C,D) -m(C,B) -f(C,A) -p(A,C) -p(C,D) -p(C,B) ｰ2 0 －2 －1 　　－2 　　 0 gf（A,B）： -f(A,C), m(D,C) m(C,B) f(D,A) p(A,C) p(D,C) p(C,B) p(D,A) ｰ3 ｰ1 ｰ3 ｰ1 ｰ3 2 ｰ3 ・・・・・・ ・・・・・・ ・・・・・・ ・・・・・・ 最良な仮説 gf(A,B):-f(A,C),m(D,C),f(A,E), 　　　　　m(C,B),f(F,A), p(A,C), 　　　　　p(D,C),p(A,E),p(C,B),p(F,A) 4 － (10+0)= ｰ6

実世界での応用 ・突然変異性物質の判別問題（King） ・データベースからの知識発見（嶋津，古川） 電子メール分類システム ・暗黙知の獲得（古川） 　　　理想的な弓の動かし方 事例：突然変異を有する化合物 背景知識：化合物の原子と結合情報  　仮説：化合物の突然変異性に関するルール

まとめ ・Progolにおける仮説生成 ・Progolの利点 逆伴意に基づき，背景知識と正例から最弱仮説 を生成 最弱仮説を包摂する木においてA*-like探索 ・Progolの利点 探索空間が縮小される

背景知識 ・既に持っている知識 ・背景知識があるとより正確な理論が 　得られる ・背景知識として、事実とルールが利用 　可能

背景知識なし 背景知識あり 正例：D1 = CuddlyPet(x)  Small(x) , Fluffy(x) , Dog(x) D2 = CuddlyPet(x)  Fluffy(x) , Cat(x) Cuddly：やわらかい Fluffy：ふわふわした C = CuddlyPet(x)  Fluffy(x) 背景知識あり 背景知識： Pet(x)  Cat(x) , Pet(x)  Dog(x) Small(x) Cat(x) D = CuddlyPet(x)  Small(x) , Fluffy(x) , Pet(x)

特殊な節とは？ ・節には半順序関係がある p(A,B) p(A,A). ＞ p(A,B) p(A,B):-q(A,B) ＞ 一般的 一般的：多くの例を説明する 特殊：少ない例しか説明しない p(A,B) 　 p(A,A). ＞ 一般的　　　 　　特殊 p(A,B) 　 p(A,B):-q(A,B) ＞ p(A,B) 　 p(桂子,B) ＞ 特殊

記述長最小原理 記述長最小原理 ・学習の記述量・・・機械学習にとって重要な問題 ・記述量の多い仮説が多くの例を説明できるのは 当然 　当然 できるだけ少ない記述量で多くの例を説明はできないか？ 記述長最小原理

包摂（subsumption）とは？ 定義： H1,H2:節 H1θ ⊆ H2 となるような代入θが存在 H1はH2をθ-subsume（θ-包摂）する。 例: parent（花子, 太郎）:- mother(花子, 太郎)を考える 包摂する節　　parent(花子, 太郎) 　　　　　　　　 parent (A, 太郎)： - mother(花子, 太郎) parent (A, B) :- mother (A, B) 包摂しない節 parent(花子，次郎) 　　　　　　　　　　 parent (A, B) :- mother (B, A)　 包摂　＝　部分集合　＋　逆代入

伴意と包摂の関係 　A subsume(包摂する) B  A ⊨ B 伴意を包摂で近似しよう

部分連言だと伴意される B ⊨ A ：BはAを伴意する A=l1･･･ln B=l1･･･lnln+1

正例：　　　　　　　　　　負例： gf（波平，タラオ）　　　　　　gf（波平 ，カツオ） gf（洋平，カツオ） 　　　　　gf（舟，タラオ）　 gf（洋平，サザエ）　　 　　　gf（洋平，タラオ） gf（洋平，ワカメ） 背景知識：f（波平，サザエ）， m（舟，ワカメ）， f（波平， カツオ），f（波平，ワカメ）， 　　　　　 m（サザエ，タラオ），f（洋平，波平） 　　　　　　 p（A，B）:- f（A，B），p（A，B）:- m（A，B）