論文の概要: Shapley Revisited: Tractable Responsibility Measures for Query Answers

• arxiv url: http://arxiv.org/abs/2503.22358v1
• Date: Fri, 28 Mar 2025 11:52:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-31 15:28:25.358440
• Title: Shapley Revisited: Tractable Responsibility Measures for Query Answers
• Title（参考訳）: Shapley氏が再考: クエリ応答に対するトラクタブルな責任対策
• Authors: Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade,
• Abstract要約: 我々は、新しい責任措置のファミリーを導入します -- 最小支援の重み付け金額(WSMS)。 任意のWSMS測度が、適切に定義された協調ゲームにおけるシェープリー値と等価であることを示す。 また、WSMSの複雑さを総合して検討し、結合クエリの様々なサブクラスに対する(難解性)結果を確立する。
• 参考スコア（独自算出の注目度）: 3.1952340441132474
• License:
• Abstract: The Shapley value, originating from cooperative game theory, has been employed to define responsibility measures that quantify the contributions of database facts to obtaining a given query answer. For non-numeric queries, this is done by considering a cooperative game whose players are the facts and whose wealth function assigns 1 or 0 to each subset of the database, depending on whether the query answer holds in the given subset. While conceptually simple, this approach suffers from a notable drawback: the problem of computing such Shapley values is #P-hard in data complexity, even for simple conjunctive queries. This motivates us to revisit the question of what constitutes a reasonable responsibility measure and to introduce a new family of responsibility measures -- weighted sums of minimal supports (WSMS) -- which satisfy intuitive properties. Interestingly, while the definition of WSMSs is simple and bears no obvious resemblance to the Shapley value formula, we prove that every WSMS measure can be equivalently seen as the Shapley value of a suitably defined cooperative game. Moreover, WSMS measures enjoy tractable data complexity for a large class of queries, including all unions of conjunctive queries. We further explore the combined complexity of WSMS computation and establish (in)tractability results for various subclasses of conjunctive queries.
• Abstract（参考訳）: 協調ゲーム理論から派生したShapley値は、与えられたクエリ応答を得るためのデータベース事実の貢献を定量化する責任尺度を定義するために用いられる。 非数値クエリでは、クエリ応答が与えられたサブセットに保持されるかどうかに応じて、プレイヤーが事実であり、富関数がデータベースの各サブセットに1または0を割り当てる協調ゲームを考える。 このようなShapley値の計算の問題は、単純な結合型クエリであっても、データの複雑さにおいて#P-hardである。 これは、何が合理的な責任尺度を構成するのかという問題を再考し、直感的な特性を満足させる、新しい責任措置のファミリー、すなわち最小支援(WSMS)の重み付けの和を導入する動機となります。 興味深いことに、WSMSの定義は単純であり、Shapley値公式と明らかな類似性はないが、WSMSのすべての測度が適切に定義された協調ゲームのShapley値と等価であることを示す。 さらに、WSMS測度は、あらゆる結合型クエリを含む、大規模なクエリのクラスにおいて、トラクタブルなデータ複雑性を享受します。 さらに、WSMS計算の複雑さを総合して検討し、結合型クエリの様々なサブクラスに対する(難解性)結果を確立する。

関連論文リスト

• Complete Approximations of Incomplete Queries [0.9626666671366836]
  すべてのデータが利用可能であるかのように、クエリが完全に答えられるかどうかを調査する。 もしそうでなければ、クエリを最大完全近似(MCS)または最小完全一般化(MCG)に再構成することを検討する。
  論文  参考訳（メタデータ） (2024-07-30T16:13:42Z)
• Shapley Value Computation in Ontology-Mediated Query Answering [3.1952340441132474]
  Shapley値は、もともと富分配のための協調ゲーム理論で導入されたもので、KRやデータベースで使われている。 本稿では,問合せ応答設定におけるShapley値計算(SVC)の複雑さ解析について述べる。
  論文  参考訳（メタデータ） (2024-07-29T14:45:14Z)
