二分決定グラフを用いた帰納論理プログラミングの解の列挙

二分決定グラフを用いた

帰納論理プログラミングの解の列挙

Enumeration of Solutions of Inductive Logic Programming with

Binary Decision Diagrams

新藤 光

1∗

_{西野 正彬}

2

_{山本 章博}

3

Hikaru Shindo

1

_{Masaaki Nishino}

2

_{Akihiro Yamamoto}

3

1

_{京都大学工学部}

1

_{Faculty of Engineering, Kyoto University}

2

_{NTT コミュニケーション科学基礎研究所}

2

_{NTT Communication Science Laboratories}

3

_{京都大学情報学研究科}

3

_{Graduate School of Informatics, Kyoto University}

Abstract: We propose a method to enumerate solutions of a given Inductive Logic Programming

(ILP) problem by a Binary Dicision Diagram (BDD). ILP is a machine learning technique based on first-order logic. A BDD is a graph representation of a boolean function of a comparably small node size. We show an algorithm for building BDD by recursively using the apply operation. In addition, we propose an efficient method to select the best hypothesises following Minimum Description Length principle (MDL). The results show that a lot of solutions are represented in one BDD of a small node size, and we found the best solutions following MDL efficiently.

1

はじめに

帰納論理プログラミングとは, 問題を一階述語論理で 表現することにより, 様々な分類問題を解決する機械学 習手法である. これまでの帰納論理プログラミングに 関する研究では, 問題の解である仮説を一つ見つける手 法の開発が中心であった. しかし, 複数の仮説を発見す ることができれば, 仮説同士を比較して, より有用な仮 説を選ぶことなどが可能になる. そこで, 本稿では帰納 論理プログラミングが解として出力する仮説を列挙す る方法を検討する. なお，仮説空間を有限とするため に，本稿では各仮説はあらかじめ与えられた n 個の確 定節からなる集合の部分集合であるとする． 仮説空間が有限であったとしても，仮説の候補の数は 2n個存在するため，素朴な方法で仮説を列挙するのは

難しい．そこで, 本報告では, Binary Decision Diagram (BDD) を用いることで大量の仮説を列挙する方法を検 討する. BDD とは, ブール関数を比較的小さいサイズ のグラフで表現することができるデータ構造であり, 計 ∗_{連絡先： 京都市左京区吉田本町京都大学情報学研究科知能情報} 学専攻山本研究室       〒 606-8501 京都市左京区吉田本町 36-1        E-mail: [email protected] 算機上のブール関数の効率的な表現方法として知られ ている. 本稿では, 帰納論理プログラミングの仮説の集 合を表す BDD を構築することを考える. ある確定節 が仮説に含まれるかどうかを一つの命題変数で表現す ると，仮説の列挙は n 引数のブール関数を同定する問 題と等価となる．本稿では，BDD の apply 演算を用い ることで仮説の集合を表す BDD を効率的に求められ ることを示す． また，得られた BDD を使った応用として，記述長最小 原理 (Minimum Description Length principle; MDL) に基づいて最良の仮説を取り出すことができることを 示す. 最良の仮説を一つ取り出す問題は, 動的計画法に よって BDD の大きさに比例する時間で解くことがで きる. さらに,  最良の仮説が複数存在する場合に，そ れらの集合を表す BDD を効率的に構築できることも 示す. 人工知能学会研究会資料 SIG-FPAI-B509-01

2

準備

2.1

帰納論理プログラミング問題

一階述語論理を用いて, 正例の集合E+_{, 負例の集合} E−_{, 背景知識B が与えられたとき,} B ∪ Σ ⊨ E+_{,B ∪ Σ ⊭ E}− ₍₁₎ をみたすような節の有限集合 Σ 見つける問題を帰納論 理プログラミング問題 (Inductive Logic Programming problem; ILP) という. 本稿では, 条件 (1) を満たす, 問題の解となる節の集合を仮説 (hypothesis) と呼ぶ. 例 2.1.1 正例の集合E+_{, 負例の集合E}−_{, 背景知識B} が次のように与えられたとき,

E+_{={e(0), e(s}2_{(0))}, E}−_{={e(s(0))}, B = {}.} この帰納論理プログラミング問題の解となる仮説 Σ と して,

