Optimal decision diagrams for classification. Florio, A., Martins, P., Schiffer, M., Serra, T., & Vidal, T. In To appear in AAAI 2023, 2023. arXiv:2205.14500.
Paper abstract bibtex 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.
@inproceedings{Florio2023a,
abstract = {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.},
archivePrefix = {arXiv},
arxivId = {2205.14500},
author = {Florio, A.M. and Martins, P. and Schiffer, M. and Serra, T. and Vidal, T.},
booktitle = {To appear in AAAI 2023},
eprint = {2205.14500},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Florio et al/Florio et al. - 2023 - Optimal decision diagrams for classification.pdf:pdf},
organization = {arXiv:2205.14500},
title = {{Optimal decision diagrams for classification}},
url = {https://arxiv.org/pdf/2205.14500.pdf},
year = {2023}
}
Downloads: 0
{"_id":"5Krbqk9E6st7bLrxy","bibbaseid":"florio-martins-schiffer-serra-vidal-optimaldecisiondiagramsforclassification-2023","author_short":["Florio, A.","Martins, P.","Schiffer, M.","Serra, T.","Vidal, T."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","abstract":"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.","archiveprefix":"arXiv","arxivid":"2205.14500","author":[{"propositions":[],"lastnames":["Florio"],"firstnames":["A.M."],"suffixes":[]},{"propositions":[],"lastnames":["Martins"],"firstnames":["P."],"suffixes":[]},{"propositions":[],"lastnames":["Schiffer"],"firstnames":["M."],"suffixes":[]},{"propositions":[],"lastnames":["Serra"],"firstnames":["T."],"suffixes":[]},{"propositions":[],"lastnames":["Vidal"],"firstnames":["T."],"suffixes":[]}],"booktitle":"To appear in AAAI 2023","eprint":"2205.14500","file":":C$\\$:/Users/Thibaut/Documents/Mendeley-Articles/Florio et al/Florio et al. - 2023 - Optimal decision diagrams for classification.pdf:pdf","organization":"arXiv:2205.14500","title":"Optimal decision diagrams for classification","url":"https://arxiv.org/pdf/2205.14500.pdf","year":"2023","bibtex":"@inproceedings{Florio2023a,\nabstract = {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.},\narchivePrefix = {arXiv},\narxivId = {2205.14500},\nauthor = {Florio, A.M. and Martins, P. and Schiffer, M. and Serra, T. and Vidal, T.},\nbooktitle = {To appear in AAAI 2023},\neprint = {2205.14500},\nfile = {:C$\\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Florio et al/Florio et al. - 2023 - Optimal decision diagrams for classification.pdf:pdf},\norganization = {arXiv:2205.14500},\ntitle = {{Optimal decision diagrams for classification}},\nurl = {https://arxiv.org/pdf/2205.14500.pdf},\nyear = {2023}\n}\n","author_short":["Florio, A.","Martins, P.","Schiffer, M.","Serra, T.","Vidal, T."],"key":"Florio2023a","id":"Florio2023a","bibbaseid":"florio-martins-schiffer-serra-vidal-optimaldecisiondiagramsforclassification-2023","role":"author","urls":{"Paper":"https://arxiv.org/pdf/2205.14500.pdf"},"metadata":{"authorlinks":{}},"html":""},"bibtype":"inproceedings","biburl":"https://w1.cirrelt.ca/~vidalt/resources/My Collection.bib","dataSources":["yinfondEAJRbDM9sJ","sempRA6PhmAdGk3yG"],"keywords":[],"search_terms":["optimal","decision","diagrams","classification","florio","martins","schiffer","serra","vidal"],"title":"Optimal decision diagrams for classification","year":2023}