Loading article…
機械学習 において、一次帰納学習器（FOIL）はルールベースの学習アルゴリズムである。
1990 年にRoss Quinlanによって開発された[ 1 ] FOIL は、一階述語論理のサブセットである関数フリーのHorn 節を学習します。ある概念の肯定例と否定例、および背景知識述語のセットが与えられると、FOIL は帰納的にその概念の論理的な定義またはルールを生成します。誘導されたルールには定数 ( color(X,red)はcolor(X,Y), red(Y)になります) や関数記号が含まれていてはなりませんが、否定述語は許容されます。再帰的な概念も学習可能です。
ID3アルゴリズムと同様に、FOILは情報理論に基づく指標を用いて、データ全体を網羅するルールを構築します。ただし、ID3とは異なり、FOILは分割統治法ではなく分離統治法を採用しており、一度に1つのルールを作成し、未解決の例を収集して次のアルゴリズムの反復処理に活用します。
FOILアルゴリズムは以下のとおりです。
FOIL のタスクが、関係father(X,Y)とparent(X,Y)が与えられたときに概念grandgarden(X,Y) を学習することであるとします。さらに、現在の Body がgrandgarden(X,Y) ← parent(X,Z)で構成されているとします。これは、Body をリテラルfather(X,X)、father(Y,Z)、parent(U,Y)、またはその他多数と結合することによって拡張できます。このリテラルを作成するには、アルゴリズムは述語名と述語の変数セットの両方を選択する必要があります (そのうち少なくとも 1 つは、節の否定されていないリテラルに既に存在している必要があります)。FOIL がリテラルparent(X,Z)を結合することによって節grandgarden(X,Y) ← trueを拡張する場合、新しい変数Zを導入します。肯定例は、grandfather(X,Y)が真でありparent(X,Z)が真であるような値 < X,Y,Z >で構成されます。否定例としては、grandfather(X,Y)が真であるがparent(X,Z)が偽である場合が挙げられる。
parent(X,Z)が追加された後の FOIL の次の反復では、アルゴリズムは、新しいリテラルの少なくとも 1 つの変数が既存の節に存在するような述語名と変数のすべての組み合わせを考慮します。これにより、非常に大きな探索空間が生じます。[ 2 ] FOIL 理論のいくつかの拡張により、基本アルゴリズムへの追加によってこの探索空間が縮小されることが示されており、場合によっては大幅に縮小されます。
FOCLアルゴリズム[ 3 ]（First Order Combined Learner ）は、さまざまな方法でFOILを拡張しており、構築中の節を拡張しながらFOCLがテストするリテラルを選択する方法に影響を与えます。検索空間に対する制約が許可され、例のセットではなくルールに基づいて定義された述語（内包述語と呼ばれる）も許可されます。最も重要なのは、学習する述語の初期近似として、潜在的に誤った仮説が許可されることです。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)のような単純な述語を実装するのではなく、変数に暗黙的な制約を導入することで、検索空間をさらに縮小します。一部の述語ではすべての変数が一意である必要があり、他の述語では可換性（ adjacent(X,Y)はadjacent(Y,X)と同等）が必要であり、さらに他の述語では特定の変数が現在の節に存在する必要がある場合があり、その他にも多くの潜在的な制約が存在します。
操作ルールとは、外延的に定義されるルール、つまり述語が真となるタプルのリストとして定義されるルールのことです。FOIL は操作ルールのみを許可しますが、FOCL は知識ベースを拡張し、非操作ルールと呼ばれるルールの組み合わせや、堅牢性を高めるために部分的に定義されたルールや誤ったルールも許可します。部分的な定義を許可することで、アルゴリズムがこれらの部分的な定義を自身で生成する必要がなくなるため、必要な作業量が削減されます。また、誤ったルールは、情報利得が正であると判断されない場合は破棄されるため、必要な作業量を大幅に増加させることはありません。非操作ルールは、組み合わせる個々のルールが単独では情報利得をもたらさない可能性があるものの、組み合わせると有用であるという利点があります。FOCL の反復処理において最も情報利得の高いリテラルが非操作的である場合、それは操作化され、その定義が構築中の節に追加されます。
演算ルールはリテラルlessThan(X,Y)のようになるかもしれません。非演算ルールはbetween(X,Y,Z) ← lessThan(X,Y), lessThan(Y,Z) のようになるかもしれません。
知識ベースに非操作ルールを追加すると、FOCL が検索しなければならない空間のサイズが大きくなります。アルゴリズムにターゲット概念 (たとえばgrandfer(X,Y) ) を単純に与えるのではなく、アルゴリズムは入力として一連の非操作ルールを受け取り、その正しさをテストして、学習した概念に対して操作化します。正しいターゲット概念は明らかに計算時間と精度を向上させますが、間違った概念であっても、アルゴリズムが動作するための基礎を与え、精度と時間を向上させます。[ 3 ]