逆方向連鎖: 基礎と応用

By Fouad Sabry

逆方向連鎖とは

「ゴールから逆方向に作業する」として知られる推論を行うプロセスは、「逆方向連鎖」として知られる手法の別名です。 これは、自動定理証明器、推論エンジン、証明アシスタント、および人工知能の範疇に入るその他のアプリケーションに実装されています。

メリット

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

第 1 章: 逆方向連鎖

第 2 章: 自動化された定理証明

第 3 章: 推論エンジン

第 4 章: ゲーム理論

第 5 章: 後方帰納法

第 6 章: 逆行分析

第 7 章: ロジック プログラミング

第 8 章: SLD 解決

第 9 章: フォワードチェーン

第 10 章: プロローグ

(II) バックワードに関する一般のよくある質問に答える

(III) 多くの分野でバックワード チェーンを使用する実際の例。

(IV) 各業界で導入すべき 266 の新興テクノロジーを簡潔に説明する 17 の付録 「バックワード チェーン」テクノロジーを 360 度完全に理解します。

本書の対象者

専門家、大学生、大学院生、愛好家、趣味愛好家など あらゆる種類の後方連鎖についての基本的な知識や情報を超えたいと考えている人。

 

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

Book preview

第 1 章: 後方チェーン

望ましい結果から逆方向に作業することは、後方連鎖(後方推論とも呼ばれる)として知られる推論手順を説明する口語的な方法です。自動定理証明者、推論エンジン、証明ヘルパーなどの人工知能アプリケーションでは、これらのアプリケーションで使用されます。

後方帰納法は、ゲーム理論で使用される手法であり、研究者がゲーム全体を取り、それをいくつかの(より単純な)サブゲームに適用して、ゲーム全体の解決策を発見します。これはチェスのゲームでは逆行分析と呼ばれ、コンピュータチェスプログラムでチェスエンドゲームのテーブルベースを生成するために使用されます。

論理プログラミングでは、後方チェーンのプロセスは SLD 解決によって処理されます。手口ポネンス推論ルールは、これらの両方の原則の基礎です。これは、最も頻繁に使用される推論規則と論理的意味を使用した推論の2つの手法の1つであり、もう1つはフォワードチェーンです。深さ優先の検索アプローチは、ファイルを検索する場合など、後方チェーン システムでよく使用されます。プロローグ。

後方連鎖のプロセスは、目的(または仮説)のリストから始まり、これらの結果のいずれかが証拠によって裏付けられているかどうかを判断するために、結果から先行へと逆方向に進みます。逆方向チェーンを使用する推論エンジンは、必要な目的に一致する結果 (Then 句) を持つ推論ルールが見つかるまで、考えられるすべての推論ルールを調べます。そのルールの先行詞 (If 句と呼ばれます) が真であることがわかっていない場合は、目標のリストに追加されます。ただし、目標を検証するには、個人が新しいルールを検証するデータも提供する必要があります。

たとえば、フリッツという名前の新しいペットが、フリッツに関する2つの情報とともにパッケージで到着するシナリオを考えてみましょう。

フリッツの鳴き声

フリッツはハエを食べる

次の 4 つのルールを含むルール セットに基づいて、ここでの目的は、フリッツが緑色かどうかを判断することです。

物Xがハエを食べ、物xが鳴くなら、物xはカエルです。

Xがさえずりと歌の両方を行う鳥である場合、Xはカナリアです。

Xがカエルの場合、Xが緑色であることは当然のことです。

カナリアは黄色であるため、X がカナリアの場合、X は黄色でなければなりません。

推論エンジンは、後方推論の手法を使用して、フリッツが緑色であるかどうかを4つの簡単なステップで判断できます。まず、調査は示さなければならない客観的な主張として組み立てられており、その主張は「フリッツは緑である」ということです。

1.ルール番号3では、目的が満たされているかどうかを判断するために、Xがフリッツに置き換えられます。したがって、ルール番号3は次のように書き換えられます。

フリッツがカエルなら– フ リッツは緑です

ルールエンジンは、フリッツが緑色であることを示す結果が表示され、目的を満たしているため、フリッツがカエルであることを示す先行詞を表示できるかどうかを決定する必要があります。その結果、先行詞は新しいターゲットに変換されます。

フリッツはカエルです

2.フリッツをもう一度例として使用して、ルール番号1は次のように書き換えられます。

フリッツが鳴き、フリッツがハエを食べるなら–フリッツはカエルです

結果(フリッツがカエルであること)は現在の目的(フリッツが鳴いてハエを食べること)と一致しているので、推論エンジンは、先行詞(フリッツが鳴いてハエを食べること)を示すことができるかどうかを判断する必要があります。その結果、先行詞は新しいターゲットに変換されます。

