テックカリキュラム

探索しない帰納論理プログラミング「Top program構築」とは?

探索しない帰納論理プログラミング「Top program構築」とは?

1. はじめに:探索しない帰納論理プログラミング

帰納論理プログラミング(Inductive Logic Programming、ILP)は、正例・負例と背景知識から、論理プログラム(Prolog のルール)を学習する機械学習の分野です。ニューラルネットワークのように重みを学習するのではなく、人が読めるルールそのものを出力するため、説明可能性や少ないデータからの汎化が求められる場面で研究されてきました。

ただし ILP には大きな弱点があります。多くのシステムは「候補となるルールの組み合わせ」を探索して正しい仮説を見つけるため、学習したいプログラムが大きくなると探索空間が指数的に膨らみ、現実的な時間で終わらなくなります。

本記事では、この問題に正面から取り組んだ論文「Top Program Construction and Reduction for polynomial time Meta-Interpretive Learning」(Stassa Patsantzis, Stephen H. Muggleton, Imperial College London。2021年1月 arXiv 公開、Machine Learning 誌の特集号「Learning and Reasoning」に掲載)を解説します。論文の主張は次の3点です。

  • 正しい仮説をすべて集めた和集合(Top program)は、それ自体が正しい仮説になる
  • Top program は探索をせずに、有限個の例から多項式時間で構築できる
  • 構築した Top program から冗長な節を取り除く(縮約する)ことで、実用的な仮説が得られる。これを Prolog で実装した学習システム Louise は、仮説空間と目標プログラムがともに大きい場合や、ラベル誤りがある場合に、探索型の代表的システム Metagol を上回った

応用レベルの記事として、Prolog の基本(事実、ルール、再帰)と、機械学習の「仮説空間」「汎化」といった用語を知っている方を想定しています。

2. 前提知識:ILPとメタ解釈学習(MIL)

2-1. ILPの問題設定

ILP では、次の3つを入力として、目標の述語(学習したい関係)を定義するルールの集合 H を出力します。

  • 正例 E⁺:成り立つべき事実(例:path(a, b))
  • 負例 E⁻:成り立ってはいけない事実(例:path(1, 2))
  • 背景知識 B:あらかじめ与えるルールや事実(例:edge(a, b))

出力される H が正しい仮説であるとは、背景知識と合わせてすべての正例を導出でき、どの負例も導出しないことをいいます。

H∧B⊧E+かつ∀e−∈E−: H∧B⧸⊧e−

記号 ⊨ は「論理的に導かれる」、⊭ は「導かれない」を表します。

2-2. メタルールで仮説の形を制限する

メタ解釈学習(Meta-Interpretive Learning、MIL)は ILP の一つの枠組みで、作れるルールの形をメタルール(metarule)という2階の節で制限します。メタルールは述語名の部分が変数になったルールのひな型です。論文に挙げられている代表例を示します。

名前メタルール表す構造
IdentityP(x, y) ← Q(x, y)別の関係で言い換える
InverseP(x, y) ← Q(y, x)引数を入れ替える
ChainP(x, y) ← Q(x, z), R(z, y)2つの関係をつなぐ(推移)
TailrecP(x, y) ← Q(x, z), P(z, y)末尾再帰
PreconP(x, y) ← Q(x), R(x, y)前提条件を付ける

P、Q、R に具体的な述語名(path、edge など)を代入すると、1本の具体的なルールができます。この代入をメタ代入(metasubstitution)と呼び、メタルールと背景知識・例に現れる記号から作れるルール全体を仮説言語 L と呼びます。

2-3. 仮説空間は仮説言語のべき集合

仮説はルールの集合なので、仮説空間 ℋ は L のべき集合(すべての部分集合の集まり)です。L が数百本のルールを含むだけで、部分集合の数は天文学的になります。代表的な MIL システム Metagol は、仮説のルール数を1本ずつ増やしながら探索する反復深化で正しい仮説を探します。論文によれば、このため MIL の先行研究で Metagol が学習した単一述語のプログラムは、多くが5節以下にとどまっていました。

3. Top programという発想

3-1. Top programの定義

論文の出発点は、図1に示されている単純な観察です。仮説空間 ℋ を探索するのは仮説言語 L の大きさに対して指数時間かかりますが、L の要素(ルール)を列挙するだけなら多項式時間で済みます。そこで、探索の対象を「ルールの集合」から「ルール1本ずつ」に切り替えます。

Top program ⊤ は次のように定義されます。L の各ルール C について、

  • 背景知識と合わせて少なくとも1つの正例を導出し
  • どの負例も導出しない

ならば C は ⊤ に含まれます。つまり、1本ずつ見て「役に立ち、かつ害がない」ルールをすべて集めたものです。

