Shapley Value Computation in Ontology-Mediated Query Answering

📄 arXiv: 2407.20058v2 📥 PDF

作者: Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade

分类: cs.AI, cs.DB

发布日期: 2024-07-29 (更新: 2024-11-25)

备注: Long version of KR 2024 homonymous paper

💡 一句话要点

研究本体介导查询应答中Shapley值的计算复杂性，并提出高效算法。

🎯 匹配领域: 支柱五：交互与反应 (Interaction & Reaction)

关键词: Shapley值 本体介导查询应答 复杂性分析 描述逻辑 概率查询评估

📋 核心要点

  1. 现有方法在本体介导查询应答中计算Shapley值效率较低，缺乏对复杂性的深入分析。
  2. 论文核心思想是利用Shapley值与概率查询评估的联系，从而简化计算过程。
  3. 论文建立了Shapley值计算复杂性的二分法，并推广了概率本体介导查询应答的现有结果。

📝 摘要（中文）

Shapley值最初用于合作博弈论中的财富分配，现已应用于知识表示和数据库领域，用于根据公式和数据库元组对查询结果或不一致性的贡献程度进行评分。本文探讨了Shapley值在本体介导查询应答（OMQA）中的应用，并对OMQA环境中Shapley值计算（SVC）的复杂性进行了详细分析。特别地，我们为本体介导查询(T,q)建立了PF/#P-hard二分法，其中本体T用描述逻辑ELHI_⊥表示，q是一个连通的、无常量的同态封闭查询。我们进一步表明，二分法的#P-hardness部分可以加强以覆盖可能不连通的带常量的查询。我们的结果利用了最近发现的SVC和概率查询评估之间的联系，并允许我们推广现有的关于概率OMQA的结果。

🔬 方法详解

问题定义：论文旨在解决本体介导查询应答（OMQA）中Shapley值计算（SVC）的复杂性问题。现有方法在处理大规模本体和复杂查询时效率低下，缺乏对SVC复杂性的理论分析，难以指导算法设计。

核心思路：论文的核心思路是利用Shapley值与概率查询评估之间的联系。通过将SVC问题转化为概率查询评估问题，可以利用现有的概率查询评估技术来加速Shapley值的计算。这种转化依赖于将本体和查询视为概率模型，并利用概率推理来估计每个公式或元组对查询结果的贡献。

技术框架：论文的技术框架主要包括以下几个步骤：1) 将本体和查询转化为概率模型；2) 利用概率查询评估技术计算查询结果的概率；3) 根据查询结果的概率计算Shapley值。具体而言，论文关注描述逻辑ELHI_⊥表示的本体和连通的、无常量的同态封闭查询。对于更一般的查询，论文也给出了相应的复杂性结果。

关键创新：论文最重要的技术创新在于建立了OMQA中SVC的PF/#P-hard二分法。这意味着对于某些类型的本体和查询，SVC问题可以在多项式时间内解决，而对于另一些类型，SVC问题是#P-hard的。这一结果为算法设计提供了理论指导，并揭示了SVC问题的内在复杂性。此外，论文还推广了现有的关于概率OMQA的结果，为概率本体推理领域做出了贡献。

关键设计：论文的关键设计在于如何将SVC问题转化为概率查询评估问题。这需要仔细选择概率模型的参数，并确保概率查询评估的结果能够准确反映每个公式或元组对查询结果的贡献。此外，论文还关注如何处理带常量的查询，并证明了即使查询是不连通的，SVC问题仍然可能是#P-hard的。

📊 实验亮点

论文建立了本体介导查询应答中Shapley值计算的PF/#P-hard二分法，为算法设计提供了理论指导。对于用描述逻辑ELHI_⊥表示的本体和连通的、无常量的同态封闭查询，论文给出了SVC复杂性的精确刻画。此外，论文还证明了即使查询是不连通的，SVC问题仍然可能是#P-hard的，从而推广了现有的关于概率OMQA的结果。

🎯 应用场景

该研究成果可应用于知识图谱问答、数据溯源、以及推荐系统等领域。通过计算Shapley值，可以评估不同知识或数据对最终结果的贡献程度，从而提高系统的可解释性和可靠性。例如，在推荐系统中，可以利用Shapley值来评估不同用户行为对推荐结果的影响，从而实现更公平、更个性化的推荐。

📄 摘要（原文）

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.