Necessary and Sufficient Conditions for Optimal Decision Trees using Dynamic Programming

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

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

Algorithmics

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

12 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 language	English
Title of host publication	Advances in Neural Information Processing Systems 36 (NeurIPS 2023)
Subtitle of host publication	37th Conference on Neural Information Processing Systems (NeurIPS 2023)
Editors	A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, S. Levine
Publisher	Curran Associates, Inc.
Pages	9173-9212
Number of pages	40
Volume	36
Publication status	Published - 2023
Event	37th Annual Conference on Neural Information Processing Systems - New Orleans, United States Duration: 10 Dec 2023 → 16 Dec 2023 Conference number: 37

Conference

Conference	37th Annual Conference on Neural Information Processing Systems
Abbreviated title	NeurIPS 2023
Country/Territory	United States
City	New Orleans
Period	10/12/23 → 16/12/23

Keywords

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

Access to Document

STreeD paperFinal published version, 656 KB

https://proceedings.neurips.cc/paper_files/paper/2023/file/1d5fce9627e15c84db572a66e029b1fc-Paper-Conference.pdf

Cite this

van der Linden, J. G. M., de Weerdt, M. M., & Demirović, E. (2023). Necessary and Sufficient Conditions for Optimal Decision Trees using Dynamic Programming. In A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, & S. Levine (Eds.), Advances in Neural Information Processing Systems 36 (NeurIPS 2023): 37th Conference on Neural Information Processing Systems (NeurIPS 2023) (Vol. 36, pp. 9173-9212). Curran Associates, Inc.. https://proceedings.neurips.cc/paper_files/paper/2023/file/1d5fce9627e15c84db572a66e029b1fc-Paper-Conference.pdf

van der Linden, J.G.M. ; de Weerdt, M.M. ; Demirović, E. / Necessary and Sufficient Conditions for Optimal Decision Trees using Dynamic Programming. Advances in Neural Information Processing Systems 36 (NeurIPS 2023): 37th Conference on Neural Information Processing Systems (NeurIPS 2023). editor / A. Oh ; T. Neumann ; A. Globerson ; K. Saenko ; M. Hardt ; S. Levine. Vol. 36 Curran Associates, Inc., 2023. pp. 9173-9212

@inproceedings{08a9312a9ae74693b59cd7bad7c410cc,

title = "Necessary and Sufficient Conditions for Optimal Decision Trees using Dynamic Programming",

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.",

keywords = "optimal decision trees, dynamic programming, necessary and sufficient conditions, group fairness, policy generation, cost-sensitive classification, f1-score",

author = "{van der Linden}, J.G.M. and {de Weerdt}, M.M. and E. Demirovi{\'c}",

year = "2023",

language = "English",

volume = "36",

pages = "9173--9212",

editor = "A. Oh and T. Neumann and A. Globerson and K. Saenko and M. Hardt and S. Levine",

booktitle = "Advances in Neural Information Processing Systems 36 (NeurIPS 2023)",

publisher = "Curran Associates, Inc.",

note = "37th Annual Conference on Neural Information Processing Systems, NeurIPS 2023 ; Conference date: 10-12-2023 Through 16-12-2023",

}

van der Linden, JGM , de Weerdt, MM & Demirović, E 2023, Necessary and Sufficient Conditions for Optimal Decision Trees using Dynamic Programming. in A Oh, T Neumann, A Globerson, K Saenko, M Hardt & S Levine (eds), Advances in Neural Information Processing Systems 36 (NeurIPS 2023): 37th Conference on Neural Information Processing Systems (NeurIPS 2023). vol. 36, Curran Associates, Inc., pp. 9173-9212, 37th Annual Conference on Neural Information Processing Systems, New Orleans, United States, 10/12/23. <https://proceedings.neurips.cc/paper_files/paper/2023/file/1d5fce9627e15c84db572a66e029b1fc-Paper-Conference.pdf>

Necessary and Sufficient Conditions for Optimal Decision Trees using Dynamic Programming. / van der Linden, J.G.M.; de Weerdt, M.M.; Demirović, E.
Advances in Neural Information Processing Systems 36 (NeurIPS 2023): 37th Conference on Neural Information Processing Systems (NeurIPS 2023). ed. / A. Oh; T. Neumann; A. Globerson; K. Saenko; M. Hardt; S. Levine. Vol. 36 Curran Associates, Inc., 2023. p. 9173-9212.

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

T1 - Necessary and Sufficient Conditions for Optimal Decision Trees using Dynamic Programming

AU - van der Linden, J.G.M.

AU - de Weerdt, M.M.

AU - Demirović, E.

N1 - Conference code: 37

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

KW - optimal decision trees

KW - dynamic programming

KW - necessary and sufficient conditions

KW - group fairness

KW - policy generation

KW - cost-sensitive classification

KW - f1-score

UR - https://github.com/algtudelft/pystreed

M3 - Conference contribution

VL - 36

SP - 9173

EP - 9212

BT - Advances in Neural Information Processing Systems 36 (NeurIPS 2023)

A2 - Oh, A.

A2 - Neumann, T.

A2 - Globerson, A.

A2 - Saenko, K.

A2 - Hardt, M.

A2 - Levine, S.

PB - Curran Associates, Inc.

T2 - 37th Annual Conference on Neural Information Processing Systems

Y2 - 10 December 2023 through 16 December 2023

ER -

van der Linden JGM , de Weerdt MM , Demirović E. Necessary and Sufficient Conditions for Optimal Decision Trees using Dynamic Programming. In Oh A, Neumann T, Globerson A, Saenko K, Hardt M, Levine S, editors, Advances in Neural Information Processing Systems 36 (NeurIPS 2023): 37th Conference on Neural Information Processing Systems (NeurIPS 2023). Vol. 36. Curran Associates, Inc. 2023. p. 9173-9212

Necessary and Sufficient Conditions for Optimal Decision Trees using Dynamic Programming

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this