帰納的論理プログラミング: 基礎と応用

By Fouad Sabry

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

帰納的論理プログラミング (ILP) として知られる記号人工知能のサブフィールドでは、例、背景知識、および論理プログラミングを一貫した表現として使用します。 仮説。 ILP システムは、既知の背景知識のエンコードと、事実の論理データベースとして表現される例のコレクションが提供される場合、仮説を立てた論理プログラムを開発します。 このプログラムにはすべての肯定的な例が含まれますが、否定的な例は含まれません。このモデルでは、仮説は肯定的な例、否定的な例、および背景知識から導き出されます。

どのようなメリットが得られるか

(I) 次のトピックに関する洞察と検証:

第 1 章: 帰納的論理プログラミング

第 2 章: Stephen Muggleton

第 3 章: プロゴール

第 4 章: プログラム合成

第 5 章: 帰納的プログラミング

第 6 章: 一次論理

第 7 章: 推論規則のリスト

第 8 章: 選言正規形

第 9 章: 解決 (論理)

第 10 章: 解答セット プログラミング

(II) 帰納的論理プログラミングに関する一般のよくある質問に答える。

(III) 多くの分野で帰納的論理プログラミングを使用する実際の例。

(IV) 帰納的論理プログラミングのテクノロジを 360 度完全に理解できるように、各業界の 266 の新興テクノロジを簡潔に説明する 17 の付録。

本書の対象者>

専門家、学部生および大学院生、愛好家、愛好家、およびあらゆる種類の帰納的論理プログラミングに関する基本的な知識や情報を超えたいと考えている人。

 

• Language: 日本語
• Publisher: 10億人の知識があります [Japanese]
• Release date: Jun 30, 2023

Book preview

第1章:帰納論理プログラミング

帰納論理プログラミング(ILP)は、データセット、知識ベース、仮説などのデータを表す論理プログラミングを標準化する記号AIの一分野です。ILPシステムは、知識エンコーディングと事実の論理データベースの形式の一連の例が与えられた場合、すべての肯定的な例を含み、否定的な例を含まない仮説論理プログラムを生成します。

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

バイオインフォマティクスとNLPは、帰納論理プログラミングから大きな恩恵を受ける2つの分野です。論理的な文脈では、ゴードン・プロトキンとエフード・シャピロが帰納的機械学習の最初の理論的基礎を確立しました。PROGOLシステムでは、マグルトンが最初に逆含意を実装しました。この文脈では、「帰納法」は数学的帰納法よりも哲学的帰納法を指します(後者は、整順序集合のすべてのメンバーの特性を証明するプロセスです)。

必要なコンテキストは論理のB理論の形で提供され、論理プログラミングでは、ホーン句は一般的な構造です。

正 と負の例は、それぞれ接続詞として E^{+} 、また E^{-} 否定されていないグラウンドリテラルと否定されたグラウンドリテラルとして示されています。

有効な仮説hは、次の結果を保証する論理ステートメントです。

{\displaystyle {\begin{array}{llll}{\text{Necessity:}}&B&\not \models &E^{+}\\{\text{Sufficiency:}}&B\land h&\color {blue}{\models }&E^{+}\\{\text{Weak consistency:}}&B\land h&\not \models &{\textit {false}}\\{\text{Strong consistency:}}&B\land h\land E^{-}&\not \models &{\textit {false}}\end{array}}}

「必要性」という言葉は、仮説なしで肯定的な事実を説明できる限り、何ができるかを制限するものではなく、その生成は固く禁じられています。

「十分性」は、すべての肯定的な例を説明するために生成された仮説hを必要とします E^{+} 。

「弱い一貫性」の原則は、確立された事実Bと矛盾する仮説hの形成を禁じています。

「強い一貫性」はまた、否定的な例と矛盾する仮説h E^{-} の生成を禁じる AとBを一緒に考える。「一貫性のない弱い」という意味。反例が提示されていない場合は、両方の基準が満たされます。

ジェロスキは「十分性」(そこでは「完全性」と呼ばれる)と「強い一貫性」だけを必要とします。