Σ ={e(0), e(s2(0))}, Σ ={e(0), e(s2(x))← e(x)} などが挙げられる.

2.2

二分決定グラフ (BDD)

BDD(Binary Decision Diagram) とは, Akers[1] に

よって提案され, Bryant[2] が発展させたブール関数を コンパクトに表現できるデータ構造である. 図 1 は, ブール関数 (x0∧ x1)∨ x2 を表す BDD である. 各内部 ノード

⃝

j は, 命題変数の変数名やインデックスでラベ ルが付けられている. 本稿では, インデックスが j の命 題変数 xj に対応するノードを

⃝

j と表す. 各内部ノー ドは, 点線と実線でそれぞれ表される 2 つの枝をもち, それぞれ 0–枝 (low-branch), 1–枝 (high-branch) とい う. グラフの終端には, f alse を表す終端ノード 0 と, true を表す終端ノード 1 がある. 親をもたないノー ドをルート (root) という. ルートからノード 0 に到 達するパスは, そのパスに対応する命題変数の値の割 り当て上で, 真偽値は偽であるということを表し, 逆に ルートからノード 1 に到達するパスは, そのパスに対 応する命題変数の値の割り当て上で, 真偽値は真である ということを表す. 本稿では, ノード数は非終端ノード のノード数を表すこととする. 0 1 0 2 1 図 1: (x0∧ x1)∨ x2を表す BDD

3

帰納論理プログラミングの仮説の

列挙

3.1

命題変数の生成

仮説に含まれうる節の有限集合を_{H とすると, 帰納} 論理プログラミングの問題は,H の部分集合のうち, 条 件を満たすものを探す問題として定式化することがで きる. 仮説を全列挙する問題は, 条件を満たすH の部 分集合の集合族を見つける問題である. これは, 適当な 命題変数を用意すると, ブール関数を同定する問題とし て定式化することができる. ここで, 仮説空間H に含まれる各節 C に対して, 節 C が仮説 Σ に含まれるとき真になるような命題変数 [C∈ Σ] を考える. C∈ Σ ⇔ [C ∈ Σ] = T この命題変数を用いて, 仮説の集合を表す BDD を構築 する. 例 3.1.1 例 2.1.1 の問題について, 命題変数を生成す る. 仮説空間H を, 例えば, {e(0), e(x),

e(s(0)), e(s(x)), e(s(x))← e(x), e(s2(0)), e(s2(x)), e(s2(x))← e(x),

e(s2(x))← e(s(x)), e(s2(x))← e(s(x)) ∧ e(x)} と定めたとき, 作成する命題変数は

[e(0)∈ Σ] [e(s2_{(0))∈ Σ]} [e(x)∈ Σ] [e(s2_{(x))∈ Σ]} [e(s(0))∈ Σ] [e(s2(x))← e(x) ∈ Σ] [e(s(x))∈ Σ] [e(s2_{(x))← e(s(x)) ∈ Σ]} [e(s(x))← e(x) ∈ Σ] [e(s2_{(x))← e(s(x)) ∧ e(x) ∈ Σ]} のようになる.

3.2

BDD の構築

