Skip to Main content Skip to Navigation
Conference papers

Optimizing Binary Decision Diagrams with MaxSAT for Classification

Hao Hu 1 Marie-José Huguet 1 Mohamed Siala 1 
1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
LAAS - Laboratoire d'analyse et d'architecture des systèmes
Abstract : The growing interest in explainable artificial intelligence (XAI) for critical decision making motivates the need for interpretable machine learning (ML) models. In fact, due to their structure (especially with small sizes), these models are inherently understandable by humans. Recently, several exact methods for computing such models are proposed to overcome weaknesses of traditional heuristic methods by providing more compact models or better prediction quality. Despite their compressed representation of Boolean functions, Binary decision diagrams (BDDs) did not gain enough interest as other interpretable ML models. In this paper, we first propose SAT-based models for learning optimal BDDs (in terms of the number of features) that classify all input examples. Then, we lift the encoding to a MaxSAT model to learn optimal BDDs in limited depths, that maximize the number of examples correctly classified. Finally, we tackle the fragmentation problem by introducing a method to merge compatible subtrees for the BDDs found via the MaxSAT model. Our empirical study shows clear benefits of the proposed approach in terms of prediction quality and interpretability (i.e., lighter size) compared to the state-of-the-art approaches.
Document type :
Conference papers
Complete list of metadata
Contributor : Marie-Jose Huguet Connect in order to contact the contributor
Submitted on : Friday, May 13, 2022 - 2:24:07 PM
Last modification on : Monday, July 4, 2022 - 8:41:41 AM


2021_12_AAAI_CRC-HAL (1).pdf
Files produced by the author(s)


  • HAL Id : hal-03667549, version 1


Hao Hu, Marie-José Huguet, Mohamed Siala. Optimizing Binary Decision Diagrams with MaxSAT for Classification. 36th AAAI Conference on Artificial Intelligence, Feb 2022, Vancouver, Canada. ⟨hal-03667549⟩



Record views


Files downloads