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.