标题： 预测然后优化框架下的决策树用于决策制定 显示英文标题

标题： Decision Trees for Decision-Making under the Predict-then-Optimize Framework

摘要： 我们考虑在预测-然后优化框架下使用决策树进行决策问题。 也就是说，我们希望首先使用决策树来预测优化问题的未知输入参数，然后通过使用预测的参数求解优化问题来做出决策。 在这种框架中，自然的损失函数是衡量由预测输入参数引起的决策的次优性，而不是使用输入参数预测误差来衡量损失。 这种自然的损失函数在文献中被称为智能预测-然后优化（SPO）损失，我们提出了一种称为SPO Trees（SPOTs）的可处理方法，在此损失下训练决策树。 SPOTs受益于决策树的可解释性，提供对上下文特征的可解释分段，将其分为具有不同最优解的组，针对感兴趣的优化问题。 我们在合成数据和真实数据上进行了若干数值实验，包括最短路径问题的旅行时间预测和新闻文章推荐的点击概率预测。 我们在这些数据集上证明，SPOTs在提供更高质量的决策的同时，比其他机器学习方法（例如CART）显著降低了模型复杂度，这些方法是为最小化预测误差而训练的。 显示英文摘要

摘要： 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.