Abstract

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

 

Quick Read (beta)