閉世界仮説

閉世界仮定( CWA )は、知識表現に使用される論理の形式体系において、真である文は真であるとも知られているという推定である。したがって、逆に、現在真であると知られていないものは偽である。同じ名前は、レイモンド・ライターによるこの仮定の論理的形式化を指すこともある。^[1]閉世界仮定の反対は開世界仮定(OWA) であり、知識の欠如は偽を意味しないというものである。CWA と OWA の決定は、同じ概念表記法を持つ概念表現の実際の意味の理解を決定する。自然言語意味の形式化が成功するには、通常、暗黙の論理的背景が CWA に基づいているか OWA に基づいているかを明示的に明らかにする必要がある。

失敗としての否定は、真であると証明できない述語をすべて偽であると信じることになるため、閉世界仮定に関連しています。

例

知識管理の文脈では、閉世界仮定は少なくとも 2 つの状況で使用されます: (1) 知識ベースが完全であることがわかっている場合 (例: すべての従業員の記録を含む企業データベース)、および (2) 知識ベースが不完全であることがわかっているが、不完全な情報から「最善の」明確な答えを導き出さなければならない場合。たとえば、データベースに、特定の記事に取り組んだ編集者を報告する次のテーブルが含まれている場合、Formal Logic で記事を編集していない人に対するクエリでは、通常、「Sarah Johnson」が返されると予想されます。

閉じた世界の仮定では、テーブルは完全であると想定され（すべての編集者と記事の関係がリストされます）、Sarah Johnson は Formal Logic の記事を編集していない唯一の編集者です。対照的に、開いた世界の仮定では、テーブルにすべての編集者と記事のタプルが含まれているとは想定されず、誰が Formal Logic の記事を編集していないかという答えは不明です。テーブルにリストされていない編集者の数は不明であり、Sarah Johnson が編集した記事のうちテーブルにリストされていない記事の数は不明です。

論理における形式化

形式論理における閉世界仮定の最初の形式化は、知識ベースに、現在それによって含意されていないリテラルの否定を追加することである。この追加の結果は、知識ベースがホーン形式である場合は常に一貫しているが、そうでない場合は一貫しているとは保証されない。たとえば、知識ベース

\{英語(Fred)\vee アイルランド語(Fred)\}

もも含意しません。 $英語(フレッド)$ $アイルランド語(フレッド)$

これら2つのリテラルの否定を知識ベースに追加すると、

\{英語(Fred)\vee アイルランド語(Fred),\neg 英語(Fred),\neg アイルランド語(Fred)\}

これは矛盾しています。言い換えれば、閉世界仮定のこの形式化は、一貫性のある知識ベースを矛盾したものに変えてしまうことがあります。閉世界仮定は、のすべてのエルブランモデルの共通部分がのモデルでもあるとき、知識ベースに矛盾を導入しません。命題の場合、この条件は単一の極小モデルを持つことと同等であり、他のモデルに true に割り当てられた変数のサブセットがない場合、モデルは極小です。 $K$ $K$ $K$ $K$

この問題に悩まされない代替の形式化が提案されている。以下の説明では、検討対象の知識ベースは命題的であると仮定する。いずれの場合も、閉世界仮定の形式化は、に対して「否定が自由」な式、つまり偽であると仮定できる式の否定に追加することに基づいている。言い換えれば、知識ベースに適用された閉世界仮定は、知識ベースを生成する。 $K$ $K$ $K$ $K$

K\cup \{\neg f~|~f\in F\}

。

否定が自由な式の集合はさまざまな方法で定義することができ、閉世界仮定のさまざまな形式化につながります。以下は、さまざまな形式化における否定が自由であることの定義です。 $F$ $K$ $f$

CWA (閉世界仮定): $f$ は、によって含意されない肯定リテラルです。 $K$

GCWA (一般化CWA): $f$ は、となるすべての正の節に対して、が成り立つような正のリテラルである。^[2] $c$ $K\not \vdash c$ $K\not \vdash c\vee f$

EGCWA (拡張 GCWA): 上記と同じですが、肯定リテラルの結合です。 $f$

CCWA (注意深いCWA): GCWA と同じですが、肯定節は、特定のセットの肯定リテラルと別のセットの (肯定と否定の両方の) リテラルで構成されている場合にのみ考慮されます。

ECWA (拡張 CWA): CCWAに似ているが、与えられた集合からのリテラルを含まない任意の式である。^[3]^[4] $f$

ECWAとサーカムスクリプションの形式主義は命題理論では一致する。^[5]^[6]クエリ回答の複雑さ（閉世界仮定の下である式が別の式によって含意されるかどうかを確認すること）は、通常、一般的な式では多項式階層の第2レベルにあり、ホーン式ではPからcoNPの範囲です。元の閉世界仮定が矛盾を導入するかどうかをチェックするには、 NPオラクルへの最大で対数回の呼び出しが必要ですが、この問題の正確な複雑さは現在わかっていません。^[7]

すべての述語に対して閉じた世界を想定することができないが、それらのいくつかが閉じていることがわかっている状況では、部分的に閉じた世界の仮定を使用することができます。この体制では、知識ベースは一般的に開いている、つまり潜在的に不完全であると考えられていますが、完全性のアサーションを使用して知識ベースの閉じている部分を指定することができます。^[8]

部分的に閉じた世界の仮定

