Necessary and Sufficient Conditions for Optimal Decision Trees using Dynamic Programming

J.G.M. van der Linden*, M.M. de Weerdt, E. Demirović

*Corresponding author for this work

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

14 Downloads (Pure)

Abstract

Global optimization of decision trees has shown to be promising in terms of accuracy, size, and consequently human comprehensibility. However, many of the methods used rely on general-purpose solvers for which scalability remains an issue. Dynamic programming methods have been shown to scale much better because they exploit the tree structure by solving subtrees as independent subproblems. However, this only works when an objective can be optimized separately for subtrees. We explore this relationship in detail and show necessary and sufficient conditions for such separability and generalize previous dynamic programming approaches into a framework that can optimize any combination of separable objectives and constraints. Experiments on five application domains show the general applicability of this framework, while outperforming the scalability of general-purpose solvers by a large margin.
Original languageEnglish
Title of host publicationAdvances in Neural Information Processing Systems 36 (NeurIPS 2023)
Subtitle of host publication37th Conference on Neural Information Processing Systems (NeurIPS 2023)
EditorsA. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, S. Levine
PublisherCurran Associates, Inc.
Pages9173-9212
Number of pages40
Volume36
Publication statusPublished - 2023
Event37th Annual Conference on Neural Information Processing Systems - New Orleans, United States
Duration: 10 Dec 202316 Dec 2023
Conference number: 37

Conference

Conference37th Annual Conference on Neural Information Processing Systems
Abbreviated titleNeurIPS 2023
Country/TerritoryUnited States
CityNew Orleans
Period10/12/2316/12/23

Keywords

  • optimal decision trees
  • dynamic programming
  • necessary and sufficient conditions
  • group fairness
  • policy generation
  • cost-sensitive classification
  • f1-score

Fingerprint

Dive into the research topics of 'Necessary and Sufficient Conditions for Optimal Decision Trees using Dynamic Programming'. Together they form a unique fingerprint.

Cite this