3-2. Top programは正しい仮説になる(定理1)

論文の定理1は、「仮説空間に正しい仮説が1つでもあれば、⊤ も正しい仮説である」というものです。直感的には次のように理解できます。

  • 正しい仮説 H があるなら、H の各ルールは負例を導出しないので ⊤ に含まれる条件を満たす。正例を1つも導出しない無駄なルールを除いても H の正例の導出は変わらないので、⊤ はすべての正例を導出できる
  • ⊤ のどのルールも単独では負例を導出しないので、⊤ 全体も負例を導出しない

正しい仮説の和集合なので、⊤ は正しい仮説の中で最も一般的なものです。論文は、Plotkin の最小汎化(LGG)や Muggleton のボトム節のように「探索せずに直接構築できる唯一の対象」と比較し、それらとの違いは ⊤ が1本の節ではなく、節の集合(仮説そのもの)である点だと述べています。

ただし、1本ずつでは負例を導出しないルールが、複数そろったとき(再帰ルールを含む場合など)に負例を導出するケースについて、論文の証明は詳しく論じていません。論文の証明は簡潔な背理法で書かれており、ここでは論文の主張として紹介します(この点は解説者の補足です)。

4. Top program構築アルゴリズム

4-1. 汎化ステップと特殊化ステップ

論文の Algorithm 1 は2段階でできています。

  1. 汎化(Generalise):各正例 e⁺ について、メタルール M にメタ代入 μ を適用したルール Mμ が、背景知識 B と正例 E⁺ と合わせて e⁺ を導出できるものをすべて集める
  2. 特殊化(Specialise):各負例 e⁻ について、集めたルールのうち e⁻ を導出してしまうものを取り除く

汎化で「正例を1つ以上説明できるルール」を網羅し、特殊化で「負例を説明してしまうルール」を削るという、3-1 の定義をそのまま手続きにしたものです。探索もバックトラックによる仮説の作り直しもありません。

4-2. 具体例:グラフの経路

論文の表1の例を示します。2種類の辺 edge_alpha(a→b→c)と edge_alnum(a→b→c と 1→2→3)があり、経路 path を学習します。

正例: path(a,b).  path(a,c).
負例: path(1,2).  path(1,3).
背景知識: edge_alpha(a,b). edge_alpha(b,c).
          edge_alnum(a,b). edge_alnum(b,c). edge_alnum(1,2). edge_alnum(2,3).
メタルール: P(x,y) :- Q(x,y).
            P(x,y) :- Q(x,z), R(z,y).

汎化ステップでは、正例を導出できるルールとして次の9本が集まります。

path(x,y) :- edge_alnum(x,y).                      % 負例 path(1,2) を導出 → 削除
path(x,y) :- edge_alpha(x,y).
path(x,y) :- path(x,y).
path(x,y) :- edge_alnum(x,z), edge_alnum(z,y).     % 負例 path(1,3) を導出 → 削除
path(x,y) :- edge_alnum(x,z), edge_alpha(z,y).
path(x,y) :- edge_alpha(x,z), edge_alnum(z,y).
path(x,y) :- edge_alpha(x,z), edge_alpha(z,y).
path(x,y) :- path(x,z), edge_alnum(z,y).
path(x,y) :- path(x,z), edge_alpha(z,y).

特殊化ステップで、負例を導出する2本(コメントで「削除」と書いたもの)が取り除かれ、残りの7本が Top program になります。edge_alnum だけでつないだルールは数字のノードにも当てはまってしまうため、負例によって排除されるわけです。

4-3. 再帰的なルールも学習できる理由

汎化ステップでは、メタルールの本体を背景知識だけでなく正例とも照合します。上の例の path(x, y) ← path(x, z), edge_alpha(z, y) のように、目標述語 path 自身を本体に含む再帰的なルールが作れるのはこのためです。正例は有限個の基底事実(変数を含まない事実)なので、照合が無限再帰に陥ることはありません。複数の目標述語を同時に与えれば、相互再帰も学習できます。論文の表5では、後者関数 predecessor を背景知識として、偶数 even と奇数 odd を相互再帰で定義するプログラムを学習しています。

even(0).
even(X) :- predecessor(X,Y), odd(Y).
odd(X)  :- predecessor(X,Y), even(Y).

5. 理論的な保証:健全性・完全性と計算量

5-1. 帰納的な健全性と完全性

論文は、Algorithm 1 が帰納的に健全(負例を導出するルールを出さない)かつ完全(正例を導出するルールをすべて出す)であることを示しています(定理2)。根拠は、確定節プログラムに対する SLD 導出(Prolog の推論方式)の健全性と完全性です。

5-2. 有限個の例で十分(定理3)

