Metraipolis › archive › dc_e3ee79938436
Solving Hard XAI Queries Based on a Compiled Dual-Rail Encoding — arXiv:2609.04931
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.04931
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T22:21:06.076Z
- SHA-256 of the archived text
1c76093b932707e41d67fc5ccbb32e433b1ff957aa3e9048f6e820bf4ebe12bf- Stable URL of this page
https://metraipolis.com/documento/dc_e3ee79938436
How to cite
Solving Hard XAI Queries Based on a Compiled Dual-Rail Encoding — arXiv:2609.04931 — arXiv (en), https://arxiv.org/abs/2609.04931 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e3ee79938436 (Metraipolis archive dc_e3ee79938436, sha256 1c76093b932707e41d67fc5ccbb32e433b1ff957aa3e9048f6e820bf4ebe12bf)
BibTeX
@misc{dce3ee79938436,
title = {Solving Hard XAI Queries Based on a Compiled Dual-Rail Encoding — arXiv:2609.04931},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.04931},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e3ee79938436; sha256 1c76093b932707e41d67fc5ccbb32e433b1ff957aa3e9048f6e820bf4ebe12bf},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.04931. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The widespread adoption of artificial intelligence (AI) within real-world applications has raised a lot of concerns regarding their trustworthiness, especially in critical applications. The field of eXplainable AI (XAI) has emerged with the objective of providing explanations to the users about the decisions made by AI systems. Several explanations for boolean classifiers have been introduced in the literature, including abductive and contrastive explanations, each giving a different insight on the decision of the classifier. However, computing an explanation for a decision of a boolean classifier is a hard problem in general. One way to deal with this complexity is to rely on a compiled representation of the classifier for which each explanation can be computed efficiently. Unfortunately, we prove in this paper that several classes of abductive explanations, remain hard to compute even for Ordered Binary Decision Diagrams, one of the most tractable subsets of the knowledge compilation map. Included in such classes are shorter abductive explanations or abductive explanations that include the explainee's preferences. To recover the benefits of working with compiled representations, we show that a proper representation of the dual-rail encoding of the classifier can be used to compute efficiently these classes of explanations. Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-07 in cs.AI). Categorie arXiv: Artificial Intelligence (cs.AI) ; Computational Complexity (cs.CC). Pagina del lavoro: https://arxiv.org/abs/2609.04931 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T22:18:11.418Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-09-07?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).