Efficient Explanations for Knowledge Compilation Languages

Understand

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.