一次帰納的学習器

機械学習 において、一次帰納的学習器( FOIL ) はルールベースの学習アルゴリズムです。

背景

1990年にロス・クインラン^[1]によって開発されたFOILは、一階述語論理のサブセットである関数フリーのホーン節を学習します。ある概念の正例と負例、そして背景知識の述語の集合が与えられると、FOILはその概念の論理的な概念定義または規則を帰納的に生成します。帰納的に生成される規則には定数（color(X,red)はcolor(X,Y), red(Y)になる）や関数記号は含まれませんが、否定述語は許容されます。また、再帰的な概念も学習可能です。

ID3アルゴリズムと同様に、FOILは情報理論に基づく指標を用いてヒルクライムを行い、データをカバーするルールを構築します。しかし、ID3とは異なり、FOILは分割統治法ではなく分離統治法を採用し、一度に1つのルールを作成し、アルゴリズムの次の反復のためにカバーされていない例を収集することに重点を置いています。^[要出典]

アルゴリズム

FOIL アルゴリズムは次のとおりです。

学習すべき例と述語のリストを入力

出力 1階ホーン節の集合

FOIL(予測、ポジ、ネガ)

Posを正の例とする

Predを学習すべき述語とする

Posが空になるまで以下を実行します:

Negを負の例とする

本文を空にする

LearnClauseBodyを呼び出す

ルールにPred ← Bodyを追加する

本文を満たすすべての例をPosから削除します

手順 LearnClauseBody

Negが空になるまで、次の操作を実行します。

文字通りのLを選択

LをBodyに結合する

Lを満たさないNeg例を削除する

例

FOIL のタスクが、関係Father(X,Y)およびParent(X,Y)が与えられたときに、概念grandiflore(X,Y) を学習することだとします。さらに、現在の Body がgrandiflore(X,Y) ← parent(X,Z)で構成されているとします。これは、Body をリテラルFather(X,X)、Father(Y,Z)、parent(U,Y)、またはその他多数と結合することによって拡張できます。このリテラルを作成するには、アルゴリズムで述語名と述語の変数セットの両方を選択する必要があります (そのうちの少なくとも 1 つは、節の非否定リテラルにすでに存在している必要があります)。FOIL がリテラルparent(X,Z)を結合して節grandiflore(X,Y) ← trueを拡張する場合、新しい変数Zが導入されます。正の例は、 grandiflore(X,Y)が trueかつparent(X,Z)が true となるような値 < X,Y,Z >で構成されるようになります。負の例は、祖父(X,Y)は真だが親(X,Z)は偽である例です。

親(X,Z)が追加された後のFOILの次の反復では、アルゴリズムは述語名と変数のすべての組み合わせを考慮し、新しいリテラルの少なくとも1つの変数が既存の節に存在するようにします。これにより、非常に大きな探索空間が生成されます。^[2] FOIL理論のいくつかの拡張により、基本アルゴリズムに追加を加えることで、この探索空間が、場合によっては大幅に縮小できることが示されています。^[要出典]

一次複合学習器

FOCLアルゴリズム^[3]（First Order Combined Learner ）は、FOILを様々な方法で拡張し、構築中の節を拡張する際にテストするリテラルの選択方法に影響を与えます。探索空間への制約が許容されるだけでなく、例集合ではなく規則に基づいて定義された述語（内包述語と呼ばれる）も許容されます。最も重要なのは、学習対象の述語の初期近似値として、潜在的に誤った仮説が許容されることです。FOCLの主な目的は、説明に基づく学習（EBL）の手法をFOILの実証的手法に 組み込むことです。

FOCLはFOILよりも追加の知識が与えられない場合でも、深さ優先探索に似た反復的な拡張探索戦略を採用します。まず、FOCLは自由変数を導入せずに節を学習しようとします。これが失敗した場合（正のゲインなし）、自由変数の数が述語の最大値を超えるまで、失敗ごとに1つの自由変数が追加されます。

制約

