A Polyhedral Study of Multivariate Decision Trees

References

• Aghaei S, Azizi MJ, Vayanos P (2019) Learning optimal and fair decision trees for non-discriminative decision-making. Proc. AAAI Conf. Artificial Intelligence 33(1):1418–1426.Google Scholar
• Aghaei S, Gómez A, Vayanos P (2024) Strong optimal classification trees. Oper. Res., ePub ahead of print July 31, https://doi.org/10.1287/opre.2021.0034.Google Scholar
• Aghaei S, Gómez A, Jo N, Vayanos P (2021) Learning optimal prescriptive trees from observational data. Preprint, submitted August 31, https://arxiv.org/abs/2108.13628.Google Scholar
• Aglin G, Nijssen S, Schaus P (2020a) Learning optimal decision trees using caching branch-and-bound search. Proc. Conf. AAAI Artificial Intelligence, vol. 34(4) (AAAI Press, Palo Alto, CA), 3146–3153.Google Scholar
• Aglin G, Nijssen S, Schaus P (2020b) PyDL8.5: A library for learning optimal decision trees. Bessiere C, ed. Proc. 29th Internat. Joint Conf. Artificial Intelligence (Yokohama, Japan), 5222–5224.Google Scholar
• Avellaneda F (2020) Efficient inference of optimal decision trees. Proc. Conf. AAAI Artificial Intelligence, vol. 34(4) (AAAI Press, Palo Alto, CA), 3195–3202.Google Scholar
• Bertsimas D, Dunn J (2017) Optimal classification trees. Machine Learn. 106:1039–1082.Google Scholar
• Boutilier J, Michini C, Zhou Z (2022) Shattering inequalities for learning optimal decision trees. Schaus P, ed. Proc. 19th Internat. Conf. Integration Constraint Programming Artificial Intelligence Oper. Res. (Springer, Cham, Switzerland).Google Scholar
• Boutilier J, Michini C, Zhou Z (2023) Optimal multivariate decision trees. Constraints 28(4):549–577.Google Scholar
• Breiman L (2001) Random forests. Machine Learn. 45(1):5–32.Google Scholar
• Breiman L, Friedman J, Stone CJ, Olshen R (1984) Classification and Regression Trees (Chapman & Hall/CRC, New York).Google Scholar
• Dash S, Günlük O, Wei D (2020) Boolean decision rules via column generation. Proc. 32nd Internat. Conf. Neural Inform. Processing Systems (NIPS’18) (Curran Associates Inc., Red Hook, NY), 4660–4670.Google Scholar
• Demirović E, Lukina A, Hebrard E, Chan J, Bailey J, Leckie C, Ramamohanarao K, Stuckey PJ (2022) Murtree: Optimal classification trees via dynamic programming and search. J. Machine Learn. Res. 23(1):1169.Google Scholar
• Dua D, Graff C (2017) UCI machine learning repository. Accessed October 28, 2024, http://archive.ics.uci.edu/ml.Google Scholar
• Dwork C, Hardt M, Pitassi T, Reingold O, Zemel R (2012) Fairness through awareness. Proc. 3rd Innovations Theoret. Comput. Sci. Conf. (Association for Computing Machinery, New York), 214–226.Google Scholar
• Gleeson J, Ryan J (1990) Identifying minimally infeasible subsystems of inequalities. INFORMS J. Comput. 2:61–63.Abstract, Google Scholar
• Goodman B, Flaxman S (2017) European union regulations on algorithmic decision-making and a “right to explanation”. AI Magazine 38(3):50–57.Google Scholar
• Günlük O, Kalagnanam J, Li M, Menickelly M, Scheinberg K (2021) Optimal decision trees for categorical data via integer programming. J. Global Optim. 81:233–260.Google Scholar
• Gurobi Optimization LLC (2023) Gurobi optimizer reference manual. Accessed October 28, 2024, https://www.gurobi.com.Google Scholar
• Hu H, Siala M, Hebrard E, Huguet MJ (2020) Learning optimal decision trees with MaxSAT and its integration in adaboost. Bessiere C, ed. Proc. 29th Internat. Joint Conf. Artificial Intelligence (International Joint Conferences on Artificial Intelligence), 1170–1176.Google Scholar
• Janota M, Morgado A (2020) Sat-based encodings for optimal decision trees with explicit paths. Pulina L, Seidl M, eds. Theory and Applications of Satisfiability Testing (Springer International Publishing, Cham, Switzerland), 501–518.Google Scholar
• Jo N, Aghaei S, Benson J, Gómez A, Vayanos P (2023) Learning optimal fair classification trees: Trade-offs between interpretability, fairness, and accuracy. Proc. 2023 AAAI/ACM Conf. AI Ethics Society (AIES ’23) (Association for Computing Machinery, New York), 181–192.Google Scholar
• Justin N, Aghaei S, Gómez A, Vayanos P (2022) Optimal robust classification trees. Proc. AAAI-22 Workshop Adversarial Machine Learn. Beyond (AAAI Press, Palo Alto, CA).Google Scholar
• Lawless C, Günlük O (2021) Fair decision rules for binary classification. Preprint, submitted July 3, https://arxiv.org/abs/2107.01325.Google Scholar
• Liaw A, Wiener M (2002) Classification and regression by randomforest. R News 2(3):18–22.Google Scholar
• Lin JJ, Zhong C, Hu D, Rudin C, Seltzer MI (2020) Generalized and scalable optimal sparse decision trees (ICML). Proc. 37th Internat. Conf. Machine Learn., vol. 119 (PMLR, New York), 6150–6160.Google Scholar
• Murdoch WJ, Singh C, Kumbier K, Abbasi-Asl R, Yu B (2019) Definitions, methods, and applications in interpretable machine learning. Proc. Natl. Acad. Sci. USA 116(44):22071–22080.Google Scholar
• Narodytska N, Ignatiev A, Pereira F, Marques-Silva J (2018) Learning optimal decision trees with SAT. Proc. 27th Internat. Joint Conf. Artificial Intelligence, 1362–1368.Google Scholar
• Nijssen S, Fromont E (2007) Mining optimal decision trees from itemset lattices. Proc. 13th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (Association for Computing Machinery, New York), 530–539.Google Scholar
• Schidler A, Szeider S (2021) SAT-based decision tree learning for large data sets. Proc. Conf. AAAI Artificial Intelligence 35(5):3904–3912.Google Scholar
• Vapnik V (1998) Statistical Learning Theory (Wiley, New York).Google Scholar
• Verhaeghe H, Nijssen S, Pesant G, Quimper CG, Schaus P (2020a) Learning optimal decision trees using constraint programming. Constraints 25:1–25.Google Scholar
• Verhaeghe H, Nijssen S, Pesant G, Quimper CG, Schaus P (2020b) Learning optimal decision trees using constraint programming (extended abstract). Bessiere C, ed. Proc. 29th Internat. Joint Conf. Artificial Intelligence (International Joint Conferences on Artificial Intelligence), 4765–4769.Google Scholar
• Verwer S, Zhang Y (2017) Learning decision trees with flexible constraints and objectives using integer optimization. Salvagnin D, Lombardi M, eds. Integration of AI and OR Techniques in Constraint Programming (Springer International Publishing, Cham, Switzerland), 94–103.Google Scholar
• Verwer S, Zhang Y (2019) Learning optimal classification trees using a binary linear program formulation. Proc. 33rd AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 1625–1632.Google Scholar
• Zhu H, Murali P, Phan DT, Nguyen LM, Kalagnanam J (2020) A scalable MIP-based method for learning optimal multivariate decision trees. Larochelle H, Ranzato M, Hadsell R, Balcan M, Lin H, eds. Proc. Annual Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY).Google Scholar