帰納的論理プログラミング

帰納的論理プログラミング( ILP ) は、例、背景知識、仮説の統一表現として論理プログラミングを 使用するシンボリック人工知能のサブフィールドです。ここでの「帰納的」という用語は、数学的(つまり、順序付けられたセットのすべてのメンバーの特性を証明する) 帰納ではなく、哲学的(つまり、観察された事実を説明する理論を提案する) 帰納を指します。既知の背景知識のエンコードと、事実の論理データベースとして表現された一連の例が与えられると、ILP システムは、すべての肯定的な例を含み、否定的な例を含まない仮説論理プログラムを導き出します。

• スキーマ:肯定的な例+否定的な例+背景知識⇒仮説。

帰納的論理プログラミングは、バイオインフォマティクスと自然言語処理で特に役立ちます。

ゴードン・プロトキンは、以前の帰納的推論に関する研究を基に、例から一般化するアプローチを採用し、1970年頃に節設定で帰納を初めて形式化した。 ^{[1] [2]} 1981年、エフード・シャピロは、モデル推論という新しいアプローチで、この分野を形作るいくつかのアイデアを導入した。これは、与えられた例の完全な公理化を探すために改良とバックトレースを使用するアルゴリズムである。^{[1] [3]}彼の最初の実装は、1981年のモデル推論システムであった。^{[4] [5]}これは、正例と負例からホーン節論理プログラムを帰納的に推論するPrologプログラムである。 ^[1]帰納的論理プログラミングという用語は、1990年にスティーブン・マグルトンの論文で初めて導入され、機械学習と論理プログラミングの交差点として定義された。^[1]マグルトンとレイ・バンティンは、1988年に述語発明と逆解決を導入した。 ^{[1] [6]}

1990年代初頭には、影響力のある帰納的論理プログラミングシステムがいくつか登場した。1990年にロス・クインランが導入したFOIL ^[7]は、命題学習アルゴリズムAQとID3のアップグレードに基づいていた。^{[8] 1990年にマグルトンとフェンが導入した}ゴーレムは、プロトキンの最小一般化アルゴリズムの制限された形式に戻った。^{[8] [9]} 1995年にマグルトンが導入したProgolシステムは、逆含意を初めて実装し、後の多くのシステムに影響を与えた。 [ 8 ^{] [10] [11] 2001年にアシュウィン・スリニヴァサンが導入したProgolの後継である}Alephは、2022年現在でも最も広く使用されているシステムの1つである。^{[10] [アップデート]}

ほぼ同じ時期に、特にバイオインフォマティクスの分野で最初の実用的なアプリケーションが登場し、2000年までに、薬物設計、発がん性および変異原性の予測、タンパク質の構造と機能の解明に帰納的論理プログラミングがうまく適用されました。^{[12]初期の研究に固有の}自動プログラミングへの焦点とは異なり、これらの分野では、リレーショナルデータマイニングの観点から帰納的論理プログラミング技術が使用されました。これらの初期アプリケーションの成功と、より大規模な従来の論理プログラムの回復における進歩の欠如が、この分野の焦点を形作りました。^[13]

最近、メタ解釈学習の導入により述語発明や再帰プログラムの学習がより実現可能になったため、自動プログラミングの古典的なタスクが再び注目されるようになりました。この手法は、2014年にMuggleton、Dianhuan Lin、Niels Pahlavi、Alireza Tamaddoni-Nezhadによって導入されたMetagolシステムで開拓されました。^[14]これにより、ILPシステムはより少ない例で動作できるようになり、文字列変換プログラム、回答セット文法、一般的なアルゴリズムの学習に成功しました。^[15]

帰納的論理プログラミングでは、いくつかの異なる学習設定が採用されていますが、最も一般的なのは含意からの学習と解釈からの学習です。^[16]どちらの場合も、入力は背景知識B、論理理論（通常は論理プログラミングで使用される節の形式）、およびそれぞれとで示される正例と負例の形で提供されます。出力は仮説Hとして与えられ、それ自体は通常1つ以上の節で構成される論理理論です。 ${\textstyle E^{+}}$${\textstyle E^{-}}$

2 つの設定では、提示される例の形式が異なります。

