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
intrepretability (i.e., lighter size) compared to the state-of-the-art
approaches.

本文提出了基于 SAT 的方法学习最优二元决策图（BDD），以更好地实现可解释的机器学习模型，并给出了一种整合兼容子树的方法，该方法与现有方法相比在预测质量和可解释性方面具有明显的优势。