ここでは, 式 (1) で表される条件を満たす仮説の集合 を表す BDD の構築する方法を示す. 正例の集合E+_{, 負} 例の集合_E−, 背景知識B, 仮説空間 H が与えられてい るとする. ただし,E+_,E−_{は基礎確定節のみからなると} する. C∈ H なる確定節 C について, 命題変数 [C ∈ Σ] を表す BDD を ICとする. 基礎単位節 C ∈ E+∪ E− について, Σ∪ B ⊨ C のとき真になるブール関数を表す BDD を FCとする. C∈ B なる基礎単位節 C については, 常に Σ∪B ⊨ C が成り立つ. T を表す BDD を FTとすれば, 基礎単位 説 C∈ B について, FC= FT (2) が成り立つ. 基礎単位節 C ∈ (E+_{∪ E}−_{)− B について, Σ ∪ B ⊨ C} が成り立つかどうかに影響するのは, ある代入 θ が存在 して, Dθ = C ← B1∧ . . . ∧ Bn となる確定節 D∈ H である. 確定節 D が Σ に含まれ, かつ Dθ = C ← B1 ∧ . . . ∧ Bn なる原子論理式 B1, . . . , Bn がすべて Σ∪ B の論理的帰結になるとき, Σ ∪ B ⊨ C が成り立つ ので, 基礎単位節 C∈ (E+_{∪ E}−_{)− B について,} FC= ∨ D∈H ∃θ Dθ=C_←B1∧...∧Bn∈H  ID∧ ∧ 1≤i≤n FBi   となる. 帰納論理プログラミングの仮説の集合を表す BDD は, ∧ C_∈E+ FC∧ ∧ C_∈E− ¬FC (3) と表される. BDD(3) は, 等価性 (2) より, ∧ C_∈E+_−B FC∧ ∧ C_∈E−_−B ¬FC (4) と同値である. 具体的なアルゴリズムは, Algorithm1 のように表 される. 例 3.2.1 例 2.1.1 において, 例 3.1.1 のように命題変数 を作成したとき, 仮説の集合を表す BDD を構築する手 順を示す. Algorithm 1 ILP の仮説の集合を表す BDD の構築 Input: 正例の集合E+_{, 負例の集合E}−_{, 背景知識B，} Output: 仮説の集合を表す BDD F 1: H ← 要素数が有限の仮説空間 2: Sp← 空集合 3: Sn← 空集合 4: for each e+ inE+− B 5: Fp← L(e+) を表す BDD の構築 (e+,H, B) 6: Spに Fpを追加 7: for each e− in E−− B 8: Fn ← L(e−) を表す BDD の構築 (e−,H, B) 9: Snに Fnを追加 10: Fp← Spの要素すべての論理積をとった BDD 11: Fn ← Sn の要素の否定すべての論理積をとった BDD 12: return Fp∧ Fn

Fe(0), Fe(s(0)), Fe(s2(0))は順に,

Fe(0)= Ie(0)∨ Ie(x),

Fe(s(0))= Ie(s(0))∨ Ie(x)∨ Ie(s(x))

∨(Ie(s(x))←e(x)∧ Fe(0)

) ,

