Optimal decision trees under constraints
(2022)
Files
Thesis_Aglin_Gael.pdf
Open Access - Adobe PDF
- 1.37 MB
Details
- Authors
- Supervisors
- Abstract
- Machine learning algorithms are used to learn models capable of predicting on unseen data. In recent years, we have seen a rise in the use of black box (complex) models. They have become popular due to their performance and are used in almost all contexts. Unfortunately, it is not possible to understand the reasons behind their prediction. It is therefore risky to use these models in critical application cases. In contrast to these models, some interpretable models provide an explanation for their prediction. Decision trees (DTs) are an example of such interpretable models. A DT hierarchically divides a dataset into small groups using successive conditions on feature values. Then, it associates predictions with these groups. The conditions leading to a group correspond to the explanation of the associated prediction. Unfortunately, in practice, DTs are neglected in favor of black-box models because the well-known DTs learning algorithms are heuristic and sometimes produce non-accurate trees. Optimal decision trees (ODTs), on the other hand, offer better performance but are very difficult to learn. Existing approaches prior to this thesis spend many hours to find an ODT of depth 2. In this thesis, we have proposed a specialized algorithm to learn ODTs in a reasonable amount of time to promote their use in everyday applications. Our algorithm is based on dynamic programming (DP) and branch-and-bound techniques. In practice, it is very time-efficient but can lead to important memory consumption due to the caching operations performed in DP. We have then proposed a technique to bound the memory consumption of our algorithm. Finally, we proposed ways to use ODTs to learn optimal forests and solve several well-known machine learning tasks.
- Affiliations
Citations
Aglin, G. (2022). Optimal decision trees under constraints. https://hdl.handle.net/2078.5/101423