Loading article…
確率的論理プログラミングとは、論理プログラミングと確率を組み合わせたプログラミングパラダイムである。
確率論理プログラミングのほとんどのアプローチは、分布意味論に基づいている。分布意味論は、プログラムを確率的事実の集合と論理プログラムに分割する。そして、プログラムのハーブランド宇宙の解釈に関する確率分布を定義する。
確率論理プログラミングのほとんどのアプローチは、分布意味論に基づいています[ 1 ]。これは、確率的ホーンアブダクション、PRISM、独立選択論理、確率的データログ、注釈付き選言付き論理プログラム、ProbLog、P-log、CP-logicなどの多くの言語の基盤となっています。言語の数は多いものの、多くは共通のアプローチを共有しており、線形複雑度で変換を行うことで、ある言語を別の言語に変換できます[ 2 ] 。
分布意味論の下では、確率的論理プログラムは、独立した確率的事実（確率が注釈付けされた基底原子式）の集合と、その確率的事実を節の本体で使用できる論理プログラムとして解釈されます。確率的事実に関連付けられた式の基底に真理値を割り当てる確率は、それらの確率の積によって与えられます。これは、確率的事実の選択が独立した確率変数であると仮定することと同等です。[ 1 ] [ 3 ]
確率的事実の真理値の選択に関わらず、結果として得られる論理プログラムが階層化されている場合、その真理値の選択に関連付けられた唯一の解釈と見なせる、唯一の最小ヘルブランドモデルが存在する。 [ 1 ]
階層化されたプログラムの重要なサブクラスは、否定を使用しないが再帰的である可能性のある肯定プログラムと、否定を使用する可能性があるが再帰的な依存関係を持たない非巡回プログラムである。[ 1 ]
解答集合プログラミングの基盤となる安定モデル意味論は、確率的事実の真理値割り当てごとに複数の解答集合を割り当てることで、階層化されていないプログラムに意味を与えます。これにより、確率質量を解答集合全体にどのように分配するかという問題が生じます。[ 4 ] [ 5 ]
確率論理プログラミング言語P-Logは、無差別原理に従って、確率質量を回答セット間で均等に分割することでこの問題を解決します。[ 4 ] [ 6 ]
あるいは、信憑性意味論に基づく確率的回答セットプログラミングでは、すべてのクエリに信憑セットが割り当てられます。その下限確率は、結果として得られるプログラムのすべての回答セットでクエリが真となる確率的事実の真理値割り当てのみを考慮することによって定義されます（慎重な推論）。その上限確率は、いくつかの回答セットでクエリが真となる割り当てを考慮することによって定義されます（大胆な推論）。[ 4 ] [ 5 ]
分布意味論の下では、確率的論理プログラムは、その述語の解釈に関する確率分布をヘルブランド宇宙上で定義します。基底クエリの確率は、クエリと世界の同時分布から得られます。それは、クエリが真となる世界の確率の合計です。[ 2 ] [ 7 ] [ 8 ]
クエリの確率を計算する問題は、（周辺）推論と呼ばれます。可能な世界の数が、基底確率的事実の数に対して指数関数的に増加するため、すべての世界を計算し、クエリを包含する世界を特定することによってこの問題を解決することは非現実的です。[ 2 ]実際、非巡回プログラムとアトミッククエリの場合、証拠としてアトムの結合が与えられた場合のクエリの条件付き確率を計算することは、すでに#P完全です。[ 9 ]
通常、正確な推論は知識コンパイルによって行われます。この方法では、命題理論とクエリが「ターゲット言語」にコンパイルされ、その後、そのターゲット言語を使用してクエリに多項式時間で応答します。コンパイルが主な計算上のボトルネックとなりますが、効率的なコンパイラの開発に多大な努力が注がれてきました。コンパイル方法は、ターゲット言語のコンパクトさと、多項式時間でサポートするクエリと変換のクラスが異なります。[ 2 ]
推論のコストが非常に高くなる可能性があるため、近似アルゴリズムが開発されました。これらのアルゴリズムは、不完全な説明のサブセットを計算するか、ランダムサンプリングを使用します。最初のアプローチでは、説明のサブセットが下限を提供し、部分的に展開された説明のセットが上限を提供します。2番目のアプローチでは、クエリの真偽が確率プログラムからサンプリングされた通常の論理プログラムで繰り返しチェックされます。クエリの確率は、成功の割合によって与えられます。[ 2 ] [ 10 ]
確率的帰納論理プログラミングは、データから確率的論理プログラムを学習することを目的としています。これには、ユーザーが節自体を与えた上でプログラムの確率注釈を推定するパラメータ学習と、確率的帰納論理プログラミングシステムによって節自体が誘導される構造学習が含まれます。[ 2 ]
パラメータ学習の一般的なアプローチは期待値最大化法または勾配降下法に基づいているが、構造学習はさまざまなヒューリスティックの下で可能な節の空間を探索することによって実行できる。[ 2 ]
2024年2月3日現在、この記事は、Riguzzi, Fabrizio; Bellodi, Elena; Zese, Riccardo (2014). "A History of Probabilistic Inductive Logic Programming" . Frontiers in Robotics and AI . 1. doi : 10.3389/frobt.2014.00006 .から全部または一部が派生しています。著作権者は、CC BY-SA 3.0およびGFDLに基づき、コンテンツの再利用を許可する形でライセンスを付与しています。関連するすべての条件を遵守する必要があります。