デフォルトロジック

デフォルト ロジックは、デフォルトの仮定による推論を形式化するために Raymond Reiterによって提案された非単調ロジックです。

デフォルト ロジックは、「デフォルトでは、何かが真である」などの事実を表現できます。対照的に、標準ロジックは、何かが真であるか、何かが偽であるかのみを表現できます。推論には、多くの場合、大多数のケースでは真であるが常に真であるとは限らない事実が含まれるため、これは問題です。古典的な例は、「鳥は通常飛ぶ」です。このルールは、標準ロジックでは、「すべての鳥は飛ぶ」と表現できますが、これはペンギンが飛ばないという事実と矛盾します。または、「ペンギンでもダチョウでもないすべての鳥は飛ぶ」と表現できますが、これはルールのすべての例外を指定する必要があります。デフォルト ロジックは、このような推論ルールを、すべての例外を明示的に言及せずに形式化することを目的としています。

デフォルト理論はペアです。Wは、確実にわかっている事実を形式化する、背景理論と呼ばれる論理式の集合です。Dは、それぞれが次の形式である デフォルト規則の集合です。${\displaystyle \langle W,D\rangle }$

${\displaystyle {\frac {\mathrm {前提条件:正当化} _{1},\dots ,\mathrm {正当化} _{n}}{\mathrm {結論} }}}$

このデフォルトによれば、前提条件が真であると信じ、それぞれのfor が現在の信念と一致している場合、結論が真であると信じるように導かれます。 ${\displaystyle \mathrm {正当化} _{i}}$${\displaystyle i=1,\dots ,n}$

Wの論理式とデフォルト内のすべての式は、もともと一階論理式であると想定されていましたが、任意の形式論理の式になる可能性もあります。命題論理の式である場合は、最も研究されているケースの 1 つです。

「鳥は通常飛ぶ」というデフォルトのルールは、次のデフォルトによって形式化されます。

${\displaystyle D=\left\{{\frac {\mathrm {鳥} (X):\mathrm {ハエ} (X)}{\mathrm {ハエ} (X)}}\right\}}$

この規則は、「Xが鳥であり、それが飛ぶと仮定できる場合、それが飛ぶと結論付けることができる」ことを意味します。鳥に関するいくつかの事実を含む背景理論は次のとおりです。

${\displaystyle W=\{\mathrm {鳥} (\mathrm {コンドル} ),\mathrm {鳥} (\mathrm {ペンギン} ),\neg \mathrm {ハエ} (\mathrm {ペンギン} ),\mathrm {ハエ} (\mathrm {蜂} )\}}$。

このデフォルト ルールによると、コンドルが飛ぶのは、前提条件Bird(Condor)が真であり、正当化Flies(Condor) が現在知られていることと矛盾しないからです。逆に、Bird(Penguin) はFlies(Penguin) を結論付けることを許可しません。デフォルトのBird(Penguin)の前提条件が真であっても、正当化Flies(Penguin) は知られていることと矛盾します。この背景理論とデフォルトから、デフォルト ルールではBird( X )からFlies( X )を導き出すことはできますが、その逆はできないため、 Bird(Bee) を結論付けることはできません。推論規則の前提を帰結から導き出すことは、帰結の説明の一形態であり、アブダクション推論の目的です。

一般的なデフォルト仮定は、真であると知られていないものは偽であると信じられるというものです。これは、閉世界仮定として知られており、すべての事実Fに対して次のようなデフォルトを使用してデフォルト ロジックで形式化されます。

${\displaystyle {\frac {:{\neg }F}{{\neg }F}}}$

たとえば、コンピュータ言語Prolog は、否定を扱うときに、一種のデフォルト仮定を使用します。つまり、否定のアトムが真であると証明できない場合は、偽であると仮定します。ただし、Prolog は、いわゆる否定を失敗として使用することに注意してください。インタープリタがアトムを評価する必要があるときは、 Fが真であることを証明しようとし、失敗した場合は真であると結論付けます。代わりに、デフォルト ロジックでは、正当化としてのデフォルトは、が現在の知識と一致する場合にのみ適用できます。 ${\displaystyle \neg F}$${\displaystyle \neg F}$${\displaystyle \neg F}$${\displaystyle \neg F}$

