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

2022年現在帰納論理プログラミングにおいて、含意からの学習は圧倒的に最も一般的な設定である。^{[ 19 ]}この設定では、正例と負例は有限集合として与えられる。${\textstyle E^{+}}$そして${\textstyle E^{-}}$それぞれ、正と否定のグラウンドリテラルの。正しい仮説Hは、次の要件を満たす節の集合であり、ターンスタイル記号は${\displaystyle \models }$論理的含意を表す: ^{[ 20 ] [ 21 ] [ 22 ]}$${\displaystyle {\begin{array}{llll}{\text{完全性:}}&B\cup H&\models &E^{+}\\{\text{一貫性: }}&B\cup H\cup E^{-}&\not \models &{\textit {false}}\end{array}}}$$ 完全性とは、生成された仮説Hがすべての肯定的な例を説明することを必要とする。${\textstyle E^{+}}$、そして一貫性により、否定例と矛盾する仮説Hの生成は禁止される。${\textstyle E^{-}}$背景知識Bを前提とした場合、両方とも。

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

解釈から学ぶ場合、肯定例と否定例は、完全または部分的なヘルブランド構造の集合として与えられ、それぞれの構造は有限個の基底リテラルの集合である。このような構造eは、節の集合のモデルであると言われる。${\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}$[ ^{24 ]​}

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

ILPシステムであるProgol ^{[ 12 ]} 、 Hail ^{[ 28 ]}、Imparo ^{[ 29 ]}は、理論B、E、Hに対して逆含意の原理^{[ 12 ]}を用いて仮説Hを見つけます。${\displaystyle B\land H\models E\iff B\land \neg E\models \neg H}$まず、条件を満たす中間理論F （ブリッジ理論と呼ばれる）を構築する。${\displaystyle B\land \neg E\models F}$そして${\displaystyle F\models \neg H}$すると${\displaystyle H\models \neg F}$反含意を用いてブリッジ理論Fの否定を一般化する。 ^{[ 30 ]}しかし、反含意の操作は非決定論性が非常に高いため、計算コストが高くなる。そのため、反含意よりも非決定論性が低い逆包含（反包含）操作を用いて代替仮説探索を行うことができる。

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

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

また、Prolog ベースのシステムの例としてはMetagolがあり、これはProlog のメタインタプリタに基づいています。一方、ASPAL と ILASP は、帰納的論理プログラミング問題を解答集合プログラミングでエンコードすることに基づいています。^{[ 35 ]}

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

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

構造学習は、 1997 年にDaphne Kollerと Avi Pfefferによって開拓されました^{[ 41 ]。}この研究では、著者らは、関連する確率的不確実性パラメータを持つ一次ルールの構造を学習します。彼らのアプローチでは、まず基礎となるグラフィカル モデルを生成し、次に期待値最大化を適用します^{[ 40 ] 。}

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

同年、Meert, W. らは、ベイジアンネットワークをそれらと同等とみなし、ベイジアンネットワークの学習技術を適用することにより、基底確率論理プログラムのパラメータと構造を学習する方法を導入した。 ^{[ 43 ] [ 40 ]}

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

2011年、Elena BellodiとFabrizio Riguzziは、確率的論理プログラム間でビームサーチを実行するSLIPCASEを発表しました。これは、確率的理論を反復的に洗練し、期待値最大化を使用して各理論のパラメータを最適化することによって行われます。^{[ 45 ]} 2014年に提案されたその拡張SLIPCOVERは、Progolのように生成されたボトム節を使用して洗練プロセスをガイドし、修正の数を減らし、探索空間をより効果的に探索します。さらに、SLIPCOVERは、有望な節の探索と理論の探索を分離します。節の空間はビームサーチで探索され、理論の空間は貪欲に探索されます。^{[ 46 ] [ 40 ]}