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

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

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.