必要な例の数にも上限があります。論文の補題5によれば、Top program を構築するまでに処理すべき正例は高々 |⊤| 個、負例は高々「正例を1つ以上導出するルールの数 − |⊤|」個です。L は有限なので、これらも有限になります。ただし論文は、PAC 学習の意味でのサンプル複雑度はまだ導出しておらず、今後の課題としています。

5-3. 多項式時間と指数時間の比較

メタルールの数を m、述語記号の数を p、メタルール本体のリテラル数の上限を k とすると、仮説言語の大きさは高々 m·p^(k+1) です(Cropper と Tourret の結果)。正例の数を c とすると、Algorithm 1 の計算量と、n 節以下の仮説を探索する場合の計算量は次のようになります。

Top program構築: O(cmpk+1)探索: O((cmpk+1)n)

左は仮説言語の大きさに比例する多項式時間、右は目標プログラムの節数 n を指数に持つ時間です。目標プログラムが大きいほど差が開きます。論文の実験データセットでは、グリッドワールドの仮説言語の大きさの上限が 81,450,625 本、仮説空間の大きさの上限は 2.037 × 10⁴⁹⁴⁴ と見積もられています。

6. 学習システムLouiseの仕組み

6-1. カプセル化による実装

Louise は Algorithm 1 を Prolog で実装した MIL システムです。Prolog では述語名を変数にしたままの単一化を直接書けないため、Louise は問題全体をカプセル化(encapsulation)します。たとえば edge(a, b) を m(edge, a, b) という1階のアトムに書き換え、メタルール P(x, y) ← Q(x, z), R(z, y) も m(P, x, y) ← m(Q, x, z), m(R, z, y) と書き換えます。こうすると述語名も通常の引数として扱え、Prolog の導出でメタ代入を求められます。学習結果は最後に元の形に戻します(excapsulation)。

6-2. Plotkinのプログラム縮約で冗長な節を除く

Top program は正しい仮説の和集合なので、冗長なルールを多く含みます。4-2 の例の path(x, y) ← path(x, y) のように、何も新しいことを言わないルールも入っています。Louise は Gordon Plotkin が1972年に示したプログラム縮約アルゴリズムを使い、「残りのルールから導出できるルール」を1本ずつ取り除きます。

  1. 未チェックのルール C を1つ選ぶ
  2. C を除いた残りの集合から C が導出できる(SLD 導出で確かめる)なら C を削除し、できなければ C に印を付ける
  3. すべてのルールに印が付くまで繰り返す

4-2 の例では、7本の Top program が次の4本に縮約されます(論文の表2)。

path(x,y) :- edge_alpha(x,y).
path(x,y) :- edge_alnum(x,z), edge_alpha(z,y).
path(x,y) :- path(x,z), edge_alnum(z,y).
path(x,y) :- path(x,z), edge_alpha(z,y).

7. 実験:Metagolとの比較

7-1. 3つの実験仮説

論文は、Louise と Metagol を比べる前に、次の3つの実験仮説を立てています。

  • 仮説1:仮説空間 ℋ と目標プログラム Θ がともに大きいとき、Louise が Metagol を上回る
  • 仮説2:ℋ に正しい仮説が含まれない(ラベル誤りがある)とき、Louise が Metagol を上回る
  • 仮説3:ℋ が Top program 1つだけからなるとき、両者は同等になる

実験は、学習データの割合を 0.1 から 0.9 まで変えながら100回ずつ(グリッドワールドは計算時間の都合で10回)学習と評価を繰り返す学習曲線の形で行い、1回の学習には300秒の時間制限を設けています。時間切れの場合は空の仮説として正解率を計算します。

7-2. 3つのデータセットと結果

データセット内容結果
グリッドワールド4×4 の格子上の移動経路。上下左右の基本移動と、組み合わせた移動を背景知識に与えるMetagol は学習データが62例の時点で時間切れ。Louise は短時間で汎化性能の高い仮説を学習(仮説1を支持)
色付きグラフ2色の有向非巡回グラフでの連結関係 connected/2。例の20%を誤ラベルにした3種類のノイズ設定とノイズなしノイズありでは正しい仮説が存在せず、Metagol の正解率は空の仮説と同じ。Louise はノイズなし以外で上回った(仮説2を支持)
M:tG 断片カードゲーム Magic: The Gathering のカード文の一部を表す文法。正例1,348件、目標は36節両者がまったく同じ仮説を学習し、正解率の曲線も一致(仮説3を支持)

M:tG の実験では、各正例がちょうど1本のルールで導出されるため、仮説空間が実質的に1つの正しい仮説に「つぶれ」ます。このとき Metagol も36節のプログラムを学習でき、これは先行研究で報告されていた Metagol の学習プログラムの7倍以上の大きさだったと論文は述べています。

