On the Complexity of Finding Second-Best Abductive Explanations
While looking for abductive explanations of a given set of manifestations, an ordering between possible solutions is often assumed. The complexity of finding/verifying optimal solutions is already known. In this paper we consider the computational complexity of finding second-best solutions. We consider different orderings, and consider also different possible definitions of what a second-best solution is.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Abductive explanations of classifiers under constraints: Complexity and properties
Abductive explanations (AXp's) are widely used for understanding decisions of classifiers. Existing definitions are suitable when features are independent. However, we show that ignoring constraints when they exist betwe…
Most General Explanations of Tree Ensembles (Extended Version)
Explainable Artificial Intelligence (XAI) is critical for attaining trust in the operation of AI systems. A key question of an AI system is ``why was this decision made this way''. Formal approaches to XAI use a formal m…
Explainable artificial intelligenceExplainable Artificial Intelligence (XAI)Locally-Minimal Probabilistic Explanations
Explainable Artificial Intelligence (XAI) is widely regarding as a cornerstone of trustworthy AI. Unfortunately, most work on XAI offers no guarantees of rigor. In high-stakes domains, e.g. uses of AI that impact humans,…
Explainable artificial intelligenceExplainable Artificial Intelligence (XAI)Solving Hard XAI Queries Based on a Compiled Dual-Rail Encoding
The widespread adoption of artificial intelligence (AI) within real-world applications has raised a lot of concerns regarding their trustworthiness, especially in critical applications. The field of eXplainable AI (XAI) …
Axiomatic Aggregations of Abductive Explanations
The recent criticisms of the robustness of post hoc model approximation explanation methods (like LIME and SHAP) have led to the rise of model-precise abductive explanations. For each data point, abductive explanations p…
Feature Importancevalid