Efficient Explanations for Knowledge Compilation Languages - IRIT - Université Toulouse III Paul Sabatier Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2021

Efficient Explanations for Knowledge Compilation Languages

Résumé

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.
Fichier principal
Vignette du fichier
paper.pdf (656.4 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03311518 , version 1 (01-08-2021)

Licence

Paternité

Identifiants

  • HAL Id : hal-03311518 , version 1

Citer

Xuanxiang Huang, Yacine Izza, Alexey Ignatiev, Martin Cooper, Nicholas Asher, et al.. Efficient Explanations for Knowledge Compilation Languages. 2021. ⟨hal-03311518⟩
120 Consultations
30 Téléchargements

Partager

Gmail Facebook X LinkedIn More