論文の概要: Tractable Responsibility Measures for Ontology-Mediated Query Answering
- arxiv url: http://arxiv.org/abs/2507.23191v1
- Date: Thu, 31 Jul 2025 02:08:12 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-01 17:19:08.929034
- Title: Tractable Responsibility Measures for Ontology-Mediated Query Answering
- Title（参考訳）: オントロジーによる問合せ応答に対するトラクタブルな応答性対策
- Authors: Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade,
- Abstract要約: オントロジーによる問合せ応答の設定における計算責任スコアの複雑さについて検討する。
このような測定は、一階述語クエリのクラスで最小限のデータ複雑性を享受できることを示す。
言語が協調してサポートしている場合、アトミッククエリにインタラクタビリティがすでに適用されていることを証明します。
- 参考スコア（独自算出の注目度）: 3.1952340441132474
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recent work on quantitative approaches to explaining query answers employs responsibility measures to assign scores to facts in order to quantify their respective contributions to obtaining a given answer. In this paper, we study the complexity of computing such responsibility scores in the setting of ontology-mediated query answering, focusing on a very recently introduced family of Shapley-value-based responsibility measures defined in terms of weighted sums of minimal supports (WSMS). By exploiting results from the database setting, we can show that such measures enjoy polynomial data complexity for classes of ontology-mediated queries that are first-order-rewritable, whereas the problem becomes "shP"-hard when the ontology language can encode reachability queries (via axioms like $\exists R. A \sqsubseteq A$). To better understand the tractability frontier, we next explore the combined complexity of WSMS computation. We prove that intractability applies already to atomic queries if the ontology language supports conjunction, as well as to unions of `well-behaved' conjunctive queries, even in the absence of an ontology. By contrast, our study yields positive results for common DL-Lite dialects: by means of careful analysis, we identify classes of structurally restricted conjunctive queries (which intuitively disallow undesirable interactions between query atoms) that admit tractable WSMS computation.
- Abstract（参考訳）: 質問応答を説明するための定量的アプローチに関する最近の研究は、与えられた回答を得るためのそれぞれの貢献を定量化するために、事実にスコアを割り当てるための責任措置を採用している。
本稿では, オントロジーによる問合せ応答の設定における, このような責任スコアの計算の複雑さについて考察し, 最小サポート(WSMS)の重み付き和(重み付き和)で定義されるシャプリー値に基づく責任尺度のファミリーに焦点をあてる。
データベース設定の結果を活用すれば、オントロジーを介するクエリのクラスが一階書き直し可能であるのに対して、オントロジー言語が到達性クエリをエンコードできる場合($\exists R. A \sqsubseteq A$ のような公理によって)、問題は "shP" ハードになることを示すことができる。
トラクタビリティのフロンティアをより深く理解するために、WSMS計算の複雑さの組み合わせについて検討する。
我々は、オントロジー言語が結合をサポートする場合や、オントロジーが存在しない場合でも ' well-behaved' 結合クエリの結合が既に原子クエリに適用可能であることを証明した。
注意深い分析により、我々は、構造的に制限された連結クエリ(クエリー原子間の望ましくない相互作用を直感的に禁止する)のクラスを同定し、抽出可能なWSMS計算を許容する。
関連論文リスト
- Neuro-Symbolic Query Compiler [57.78201019000895]
本稿では,このギャップを埋めるために,言語文法規則とコンパイラ設計に触発されたニューラルシンボリックなフレームワークQCompilerを提案する。
理論上は、複雑なクエリを形式化するのに最小でも十分なバックス・ナウアー形式(BNF)の文法を$G[q]$で設計する。
葉のサブクエリの原子性は、より正確な文書検索と応答生成を保証し、複雑なクエリに対処するRAGシステムの能力を大幅に改善する。
論文 参考訳（メタデータ） (2025-05-17T09:36:03Z) - Shapley Revisited: Tractable Responsibility Measures for Query Answers [3.1952340441132474]
我々は、新しい責任措置のファミリーを導入します -- 最小支援の重み付け金額(WSMS)。
任意のWSMS測度が、適切に定義された協調ゲームにおけるシェープリー値と等価であることを示す。
また、WSMSの複雑さを総合して検討し、結合クエリの様々なサブクラスに対する(難解性)結果を確立する。
論文 参考訳（メタデータ） (2025-03-28T11:52:26Z) - H-STAR: LLM-driven Hybrid SQL-Text Adaptive Reasoning on Tables [56.73919743039263]
本稿では,2段階のプロセスにシンボル的アプローチと意味的アプローチ(テキスト的アプローチ)を統合し,制約に対処する新しいアルゴリズムを提案する。
実験の結果,H-STARは3つの質問応答(QA)と事実検証データセットにおいて,最先端の手法を大幅に上回っていることがわかった。
論文 参考訳（メタデータ） (2024-06-29T21:24:19Z) - Adaptive-RAG: Learning to Adapt Retrieval-Augmented Large Language Models through Question Complexity [59.57065228857247]
Retrieval-augmented Large Language Models (LLMs) は、質問回答(QA)のようなタスクにおける応答精度を高めるための有望なアプローチとして登場した。
本稿では,クエリの複雑さに基づいて,LLMの最適戦略を動的に選択できる適応型QAフレームワークを提案する。
オープンドメインのQAデータセットを用いて、複数のクエリの複雑さを網羅し、QAシステムの全体的な効率性と精度を高めることを示す。
論文 参考訳（メタデータ） (2024-03-21T13:52:30Z) - Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors [58.340159346749964]
本稿では,証明可能な推論能力を備えた複雑なクエリを用いたエンドツーエンド学習を支援するニューラルシンボリック手法を提案する。
これまでに検討されていない10種類の新しいクエリを含む新しいデータセットを開発する。
提案手法は,新しいデータセットにおいて先行手法を著しく上回り,既存データセットにおける先行手法を同時に上回っている。
論文 参考訳（メタデータ） (2023-04-14T11:35:35Z) - Logical Message Passing Networks with One-hop Inference on Atomic
Formulas [57.47174363091452]
本稿では,ニューラルネットワーク演算子から知識グラフの埋め込みを分解する,複雑な問合せ応答のためのフレームワークを提案する。
クエリグラフの上に、局所的な原子式上のワンホップ推論とグローバル論理的推論を結びつける論理メッセージパッシングニューラルネットワーク(LMPNN)を提案する。
我々のアプローチは、最先端のニューラルCQAモデルをもたらす。
論文 参考訳（メタデータ） (2023-01-21T02:34:06Z) - Successive Prompting for Decomposing Complex Questions [50.00659445976735]
最近の研究は、大規模言語モデル(LM)の機能を活用して、数ショットで複雑な質問応答を行う。
そこでは、複雑なタスクを単純なタスクに繰り返し分解し、それを解決し、最終解を得るまでプロセスを繰り返します。
我々の最良のモデル(逐次プロンプト付き)は、DROPデータセットの数ショットバージョンにおいて、5%の絶対F1の改善を実現します。
論文 参考訳（メタデータ） (2022-12-08T06:03:38Z) - From Conjunctive Queries to Instance Queries in Ontology-Mediated
Querying [17.79631575141597]
本稿では,ALCファミリーの表現的記述論理と接続的クエリの(一意)に基づくオントロジーによるクエリについて考察する。
この結果には,このような書き換えが可能なタイミングの正確な特徴と,書き換え可能性を決定するための厳密な複雑性境界が含まれている。
論文 参考訳（メタデータ） (2020-10-22T16:40:59Z) - Answering Counting Queries over DL-Lite Ontologies [0.0]
本稿では,クエリをカウントする一般的な形式を導入し,従来の提案に関連付けるとともに,そのようなクエリに答えることの複雑さについて検討する。
我々は、複雑性境界の改善を確立させる、実践的に関連するいくつかの制約について検討する。
論文 参考訳（メタデータ） (2020-09-02T11:10:21Z) - A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
我々の懸念は、標準的なデータベースクエリへの記述とそれらの最適な書き換えを介し、クエリに応答する際のデータ複雑さを効率的に決定することである。
我々は、疎結合シロップ(d-シロップ)と呼ばれるブール共役型クエリに焦点を当てる。
一部のd-シロップは指数的な大きさの分解能しか持たないが、そのうちのいくつかは二重指数サイズの正存在量書き換えと単帰的データログ書き換えのみである。
論文 参考訳（メタデータ） (2020-06-07T14:47:07Z) - When is Ontology-Mediated Querying Efficient? [10.971122842236024]
関係データベース上でのオントロジーによるクエリの評価について検討する。
OMQ のクラスの特徴として,複雑な組み合わせによるトラクタブルなクラスを提供しています。
また、与えられた OMQ が有界木幅の OMQ に等しいかどうかを決定する複雑さについても検討する。
論文 参考訳（メタデータ） (2020-03-17T16:32:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。