Summary of Shapley Value Computation in Ontology-mediated Query Answering, by Meghyn Bienvenu et al.
Shapley Value Computation in Ontology-Mediated Query Answering
by Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade
First submitted to arxiv on: 29 Jul 2024
Categories
- Main: Artificial Intelligence (cs.AI)
- Secondary: Databases (cs.DB)
GrooveSquid.com Paper Summaries
GrooveSquid.com’s goal is to make artificial intelligence research accessible by summarizing AI papers in simpler terms. Each summary below covers the same AI paper, written at different levels of difficulty. The medium difficulty and low difficulty versions are original summaries written by GrooveSquid.com, while the high difficulty version is the paper’s original abstract. Feel free to learn from the version that suits you best!
| Summary difficulty | Written by | Summary |
|---|---|---|
| High | Paper authors | High Difficulty Summary Read the original abstract here |
| Medium | GrooveSquid.com (original content) | Medium Difficulty Summary This research paper explores the application of Shapley values in ontology-mediated query answering (OMQA) for assigning scores to formulas and database tuples based on their contribution to obtaining a query result or inconsistency. The authors present a detailed complexity analysis of Shapley value computation (SVC) in the OMQA setting, showing that SVC is PF/#P-hard for certain types of queries. They also demonstrate connections between SVC and probabilistic query evaluation, allowing them to generalize existing results on probabilistic OMQA. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary This paper looks at how to use a special kind of math called Shapley values in a field called ontology-mediated query answering (OMQA). OMQA is like searching for specific information in a big database. The researchers want to figure out how to assign scores to the different pieces of information based on how well they help answer a question or find something that’s inconsistent. They do some really hard math to show that this process can be very complex and take a long time, but it helps us understand how to make our searches better. |