フリッツは鳴き声を上げ、フリッツはハエを食べる

3. この目的は 2 つのアサーションの組み合わせであるため、推論エンジンはそれを 2 つの補助的な目標に分割し、それぞれが真であることを示す必要があります。

フリッツの鳴き声

フリッツはハエを食べる

4.推論エンジンは、これらのサブ目標の両方が開始事実として提示されたことを観察します。これは、これらのサブ目標の両方を証明するための最初のステップです。このため、接続詞は正しいです。

フリッツは鳴き声を上げ、フリッツはハエを食べる

このため、ルール番号1の先行詞は正確であり、その結果も正確でなければなりません。

フリッツはカエルです

このため、ルール番号3の先行詞も真でなければなりません。

フリッツは緑です

この推論により、推論エンジンはフリッツが土の色であることを示すことができます。2番目と4番目の規則は守られませんでした。

目標は常に含意の結果の肯定されたバージョンと一致し(modus tollensのように否定されたバージョンではない)、それでも、それらの前例は新しい目標と見なされます(そして、結果を肯定するような結論ではありません)、最終的には既知の事実と一致する必要があります(通常、先行例が常に真である結果として定義されます)。その結果、利用されている推論ルールはモダスポネンです。

この手法は、データ駆動型のフォワードチェーン推論とは対照的に、目標駆動型と呼ばれ、目標のリストがどのルールを選択して使用するかを決定するという事実にちなんで名付けられました。後方連鎖の方法は、エキスパートシステムによってかなり頻繁に使用されます。

バックワードチェーンは、Prolog、Knowledge Machine、ECLiPSeなどのプログラミング言語の推論エンジン内に見られる機能です。

{第 1 章終了}

第2章 自動定理証明

ATPまたは自動演繹と呼ばれることもある自動定理証明は、コンピュータプログラムによる数学的定理の証明を扱う自動推論および数学的論理の分野です。このトピックの他の名前には、自動推論と自動推論が含まれます。コンピュータサイエンスの発展の背後にある重要な原動力は、数学的定理の検証へのコンピュータ化された論理の適用でした。

アリストテレスは形式論理学の父とされることが多いが、19世紀後半から20世紀初頭にかけては、近代論理学や形式数学が発達した。

FregeのBegriffsschrift(1879)は、包括的な命題計算と基本的に現代的な述語論理の両方を含む最初の出版物でした。

しかし、この有望な結果を得た直後に、Kurt Gödelは『プリンキピア・マテマティカと関連システムの形式的に決定不可能な命題について』(1931年)を発表し、十分に頑健なすべての公理的枠組みには、その枠組み自体では証明できない真の命題が含まれていることを実証した。

1930年代、アロンゾ・チャーチとアラン・チューリングは、一方では互いに同一の計算可能性の2つの異なる定義を提供し、他方では答えられない問題の具体的な例を提供した。

民間用に設計された最初のコンピューターは、第二次世界大戦の終結後間もなく商業的にアクセスできるようになりました。1954年にニュージャージー州プリンストンの高等研究所で、マーティンデイビスはプレスバーガーのアルゴリズムをJOHNNIAC真空管コンピューターに最初にコーディングした人でした。デイビスは、組織の最も重要な成果は、任意の2つの偶数整数の合計も偶数であることを示すことであると主張しています。

その下にある推論に応じて、 数式の正しさを判断することは、簡単な作業から克服できない障害までさまざまです。

命題論理の最も一般的なインスタンスに関しては、 課題は解決できますが、それは共NP完全です、 したがって、一般的な証明ジョブには、指数関数的に増加するランタイムを持つアルゴリズムのみが存在すると仮定されます。

一階述語計算の場合、ゲーデルの完全性定理は、定理(証明可能なステートメント)が論理的に有効な整形式式であると述べているため、有効な式を再帰的に列挙することが可能です。 リソースの無制限の供給が与えられた場合、 ある時点で正しい式が存在することが示される場合があります。

ただし、無効な公式(特定の理論に伴わない式)は、通常、認識できない場合があります。

上記のすべては一次の理論に当てはまり、ペアノ算術のようなものが含まれます。

しかし、一次理論を用いて説明され得る特定のモデルを参照すると、モデルを定義するために使用されている理論では、真実であるが決定できない特定の主張が存在する可能性がある。

たとえば、ゲーデルの不完全性定理により、自然数に関連する公理が成り立つ理論は、それらの公理が成り立つ場合、自然数に対して成り立つすべての一次命題を証明できないことを認識しています。 正しい公理のリストが無限に列挙可能であることが許されたとしても、これは何も変わりません。