変数に型制約を課さない FOIL とは異なり、FOCL では、単純な形式の背景知識を組み込むための安価な方法として型付けを使用します。たとえば、述語livesAt(X,Y) にはlivesAt(person, location)という型がある場合があります。ただし、型がなければnextDoor(X,Y)で人物Xと人物Y が隣同士に住んでいるかどうか、または 2 つの場所が隣同士かどうかを判断できるという追加の述語を導入する必要がある場合があります。型がある場合、この機能を維持するためにはnextDoor(person, person)とnextDoor(location, location)という 2 つの異なる述語が必要になります。ただし、この型付けメカニズムにより、isPerson(X)やisLocation(Y)などの述語は不要になり、AとBが人物変数として定義されている場合はlivesAt(A,B) を考慮する必要がなくなり、検索空間が削減されます。さらに、型付けにより、 livesAt(A,B)などの不可能なリテラルを考慮から除外することで、結果として得られるルールの精度を向上させることができます。このようなリテラルは、高い情報ゲインがあるように見える場合があります。

FOCLは、equals(X,X)やbetween(X,X,Y)といった単純な述語を実装するのではなく、変数に暗黙的な制約を導入することで、探索空間をさらに縮小します。述語の中には、すべての変数が一意でなければならないもの、可換性（ ajax(X,Y)はajax(Y,X)と同等）が必要なもの、特定の変数が現在の節に存在することを要求するものなど、様々な制約が考えられます。

運用ルール

操作的ルールは、外延的に定義されるルール、または述語が真となるタプルのリストとして定義されるルールです。FOIL は操作的ルールのみを許可します。FOCL は知識ベースを拡張して、非操作的ルールと呼ばれるルールの組み合わせや、堅牢性のために部分的に定義されたルールや正しくないルールも許可します。部分的な定義を許可すると、アルゴリズムがこれらの部分的な定義を自身で生成する必要がないため、必要な作業量が削減されます。また、正しくないルールは、肯定的な情報ゲインをもたらさないと判断された場合は破棄されるため、必要な作業量が大幅に増加することはありません。非操作的ルールは、組み合わせる個々のルール自体では情報ゲインをもたらさない可能性がありますが、組み合わせると役立つため、有利です。FOCL の反復で最も情報ゲインが大きいリテラルが非操作的である場合、それは操作化され、その定義が構築中の節に追加されます。

入力 操作化されるリテラル、正例のリスト、負例のリスト

演算形式の出力リテラル

操作化（リテラル、肯定的な例、否定的な例）

リテラルが操作 可能であれば

リテラルを返す

OperationalLiteralsを空セットに初期化する

リテラルの定義の各節について

正例と負例における節の情報ゲインを計算する

最大利得の条項について

節内の 各リテラルLについて

OperationalLiteralsにOperationalize( L , Positive examples, Negative examples)を追加する

操作ルールはリテラルlessThan(X,Y)である可能性があり、非操作ルールはbetween(X,Y,Z) ← lessThan(X,Y), lessThan(Y,Z) である可能性があります。

初期ルール

知識ベースに非操作的ルールを追加すると、FOCLが探索しなければならない空間のサイズが増大します。アルゴリズムは、単に対象概念（例えば、grandfer(X,Y)）を与えるのではなく、一連の非操作的ルールを入力として受け取り、その正確性を検証し、学習した概念に対して操作化します。対象概念が正しければ計算時間と精度は明らかに向上しますが、誤った概念であっても、アルゴリズムはそれを基に作業を進めることで、精度と計算時間を向上させることができます。^[3]

参考文献

• http://www.csc.liv.ac.uk/~frans/KDD/Software/FOIL_PRM_CPAR/foil.html

1. JR Quinlan. 関係から論理定義を学ぶ. 機械学習, 第5巻, 第3号, 1990年. [1]
2. Var を、ルールRの任意の節（最後の接続詞を除く）における異なる変数の最大数とする。MaxP を、最大アリティMaxAを持つ述語の数とする。このとき、 Rを学習するために生成されるノード数の近似値は、 Pazzani and Kibler (1992) に示されているように、 NodesSearched ≤ 2 * MaxP * (Var + MaxA – 1) ^MaxAとなる。
3. マイケル・パッツァーニとデニス・キブラー著「帰納的学習における知識の有用性」機械学習、第9巻第1号、1992年。[2]