以下は、さまざまな種類の家族関係について学ぶときに頭字語を使用する方法の古典的な図です。

パー:親、フェム:女性、ダウ:娘、G:ジョージ、H:ヘレン、m:メアリー、t:トム、n:ナンシー 、e  :イブ .

最初のステップは、必要なコンテキストを取得することです(写真を参照)

{\textit {par}}(h,m)\land {\textit {par}}(h,t)\land {\textit {par}}(g,m)\land {\textit {par}}(t,e)\land {\textit {par}}(n,e)\land {\textit {fem}}(h)\land {\textit {fem}}(m)\land {\textit {fem}}(n)\land {\textit {fem}}(e)

、肯定的な例

{\textit {dau}}(m,h)\land {\textit {dau}}(e,t) 、および反例がないことを意味する無意味なステートメント「true」。

Plotkinによって提案された「相対的最小一般一般化」の帰納的論理プログラミング手法は、娘関係dauを形式的に定義する方法を学ぶために使用されます。

このメソッドで実行される手順は次のとおりです。

文字通り肯定的な例は、入手可能なすべての情報で文脈化する必要があります。

{\displaystyle {\begin{aligned}{\textit {dau}}(m,h)\leftarrow {\textit {par}}(h,m)\land {\textit {par}}(h,t)\land {\textit {par}}(g,m)\land {\textit {par}}(t,e)\land {\textit {par}}(n,e)\land {\textit {fem}}(h)\land {\textit {fem}}(m)\land {\textit {fem}}(n)\land {\textit {fem}}(e)\\{\textit {dau}}(e,t)\leftarrow {\textit {par}}(h,m)\land {\textit {par}}(h,t)\land {\textit {par}}(g,m)\land {\textit {par}}(t,e)\land {\textit {par}}(n,e)\land {\textit {fem}}(h)\land {\textit {fem}}(m)\land {\textit {fem}}(n)\land {\textit {fem}}(e)\end{aligned}}}

、句形式を正規化します。

{\displaystyle {\begin{aligned}{\textit {dau}}(m,h)\lor \lnot {\textit {par}}(h,m)\lor \lnot {\textit {par}}(h,t)\lor \lnot {\textit {par}}(g,m)\lor \lnot {\textit {par}}(t,e)\lor \lnot {\textit {par}}(n,e)\lor \lnot {\textit {fem}}(h)\lor \lnot {\textit {fem}}(m)\lor \lnot {\textit {fem}}(n)\lor \lnot {\textit {fem}}(e)\\{\textit {dau}}(e,t)\lor \lnot {\textit {par}}(h,m)\lor \lnot {\textit {par}}(h,t)\lor \lnot {\textit {par}}(g,m)\lor \lnot {\textit {par}}(t,e)\lor \lnot {\textit {par}}(n,e)\lor \lnot {\textit {fem}}(h)\lor \lnot {\textit {fem}}(m)\lor \lnot {\textit {fem}}(n)\lor \lnot {\textit {fem}}(e)\end{aligned}}}

、互換性のあるすべてのリテラルを不一致に結合します。

{\textit {dau}}(x_{{me}},x_{{ht}}) from および 、 from および {\textit {dau}}(m,h) {\textit {dau}}(e,t) 、 \lnot {\textit {par}}(x_{{ht}},x_{{me}}) \lnot {\textit {par}}(h,m) from \lnot {\textit {par}}(t,e) および 、 from  \lnot {\textit {fem}}(x_{{me}}) \lnot {\textit {fem}}(m) \lnot {\textit {fem}}(e) および \lnot {\textit {par}}(g,m) 、同様に \lnot {\textit {par}}(g,m) 、 \lnot {\textit {par}}(g,m) コンテキストを必要とする他のすべてのリテラルの場合

\lnot {\textit {par}}(x_{{gt}},x_{{me}}) から \lnot {\textit {par}}(g,m) \lnot {\textit {par}}(t,e) と 、文字通り意図されていない多数の比喩的な表現を含む

正のリテラルに見つからない変数は、否定されたリテラルから削除して削除する必要があります。

