Shapley Revisited: Tractable Responsibility Measures for Query Answers

• URL: http://arxiv.org/abs/2503.22358v1
• Date: Fri, 28 Mar 2025 11:52:26 GMT
• Title: Shapley Revisited: Tractable Responsibility Measures for Query Answers
• Authors: Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade,
• Abstract summary: We introduce a new family of responsibility measures -- weighted sums of minimal supports (WSMS)<n>We prove that every WSMS measure can be equivalently seen as the Shapley value of a suitably defined cooperative game.<n>We also explore the combined complexity of WSMS and establish (in)tractability results for various subclasses of conjunctive queries.
• Score: 3.1952340441132474
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Complete Approximations of Incomplete Queries [0.9626666671366836]
  We investigate whether a query can be fully answered, as if all data were available. If not, we explore reformulating the query into either Maximal Complete approximations (MCSs) or the Minimal Complete Generalization (MCG)
  arXiv  Detail & Related papers  (2024-07-30T16:13:42Z)
• Shapley Value Computation in Ontology-Mediated Query Answering [3.1952340441132474]
  The Shapley value, originally introduced in cooperative game theory for wealth distribution, has found use in KR and databases. We present a detailed complexity analysis of Shapley value computation (SVC) in the query answering setting.
  arXiv  Detail & Related papers  (2024-07-29T14:45:14Z)
• Benchmarking Complex Instruction-Following with Multiple Constraints Composition [72.82640456309821]
  How to evaluate the ability of complex instruction-following of large language models (LLMs) has become a critical research problem. Existing benchmarks mainly focus on modeling different types of constraints in human instructions while neglecting the composition of different constraints. We propose ComplexBench, a benchmark for comprehensively evaluating the ability of LLMs to follow complex instructions composed of multiple constraints.
  arXiv  Detail & Related papers  (2024-07-04T14:50:45Z)
• QFMTS: Generating Query-Focused Summaries over Multi-Table Inputs [63.98556480088152]
  Table summarization is a crucial task aimed at condensing information into concise and comprehensible textual summaries. We propose a novel method to address these limitations by introducing query-focused multi-table summarization. Our approach, which comprises a table serialization module, a summarization controller, and a large language model, generates query-dependent table summaries tailored to users' information needs.
  arXiv  Detail & Related papers  (2024-05-08T15:05:55Z)
• STaRK: Benchmarking LLM Retrieval on Textual and Relational Knowledge Bases [93.96463520716759]
  We develop STARK, a large-scale Semi-structure retrieval benchmark on Textual and Knowledge Bases. Our benchmark covers three domains: product search, academic paper search, and queries in precision medicine. We design a novel pipeline to synthesize realistic user queries that integrate diverse relational information and complex textual properties.
  arXiv  Detail & Related papers  (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) have emerged as a promising approach to enhancing response accuracy in several tasks, such as Question-Answering (QA) We propose a novel adaptive QA framework, that can dynamically select the most suitable strategy for (retrieval-augmented) LLMs based on the query complexity. We validate our model on a set of open-domain QA datasets, covering multiple query complexities, and show that ours enhances the overall efficiency and accuracy of QA systems.
  arXiv  Detail & Related papers  (2024-03-21T13:52:30Z)
• Meta Operator for Complex Query Answering on Knowledge Graphs [58.340159346749964]
  We argue that different logical operator types, rather than the different complex query types, are the key to improving generalizability. We propose a meta-learning algorithm to learn the meta-operators with limited data and adapt them to different instances of operators under various complex queries. Empirical results show that learning meta-operators is more effective than learning original CQA or meta-CQA models.
  arXiv  Detail & Related papers  (2024-03-15T08:54:25Z)
• On Evaluating the Integration of Reasoning and Action in LLM Agents with Database Question Answering [25.57202500348071]
  This study introduces a new long-form database question answering dataset designed to evaluate how Large Language Models interact with a database. The task requires LLMs to strategically generate multiplesql queries to retrieve sufficient data from a database, to reason with the acquired context, and to synthesize them into a comprehensive analytical narrative. We propose and evaluate two interaction strategies, and provide a fine-grained analysis of the individual stages within the interaction.
  arXiv  Detail & Related papers  (2023-11-16T09:55:07Z)
• Successive Prompting for Decomposing Complex Questions [50.00659445976735]
  Recent works leverage the capabilities of large language models (LMs) to perform complex question answering in a few-shot setting. We introduce Successive Prompting'', where we iteratively break down a complex task into a simple task, solve it, and then repeat the process until we get the final solution. Our best model (with successive prompting) achieves an improvement of 5% absolute F1 on a few-shot version of the DROP dataset.
  arXiv  Detail & Related papers  (2022-12-08T06:03:38Z)
• Answering Counting Queries over DL-Lite Ontologies [0.0]
  We introduce a general form of counting query, relate it to previous proposals, and study the complexity of answering such queries. We consider some practically relevant restrictions, for which we establish improved complexity bounds.
  arXiv  Detail & Related papers  (2020-09-02T11:10:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.