Efficient Explanations for Knowledge Compilation Languages
This provides incremental improvements for practitioners in constraint programming and machine learning by enabling faster explanations in specific knowledge compilation contexts.
The paper tackles the problem of efficiently explaining decisions in knowledge compilation languages, showing that for many prominent languages like d-DNNF, explanations can be computed in polynomial time, and it explores conditions for extending this to more succinct languages.
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.