{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,6]],"date-time":"2026-08-06T11:38:17Z","timestamp":1786016297545,"version":"3.56.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,2,6]],"date-time":"2026-02-06T00:00:00Z","timestamp":1770336000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T00:00:00Z","timestamp":1775520000000},"content-version":"vor","delay-in-days":60,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J. King Saud Univ. Comput. Inf. Sci."],"published-print":{"date-parts":[[2026,4]]},"abstract":"Abstract<\/jats:title>\n \n Learning minimal interpretable models (e.g., decision trees, decision sets, and binary decision diagrams) is computationally challenging, yet increasingly important in high-stakes settings. We use decision trees as a canonical case study, but the proposed structural parameter is solver-agnostic. Recent parameterized-complexity results show fixed-parameter tractability when parameterized by model size\n s<\/jats:italic>\n and a data-dependent conflict parameter\n \n \n $$\\delta $$<\/jats:tex-math>\n \n \u03b4<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , the maximum Hamming disagreement between oppositely labeled examples. We show that\n \n \n $$\\delta $$<\/jats:tex-math>\n \n \u03b4<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is highly noise-sensitive: under small relevant support and independent irrelevant features,\n \n \n $$\\delta $$<\/jats:tex-math>\n \n \u03b4<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n typically scales with ambient dimension, making\n \n \n $$\\delta $$<\/jats:tex-math>\n \n \u03b4<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -based branching uninformative. We introduce a distribution-aware alternative, the\n effective conflict width<\/jats:italic>\n \n \n $$\\kappa _\\tau $$<\/jats:tex-math>\n \n \n \u03ba<\/mml:mi>\n \u03c4<\/mml:mi>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , obtained by restricting conflicts to features whose relevance exceeds a threshold. We instantiate this idea as structure-guided branching (SGB), which branches on relevance-filtered conflict features and safely falls back to full\n \n \n $$\\delta $$<\/jats:tex-math>\n \n \u03b4<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -branching. Using conflict-driven branching simulations to isolate search-tree effects, we find that\n \n \n $$\\kappa _\\tau $$<\/jats:tex-math>\n \n \n \u03ba<\/mml:mi>\n \u03c4<\/mml:mi>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n can remain stable as dimension grows and yields substantial reductions in explored search nodes on synthetic data and multiple real datasets. These results suggest structural parameters can improve the noise robustness of exact interpretable learning and can serve as solver-agnostic pruning signals.\n <\/jats:p>","DOI":"10.1007\/s44443-026-00535-7","type":"journal-article","created":{"date-parts":[[2026,2,6]],"date-time":"2026-02-06T11:58:25Z","timestamp":1770379105000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Removing $$\\delta $$-dependence in minimal interpretable model learning: distribution conditions and structural parameters"],"prefix":"10.1007","volume":"38","author":[{"given":"Zhigao","family":"Huang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shiyan","family":"Zheng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Quanfa","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,2,6]]},"reference":[{"issue":"4","key":"535_CR1","doi-asserted-by":"publisher","first-page":"2223","DOI":"10.1287\/opre.2021.0034","volume":"73","author":"S Aghaei","year":"2025","unstructured":"Aghaei S, G\u00f3mez A, Vayanos P (2025) Strong optimal classification trees. Oper Res 73(4):2223\u20132241. https:\/\/doi.org\/10.1287\/opre.2021.0034","journal-title":"Oper Res"},{"key":"535_CR2","unstructured":"Angelino E, Larus-Stone N, Alabi D, Seltzer M, Rudin C (2018) Learning certifiably optimal rule lists for categorical data. J Mach Learn Res 18(234):1\u201378. https:\/\/jmlr.org\/papers\/v18\/17-716.html"},{"key":"535_CR3","doi-asserted-by":"publisher","unstructured":"Avellaneda F (2025) Learning optimal oblique decision trees with (max)sat. In: Kwok J (ed) Proceedings of the thirty-fourth international joint conference on artificial intelligence, IJCAI-25. International Joint Conferences on Artificial Intelligence Organization, pp 2558\u20132565, main Track. https:\/\/doi.org\/10.24963\/ijcai.2025\/285","DOI":"10.24963\/ijcai.2025\/285"},{"key":"535_CR4","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1016\/j.inffus.2019.12.012","volume":"58","author":"A Barredo Arrieta","year":"2020","unstructured":"Barredo Arrieta A, D\u00edaz-Rodr\u00edguez N, Del Ser J, Bennetot A, Tabik S, Barbado A, Garcia S, Gil-Lopez S, Molina D, Benjamins R, Chatila R, Herrera F (2020) Explainable artificial intelligence (xai): concepts, taxonomies, opportunities and challenges toward responsible ai. Inf Fusion 58:82\u2013115. https:\/\/doi.org\/10.1016\/j.inffus.2019.12.012","journal-title":"Inf Fusion"},{"issue":"7","key":"535_CR5","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1007\/s10994-017-5633-9","volume":"106","author":"D Bertsimas","year":"2017","unstructured":"Bertsimas D, Dunn J (2017) Optimal classification trees. Mach Learn 106(7):1039\u20131082. https:\/\/doi.org\/10.1007\/s10994-017-5633-9","journal-title":"Mach Learn"},{"issue":"1","key":"535_CR6","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1023\/A:1010933404324","volume":"45","author":"L Breiman","year":"2001","unstructured":"Breiman L (2001) Random forests. Mach Learn 45(1):5\u201332. https:\/\/doi.org\/10.1023\/A:1010933404324","journal-title":"Mach Learn"},{"issue":"8","key":"535_CR7","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1109\/TC.1986.1676819","volume":"35","author":"RE Bryant","year":"1986","unstructured":"Bryant RE (1986) Graph-based algorithms for boolean function manipulation. IEEE Trans Comput 35(8):677\u2013691. https:\/\/doi.org\/10.1109\/TC.1986.1676819","journal-title":"IEEE Trans Comput"},{"issue":"8","key":"535_CR8","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/3546036","volume":"65","author":"V Chen","year":"2022","unstructured":"Chen V, Li J, Kim JS, Plumb G, Talwalkar A (2022) Interpretable machine learning: moving from mythos to diagnostics. Commun ACM 65(8):43\u201350. https:\/\/doi.org\/10.1145\/3546036","journal-title":"Commun ACM"},{"key":"535_CR9","doi-asserted-by":"publisher","unstructured":"Cygan M, Fomin FV, Kowalik \u0141, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S (2015) Parameterized algorithms. Springer International Publishing. https:\/\/doi.org\/10.1007\/978-3-319-21275-3","DOI":"10.1007\/978-3-319-21275-3"},{"key":"535_CR10","doi-asserted-by":"publisher","unstructured":"Doshi-Velez F, Kim B (2017) Towards a rigorous science of interpretable machine learning. arXiv:1702.08608, https:\/\/doi.org\/10.48550\/arXiv.1702.08608","DOI":"10.48550\/arXiv.1702.08608"},{"issue":"5","key":"535_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3236009","volume":"51","author":"R Guidotti","year":"2018","unstructured":"Guidotti R, Monreale A, Ruggieri S, Turini F, Giannotti F, Pedreschi D (2018) A survey of methods for explaining black box models. ACM Comput Surv 51(5):1\u201342. https:\/\/doi.org\/10.1145\/3236009","journal-title":"ACM Comput Surv"},{"issue":"1","key":"535_CR12","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s10898-021-01009-y","volume":"81","author":"O G\u00fcnl\u00fck","year":"2021","unstructured":"G\u00fcnl\u00fck O, Kalagnanam J, Li M, Menickelly M, Scheinberg K (2021) Optimal decision trees for categorical data via integer programming. J Global Optim 81(1):233\u2013260. https:\/\/doi.org\/10.1007\/s10898-021-01009-y","journal-title":"J Global Optim"},{"key":"535_CR13","unstructured":"Hu X, Rudin C, Seltzer M (2019) Optimal sparse decision trees. In: Advances in neural information processing systems, vol\u00a032, pp 7265\u20137273"},{"issue":"1","key":"535_CR14","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0020-0190(76)90095-8","volume":"5","author":"L Hyafil","year":"1976","unstructured":"Hyafil L, Rivest RL (1976) Constructing optimal binary decision trees is np-complete. Inf Process Lett 5(1):15\u201317. https:\/\/doi.org\/10.1016\/0020-0190(76)90095-8","journal-title":"Inf Process Lett"},{"key":"535_CR15","unstructured":"Kelly M, Longjohn R, Nottingham K (2026) The uci machine learning repository. https:\/\/archive.ics.uci.edu. Accessed 22 Jan 2026; for individual datasets, use the repository\u2019s dataset-specific \u2019Cite\u2019 button. https:\/\/archive.ics.uci.edu"},{"key":"535_CR16","doi-asserted-by":"publisher","unstructured":"Lakkaraju H, Bach SH, Leskovec J (2016) Interpretable decision sets: a joint framework for description and prediction. In: Proceedings\u00a0of the 22nd ACM SIGKDD international conference\u00a0on knowledge discovery and data mining, KDD \u201916. ACM, pp 1675\u20131684. https:\/\/doi.org\/10.1145\/2939672.2939874","DOI":"10.1145\/2939672.2939874"},{"key":"535_CR17","unstructured":"Molnar C (2022) Interpretable machine learning, 2nd edn. Christoph Molnar. https:\/\/christophm.github.io\/interpretable-ml-book\/"},{"key":"535_CR18","doi-asserted-by":"publisher","unstructured":"Narodytska N, Ignatiev A, Pereira F, Marques-Silva J (2018) Learning optimal decision trees with sat. In: Proceedings of the twenty-seventh international joint conference on artificial intelligence, IJCAI-18. International Joint Conferences on Artificial Intelligence Organization, pp 1362\u20131368. https:\/\/doi.org\/10.24963\/ijcai.2018\/189","DOI":"10.24963\/ijcai.2018\/189"},{"key":"535_CR19","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2025.104441","volume":"350","author":"S Ordyniak","year":"2026","unstructured":"Ordyniak S, Paesani G, Rychlicki M, Szeider S (2026) A general theoretical framework for learning smallest interpretable models. Artif Intell 350:104441. https:\/\/doi.org\/10.1016\/j.artint.2025.104441","journal-title":"Artif Intell"},{"key":"535_CR20","doi-asserted-by":"publisher","unstructured":"Ordyniak S, Paesani G, Rychlicki M, Szeider S (2024) A general theoretical framework for learning smallest interpretable models. In: Proceedings of the AAAI conference on artificial intelligence, vol\u00a038. AAAI Press, pp 10662\u201310669. https:\/\/doi.org\/10.1609\/aaai.v38i9.28937","DOI":"10.1609\/aaai.v38i9.28937"},{"issue":"8","key":"535_CR21","doi-asserted-by":"publisher","first-page":"1226","DOI":"10.1109\/TPAMI.2005.159","volume":"27","author":"H Peng","year":"2005","unstructured":"Peng H, Long F, Ding C (2005) Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy. IEEE Trans Pattern Anal Mach Intell 27(8):1226\u20131238. https:\/\/doi.org\/10.1109\/TPAMI.2005.159","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"issue":"5","key":"535_CR22","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1038\/s42256-019-0048-x","volume":"1","author":"C Rudin","year":"2019","unstructured":"Rudin C (2019) Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nat Mach Intell 1(5):206\u2013215. https:\/\/doi.org\/10.1038\/s42256-019-0048-x","journal-title":"Nat Mach Intell"},{"issue":"3\u20134","key":"535_CR23","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/s10601-020-09312-3","volume":"25","author":"H Verhaeghe","year":"2020","unstructured":"Verhaeghe H, Nijssen S, Pesant G, Quimper C-G, Schaus P (2020) Learning optimal decision trees using constraint programming. Constraints 25(3\u20134):226\u2013250. https:\/\/doi.org\/10.1007\/s10601-020-09312-3","journal-title":"Constraints"},{"key":"535_CR24","doi-asserted-by":"publisher","unstructured":"Verwer S, Zhang Y (2017) Learning decision trees with flexible constraints and objectives using integer optimization. In: Salvagnin D, Lombardi M (eds) Integration of AI and OR techniques in constraint programming. Lecture Notes in Computer Science, vol 10335. Springer, Cham, pp 94\u2013103. https:\/\/doi.org\/10.1007\/978-3-319-59776-8_8","DOI":"10.1007\/978-3-319-59776-8_8"},{"key":"535_CR25","doi-asserted-by":"publisher","unstructured":"Verwer S, Zhang Y (2019) Learning optimal classification trees using a binary linear program formulation. In: Proceedings of the AAAI conference on artificial intelligence, vol\u00a033, pp 1625\u20131632. https:\/\/doi.org\/10.1609\/aaai.v33i01.33011624","DOI":"10.1609\/aaai.v33i01.33011624"},{"key":"535_CR26","doi-asserted-by":"publisher","first-page":"1251","DOI":"10.1613\/jair.1.12719","volume":"72","author":"J Yu","year":"2021","unstructured":"Yu J, Ignatiev A, Stuckey PJ, Le Bodic P (2021) Learning optimal decision sets and lists with sat. J Artif Intell Res 72:1251\u20131279. https:\/\/doi.org\/10.1613\/jair.1.12719","journal-title":"J Artif Intell Res"}],"container-title":["Journal of King Saud University Computer and Information Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s44443-026-00535-7","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s44443-026-00535-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s44443-026-00535-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T17:27:31Z","timestamp":1777915651000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s44443-026-00535-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,6]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["535"],"URL":"https:\/\/doi.org\/10.1007\/s44443-026-00535-7","relation":{},"ISSN":["1319-1578","2213-1248"],"issn-type":[{"value":"1319-1578","type":"print"},{"value":"2213-1248","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,6]]},"assertion":[{"value":"18 December 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 January 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 February 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"120"}}