Learning Optimal Decision Trees Under Memory Constraints

被引:3
作者
Aglin, Gael [1 ]
Nijssen, Siegfried [1 ]
Schaus, Pierre [1 ]
机构
[1] UCLouvain, ICTEAM, Louvain La Neuve, Belgium
来源
MACHINE LEARNING AND KNOWLEDGE DISCOVERY IN DATABASES, ECML PKDD 2022, PT V | 2023年 / 13717卷
关键词
Decision trees; Optimization; Memory management;
D O I
10.1007/978-3-031-26419-1_24
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Existing algorithms for learning optimal decision trees can be put into two categories: algorithms based on the use of Mixed Integer Programming (MIP) solvers and algorithms based on dynamic programming (DP) on itemsets. While the algorithms based on DP are the fastest, their main disadvantage compared to MIP-based approaches is that the amount of memory these algorithms may require to find an optimal solution is not bounded. Consequently, for some datasets these algorithms can only be executed on machines with large amounts of memory. In this paper, we propose the first DP-based algorithm for learning optimal decision trees that operates under memory constraints. Core contributions of this work include: (1) strategies for freeing memory when too much memory is used by the algorithm; (2) an effective approach for recovering the optimal decision tree when parts of the memory are freed. Our experiments demonstrate a favorable trade-off between memory constraints and the run times of our algorithm.
引用
收藏
页码:393 / 409
页数:17
相关论文
共 13 条
[1]  
Aghaei S, 2022, Arxiv, DOI arXiv:2103.15965
[2]  
Aglin G, 2020, PROCEEDINGS OF THE TWENTY-NINTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, P5222
[3]  
Aglin G, 2020, AAAI CONF ARTIF INTE, V34, P3146
[4]  
Angelino E., 2018, arXiv
[5]   Optimal classification trees [J].
Bertsimas, Dimitris ;
Dunn, Jack .
MACHINE LEARNING, 2017, 106 (07) :1039-1082
[6]  
Demirovic E, 2022, J MACH LEARN RES, V23
[7]  
Hu XY, 2019, ADV NEUR IN, V32
[8]  
Hyafil L., 1976, Information Processing Letters, V5, P15, DOI 10.1016/0020-0190(76)90095-8
[9]  
Lin J., 2020, P 37 INT C MACH LEAR, V119, P6150
[10]   Optimal constraint-based decision tree induction from itemset lattices [J].
Nijssen, Siegfried ;
Fromont, Elisa .
DATA MINING AND KNOWLEDGE DISCOVERY, 2010, 21 (01) :9-51