以外の変数を含むすべての否定リテラルを削除した後 x_{{me}},x_{{ht}}

{\textit {dau}}(x_{{me}},x_{{ht}})\lor \lnot {\textit {par}}(x_{{ht}},x_{{me}})\lor \lnot {\textit {fem}}(x_{{me}})

、 は、根拠として使用される基本知識からのすべてのリテラルとともに、

句のホーン形式に戻します。

{\textit {dau}}(x_{{me}},x_{{ht}})\leftarrow {\textit {par}}(x_{{ht}},x_{{me}})\land {\textit {fem}}(x_{{me}})\land ({\text{all background knowledge facts}})

rlgg法を使用して得られた仮説hはホーン節です。

重要なコンテキスト情報を省略すると、この条項は非公式に「 x_{{me}} if x_{{ht}} の娘と呼ばれ x_{{ht}} 、女性の親であり x_{{me}} x_{{me}} 、女性である」と読みますが、これは一般的に合意された定義です。

前述の条件を参照して、名詞句述語dauは確立された語彙ではなく、その述語を持つ任意の特性の推論を除外するため、「必要性」の基準が満たされました。

計算された仮説hは、背景知識からとともに、最初の肯定的な例を意味し、同様に {\textit {par}}(h,m)\land {\textit {fem}}(m) h {\textit {dau}}(m,h) および背景知識から、2番目の肯定的な例を意味するため、「十分性」を証明 {\textit {par}}(t,e)\land {\textit {fem}}(e) します {\textit {dau}}(e,t) 。

H は「弱い一貫性」の条件を満たし、h は先行情報によって定義される(有限の)ヘルブランド構造において真であるから、;「非常に一貫性がある」という意味です。

家族の祖母の伝統的な意味、すなわち。

{\textit {gra}}(x,z)\leftarrow {\textit {fem}}(x)\land {\textit {par}}(x,y)\land {\textit {par}}(y,z)

yが主節内でのみ使用されるため、上記の方法で教えることはできません。第4段階では、対応するリテラルが削除されていました。

この欠点を修正するには、さまざまなリテラル選択後ヒューリスティックでパラメータ化を可能にするには、そのステップを調整する必要があります。

歴史的に、GOLEMシステムはrlgg方法論を使用して開発されました。

帰納論理プログラミングシステムは、入力論理理論として受け取り、 B,E^{+},E^{-} 正しい仮説を出力するプログラムです H wrt理論 B,E^{+},E^{-} ILPシステムのアルゴリズムは、仮説検索と仮説選択の2つの部分で構成されています。

仮説を検索する帰納論理プログラミング手順から始まり、選択アルゴリズムを使用して、見つかった仮説のサブセットを選択します(ほとんどのシステムでは、これは1つの仮説にすぎません)。

発見された各仮説には、選択アルゴリズムによってスコアが与えられ、最高スコアの仮説が返されます。

たとえば、コルモゴロフ複雑度が最小の仮説は、最小圧縮長に応じて最高のスコアを持ちます。

ILPシステムは、任意の入力論理理論に対して完全なIFであり、これらの入力理論に対する B,E^{+},E^{-} 正しい仮説H wrtは、その仮説検索手順で見つけることができます。

プロゴールと他の現代のILPシステム、B理論、 E、 H:

B\land H\models E\iff B\land \neg E\models \neg H

に関する。

まず、条件と を満たすブリッジ理論と呼ばれる中間理論 B\land \neg E\models F F  を構築する F\models \neg H 。

次に H\models \neg F 、 として、彼らはFのブリッジ理論の否定を一般化するために反含意を使用します。

ただし、反含意演算は、その高い非決定性のために計算コストが高くなります。

したがって、反含意よりも非決定論的操作が少ない反包摂は、対立仮説を検索するために使用できます。

特定のILPシステムの仮説検索手順が網羅的であるかどうかという問題が生じます。山本の例を例にとると、逆含意推論規則を用いたProgolの仮説探索手順が不完全であることがわかります。プロシージャ。

1階の素朴ベイズ分類器(1BC)と2次(1BC2):

エース(複合エンジン)