したがって、自動定理証明者は、研究されているステートメントが採用されている理論で決定できない場合、関心のあるモデルで成り立つかどうかに関係なく、証明の検索を終了できません。

この制限は理論的であるという事実にもかかわらず、実際には、定理証明者は、一次理論(整数など)によって完全に特徴付けることができないモデルであっても、さまざまな困難な状況に取り組む能力を持っています。

証明の検証はそれほど複雑ではありませんが、同様のトピックであり、定理の既存の証明が有効であることを確認するためにチェックされます。これを行うには、個々の証明ステップが単純な再帰関数またはプログラムによって検証可能であることがしばしば不可欠です。したがって、問題は常に解決することができます。

自動定理証明者によって作成される証明はしばしばかなり広範囲であるため、証明圧縮の主題は重要です。証明者の出力を小さくし、その結果、より簡単に理解してチェックできるようにするために、さまざまな戦略が開発されてきました。

証明ヘルパーは、ヒントを受け取って処理するために、人間のユーザーの参加を必要とします。証明者は、自動化の程度に応じて、ユーザーが正式な方法で証拠を提供する、単に証明チェッカーに縮小される場合があります。あるいは、実質的な証明義務が自動的に完了することもあります。全自動システムでさえ、ロビンズ予想である人間の数学者をかなりの時間逃れてきた少なくとも1つを含む、多くの興味深く難しい定理を証明しています。インタラクティブ証明器はさまざまなタスクに使用されますが、全自動システムでさえ、多くの興味深く難しい定理を証明しています。ただし、これらの成果は一貫しておらず、困難な問題に取り組むには、熟練したユーザーが必要になることがよくあります。

定理証明と他の手法との間に時々引き出される別の違いは、プロセスが公理から始まり、推論の規則を使用して新しい推論ステップを生成する伝統的な証明で構成されている場合、プロセスは定理証明と見なされることです。定理の証明は他の手法よりも厳密であると考えられているため、この区別が描かれることがあります。他の方法には、最も単純な形式では、多数の異なる状態を列挙する面倒で時間のかかるプロセスであるモデル検証が含まれる場合があります(ただし、モデルチェッカーの実際の実装には多くの巧妙さが必要であり、単にブルートフォースに還元されるわけではありません)。

ハイブリッド定理証明システムがあり、その機能の1つは、推論規則としてモデル検証を採用することです。与えられた定理を証明するために特別に開発された他のプログラムがあります。これらのプログラムには、プログラムが特定の結果で完了した場合、定理が正しい必要があることを示す(多くの場合非公式の)証明が含まれています。プログラムの計算の膨大なサイズのために人間が検証することは本質的に不可能であった最初の主張された数学的証明は、それが提示されたときに多くの論争を引き起こした4色定理の機械支援証明でした。この良い例は、4色定理の機械支援証明です(そのような証明は非測量証明と呼ばれます)。コンピュータ支援証明のそのような例の1つは、Connect Fourのゲームの最初のプレイヤーが常に勝利を収めるという事実を示すものです。

自動定理証明の商用アプリケーションへの統合は、集積回路の検証と設計において特に一般的です。Pentium FDIVの問題が発見されて以来、現代のマイクロプロセッサの洗練された浮動小数点ユニットは、設計プロセス全体を通じてより高いレベルの精査を受けてきました。自動定理証明は、除算やその他の操作がCPUに正確に実装されていることを確認するために、AMD、Intel、およびその他の企業によって使用されています。

1960年代後半、自動控除の研究に資金を提供した組織は、調査結果の実用的なアプリケーションを見つける必要性をより重視し始めました。Pascal、Adaなどの言語で書かれたコンピュータプログラムの正しさを検証するという課題に対する一階定理証明者の使用は、生産的であることが証明された最初の分野の1つでした。これは、プログラム検証の分野でした。最初のプログラム検証システムの中で、スタンフォード大学のデビッド・ラッカムによって作成されたスタンフォードパスカル検証機は、特に革新的であると際立っています。

定理証明者のための何千もの問題(TPTP)問題ライブラリとして知られる標準的なベンチマーク例の大規模なライブラリの存在は、実装されたシステムの品質に有益でした。毎年開催されるCADE ATPシステムコンペティション(CASC)も、この改善に貢献した要因です。CASCは、一次問題の多くの重要なクラスに対して開催される一次システムの競争です。

以下は、いくつかの重要なシステムのリストであり、そのすべてがCASCコンペティションの少なくとも1つのカテゴリで勝利を収めています。

Eは、高レベルのパフォーマンスを備えた包括的な一次論理証明者ですが、完全に方程式計算に基づいています,