7-3. Louiseが苦手なケース

結果は Louise に一方的に有利なものではありません。色付きグラフのノイズなし設定では、目標の定義に不要な背景知識の述語が多く含まれていたため、Louise は過度に一般的なルールを学習し、序盤の正解率が Metagol より低くなりました。不要な述語を除いて仮説空間を小さくした再実験では、ノイズなしの正解率は改善した一方で、偽陰性(正例を負例と誤ラベル)の設定では悪化し、正例と負例の両方に誤ラベルを入れた設定では空の仮説より悪い結果になっています。

8. 実務での考え方とよくある誤解

8-1. どんなときにTop program構築が向いているか

論文の結果を踏まえると、使い分けの目安は次のとおりです。

  • 学習したいルールの数が多く、組み合わせの探索が現実的でない場合
  • 学習データにラベルの誤りが混じる可能性があり、「完全に正しい仮説」が存在しないかもしれない場合
  • 逆に、仮説空間が小さい場合や、背景知識に無関係な述語が多く負例が少ない場合は、探索型でも十分か、そちらのほうが良いこともある

8-2. よくある誤解

  • 誤解1:多項式時間なら何でも速い。計算量は仮説言語の大きさ m·p^(k+1) に比例するので、背景知識の述語数 p やメタルール本体の長さ k が増えると、多項式でも急速に重くなります。
  • 誤解2:Top program をそのまま使えばよい。Top program は正しい仮説の中で最も一般的なものなので、負例が少ないと過度に一般的なルールを含みます。縮約と、十分な負例が欠かせません。
  • 誤解3:メタルールは自動で決まる。MIL ではメタルールの選択が強い帰納バイアスになり、論文の実験でも人が選んでいます。論文は、ニューラルネットワークのアーキテクチャ選択や SVM のカーネル選択と同じ種類の問題だと位置づけ、Louise にはメタルールの抽出・生成のライブラリがあると述べています。

9. 論文に対する評価と限界

9-1. 論文が主張していること

論文が主張しているのは、Top program が正しい仮説であること、その構築アルゴリズムと、有限個の例・多項式時間で構築できることの証明、Louise の実装、Metagol との比較実験です。今後の課題としては、過度に一般的な Top program への対策(最小サイズの正しい仮説を選ぶ別の縮約手続き)、述語発明(新しい補助述語を自動で作ること)を行う Dynamic Learning 設定の詳しい説明、メタルールの自動選択、サンプル複雑度の導出、MIL 以外の ILP 設定や Answer Set Programming での実装を挙げています。

9-2. 解説者による補足

以下は論文の記述をもとにした解説者の見解です。

  • 「最も一般的な正しい仮説」の扱い:Top program は定義上、負例で否定されない限りルールを残します。負例を集めにくい現場では過度な一般化が起きやすく、出力されたルールを人がレビューする運用が現実的です。ILP の強みである「読めるルールが出る」点が、この確認を助けます。
  • 実験規模:実験は3種類のデータセットで、グリッドワールドは 4×4 と小さく、比較対象も Metagol のみです。2021年時点の論文であり、その後に登場した ILP システムとの比較は含まれていません。
  • LLM時代の位置づけ:大規模言語モデル(LLM)がコードを生成する現在でも、正例・負例に対する整合性が論理的に保証されたルールを、少ないデータから学習できる点は ILP の独自の価値です。LLM が提案したルール候補を、Top program 構築のような健全な手続きで検証・絞り込むといった組み合わせも考えられます(これは解説者の見解であり、論文では扱っていません)。

10. まとめ:探索から構築へ

本記事では、メタ解釈学習(MIL)における Top program 構築と縮約を解説しました。要点は次のとおりです。

  • 帰納論理プログラミングの多くは仮説空間(ルールのべき集合)を探索するため、目標プログラムが大きいと指数時間がかかる
  • 正例を1つ以上導出し、負例を導出しないルールをすべて集めた Top program は、それ自体が正しい仮説になる
  • Top program は汎化(正例で集める)と特殊化(負例で削る)の2段階で、探索せずに多項式時間・有限個の例で構築できる
  • Plotkin のプログラム縮約で冗長な節を除くと、実用的な仮説が得られる。再帰や相互再帰のルールも学習できる
  • 実装 Louise は、仮説空間と目標プログラムが大きい場合やラベル誤りがある場合に Metagol を上回った。一方で、無関係な背景知識が多く負例が少ない場合は過度に一般的になりやすい

「組み合わせを探す」のではなく「条件を満たす部品をすべて集めてから削る」という発想の転換は、ILP に限らず、組み合わせ爆発に悩む探索問題を考えるときのヒントになります。

11. 参考文献・関連研究

本記事は2026年11月時点で公開されている文献・情報に基づく解説です。