提出用'特征'分析逻辑归因中解释的多样性与差异性
Complexity of Faceted Explanations in Propositional Abduction
- 引入'特征'概念：在某些解释中出现但非必现的命题变量
- 揭示解释间差异性的新度量方式，支持更精细的推理分析
- 适用于诊断、规划等场景，适合关注解释稳定性的研究者
归因推理是一种流行的非单调推理范式，旨在解释观察到的症状和表现，广泛应用于人工智能中的诊断、规划及数据库更新。在命题归因中，知识通过命题公式表达。命题归因任务的计算复杂性已得到系统性刻画，包括对布尔片段的详细分类。然而，最具洞察力的推理问题（计数与枚举）具有高度计算难度。为此，本文探讨决策与计数之间的推理关系，在保持良好复杂性的同时深化对解释的理解。引入命题归因中的'特征'概念，即出现在某些解释中但并非所有解释都包含的原子命题。通过特征分析，可实现对解释多样性的更细粒度理解（异质性）。此外，还考虑两个解释间的距离，进一步刻画解释的异同。本文在多种设定下全面分析了命题归因中的特征，包括在Post框架下的近乎完整刻画。
原文摘要 · Abstract (English)
Abductive reasoning is a popular non-monotonic paradigm that aims to explain observed symptoms and manifestations. It has many applications, such as diagnosis and planning in artificial intelligence and database updates. In propositional abduction, we focus on specifying knowledge by a propositional formula. The computational complexity of tasks in propositional abduction has been systematically characterized - even with detailed classifications for Boolean fragments. Unsurprisingly, the most insightful reasoning problems (counting and enumeration) are computationally highly challenging. Therefore, we consider reasoning between decisions and counting, allowing us to understand explanations better while maintaining favorable complexity. We introduce facets to propositional abductions, which are literals that occur in some explanation (relevant) but not all explanations (dispensable). Reasoning with facets provides a more fine-grained understanding of variability in explanations (heterogeneous). In addition, we consider the distance between two explanations, enabling a better understanding of heterogeneity/homogeneity. We comprehensively analyze facets of propositional abduction in various settings, including an almost complete characterization in Post's framework.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。