CAREER: Statistical Learning with Recursive Partitioning: Algorithms, Accuracy, and Applications

随着数据驱动技术在高风险决策环境中的不断采用和部署，对快速、可解释的算法的需求变得前所未有的重要。作为这样的候选者之一，使用决策树（一种分层组织的数据结构）来构建预测或因果模型已经变得越来越普遍。这种趋势是由决策树和基于规则的决策之间的吸引人的联系所激发的，特别是在临床、法律的或商业环境中，因为树结构模仿人类用户可能思考和推理的顺序方式，从而促进人机交互。为了使它们快速计算，决策树通常使用称为递归分区的算法来构建，其中树的决策节点以贪婪的自上而下的方式从数据中学习。该项目的总体目标是准确理解基于递归划分的决策树的优势和局限性，并在此过程中深入了解如何在实践中提高其性能。除了这种影响，高中，本科和研究生研究助理将垂直整合，并在学术和专业上受益。有学生、学者和行业专业人士参与的创新课程、研讨会以及数据和方法竞赛将促进外联工作，并鼓励广大受众的参与。这个建议的目的是提供一个全面的研究的统计特性的贪婪递归分割算法训练决策树，在两个基本的情况下证明。该项目的第一个推力将开发一个理论框架，用于分析斜决策树，其中，与传统的轴对齐分裂只涉及一个协变量相比，在每个决策节点的分裂发生在协变量的线性组合。虽然自80年代中期以来，这种方法已经引起了计算机科学和优化社区的极大关注，但它们提供的相对于轴对齐同行的优势仍然只是经验证明，并且对它们成功的解释主要基于几何学。填补理论与实践之间的这一长期空白，PI将研究通过递归最小化平方误差构建的斜回归树如何适应由岭函数线性组合组成的丰富的回归模型。这为统计学家提供了一个定量基线，以比较和对比决策树与其他解释性较低的方法，如投影寻踪回归和神经网络，目标是类似的模型形式。至关重要的是，为了解决在每个决策节点处找到最优分裂超平面的组合复杂性，PI的框架可以容纳文献中的许多现有计算工具。研究的一个主要组成部分是来自递归划分和凸优化问题的顺序贪婪近似算法之间的联系（例如，正交贪婪算法）。 第二个重点是轴对齐递归划分的微妙逐点属性，对异质因果效应估计的影响，其中在协变量的整个支持上的精确逐点估计对于有效推断是必不可少的（例如，测试假设和构建置信区间）。受简单设置的启发，决策树可证明无法实现最佳性能，PI将研究信噪比如何影响逐点估计的质量。虽然重点是直接使用决策树进行因果效应估计，但PI还将研究多步半参数设置的影响，其中初步未知函数（例如，倾向得分）是通过机器学习工具以及条件分位数回归来估计的，这两种方法都需要具有高逐点精度的估计器。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

As data-driven technologies continue to be adopted and deployed in high-stakes decision-making environments, the need for fast, interpretable algorithms has never been more important. As one such candidate, it has become increasingly common to use decision trees, a hierarchically organized data structure, for building a predictive or causal model. This trend is spurred by the appealing connection between decision trees and rule-based decision-making, particularly in clinical, legal, or business contexts, as the tree structure mimics the sequential way a human user may think and reason, thereby facilitating human-machine interaction. To make them fast to compute, decision trees are popularly constructed with an algorithm called recursive partitioning, in which the decision nodes of the tree are learned from the data in a greedy, top-down manner. The overarching goal of this project is to develop a precise understanding of the strengths and limitations of decision trees based on recursive partitioning, and, in doing so, gain insights on how to improve their performance in practice. In addition to this impact, high-school, undergraduate, and graduate research assistants will be vertically integrated and benefit both academically and professionally. Innovative curricula, workshops, and data and methods competitions involving students, academics, and industry professionals will facilitate outreach and encourage participation from a broad audience. This proposal aims to provide a comprehensive study of the statistical properties of greedy recursive partitioning algorithms for training decision trees, as is demonstrated in two fundamental contexts. The first thrust of the project will develop a theoretical framework for the analysis of oblique decision trees, where, in contrast to conventional axis-aligned splits involving only a single covariate, the splits at each decision node occur at linear combinations of the covariates. While this methodology has garnered significant attention from the computer science and optimization communities since the mid-80s, the advantages they offer over their axis-aligned counterparts remain only empirically justified, and explanations for their success are largely based on heuristics. Filling this long-standing gap between theory and practice, the PI will investigate how oblique regression trees, constructed by recursively minimizing squared error, can adapt to a rich class of regression models consisting of linear combinations of ridge functions. This provides a quantitative baseline for a statistician to compare and contrast decision trees with other less interpretable methods, such as projection pursuit regression and neural networks, that target similar model forms. Crucially, to address the combinatorial complexity of finding the optimal splitting hyperplane at each decision node, the PI’s framework can accommodate many existing computational tools in the literature. A major component of the research is derived from connections between recursive partitioning and sequential greedy approximation algorithms for convex optimization problems (e.g., orthogonal greedy algorithms). The second thrust focuses on the delicate pointwise properties of axis-aligned recursive partitioning, with implications for heterogeneous causal effect estimation, where accurate pointwise estimates over the entire support of the covariates are essential for valid inference (e.g., testing hypotheses and constructing confidence intervals). Motivated by simple setting where decision trees provably fail to achieve optimal performance, the PI will investigate how the signal-to-noise ratio affects the quality of pointwise estimation. While the focus is on causal effect estimation directly using decision trees, the PI will also investigate implications for multi-step semi-parametric settings, where preliminary unknown functions (e.g., propensity scores) are estimated with machine learning tools, as well as conditional quantile regression, both of which require estimators with high pointwise accuracy.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.