Efficient Explanations for Knowledge Compilation Languages

  • 2021-07-08 09:58:58
  • Xuanxiang Huang, Yacine Izza, Alexey Ignatiev, Martin C. Cooper, Nicholas Asher, Joao Marques-Silva
  • 0


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)

loading the full paper ...