デフォルトは、前提条件がない場合（または、同等に、前提条件がトートロジーである場合）、カテゴリカルまたは前提条件なしです。デフォルトは、結論と同等の単一の正当化がある場合、正規です。デフォルトは、カテゴリカルかつ正規の場合、超正規です。デフォルトは、すべての正当化が結論を必然的に伴う場合、半正規です。デフォルト理論は、含まれるすべてのデフォルトがカテゴリカル、正規、超正規、または半正規である場合、それぞれカテゴリカル、正規、超正規、または半正規と呼ばれます。

デフォルト ルールは、その前提条件が理論によって必然的に導かれ、その正当性が理論とすべて一致している場合に、理論に適用できます。デフォルト ルールを適用すると、その結果が理論に追加されます。その結果得られた理論に、他のデフォルト ルールを適用できます。 他のデフォルトを適用できない理論の場合、その理論はデフォルト理論の拡張と呼ばれます。 デフォルト ルールは異なる順序で適用でき、これにより異なる拡張がもたらされる場合があります。ニクソン ダイヤモンドの例は、2 つの拡張を持つデフォルト理論です。

${\displaystyle \left\langle \left\{{\frac {\mathrm {共和党} (X):\neg \mathrm {平和主義者} (X)}{\neg \mathrm {平和主義者} (X)}},{ \frac {\mathrm {クエーカー} (X):\mathrm {平和主義者} (X)}{\mathrm {平和主義者} (X)}}\right\},\left\{\mathrm {共和党} (\mathrm {ニクソン} ),\mathrm {クエーカー} (\mathrm {ニクソン} )\right\}\right\rangle }$

ニクソンは共和党員であり、クエーカー教徒でもあるため、両方のデフォルトを適用できます。ただし、最初のデフォルトを適用すると、ニクソンは平和主義者ではないという結論に至り、2 番目のデフォルトは適用できません。同様に、2 番目のデフォルトを適用すると、ニクソンは平和主義者であることが判明し、1 番目のデフォルトは適用できません。したがって、この特定のデフォルト理論には 2 つの拡張があり、1 つはPacifist(Nixon)が真であり、もう 1 つはPacifist(Nixon)が偽です。

デフォルト ロジックの本来の意味論は、関数の不動点に基づいていました。以下は、同等のアルゴリズム定義です。デフォルトに自由変数を含む式が含まれている場合、その式は、これらすべての変数に値を与えることによって得られるすべてのデフォルトの集合を表すものと見なされます。デフォルトは、すべての理論が矛盾しない場合に、命題理論Tに適用できます。このデフォルトをTに適用すると、理論 が得られます。次のアルゴリズムを適用することで、拡張を生成できます。 ${\displaystyle {\frac {\alpha :\beta _{1},\ldots ,\beta _{n}}{\gamma }}}$${\displaystyle T\models \alpha }$${\displaystyle T\cup \{\beta _{i}\}}$${\displaystyle T\cup \{\gamma \}}$

T = W /* 現在の理論 */
A = 0 /* これまで適用されたデフォルトのセット */
 
              /* デフォルトのシーケンスを適用する */
一方、 Aには存在せずTに適用可能なデフォルトdが存在する。
    dの結果をTに加える
    Aにdを加える
 
              /* 最終的な一貫性チェック */
 
    Aのデフォルトdごとに
        Tはdのすべての正当化と一致している
それから
    出力T

このアルゴリズムは非決定論的であり、与えられた理論Tに複数のデフォルトを交互に適用することができます。ニクソンダイヤモンドの例では、最初のデフォルトを適用すると、2 番目のデフォルトを適用できない理論が生まれ、その逆も同様です。その結果、ニクソンが平和主義者である場合と、ニクソンが平和主義者でない場合の 2 つの拡張が生成されます。

適用されたすべてのデフォルトの正当性の一貫性の最終チェックは、一部の理論に拡張がないことを意味します。特に、適用可能なデフォルトのすべての可能なシーケンスでこのチェックが失敗すると、この状況が発生します。次のデフォルト理論には拡張がありません。

