Efficient Explanations for Knowledge Compilation Languages

Abstract

Knowledge compilation (KC) languages find a growing number of practical uses, including in Constraint Programming (CP) and in Machine Learning (ML). In most applications, one natural question is how to explain the decisions made by models represented by a KC language. This paper shows that for many of the best known KC languages, well-known classes of explanations can be computed in polynomial time. These classes include deterministic decomposable negation normal form (d-DNNF), and so any KC language that is strictly less succinct than d-DNNF. Furthermore, the paper also investigates the conditions under which polynomial time computation of explanations can be extended to KC languages more succinct than d-DNNF.

References in corpus (6)

• OpenML: networked science in machine learning
• Explaining Explanations in AI
• Towards Explainable Artificial Intelligence
• Explanation in Human-AI Systems: A Literature Meta-Review, Synopsis of Key Ideas and Publications, and Bibliography for Explainable AI
• On The Reasons Behind Decisions
• The Language of Search

Cited by in corpus (1)

• On Tackling Explanation Redundancy in Decision Trees