論文の概要: Shapley Value Computation in Ontology-Mediated Query Answering
- arxiv url: http://arxiv.org/abs/2407.20058v2
- Date: Mon, 25 Nov 2024 10:04:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-26 14:14:37.913451
- Title: Shapley Value Computation in Ontology-Mediated Query Answering
- Title(参考訳): オントロジーを用いた問合せ回答における共有値計算
- Authors: Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade,
- Abstract要約: Shapley値は、もともと富分配のための協調ゲーム理論で導入されたもので、KRやデータベースで使われている。
本稿では,問合せ応答設定におけるShapley値計算(SVC)の複雑さ解析について述べる。
- 参考スコア(独自算出の注目度): 3.1952340441132474
- License:
- Abstract: The Shapley value, originally introduced in cooperative game theory for wealth distribution, has found use in KR and databases for the purpose of assigning scores to formulas and database tuples based upon their contribution to obtaining a query result or inconsistency. In the present paper, we explore the use of Shapley values in ontology-mediated query answering (OMQA) and present a detailed complexity analysis of Shapley value computation (SVC) in the OMQA setting. In particular, we establish a PF/#P-hard dichotomy for SVC for ontology-mediated queries (T,q) composed of an ontology T formulated in the description logic ELHI_\bot and a connected constant-free homomorphism-closed query q. We further show that the #P-hardness side of the dichotomy can be strengthened to cover possibly disconnected queries with constants. Our results exploit recently discovered connections between SVC and probabilistic query evaluation and allow us to generalize existing results on probabilistic OMQA.
- Abstract(参考訳): Shapleyの値は、もともと富分配のための協調ゲーム理論で導入されたもので、KRやデータベースにおいて、クエリ結果や一貫性の獲得への貢献に基づいて、公式やデータベースタプルにスコアを割り当てるために使われてきた。
本稿では,オントロジーによる問合せ応答(OMQA)におけるShapley値の利用について検討し,OMQA設定におけるShapley値計算(SVC)の複雑さ解析について述べる。
特に、記述論理 ELHI_\bot で定式化されたオントロジー T と接続された定数自由同型閉クエリ q からなるオントロジー型クエリ (T,q) に対して、SVC のためのPF/#Pハード二分法を確立する。
さらに、二分法における#P硬度側は、不連結なクエリを定数でカバーするために強化可能であることを示す。
本稿では,最近発見されたSVCと確率的クエリ評価の関連性を利用して,確率的OMQAの既存結果を一般化する。
関連論文リスト
- Effective Instruction Parsing Plugin for Complex Logical Query Answering on Knowledge Graphs [51.33342412699939]
知識グラフクエリ埋め込み(KGQE)は、不完全なKGに対する複雑な推論のために、低次元KG空間に一階論理(FOL)クエリを埋め込むことを目的としている。
近年の研究では、FOLクエリの論理的セマンティクスをよりよく捉えるために、さまざまな外部情報(エンティティタイプや関係コンテキストなど)を統合している。
コードのようなクエリ命令から遅延クエリパターンをキャプチャする効果的なクエリ命令解析(QIPP)を提案する。
論文 参考訳(メタデータ) (2024-10-27T03:18:52Z) - pEBR: A Probabilistic Approach to Embedding Based Retrieval [4.8338111302871525]
埋め込み検索は、クエリとアイテムの両方の共有セマンティック表現空間を学習することを目的としている。
現在の産業実践では、検索システムは典型的には、異なるクエリに対して一定数のアイテムを検索する。
論文 参考訳(メタデータ) (2024-10-25T07:14:12Z) - 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) - Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases [3.386124605656362]
私たちはShapleyのようなスコアを確率的設定に適応させ、期待値を計算することを目的としています。
本稿では,期待値のシェープ値とブール関数の期待値の計算が時間内に解釈可能であることを示す。
本稿では,データベースの証明を通じてデータベースに適用し,このアルゴリズムをProvableシステム内で効果的に実装する。
論文 参考訳(メタデータ) (2024-01-12T10:34:31Z) - Knowledge Base Question Answering by Case-based Reasoning over Subgraphs [81.22050011503933]
本モデルでは,既存のKG補完アルゴリズムよりも複雑な推論パターンを必要とする問合せに対して,より効果的に答えることを示す。
提案モデルは、KBQAベンチマークの最先端モデルよりも優れているか、競合的に動作する。
論文 参考訳(メタデータ) (2022-02-22T01:34:35Z) - From Conjunctive Queries to Instance Queries in Ontology-Mediated
Querying [17.79631575141597]
本稿では,ALCファミリーの表現的記述論理と接続的クエリの(一意)に基づくオントロジーによるクエリについて考察する。
この結果には,このような書き換えが可能なタイミングの正確な特徴と,書き換え可能性を決定するための厳密な複雑性境界が含まれている。
論文 参考訳(メタデータ) (2020-10-22T16:40:59Z) - Robust Question Answering Through Sub-part Alignment [53.94003466761305]
我々はアライメント問題として質問応答をモデル化する。
私たちは、SQuAD v1.1でモデルをトレーニングし、いくつかの逆および外ドメインデータセットでそれをテストします。
論文 参考訳(メタデータ) (2020-04-30T09:10:57Z) - CQE in Description Logics Through Instance Indistinguishability
(extended version) [0.0]
Description Logics (DL) におけるプライバシ保護クエリ応答に関する研究
DL-Lite$_mathcal$$で応答するデータ複雑性の結果を導出します。
我々は,CQEに対する近似秘密性解答という意味論的に確立された概念を同定する。
論文 参考訳(メタデータ) (2020-04-24T17:28:24Z) - Query Focused Multi-Document Summarization with Distant Supervision [88.39032981994535]
既存の作業は、クエリとテキストセグメント間の関連性を推定する検索スタイルの手法に大きく依存している。
本稿では,クエリに関連するセグメントを推定するための個別モジュールを導入した粗大なモデリングフレームワークを提案する。
我々のフレームワークは、標準QFSベンチマークにおいて、強力な比較システムよりも優れていることを実証する。
論文 参考訳(メタデータ) (2020-04-06T22:35:19Z) - Conditional Self-Attention for Query-based Summarization [49.616774159367516]
条件依存モデリング用に設計されたニューラルネットワークモジュールであるテキスト条件自己アテンション(CSA)を提案する。
DebatepediaとHotpotQAベンチマークデータセットの実験は、CSAがバニラトランスフォーマーを一貫して上回っていることを示している。
論文 参考訳(メタデータ) (2020-02-18T02:22:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。