2022年現在^{[アップデート]}、含意からの学習は、これまでのところ、帰納的論理プログラミングで最も人気のある設定です。^[16]この設定では、正の例と負の例は、それぞれ正の基底リテラルと否定の基底リテラルの有限集合ととして与えられます。正しい仮説Hは、次の要件を満たす節の集合であり、回転木馬の記号は論理的含意を表します。^{[16] [17] [18]} 完全性では、生成された仮説hがすべての正の例を説明する必要があり、一貫性では、背景知識Bが与えられた場合、負の例と矛盾する仮説hの生成を禁止します。 ${\textstyle E^{+}}$${\textstyle E^{-}}$ ${\displaystyle \models}$ $${\displaystyle {\begin{array}{llll}{\text{完全性:}}&B\cup H&\models &E^{+}\\{\text{一貫性: }}&B\cup H\cup E^{-}&\not \models &{\textit {false}}\end{array}}}$$${\textstyle E^{+}}$${\textstyle E^{-}}$

マグルトンの概念学習の設定では、^[19]「完全性」は「十分性」と呼ばれ、「一貫性」は「強い一貫性」と呼ばれています。さらに2つの条件が追加されています。「必然性」は、Bがを伴わないことを仮定し、 hに制約を課しませんが、肯定的な事実が仮説なしで説明できる限り、仮説の生成を禁止します。「弱い一貫性」は、から矛盾を導き出すことはできないと述べ、背景知識Bと矛盾する仮説hの生成を禁止します。弱い一貫性は強い一貫性によって暗示されます。否定的な例が与えられていない場合、両方の要件が一致します。弱い一貫性は、完全性と強い一貫性が保証できないノイズの多いデータの場合に特に重要です。^[19]${\textstyle E^{+}}$${\textstyle B\land H}$

解釈から学習する場合、正例と負例は、それぞれが基底リテラルの有限集合である完全または部分的なエルブラン構造の集合として与えられる。このような構造e は、任意の代入に対して が成り立ち、となる の任意の節がも成り立つ場合、節集合のモデルであると言われる。目標は、完全な仮説、つまりすべての正例は のモデルであり 、矛盾がない仮説、つまりどの負例も のモデルではない仮説を出力することである。^[16]${\textstyle B\cup H}$ ${\textstyle \theta }$${\textstyle \mathrm {head} \leftarrow \mathrm {body} }$${\textstyle B\cup H}$${\textstyle \mathrm {body} \theta \subseteq e}$${\displaystyle \mathrm {head} \theta \subseteq e}$${\textstyle B\cup H}$${\textstyle B\cup H}$

帰納的論理プログラミング システムは、論理理論を入力として受け取り、理論に関する正しい仮説Hを出力するプログラムです。任意の入力論理理論に対して、その仮説検索手順でこれらの入力理論に関する任意の正しい仮説Hを見つけることができる場合にのみ、システムは完全です。帰納的論理プログラミング システムは、検索ベース システムとメタ解釈システムの 2 つのクラスに大まかに分類できます。 ${\displaystyle B,E^{+},E^{-}}$${\displaystyle B,E^{+},E^{-}}$${\displaystyle B,E^{+},E^{-}}$

検索ベースのシステムは、可能な節の空間が包含関係の下で完全な格子を形成することを利用します。包含関係では、に適用した結果がのサブセットとなるような置換がある場合、 1 つの節が 別の節を包含します。この格子は、ボトムアップまたはトップダウンのいずれかで走査できます。 ${\textstyle C_{1}}$${\textstyle C_{2}}$ ${\textstyle \theta }$${\textstyle C_{1}\theta }$${\textstyle \theta }$${\textstyle C_{1}}$${\textstyle C_{2}}$

包含格子を探索するボトムアップ法は、1970年にPlotkinが節論理における帰納法を形式化する最初の研究を行って以来研究されてきた。^{[1] [20]使用される手法には、}反統一に基づく最小一般化と、解決推論規則の反転に基づく逆解決が含まれる。

最小一般化アルゴリズムは、2つの節とを入力として受け取り、およびの最小一般化 、つまり および を包含し 、 および を包含する他のすべての節に包含される節を出力します。最小一般化は、最初におよびからのすべての選択を計算することによって計算できます。これらの選択は、同じ述語記号と否定/非否定状態を共有するリテラルのペアです 。次に、個々の選択の最小一般化の選言として最小一般化が得られ、これは第1階の統語的反統一によって得られます。^[21]${\textstyle C_{1}}$${\textstyle C_{2}}$${\textstyle C_{1}}$${\textstyle C_{2}}$${\textstyle C}$${\textstyle C_{1}}$${\textstyle C_{2}}$${\textstyle C_{1}}$${\textstyle C_{2}}$${\textstyle C}$${\textstyle D}$${\displaystyle (L,M)\in (C_{1},C_{2})}$