Fe(s2₍₀₎₎= I_e(s2₍₀₎₎∨ I_e(x)∨ I_e(s(x))∨ I_e(s2_(x))

∨(Ie(s2_(x))←e(x)∧ F_e(0)

) ∨(Ie(s2_{(x))←e(s(x))}∧ F_e(s(0))

)

∨(Ie(s2(x))_{←e(s(x))∧e(x)}∧ Fe(s(0))∧ Fe(0)

) . のように計算でき, 仮説の集合を表す BDD は,

Fe(0)∧ Fe(s2₍₀₎₎∧ ¬F_e(s(0))

で得られ, 図 2 のようになる. 3.2.1 提案手法が適用可能な条件 仮説空間_{H について, 提案手法が適用できる条件を} 示す. 定理 1 Algorithm1 によって有限のステップ数で BDD を構築することができる必要十分条件は, 任意の確定節 A← B1∧ . . . ∧ Bn∈ H について, A⪰ Bi (i = 1, . . . , n) なる順序関係 _{⪰ を定義したとき,} A⪰ X1, X1⪰ X2, . . . , Xn ⪰ A となるようなリテラルの列_{{Xi}i=1,...,n} が存在しない ことである.

0 ⃝[e(0) ∈ Σ] 1 ⃝[e(x) ∈ Σ] 2 ⃝[e(s(0)) ∈ Σ] 3 ⃝[e(s(x)) ∈ Σ] 4 ⃝[e(s(x)) ← e(x) ∈ Σ] 5 ⃝[e(s2_{(0))∈ Σ]} 6 ⃝[e(s2_{(x))∈ Σ]} 7 ⃝[e(s2_{(x))← e(x) ∈ Σ]} 8 ⃝[e(s2_{(x))← e(s(x)) ∈ Σ]} 9

⃝[e(s2_{(x))← e(s(x)) ∧ e(x) ∈ Σ]}

0 1 0 1 2 3 4 5 6 7 図 2: 命題変数と仮説の集合を表す BDD 例 3.2.2 条件を満たす仮説空間の例として, 縮小確定 節 (reducing definite clause)[6] のみからなる仮説空間

がある. 例 3.1.1 で定めた仮説空間H は, 縮小確定節の みからなるので, 仮説の集合を表す BDD を有限ステッ プで構築できる.

4

MDL

における最良の仮説の探索

と列挙

4.1

記述長最小原理

仮説の簡潔さを表す指標として, 記述長最小原理 (Min-imum Description Length principle; MDL)[10] があ る. MDL は, データとモデルを含めて, これらを最も 少ない記述量で記述できるモデルが最良であるとする モデル選択原理である. 仮説は節の集合であり, 節はリ テラルの選言からなるので, 本稿では, 仮説 Σ の記述長 をリテラルの数で近似し, MDL に基づいた評価関数と して, M DL(Σ) = p− (n + c) (5) を定義する. ここで, p ={C|C ∈ E+, Σ⊨ C} の要素数, n ={C|C ∈ E−, Σ⊨ C} の要素数, c = ∑ C_∈Σ l(C) である. ただし, l(C) は節 C を構成するリテラルの数 である. 本稿では, 問題の解として正しい仮説のみを考 えるので, p =|E+_{|, n = |ϕ| = 0 となる.}

4.2

MDL における最良の仮説の探索

MDL における最良の仮説を, 構築した BDD から取 り出すことを考える. 式 (4) で表される BDD におい て, 各ノード i の重みとして, 対応する確定節 C の評価 値 l(C) を割り当てる. つまり, ノード i が表す命題変 数が [C ∈ Σ] のとき, ノード i の重み wiを, wi = l(C) (6) とする. 式 (4) で表される BDD 上に, 式 (6) のように 節と重みを対応付けた BDD について, 次の定理が成り 立つ. 定理 2 正例の集合E+_{, 負例の集合E}+_{, 背景知識B が与} えられた帰納論理プログラミング問題について, 式 (4) で表される BDD 上に, 式 (6) のように節と重みを対応 付けた BDD を F とする. F において, ルートから終 端ノード 1 へのパスのうち, 重みの和を最小にするパ スにおいて, 1-枝をとるノードに対応する節のみからな る仮説は記述長最小原理における最良の仮説である. ルートからノード 1 への重みの和が最小のパスを 動的計画法を用いて計算する方法を説明する. ノー ド数 n の BDD と, インデックス i のノードの重み wi(i = 2, . . . , n + 1) が与えられ, トポロジカル順序に 従ってノードにそれぞれインデックスが割り振られて いるとする. ただし, ノード 0 , ノード 1 , ルートの インデックスはそれぞれ 0, 1, n + 1 とする. 各ノード i において, ノード i からノード 1 まで のパスの重みの和で最小の値を mi とする. はじめに, m0, m1 を以下のように初期化する. m0=∞, m1= 0. i > 1 なるノード i において,

mi= min (m[lowi], m[highi] + wi)

ここで, lowi, highiはノード i の 0–枝, 1–枝をたどっ た先のノードのインデックスを表している. このとき, ti=        0 (m[lowi] > m[highi] + wi) 1 (m[lowi] < m[highi] + wi) 2 (m[lowi] = m[highi] + wi) を記憶しておく. 全てのノードについて mi, tiを計算した後, BDD の ルートから ノード 1 までたどることで, 最良の仮説が 得られる. ここで, ノード i において, たどる先として 選択する枝は, ti の値によって, 選択する枝 =        0–枝 (ti= 0) 1–枝 (ti= 1) 0–枝または 1–枝 (ti= 2) と定める.

4.3

MDL における最良の仮説の列挙

評価値が同じであるような最良の仮説が複数ある場 合が考えられる. このとき, 最良の仮説の集合を表す BDD を構築することを考える. 4.2 のように, mi, ti を計算後, ルートからノードをたどりながら, 最良の仮 説の集合を表す BDD を構築する. 以下の操作を, BDD のノード数が 1 以下になるまで続ける. ノード i において, 1. ti = 0 のとき, ノード i の 1–枝の指す先をノー ド 0 に移し, 0–枝をたどった先の部分木に対し て, 処理を繰り返す. 2. ti = 1 のとき, ノード i の 0–枝の指す先をノー ド 0 に移し, 1–枝をたどった先の部分木に対し て, 処理を繰り返す. 3. ti= 2 のとき, ノード i の 0–枝をたどった先の部 分木, 1–枝をたどった先の部分木それぞれに対し て, 処理を繰り返す. ここで, ノード i の枝の指す先をノード 0 を移し替え る操作は, ノード i に対応する命題変数 1 つからなる BDD と, 先を移し替えない枝をたどった先の部分木が 表す BDD の論理積を取ることによって行うことがで きる. ここまでの操作で得られた BDD は, 構築した BDD に現れない変数についての情報をもたない. 式 (5) の値 は非負であるため, 仮説の正しさに影響しない冗長な節 は, 最良の仮説にはすべて含まれない. そのため, BDD に現れない変数すべての否定の論理積をとった BDD を 考え, 上の操作で得られた BDD との論理積をとれば十 分である.

5

実験

本稿で提案した手法を評価するために, 以下のような 実験を行った. • 自然数の分類問題について, 問題のサイズを変え ながら, 仮説の集合を表す BDD を構築した. • 公開されている実データに関する分類問題につい て, 仮説の集合を表す BDD を構築した.

実行環境は, OS: Ubuntu 17.10, CPU: Intel Xeon(R) E5-1650 v3 3.50GHz×12 , RAM: 125.8GB であり, 実 装言語には Scala 2.11.4 を用い, BDD の実装は Jav-aBDD1_{を用いた.}

1_{http://javabdd.sourceforge.net/}

5.1

自然数の分類問題

基礎単位節 e(0), e(s(0)), e(s2_{(0)), . . . , e(s}n_{(0)) に対}

して, 正例の集合と負例の集合がそれぞれ, n が偶数のとき,

E+_{={e(0), e(s}2_{(0)), . . . , e(s}n_(0))},

E−_{={e(s(0)), e(s}3_{(0)), . . . , e(s}n+1_(0))}

n が奇数のとき,

E+_{={e(0), e(s}2_{(0)), . . . , e(s}n+1_(0))},

E−_{={e(s(0)), e(s}3 (0)), . . . , e(sn(0))} のように与えられる帰納論理プログラミング問題を考 える. ただし, 背景知識は空集合とした. 仮説空間は, 次のように制限した. 次の 4 つの条件をすべて満たす 確定節 C = A← B1∧ . . . ∧ Bnからなる集合をJ とす

る. (i) C は縮小確定節. (ii)|A| < max

D∈E+_∪E−|D|. (iii) 節

中に現れる述語記号, 関数記号, 定数記号はE+_{∪ E−に}

現れるもののみである. (iv) 節中に変数が現れる場合, 節を構成するすべてのリテラルにその変数が現れる. このとき,H = E+_{∪ E}−_{∪ J を仮説空間とする.} 例 5.1.1 n = 1 のときの問題は,

E+_{={e(0), e(s}2_{(0))}, E}− _={e(s(0))},

H = {e(0), e(x), (s(0)), e(s(x)), e(s(x)) ← e(x), e(s2(0)), e(s2(x)), e(s2(x))← e(x),

e(s2(x))← e(s(x)), e(s2(x))← e(s(x)) ∧ e(x)}. のようになる.

5.2

実データの分類問題

公開されている実データに関する分類問題を, 帰納論 理プログラミングの問題に変換した. 仮説空間に含ま れる確定節の本体の長さの最大値は 2 とした. 実データ として, UCI Machine Learning Repository2 _{より, (1)} Soybean(small)3 _{と (2) Shuttle Landing Control}4 _を 用いた. 目標概念をそれぞれ D1, no auto としたもの を, 問題 (1), 問題 (2) とする.

5.3

結果と考察

自然数の分類問題について, 表 1 から, n が大きくな るにつれて, 仮説の総数は指数関数的に増加している ことがわかる. また, 仮説の総数の増加に比べ, 変数の 2_{http://archive.ics.uci.edu/ml/index.php} 3_{https://archive.ics.uci.edu/ml/datasets/soybean+(small)} 4_{https://archive.ics.uci.edu/ml/datasets/Shuttle+Landing+Control}

n 変数の数 BDD のノード数 仮説の総数 BDD の構築時間 探索時間 最良 BDD の構築時間

1 10 8 28 7.56msec 0.98msec 0.62msec

2 19 14 192 9.63msec 1.09msec 0.68msec

3 36 27 1.2517376× 107 _{1.90× 10msec 2.00msec 1.02msec}

4 69 42 1.305670057984× 1013 _{3.08× 10msec 2.38msec 1.16msec}

5 134 69 4.817059901466879× 1032 _{7.00× 10msec 6.87msec 1.48msec}

6 263 101 9.770133092280778× 1063 _{3.50× 10}2_{msec 1.31× 10msec 2.21msec} 7 520 156 2.2626082457629705× 10141 _{1.68× 10}3_{msec 4.44× 10msec 1.68msec} 8 1033 219 1.7976931348623157× 10308_{以上 1.20× 10}4_{msec 1.88× 10}2_{msec 2.66msec}

表 1: 自然数の分類問題に関する実験結果

問題 変数の数 BDD のノード数 仮説の総数 BDD の構築時間 探索時間 最良 BDD の構築時間

(1) 2243 788498 1.7976931348623157× 10308_{以上 13495msec 911msec 1153msec}

(2) 117 2345 6.7593966143× 1010 _{30msec 9msec 6msec}

表 2: 実データの分類問題に関する実験結果 数, BDD のノード数の増加は緩やかである. さらに, 仮 説を一つ一つ探索するよりはやく BDD を構築できて おり, 効率よく最良の仮説を取り出せていると考えら れる. 実データの分類問題について, 表 2 より, 仮説の集合 を表す BDD は, 非常に大きい仮説の総数に対して, 比 較的少ないノード数の BDD で表せていることがわか る. また, 最良の仮説の集合を表す BDD についても, 比較的短い実行時間で構築できていると考えられる. ま た, 問題 (1) で実際に得られた 2 つの最良の仮説は, Σbest={class(x, D1) ← stem canker(x, above soil)},

Σbest={class(x, D1) ← fruiting bodies(x, absent)}

であった. 確定節の集合の形で表すことのできる規則 のうち, シンプルに記述できる仮説を, 最良の仮説とし て取り出せていることがわかる.

6

おわりに

本稿で提案した手法では, 複数個の BDD に演算を適 用するが, 先頭の BDD から順に演算を適用していく と, 一つの BDD が非常に大きくなり効率が悪い. そ のため, 小さいものから順に演算を適用していくなど の工夫が考えられる. また, BDD の他にゼロサプレス 型二分決定グラフ (Zero–supressed Decision Diagram; ZDD)[7] を用いて列挙することも考えられる.

謝辞

本研究は一部 JSPS 科研費 JP17K19973 及び京都大 学情報学研究科–NTT コミュニケーション基礎科学研 究所共同研究の支援を受けている.

参考文献

[1] Akers, S.B.: Binary Decision Diagram, IEEE Trans. on Computers, Vol. C-27, No. 6, pp. 509-516 (1978).

[2] Bryant, R.E.: Graph-Based Algorithms for Boolean Function Manipulation, IEEE Trans. on Computers, Vol. C-35, No. 8, pp. 677-691 (1985). [3] Gr¨unwald, P.D.:The Minimum Description Length Principle, vol. 1, MIT Press Books, Boston, MA, The MIT Press, (2007).

[4] 古川幸一, 尾崎知伸, 植野研: 帰納論理プログラミ ング, 共立出版 (1994).

[5] Knuth, D.E.: The Art of Computer Programming, Volume 4, Fascicle 1, chapter 7.1.4, pp. 70-148 (2008).

[6] 近藤誠一, 山本章博: SAT ソルバーを用いた帰納論 理プログラミング, 人工知能学会研究会資料 (SIG-FAI-B104), pp. 75-80 (2012).

[7] Minato, S.: Zero-suppressed BDDs for set manip-ulation in combinatorial problems, Proceedings of the 30th international Design Automation Confer-ence (DAC). ACM, pp. 272-277 (1993).

[8] 森下真一: 知識と推論, 共立出版 (1994).

[9] Muggleton, S.: Inverse entailment and Progol, New generation computing, Vol. 13, No. 3, pp. 245-286 (1995).

[10] Rissanen, J.: Modeling by Shortest Description, Automatica, Vol. 14, pp. 456-471 (1978).