${\displaystyle \left\langle \left\{{\frac {:A(b)}{\neg A(b)}}\right\},\emptyset \right\rangle }$

は背景理論と一致しているため、デフォルトを適用することができ、誤った結論につながります。ただし、この結果は、最初のデフォルトを適用するために行われた仮定を覆すものです。したがって、この理論には拡張がありません。 ${\displaystyle A(b)}$${\displaystyle A(b)}$

通常のデフォルト理論では、すべてのデフォルトは正規です。つまり、各デフォルトの形式は です。通常のデフォルト理論には、少なくとも 1 つの拡張があることが保証されています。さらに、通常のデフォルト理論の拡張は相互に矛盾しています。つまり、互いに矛盾しています。 ${\displaystyle {\frac {\phi :\psi }{\psi }}}$

デフォルト理論には、0 個、1 個、またはそれ以上の拡張を含めることができます。デフォルト理論からの式の 含意は、次の 2 つの方法で定義できます。

懐疑的

式がデフォルト理論によって含意される場合、それはそのすべての拡張によって含意される。

信じやすい

式がデフォルト理論によって含意されるのは、その式が少なくとも 1 つの拡張によって含意される場合です。

したがって、ニクソンのダイヤモンド例の理論には、ニクソンが平和主義者であるという拡張と、ニクソンが平和主義者ではないという拡張の 2 つがあります。その結果、Pacifist(Nixon)も¬Pacifist(Nixon)も懐疑的に含意されませんが、両方とも信じやすい形で含意されます。この例が示すように、デフォルト理論の信じやすい結果は、互いに矛盾する可能性があります。

デフォルト ロジックの次の代替推論規則はすべて、元のシステムと同じ構文に基づいています。

正当化

元のものと異なるのは、 Tセットが適用されたデフォルトの正当性と矛盾する場合にはデフォルトが適用されないという点です。

簡潔

デフォルトは、その結果がTによってすでに含意されていない場合にのみ適用されます(正確な定義はこれよりも複雑です。これはその背後にある主なアイデアにすぎません)。

制約

デフォルトは、背景理論、適用されたすべてのデフォルトの正当性、および適用されたすべてのデフォルトの結果（このデフォルトを含む）で構成されるセットが一貫している場合にのみ適用されます。

ラショナル

制約付きデフォルト ロジックに似ていますが、追加するデフォルトの結果は整合性チェックでは考慮されません。

用心深い

適用可能だが互いに競合するデフォルト (ニクソン ダイヤモンドの例のような) は適用されません。

推論規則の正当化されたバージョンと制約されたバージョンは、すべてのデフォルト理論に少なくとも 1 つの拡張を割り当てます。

次のデフォルト ロジックのバリアントは、構文とセマンティクスの両方において元のものと異なります。

断定的なバリエーション

アサーションは、式と式のセットで構成されるペアです。このようなペアは、pが真であることを示しますが、式はpが真であることを証明するために一貫していると想定されています。アサーションのデフォルト理論は、背景理論と呼ばれるアサーション理論 (アサーション式の集合) と、元の構文で定義されたデフォルトの集合で構成されます。アサーション理論にデフォルトが適用されるたびに、その結​​果と正当化の集合で構成されるペアが理論に追加されます。次のセマンティクスはアサーション理論を使用します。${\displaystyle \langle p:\{r_{1},\ldots ,r_{n}\}\rangle }$${\displaystyle r_{1},\ldots ,r_{n}}$

• 累積デフォルトロジック
• 仮定のデフォルトロジックへのコミットメント
• 準デフォルトロジック

弱い拡張

前提条件が背景理論と適用されたデフォルトの結果から構成される理論において妥当であるかどうかをチェックするのではなく、生成される拡張において前提条件の妥当性がチェックされます。言い換えれば、拡張を生成するアルゴリズムは、理論を推測し、それを背景理論の代わりに使用することから始まります。拡張生成プロセスの結果として得られるものは、最初に推測された理論と同等である場合にのみ、実際には拡張となります。このデフォルト ロジックの変形は、原理的に自己認識論理に関連しており、理論は、真であると仮定すると、式が最初の仮定をサポートするという理由だけで、 xが真となるモデルを持ちます。${\displaystyle \Box x\rightarrow x}$${\displaystyle \Box x}$${\displaystyle \Box x\rightarrow x}$

