Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03311518
Contributor : Xuanxiang Huang Connect in order to contact the contributor
Submitted on : Sunday, August 1, 2021 - 9:37:41 AM
Last modification on : Tuesday, October 19, 2021 - 2:23:44 PM

File

paper.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

  • HAL Id : hal-03311518, version 1

Citation

Xuanxiang Huang, Yacine Izza, Alexey Ignatiev, Martin Cooper, Nicholas Asher, et al.. Efficient Explanations for Knowledge Compilation Languages. 2021. ⟨hal-03311518⟩

Share

Metrics

Record views

69

Files downloads

15