Cost-Based Semantics for Querying Inconsistent Weighted Knowledge Bases

技術要約：不整合な重み付き知識ベースのクエリに対するコストベースのセマンティクス

問題提起
オントロジー媒介クエリ回答（OMQA）は、TBox（オントロジー）とABox（データ）からなる記述論理（DL）知識ベース（KB）に依存している。矛盾を含む場合にすべてが含意されてしまう古典的なOMQAセマンティクス（一階述語論理に基づくもの）は、有益な回答を提供できない。既存のアプローチは、リペア（修復）を通じて不整合を扱うが（例：ARおよびbraveセマンティクス）、これらは通常、TBoxは信頼できると仮定し、ABoxのみを修正するものである。さらに、標準的なリペアセマンティクスは、多くの場合、すべてのアサーションを等しく信頼できると見なすか、あるいは基数に基づく最大性に依存しており、信頼度の差異に基づいて競合する情報を優先順位付けする洗練された手法を欠いている。

本論文は、定量的なフレームワークを導入することで、不整合なDL知識ベースをクエリするという課題に対処する。核心となる問題は、TBoxの公理とABOXのアサーションの両方が違反される可能性があり、違反が割り当てられた重みに従ってペナルティを課される状況において、意味のある「確実な回答（certain answers）」と「可能な回答（possible answers）」を定義することである。

手法およびフレームワーク
著者らは、重み付き知識ベース（Weighted Knowledge Base: WKB） フレームワーク $K_\omega = (\langle \mathcal{T}, \mathcal{A} \rangle, \omega)$ を提案している。

• 重み: コスト関数 $\omega$ は、$\mathcal{T}$ 内のすべての公理および $\mathcal{A}$ 内のすべてのアサーションに対して、値 $\mathbb{N}_{>0} \cup \{+\infty\}$ を割り当てる。無限の重みは、満たされなければならない「ハード」な制約を表し、有限の重みは、高い値ほど信頼性が高いことを示す「ソフト」な制約を表す。
• 解釈のコスト: 解釈 $I$ のコストは、違反したすべての公理およびアサーションの重みの総和として定義される。具体的には、概念包含 $\tau$ について、コストには $\omega_\tau \times |vio_\tau(I)|$ が含まれる（ここで $vio_\tau(I)$ は包含を違反している領域要素の集合である）。アサーションは最大で一度だけ違反される。
• セマンティクス: 本論文では、コストに基づく解釈に基づいた4つのクエリ含意セマンティクスを定義する：
  1. $k$-コスト境界確実（$K_\omega \models^k_c q$）: コスト $\le k$ であるすべての解釈において $q$ が成立する。
  2. $k$-コスト境界可能（$K_\omega \models^k_p q$）: コスト $\le k$ である少なくとも一つの解釈において $q$ が成立する。
  3. 最適コスト確実（$K_\omega \models^{opt}_c q$）: 最小コスト（$optc(K_\omega)$）を持つすべての解釈において $q$ が成立する。
  4. 最適コスト可能（$K_\omega \models^{opt}_p q$）：最小コストを持つ少なくとも一つの解釈において $q$ が成立する。

本フレームワークは既存のリペアセマンティクスを一般化する。具体的には、TBoxの公理が無限の重みを持つ場合、最適コスト確実セマンティクスは、保持されるアサーションの重みの総和を最大化する $\le_\omega$-AR セマンティクス（Bienvenu, Bourgaux, and Goasdoué 2014）と一致する。

主な貢献
主要な貢献は、この設定における主要な決定問題の**結合複雑度（combined complexity）およびデータ複雑度（data complexity）**に関する包括的な分析である。

1. 有界コスト充足可能性（Bounded Cost Satisfiability: BCS）: コスト $\le k$ である解釈が存在するかどうかを判定する。
2. 確実および可能回答の認識: 定義された4つのセマンティクス下での含意を判定する。

本研究は、軽量な $\mathcal{EL}^\bot$ から表現力の高い $\mathcal{ALCO}$ （および上限証明のための $\mathcal{ALCO}^\mathcal{Q}$）に至る幅広い記述論理を対象とし、インスタンスクエリ（IQ）および結合クエリ（CQ）の両方を扱う。

複雑度の結果
本論文は、以下に要約されるタイトな複雑度境界を確立している：

• 結合複雑度:

  • ほとんどの問題は EXPTIME完全 である。
  • CQに対する確実回答の認識（有界および最適コストの両方）は 2EXPTIME完全 である。この高い複雑度は、特定のコストを持つすべてのモデルにわたって含意を検証する必要があることに起因しており、これは循環的（circumscribed）な知識ベースに関連している。
  • これらの境界は、重みとコスト境界 $k$ がバイナリでエンコードされている場合でも保持される。

• データ複雑度:

  • 有界コスト充足可能性（BCS）: NP完全。
  • 有界コスト回答（IQ/CQ）: NP完全（可能）および coNP完全（確実）。
  • 最適コスト回答: 複雑度は重みのエンコーディングに大きく依存する：
    • 重みが**単項式（unary）**でエンコードされているか、ABoxのサイズとは独立して制限されている場合、問題は $\Theta^p_2$-完全 である（NPオラクルへの対数回の呼び出しによる多項式時間で解決可能）。
    • 重みがバイナリでエンコードされており、ABoxのサイズに対して指数関数的になり得る場合、問題は $\Delta^p_2$-完全 となる（NPオラクルへのアクセスを伴う多項式時間で解決可能）。
  • 本論文は、バイナリ重みを用いた最適コスト確実セマンティクスにおいて、上界は未解決であるが、下界は $\Delta^p_2$-困難であることを指摘している。

意義および主張
著者らは、コストベースのセマンティクス下での不整合な知識ベースのクエリに関する複雑度の景観について、「ほぼ完全な全体像」を提供したと主張している。本研究の意義は以下の点にある：

1. 定量的柔軟性: 二値的な整合性から、回答をその「堅牢性」（すなわち、最適コストに近い解釈において成立するかどうか）に基づいてランク付けまたはフィルタリングできる、段階的なアプローチへと移行していること。
2. 一般化: データベースにおけるソフト制約（Carmeli et al. 2021）とオントロジーにおける重み付きリペアの概念を統合し、最適コストセマンティクスが好ましいリペアセマンティクスを自然に一般化することを示した。
3. 技術的深度: 本論文の複雑度の証明は、以下のものを含むDL推論の高度な技術を活用・適応させている：
   • 上界を確立するためのフィルタリングおよび有界モデル特性。
   • 下界を確立するための、基数クエリ回答および循環的知識ベースからの還元。
   • 重み付き違反の特定の制約を扱うための、カウンティングクエリ文献（Manière 2022）からの「インターレース（interlacing）」および「商（quotient）」構成の適応。

本論文は、将来の方向性として、特に逆ロール、ロール包含、および関数的ロールを持つDL（例：DL-Liteファミリー）への拡張を挙げ、現在の境界上界のための手法がこれらの構成には容易に転用できないことを述べている。また、実用的なアルゴリズムの実装に向けた課題についても強調している。