背景知識を考慮するために、帰納的論理プログラミングシステムは、背景理論に対する包含の観点から定義される相対的最小一般化を採用する。一般に、このような相対的最小一般化が存在することは保証されていないが、背景理論Bが基底 リテラルの有限集合である場合、Bの否定はそれ自体が節である。この場合、相対的最小一般化は、 Bの否定をと の両方で分離し、その後、前と同じようにそれらの最小一般化を計算することによって計算できる。 ^[22]${\textstyle C_{1}}$${\textstyle C_{2}}$

相対最小一般化はボトムアップシステムゴーレムの基礎である。^{[8] [9]}

逆解析は、解析演算子を反転させる帰納的推論手法です。

逆解決は、解決ステップの解決元に関する情報を取り、可能な解決節を計算します。帰納的論理プログラミングでは、V演算子とW演算子の2種類の逆解決演算子が使用されています。V演算子は、節とを入力として受け取り、がおよび の解決元となるような節を返します。W演算子は、2つの節とを受け取り、がおよびの解決元であり、がおよびの解決元となる ような3つの節、およびを返します。^[23]${\textstyle R}$${\textstyle C_{1}}$${\textstyle C_{2}}$${\textstyle R}$${\textstyle C_{1}}$${\textstyle C_{2}}$${\textstyle R_{1}}$${\textstyle R_{2}}$${\textstyle C_{1}}$${\textstyle C_{2}}$${\textstyle C_{3}}$${\textstyle R_{1}}$${\textstyle C_{1}}$${\textstyle C_{2}}$${\textstyle R_{2}}$${\textstyle C_{2}}$${\textstyle C_{3}}$

逆解析は、1988年にスティーブン・マグルトンとレイ・バンティンによって、帰納的論理プログラミングシステムCigolで使用するために初めて導入されました。 ^[6] 1993年までに、逆解析演算子とその特性に関する研究が急増しました。^[23]

ILPシステムProgol、^[11]、 Hail ^[24]、およびImparo ^[25]は、逆含意の原理^[11]を使用して、理論B、E、H：に対する仮説Hを見つけます。まず、条件およびを満たすブリッジ理論と呼ばれる中間理論Fを構築します。次に、として、ブリッジ理論Fの否定を反含意で一般化します。^[26]ただし、反含意の操作は非決定性が非常に高いため、計算コストが高くなります。したがって、代わりに逆包含（反包含）操作を使用して対立仮説検索を実行できます。これは、反含意よりも非決定性が低くなります。 ${\displaystyle B\land H\models E\iff B\land \neg E\models \neg H}$${\displaystyle B\land \neg E\models F}$${\displaystyle F\models\negH}$${\displaystyle H\models \neg F}$

特定の帰納的論理プログラミングシステムの仮説探索手順の完全性に関する疑問が生じる。例えば、逆含意推論規則に基づくProgolの仮説探索手順は、山本の例によれば完全ではない。^[27]一方、Imparoは反含意手順^[28]とその拡張逆包含手順^[29]の両方によって完全である。

メタ解釈システムまたはメタレベルシステムは、仮説グラフを明示的に検索するのではなく、帰納的論理プログラミングプログラムをメタレベル論理プログラムとしてエンコードし、それを解いて最適な仮説を取得します。問題の仕様を表現するために使用される形式には、Prologと解答セットプログラミングがあり、既存のPrologシステムと解答セットソルバーが制約を解決するために使用されます。^[30]

Prologベースのシステムの例としては、Prologのメタインタープリタに基づいたMetagolがあります。一方、ASPALとILASPは、解答セットプログラミングにおける帰納的論理プログラミング問題のエンコードに基づいています。^[30]

ILPの進化的アルゴリズムは、集団ベースのアプローチを使用して仮説を進化させ、選択、交差、突然変異を通じて仮説を洗練させます。EvoLearnerのような方法は、構造化された機械学習ベンチマークにおいて従来のアプローチよりも優れていることが示されています。^[31]

