{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,25]],"date-time":"2026-08-25T10:08:00Z","timestamp":1787652480403,"version":"build-2736575974"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T00:00:00Z","timestamp":1672099200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T00:00:00Z","timestamp":1672099200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Artif Intell Rev"],"published-print":{"date-parts":[[2023,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present an approach to improve the accuracy-interpretability trade-off of Machine Learning (ML) Decision Trees (DTs). In particular, we apply Maximum Satisfiability technology to compute Minimum Pure DTs (MPDTs). We improve the runtime of previous approaches and, show that these MPDTs can outperform the accuracy of DTs generated with the ML framework <jats:italic>sklearn<\/jats:italic>.<\/jats:p>","DOI":"10.1007\/s10462-022-10377-0","type":"journal-article","created":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T20:02:31Z","timestamp":1672171351000},"page":"8303-8323","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Interpretable decision trees through MaxSAT"],"prefix":"10.1007","volume":"56","author":[{"given":"Josep","family":"Al\u00f2s","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carlos","family":"Ans\u00f3tegui","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eduard","family":"Torres","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,12,27]]},"reference":[{"key":"10377_CR1","doi-asserted-by":"crossref","unstructured":"Aglin G, Nijssen S, Schaus P (2020) Learning optimal decision trees using caching branch-and-bound search. In: AAAI 2020, IAAI 2020, EAAI 2020, New York, NY, USA, February 7\u201312, 2020. AAAI Press, pp 3146\u20133153, https:\/\/aaai.org\/ojs\/index.php\/AAAI\/article\/view\/5711","DOI":"10.1609\/aaai.v34i04.5711"},{"key":"10377_CR2","doi-asserted-by":"crossref","unstructured":"Ans\u00f3tegui C, Ojeda J, Pacheco A et\u00a0al (2021) Optilog: a framework for sat-based systems. In: SAT 2021, Cham, pp 1\u201310","DOI":"10.1007\/978-3-030-80223-3_1"},{"key":"10377_CR3","first-page":"51","volume":"256","author":"C Ans\u00f3tegui","year":"2013","unstructured":"Ans\u00f3tegui C, Izquierdo I, Many\u00e0 F et al (2013) A max-sat-based approach to constructing optimal covering arrays. Front Artif Intell Appl 256:51\u201359","journal-title":"Front Artif Intell Appl"},{"key":"10377_CR4","doi-asserted-by":"crossref","unstructured":"Avellaneda F (2020) Efficient inference of optimal decision trees. In: AAAI 2020, IAAI 2020, EAAI 2020, New York, NY, USA, February 7\u201312, 2020. AAAI Press, pp 3195\u20133202","DOI":"10.1609\/aaai.v34i04.5717"},{"key":"10377_CR5","unstructured":"Bacchus F, Berg J, J\u00e4rvisalo M, et\u00a0al (2021) Maxsat evaluation 2021: solver and benchmark descriptions"},{"key":"10377_CR6","first-page":"10","volume":"2020","author":"J Berg","year":"2020","unstructured":"Berg J, Demirovic E, Stuckey P (2020) Loandra in the 2020 maxsat evaluation. MaxSAT Evaluation 2020:10","journal-title":"MaxSAT Evaluation"},{"key":"10377_CR7","doi-asserted-by":"publisher","unstructured":"Berre DL, Parrain A (2010) The sat4j library, release 2.2. J Satisf Boolean Model Comput 7(2-3):59\u20136. https:\/\/doi.org\/10.3233\/sat190075","DOI":"10.3233\/sat190075"},{"key":"10377_CR8","doi-asserted-by":"crossref","unstructured":"Bessiere C, Hebrard E, O\u2019Sullivan B (2009) Minimising decision tree size as combinatorial optimisation. In: CP 2009, Lisbon, Portugal, September 20\u201324, 2009, Proceedings, vol 5732. Springer, pp 173\u2013187","DOI":"10.1007\/978-3-642-04244-7_16"},{"key":"10377_CR9","unstructured":"Biere A (2019) CaDiCaL at the SAT Race 2019. In: Proc.\u00a0of SAT Race 2019 \u2013 Solver and Benchmark Descriptions, Department of Computer Science Series of Publications B, vol B-2019-1. University of Helsinki, pp 8\u20139"},{"key":"10377_CR10","unstructured":"Biere A, Heule M, van Maaren H et\u00a0al (eds) (2009) Handbook of satisfiability, frontiers in artificial intelligence and applications, vol 185, IOS Press"},{"key":"10377_CR11","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1145\/1401890.1401919","volume":"2008","author":"L De Raedt","year":"2008","unstructured":"De Raedt L, Guns T, Nijssen S (2008) Constraint programming for itemset mining. KDD 2008:204\u2013212. https:\/\/doi.org\/10.1145\/1401890.1401919","journal-title":"Constraint programming for itemset mining. KDD"},{"key":"10377_CR12","unstructured":"Dua D, Graff C (2017) UCI machine learning repository. http:\/\/archive.ics.uci.edu\/ml"},{"issue":"1\u20134","key":"10377_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.3233\/sat190014","volume":"2","author":"N E\u00e9n","year":"2006","unstructured":"E\u00e9n N, S\u00f6rensson N (2006) Translating pseudo-boolean constraints into SAT. J Satisf Boolean Model Comput 2(1\u20134):1\u201326. https:\/\/doi.org\/10.3233\/sat190014","journal-title":"J Satisf Boolean Model Comput"},{"key":"10377_CR14","unstructured":"European Commission (2021) Proposal for a Regulation of the European Parliament and of the Council laying down harmonised rules on artificial intelligence (Artificial Intelligence Act) and Amending Certain Union Legislative Acts. https:\/\/eur-lex.europa.eu\/legal-content\/EN\/TXT\/?uri=CELEX:52021PC0206"},{"issue":"1","key":"10377_CR15","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1006\/jcss.1997.1504","volume":"55","author":"Y Freund","year":"1997","unstructured":"Freund Y, Schapire RE (1997) A decision-theoretic generalization of on-line learning and an application to boosting. J Comput Syst Sci 55(1):119\u2013139. https:\/\/doi.org\/10.1006\/jcss.1997.1504","journal-title":"J Comput Syst Sci"},{"issue":"9","key":"10377_CR16","doi-asserted-by":"publisher","first-page":"2027","DOI":"10.1093\/bioinformatics\/bti278","volume":"21","author":"S Hautaniemi","year":"2005","unstructured":"Hautaniemi S, Kharait S, Iwabu A et al (2005) Modeling of signal-response cascades using decision tree analysis. Bioinformatics 21(9):2027\u20132035. https:\/\/doi.org\/10.1093\/bioinformatics\/bti278","journal-title":"Bioinformatics"},{"key":"10377_CR17","unstructured":"Hu X, Rudin C, Seltzer MI (2019) Optimal sparse decision trees. In: NeurIPS 2019, December 8\u201314, 2019, Vancouver, BC, Canada, pp 7265\u20137273, https:\/\/proceedings.neurips.cc\/paper\/2019\/hash\/ac52c626afc10d4075708ac4c778ddfc-Abstract.html"},{"key":"10377_CR18","doi-asserted-by":"publisher","unstructured":"Hu H, Siala M, Hebrard E et\u00a0al (2020) Learning optimal decision trees with maxsat and its integration in adaboost. In: IJCAI 2020. ijcai.org, pp 1170\u20131176, https:\/\/doi.org\/10.24963\/ijcai.2020\/163","DOI":"10.24963\/ijcai.2020\/163"},{"key":"10377_CR19","doi-asserted-by":"publisher","unstructured":"Janota M, Morgado A (2020) Sat-based encodings for optimal decision trees with explicit paths. In: SAT 2020, Alghero, Italy, July 3\u201310, 2020, Proceedings, Lecture notes in computer science, vol 12178. Springer, pp 501\u2013518, https:\/\/doi.org\/10.1007\/978-3-030-51825-7_35","DOI":"10.1007\/978-3-030-51825-7_35"},{"key":"10377_CR20","doi-asserted-by":"publisher","first-page":"59","DOI":"10.3233\/SAT190075","volume":"7","author":"D Le Berre","year":"2010","unstructured":"Le Berre D, Parrain A (2010) The sat4j library, release 2.2. J Satisf Boolean Model Comput 7:59\u201364. https:\/\/doi.org\/10.3233\/SAT190075","journal-title":"J Satisf Boolean Model Comput"},{"key":"10377_CR21","first-page":"19","volume":"2021","author":"Z Lei","year":"2021","unstructured":"Lei Z, Cai S, Geng F et al (2021) Satlike-c: Solver description. MaxSAT Evaluation 2021:19","journal-title":"MaxSAT Evaluation"},{"key":"10377_CR22","unstructured":"Moshkovitz M, Yang YY, Chaudhuri K (2021) Connecting interpretability and robustness in decision trees through separation. arXiv:2102.07048"},{"key":"10377_CR23","first-page":"21","volume":"2021","author":"A Nadel","year":"2021","unstructured":"Nadel A (2021) Tt-open-wbo-inc-21: an anytime maxsat solver entering mse\u201921. MaxSAT Evaluation 2021:21","journal-title":"MaxSAT Evaluation"},{"key":"#cr-split#-10377_CR24.1","doi-asserted-by":"crossref","unstructured":"Narodytska N, Ignatiev A, Pereira F et\u00a0al (2018) Learning optimal decision trees with SAT. In: Lang J","DOI":"10.24963\/ijcai.2018\/189"},{"key":"#cr-split#-10377_CR24.2","unstructured":"(ed) IJCAI 2018, July 13-19, 2018, Stockholm, Sweden. ijcai.org, pp 1362-1368"},{"issue":"1","key":"10377_CR25","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1186\/s13040-017-0154-4","volume":"10","author":"RS Olson","year":"2017","unstructured":"Olson RS, La Cava W, Orzechowski P et al (2017) Pmlb: a large benchmark suite for machine learning evaluation and comparison. BioData Min 10(1):36. https:\/\/doi.org\/10.1186\/s13040-017-0154-4","journal-title":"BioData Min"},{"key":"10377_CR26","doi-asserted-by":"crossref","unstructured":"Romano JD, Le TT, La\u00a0Cava W et\u00a0al (2021) Pmlb v1.0: an open source dataset collection for benchmarking machine learning methods. arXiv preprint arXiv:2012.00058v2","DOI":"10.1093\/bioinformatics\/btab727"},{"key":"10377_CR27","doi-asserted-by":"crossref","unstructured":"Schidler A, Szeider S (2021) Sat-based decision tree learning for large data sets. In: AAAI","DOI":"10.1609\/aaai.v35i5.16509"},{"key":"10377_CR28","unstructured":"Scikit-learn developers (2020) Decision Trees (Scikit documentation). https:\/\/scikit-learn.org\/stable\/modules\/tree.html#tree-algorithms-id3-c4-5-c5-0-and-cart"},{"key":"10377_CR29","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1023\/A:1022699900025","volume":"4","author":"PE Utgoff","year":"1989","unstructured":"Utgoff PE (1989) Incremental induction of decision trees. Mach Learn 4:161\u2013186. https:\/\/doi.org\/10.1023\/A:1022699900025","journal-title":"Mach Learn"},{"key":"10377_CR30","unstructured":"Verhaeghe H, Nijssen S, Pesant G, et\u00a0al (2019) Learning optimal decision trees using constraint programming. In: BNAIC 2019, Benelearn 2019, Brussels, Belgium, November 6\u20138, 2019, CEUR workshop proceedings, vol 2491. CEUR-WS.org. http:\/\/ceur-ws.org\/Vol-2491\/abstract109.pdf"},{"key":"10377_CR31","doi-asserted-by":"publisher","unstructured":"Verwer S, Zhang Y (2019) Learning optimal classification trees using a binary linear program formulation. In: AAAI 2019, IAAI 2019, EAAI 2019, Honolulu, Hawaii, USA, January 27\u2013February 1, 2019. AAAI Press, pp 1625\u20131632, https:\/\/doi.org\/10.1609\/aaai.v33i01.33011624","DOI":"10.1609\/aaai.v33i01.33011624"}],"container-title":["Artificial Intelligence Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10462-022-10377-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10462-022-10377-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10462-022-10377-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,28]],"date-time":"2023-06-28T02:15:04Z","timestamp":1687918504000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10462-022-10377-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,27]]},"references-count":32,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2023,8]]}},"alternative-id":["10377"],"URL":"https:\/\/doi.org\/10.1007\/s10462-022-10377-0","relation":{},"ISSN":["0269-2821","1573-7462"],"issn-type":[{"value":"0269-2821","type":"print"},{"value":"1573-7462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,27]]},"assertion":[{"value":"12 December 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 December 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}