選言デフォルトロジック

デフォルトの結果は、単一の式ではなく、一連の式です。デフォルトが適用されるたびに、その結​​果の少なくとも 1 つが非決定論的に選択され、真になります。

デフォルトの優先順位

デフォルトの相対的な優先順位は明示的に指定できます。理論に適用可能なデフォルトのうち、最も好ましいものの 1 つだけを適用できます。デフォルト ロジックの一部のセマンティクスでは、優先順位を明示的に指定する必要はありません。むしろ、より具体的なデフォルト (より少ないケースに適用可能なもの) が、より具体的でないデフォルトよりも優先されます。

統計的変異

統計的デフォルトとは、エラーの頻度に上限が設定されたデフォルトです。言い換えると、デフォルトは、適用された回数のうち最大でもその割合で誤った推論規則であると想定されます。

デフォルト理論は他のロジックの理論に翻訳することができ、その逆も可能です。翻訳に関しては以下の条件が考慮されています。

結果保存

元の理論と翻訳された理論は同じ（命題的）結果をもたらします。

忠実な

この条件は、デフォルト ロジックの 2 つのバリアント間の翻訳、またはデフォルト ロジックと、拡張に類似した概念が存在するロジック (たとえば、様相論理のモデル) 間の翻訳の場合にのみ意味を持ちます。元の理論と翻訳された理論の拡張 (またはモデル) 間にマッピング (通常は一対一) が存在する場合、翻訳は忠実です。

モジュラー

デフォルト ロジックから別のロジックへの変換は、デフォルトと背景理論を別々に翻訳できる場合にモジュール化されます。さらに、背景理論に式を追加しても、新しい式が変換の結果に追加されるだけです。

同じアルファベット

元の理論と翻訳された理論は同じアルファベットに基づいて構築されています。

多項式

変換の実行時間または生成された理論のサイズは、元の理論のサイズの多項式である必要があります。

翻訳は通常、忠実であること、または少なくとも結果が維持されることが求められますが、モジュール性や同じアルファベットの条件は無視されることがあります。

命題デフォルト論理と以下の論理間の翻訳可能性が研究されました。

• 古典的な命題論理;
• 自己認識論理;
• 半正規理論に限定された命題デフォルト論理。
• デフォルトロジックの代替セマンティクス。
• 外接。

変換が存在するかどうかは、どの条件が課されるかによって異なります。命題デフォルト論理から古典的な命題論理への変換では、多項式階層が崩壊しない限り、多項式サイズの命題理論が常に生成されるとは限りません。自己認識論理への変換が存在するかどうかは、モジュール性または同じアルファベットの使用が必要かどうかによって異なります。

デフォルト ロジックに関する次の問題の計算複雑度は既知 です。

拡張機能の存在

命題デフォルト理論が少なくとも 1 つの拡張を持つかどうかを決定することは-完全である。${\displaystyle \Sigma _{2}^{P}}$

懐疑的な含意

命題デフォルト理論が命題式を懐疑的に含意するかどうかを決定することは完全である。${\displaystyle \Pi_{2}^{P}}$

信じやすい含意

命題デフォルト理論が命題式を信じやすく含意するかどうかを決定することは完全である。${\displaystyle \Sigma _{2}^{P}}$

拡張子のチェック

命題式が命題デフォルト理論の拡張と同等であるかどうかを決定することは-完全である。${\displaystyle \Delta _{2}^{P[\log ]}}$

モデルチェック

命題解釈が命題デフォルト理論の拡張モデルであるかどうかを決定することは完全である。${\displaystyle \Sigma _{2}^{P}}$

デフォルト ロジックを実装している 4 つのシステムは、DeReS ^{[ permanent dead link ‍ ]}、XRay、GADeL Archived 2007-04-06 at the Wayback Machine、および Catala です。

