Decision Trees for Decision-Making under the Predict-then-Optimize Framework
By Adam N. Elmachtoub, Jason Cheuk Nam Liang, Ryan McNellis. 2020
147 citations recorded by the source corpus.
We consider the use of decision trees for decision-making problems under the predict-then-optimize framework. That is, we would like to first use a decision tree to predict unknown input parameters of an optimization problem, and then make decisions by solving the optimization problem using the predicted parameters. A natural loss function in this framework is to measure the suboptimality of the decisions induced by the predicted input parameters, as opposed to measuring loss using input parameter prediction error. This natural loss function is known in the literature as the Smart Predict-then-Optimize (SPO) loss, and we propose a tractable methodology called SPO Trees (SPOTs) for training decision trees under this loss. SPOTs benefit from the interpretability of decision trees, providing an interpretable segmentation of contextual features into groups with distinct optimal solutions to the optimization problem of interest. We conduct several numerical experiments on synthetic and real data including the prediction of travel times for shortest path problems and predicting click probabilities for news article recommendation. We demonstrate on these datasets that SPOTs simultaneously provide higher quality decisions and significantly lower model complexity than other machine learning approaches (e.g., CART) trained to minimize prediction error.
Subfields: Artificial Intelligence
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Emmanuel Hebrard
- Ryan McNellis
- Peter James Stuckey
- Kris Johnson Ferreira
- Ali Aouad
- C. Leckie
- Emir Demirovi'c
- Jeffrey Chan
Citations in the corpus
- MurTree: Optimal Decision Trees via Dynamic Programming and Search (2020, background): “…trees (Kontschieder et al. (2015); Tanno et al. (2019)), randomised trees (Blanquero et al. (2020)), end-to-end learning of decision trees (Hehn et al. (2019); Elmachtoub et al. (2020)), and dynamic programming methods to construct decision trees from random forests (Vidal and Schiffer (2020)).”
- Market Segmentation Trees (2019, methodology): “An introduction to decision trees may be found in Friedman et al. (2001), as well as more recent surveys on their interpretability Rudin (2019) and optimization algorithms (Carrizosa et al.”