強い否定を持つ論理プログラムの言語は、いくつかの文に対して閉世界仮定を仮定し、他の文を開世界仮定の領域に残すことを可能にする。^[9] OWAとCWAの中間的な基盤は、部分的閉世界仮定(PCWA)。PCWA では、知識ベースは一般にオープンワールドセマンティクスで扱われますが、完全性アサーションを介して、クローズドワールドセマンティクスで扱われるべき部分をアサートすることができます。PCWA は、オープンドメインのために CWA が適用できない状況で特に必要ですが、OWA は何でも真実である可能性があると認めるほど信じやすいです。^[10]^[11]

参照

参考文献

^ Reiter, Raymond (1978)。「閉じた世界のデータベースについて」。Gallaire, Hervé、Minker, Jack著『論理とデータベース』Plenum Press、pp. 119–140。ISBN 9780306400605 。
^ Minker, Jack (1982)、「不定データベースと閉世界仮定について」、第 6 回自動演繹会議、コンピュータサイエンスの講義ノート、第 138 巻、Springer Berlin Heidelberg、pp. 292–308、doi :10.1007/BFb0000066、ISBN 978-3-540-11558-8
^ Suchenek, Marek A. (1997)、「閉世界仮定の下でのクエリの評価」、Kluwer Academic Publishers / Springer (18): 237–263、doi :10.1023/A:1005723423016
^ Suchenek, Marek A. (2000)、「閉世界仮定の下でのクエリの評価。パート II: 階層的なケース」、Kluwer Academic Publishers / Springer (25): 247–289、doi :10.1023/A:1006319819647
^ Eiter, Thomas; Gottlob, Georg (1993年6月). 「命題的サーカムスクリプションと拡張された閉世界推論はΠ 2 pである」。理論計算機科学。114 (2): 231–245. doi :10.1016/0304-3975(93)90073-3. ISSN 0304-3975. ${\displaystyle \Pi _{2}^{p}}\Pi _{2}^{p}-complete$
^ Lifschitz, Vladimir (1985年11月). 「閉世界データベースとサーカムスクリプション」. 人工知能. 27 (2): 229–235. doi :10.1016/0004-3702(85)90055-4. ISSN 0004-3702.
^ Cadoli, Marco; Lenzerini, Maurizio (1994 年 4 月)。「命題的 閉世界推論と限定の複雑さ」。Journal of Computer and System Sciences。48 (2): 255–310。doi :10.1016/S0022-0000(05)80004-2。ISSN 0022-0000。
^ Razniewski, Simon; Savkovic, Ognjen; Nutt, Werner (2015). 「部分的に閉じた世界の仮定をひっくり返す」(PDF)。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です
^ ラッセル、スチュアート J.、ノーヴィグ、ピーター (2010)。人工知能：現代的アプローチ（第 3 版）。アッパーサドルリバー：プレンティスホール。
^ Motro (1989). 「完全性 = 妥当性 + 完全性」
^ Razniewski, Simon; Savkovic, Ognjen; Nutt, Werner (2015). 「部分的に閉じた世界の仮定をひっくり返す」(PDF)。

外部リンク

https://web.archive.org/web/20090624113015/http://www.betaversion.org/~stefano/linotype/news/91/
認識論的演算子によるセマンティックウェブにおける閉世界推論
ライターの1978年の閉世界仮説に関する講演からの抜粋

[1] Reiter, Raymond (1978)。「閉じた世界のデータベースについて」。Gallaire, Hervé、Minker, Jack著『論理とデータベース』Plenum Press、pp. 119–140。ISBN 9780306400605 。

[2] Minker, Jack (1982)、「不定データベースと閉世界仮定について」、第 6 回自動演繹会議、コンピュータサイエンスの講義ノート、第 138 巻、Springer Berlin Heidelberg、pp. 292–308、doi :10.1007/BFb0000066、ISBN 978-3-540-11558-8

[3] Suchenek, Marek A. (1997)、「閉世界仮定の下でのクエリの評価」、Kluwer Academic Publishers / Springer (18): 237–263、doi :10.1023/A:1005723423016

[4] Suchenek, Marek A. (2000)、「閉世界仮定の下でのクエリの評価。パート II: 階層的なケース」、Kluwer Academic Publishers / Springer (25): 247–289、doi :10.1023/A:1006319819647

[5] Eiter, Thomas; Gottlob, Georg (1993年6月). 「命題的サーカムスクリプションと拡張された閉世界推論はΠ 2 pである」。理論計算機科学。114 (2): 231–245. doi :10.1016/0304-3975(93)90073-3. ISSN 0304-3975. ${\displaystyle \Pi _{2}^{p}}\Pi _{2}^{p}-complete$

[6] Lifschitz, Vladimir (1985年11月). 「閉世界データベースとサーカムスクリプション」. 人工知能. 27 (2): 229–235. doi :10.1016/0004-3702(85)90055-4. ISSN 0004-3702.

[7] ^ Cadoli, Marco; Lenzerini, Maurizio (1994 年 4 月)。「命題的 閉世界推論と限定の複雑さ」。Journal of Computer and System Sciences。48 (2): 255–310。doi :10.1016/S0022-0000(05)80004-2。ISSN 0022-0000。

[PCWA2015-8] Razniewski, Simon; Savkovic, Ognjen; Nutt, Werner (2015). 「部分的に閉じた世界の仮定をひっくり返す」(PDF)。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です

[9] ラッセル、スチュアート J.、ノーヴィグ、ピーター (2010)。人工知能：現代的アプローチ（第 3 版）。アッパーサドルリバー：プレンティスホール。

[10] Motro (1989). 「完全性 = 妥当性 + 完全性」

[Razniewskietal2015-11] Razniewski, Simon; Savkovic, Ognjen; Nutt, Werner (2015). 「部分的に閉じた世界の仮定をひっくり返す」(PDF)。