Optimal Decision Diagrams for Classification

Decision diagrams for classification have some notable advantages over decision trees, as their internal connections can be determined at training time and their width is not bound to grow exponentially with their depth. Accordingly, decision diagrams are usually less prone to data fragmentation in internal nodes. However, the inherent complexity of training these classifiers acted as a long-standing barrier to their widespread adoption. In this context, we study the training of optimal decision diagrams (ODDs) from a mathematical programming perspective. We introduce a novel mixed-integer linear programming model for training and demonstrate its applicability for many datasets of practical importance. Further, we show how this model can be easily extended for fairness, parsimony, and stability notions. We present numerical analyses showing that our model allows training ODDs in short computational times, and that ODDs achieve better accuracy than optimal decision trees, while allowing for improved stability without significant accuracy losses.

Authors

• Alexandre M. Florio CIRRELT & SCALE-AI Chair in Data-Driven Supply Chains Department of Mathematical and Industrial Engineering, Polytechnique Montreal, Canada
• Pedro Martins Department of Computer Science, Pontifical Catholic University of Rio de Janeiro, Brazil
• Maximilian Schiffer School of Management & Munich Data Science Institute, Technical University of Munich, Germany
• Thiago Serra Freeman College of Management, Bucknell University, USA
• Thibaut Vidal Department of Mathematics and Industrial Engineering, Polytechnique Montréal CIRRELT & SCALE-AI Chair in Data-Driven Supply Chains

Keywords

• ML: Classification and Regression
• SO: Applications
• SO: Mixed Discrete/Continuous Search