• 回答セットプログラミング
• 無効化可能なロジック
• 非単調な論理
• 論理プログラミング

• G. Antoniou (1999). デフォルトロジックに関するチュートリアル。ACM Computing Surveys、31(4):337-359。
• M. Cadoli、FM Donini、P. Liberatore、および M. Schaerf (2000)。命題的知識表現形式の空間効率。Wayback Machineに 2013-05-09 にアーカイブ。Journal of Artificial Intelligence Research、13:1-31。
• P. Cholewinski、V. Marek、M. Truszczynski (1996)。デフォルト推論システム DeReS。知識表現および推論の原理に関する第 5 回国際会議 (KR'96) の議事録、518-528 ページ。
• J. Delgrande および T. Schaub (2003)。ライターのデフォルト ロジックとその (主要な) 変種との関係について。不確実性を伴う推論に対する記号的および定量的アプローチに関する第 7 回ヨーロッパ会議 (ECSQARU 2003)、452-463 ページ。
• JP Delgrande、T. Schaub、WK Jackson (1994)。デフォルトロジックへの代替アプローチ。人工知能、70:167-237。
• G. Gottlob (1992)。非単調論理の計算量結果。Journal of Logic and Computation、2:397-425。
• G. Gottlob (1995)。デフォルト論理を標準的な自己認識論理に変換する。Journal of the ACM、42:711-740。
• T. Imielinski (1987)。デフォルトをサーカムスクリプションに変換する結果。人工知能、32:131-146。
• T. Janhunen (1998)。自己認識論、デフォルトおよび優先論理、および並列限定の相互翻訳可能性について。人工知能の論理に関する第 6 回ヨーロッパワークショップ (JELIA'98) の議事録、216-232 ページ。
• T. Janhunen (2003)。半正規性がデフォルトの表現力に与える影響の評価。人工知能、144:233-250。
• HE KyburgとCM. Teng (2006)。非単調論理と統計的推論。計算知能、22(1):26-51。
• P. Liberatore および M. Schaerf (1998)。命題デフォルト論理のモデル検査の複雑さ。第 13 回ヨーロッパ人工知能会議 (ECAI'98) の議事録、18 ～ 22 ページ。
• W. Lukaszewicz (1988). デフォルトロジックに関する考察：代替アプローチComputational Intelligence , 4(1):1-16.
• W. Marek と M. Truszczynski (1993)。非単調論理: 文脈依存推論。Springer。
• A. Mikitiuk および M. Truszczynski (1995)。制約付きおよび合理的なデフォルト ロジック。第 14 回国際人工知能合同会議 (IJCAI'95) の議事録、1509-1517 ページ。
• P. Nicolas、F. Saubion、I. Stéphan (2001)。デフォルトロジック推論システムのヒューリスティック。Wayback Machineに2017-09-07にアーカイブ。International Journal on Artificial Intelligence Tools、10(4):503-523。
• R.ライター（1980）「デフォルト推論のロジック」人工知能、13:81-132。
• T. Schaub、S. Brüning、および P. Nicolas (1996)。XRay: デフォルト推論のための Prolog テクノロジ定理証明器: システムの説明。第 13 回国際自動演繹会議 (CADE'96) の議事録、293-297 ページ。
• G. Wheeler (2004)。リソース制限付きデフォルトロジック。第10回非単調推論国際ワークショップ(NMR-04)の議事録、ウィスラー、ブリティッシュコロンビア、416-422。
• G. Wheeler および C. Damasio (2004)。統計的デフォルト ロジックの実装。第 9 回ヨーロッパ人工知能ロジック会議 (JELIA 2004) の議事録、LNCS シリーズ、Springer、121-133 ページ。

• Schmidt, Charles F. RCI.Rutgers.edu、「Default Logic」。2004 年 8 月 10 日閲覧。
• Ramsay, Allan (1999). UMIST.ac.uk, Default Logic. 2004 年 8 月 10 日閲覧。
• Stanford.edu、無効化可能な推論、スタンフォード哲学百科事典。