• Benchmarking Complex Instruction-Following with Multiple Constraints Composition [72.82640456309821]
  大規模言語モデル(LLM)の複雑な命令追従能力の評価方法が重要な研究課題となっている。 既存のベンチマークは主に、異なる制約の構成を無視しながら、人間の指示で異なるタイプの制約をモデル化することに焦点を当てている。 複数の制約からなる複雑な命令に従うLLMの能力を総合的に評価するためのベンチマークである ComplexBench を提案する。
  論文  参考訳（メタデータ） (2024-07-04T14:50:45Z)
• QFMTS: Generating Query-Focused Summaries over Multi-Table Inputs [63.98556480088152]
  表要約は、情報を簡潔で分かりやすいテキスト要約に凝縮するための重要な課題である。 本稿では,クエリ中心のマルチテーブル要約を導入することで,これらの制約に対処する新しい手法を提案する。 提案手法は,テーブルシリアライズモジュール,要約コントローラ,および大規模言語モデルからなり,ユーザの情報要求に合わせたクエリ依存のテーブル要約を生成する。
  論文  参考訳（メタデータ） (2024-05-08T15:05:55Z)
• STaRK: Benchmarking LLM Retrieval on Textual and Relational Knowledge Bases [93.96463520716759]
  テキストと知識ベースを用いた大規模半構造検索ベンチマークSTARKを開発した。 本ベンチマークでは, 製品検索, 学術論文検索, 精密医療におけるクエリの3分野について検討した。 多様なリレーショナル情報と複雑なテキスト特性を統合した,現実的なユーザクエリを合成する,新しいパイプラインを設計する。
  論文  参考訳（メタデータ） (2024-04-19T22:54:54Z)
• 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)
• Meta Operator for Complex Query Answering on Knowledge Graphs [58.340159346749964]
  我々は、異なる複雑なクエリタイプではなく、異なる論理演算子型が一般化性を向上させる鍵であると主張する。 本稿では,メタ演算子を限られたデータで学習し,様々な複雑なクエリの演算子のインスタンスに適応するメタ学習アルゴリズムを提案する。 実験結果から,メタオペレータの学習は,従来のCQAモデルやメタCQAモデルよりも効果的であることが示唆された。
  論文  参考訳（メタデータ） (2024-03-15T08:54:25Z)
• On Evaluating the Integration of Reasoning and Action in LLM Agents with Database Question Answering [25.57202500348071]
  本研究では、大規模言語モデルがデータベースとどのように相互作用するかを評価するために設計された、新しい長文データベース質問応答データセットを提案する。 このタスクでは、LLMが戦略的に複数のクエリを生成し、データベースから十分なデータを取得し、取得したコンテキストを推論し、それらを総合的な分析的な物語に合成する必要がある。 本稿では2つのインタラクション戦略を提案し評価し、インタラクション内の個々のステージを詳細に分析する。
  論文  参考訳（メタデータ） (2023-11-16T09:55:07Z)
• Successive Prompting for Decomposing Complex Questions [50.00659445976735]
  最近の研究は、大規模言語モデル(LM)の機能を活用して、数ショットで複雑な質問応答を行う。 そこでは、複雑なタスクを単純なタスクに繰り返し分解し、それを解決し、最終解を得るまでプロセスを繰り返します。 我々の最良のモデル(逐次プロンプト付き)は、DROPデータセットの数ショットバージョンにおいて、5%の絶対F1の改善を実現します。
  論文  参考訳（メタデータ） (2022-12-08T06:03:38Z)
• Answering Counting Queries over DL-Lite Ontologies [0.0]
  本稿では,クエリをカウントする一般的な形式を導入し,従来の提案に関連付けるとともに,そのようなクエリに答えることの複雑さについて検討する。 我々は、複雑性境界の改善を確立させる、実践的に関連するいくつかの制約について検討する。
  論文  参考訳（メタデータ） (2020-09-02T11:10:21Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。