• 1BC および 1BC2: 一次単純ベイズ分類器:
• ACE（複合エンジン）
• アレフ
• Atom は 2014-03-26 にWayback Machineにアーカイブされました
• クローディアン^{[永久リンク切れ‍ ]}
• DL-Learner は 2019-08-15 にWayback Machineでアーカイブされました
• Dマックス
• FastLAS (回答セットからの高速学習)
• FOIL (一次帰納的学習器)
• ゴーレム
• ILASP (回答セットプログラムの帰納的学習)
• インパロ^[28]
• Inthelex (EXamples の INcremental THEory Learner) 2011-11-28 にWayback Machineでアーカイブされました
• ライム
• メタゴール
• ミオ
• MIS (モデル推論システム) by Ehud Shapiro
• オントラーン
• ポッパー
• プロゴール
• RSSD
• Warmr (現在は ACE に含まれています)
• プロゴーレム^{[32] [33]}

確率的帰納的論理プログラミングは、帰納的論理プログラミングの設定を確率的論理プログラムの学習に適応させたものである。これは、確率的論理プログラミングの形式主義における統計的関係学習の一形態とみなすことができる。^{[34] [35]}

与えられた

1. 確率的論理プログラムBとしての背景知識、および
2. 肯定的な例と否定的な例の集合と${\textstyle E^{+}}$${\textstyle E^{-}}$

確率的帰納的論理プログラミングの目標は、正例の確率が最大化され、負例の確率が最小化されるような確率的論理プログラムを見つけることである。 ^[35]${\textstyle H}$${\textstyle {H\cup B}}$

この問題には、パラメータ学習と構造学習の2つのバリエーションがある。前者では、 Hの構造（節）が与えられ、与えられた節の確率注釈を推測することが目的であるのに対し、後者では、 Hの構造と確率パラメータの両方を推測することが目的である。古典的な帰納的論理プログラミングと同様に、例は例として、または（部分的な）解釈として与えられる。^[35]

分布意味論に従う言語のパラメータ学習は、期待値最大化アルゴリズムまたは勾配降下法によって行われてきた。期待値最大化アルゴリズムは、期待値と最大化のステップを繰り返し実行するサイクルで構成される。期待値ステップでは、確率パラメータの現在の値に応じて隠れ変数の分布が計算され、最大化ステップではパラメータの新しい値が計算される。勾配降下法は、対象関数の勾配を計算し、勾配の方向にパラメータを繰り返し変更する。^[35]

構造学習は 1997年にダフネ・コラーとアヴィ・フェッファーによって開拓されました^[36] 。著者らは、関連する確率的不確実性パラメータを持つ一次ルールの構造を学習します。彼らのアプローチでは、予備段階で基礎となるグラフィカルモデルを生成し、次に期待最大化を適用します^{[35] 。}

2008年に、De RaedtらはProbLogプログラムで理論圧縮を実行するアルゴリズムを発表しました。理論圧縮とは、与えられた正例と負例の集合の確率を最大化するために、理論から可能な限り多くの節を削除するプロセスを指します。理論に新しい節を追加することはできません。^{[35] [37]}

同年、W. Meertらは、ベイジアンネットワークを同等のものとして考え、ベイジアンネットワークの学習技術を応用することで、基礎確率論理プログラムのパラメータと構造を学習する方法を紹介した。 ^{[38] [35]}

2010年にDe RaedtとIngo Thonによって導入されたProbFOILは、帰納的論理プログラミングシステムFOIL とProbLogを組み合わせたものである。論理ルールは確率データから学習される。つまり、例自体とその分類は確率的になり得る。ルールセットは、例の説明から例の確率を予測できるようにする必要がある。この設定では、パラメータ（確率値）は固定されており、構造を学習する必要がある。^{[39] [35]}

2011年、エレナ・ベロディとファブリツィオ・リグッツィは、確率理論を繰り返し改良し、期待最大化法を用いて各理論のパラメータを最適化することで、確率論理プログラム間でビーム探索を行うSLIPCASEを発表しました。^[40] 2014年に提案されたその拡張であるSLIPCOVERは、Progolのように生成されたボトム節を使用して改良プロセスをガイドし、修正回数を減らして探索空間をより効率的に探索します。さらに、SLIPCOVERは有望な節の探索を理論の探索から分離します。節の空間はビーム探索で探索され、理論の空間は貪欲に探索されます。^{[41] [35]}

• 常識的な推論
• 形式概念分析
• 帰納的推論
• 帰納的プログラミング
• 帰納的確率
• 統計的関係学習
• バージョン空間学習

この記事には、フリーコンテンツ作品 からのテキストが組み込まれています。CC-BY 4.0 (ライセンスステートメント/許可) に基づいてライセンスされています。テキストは、A History of Probabilistic Inductive Logic Programming​、Fabrizio Riguzzi、Elena Bellodi、Riccardo Zese、Frontiers Mediaから引用されています。