AF: Small: Building a rich and rigorous theory of decision tree learning

决策树是指定如何将对一系列问题的答复合并为单个全局决策的逻辑流程图。决策树是表示决策过程的最自然的方式之一，它们渗透到日常生活中。例如，贷款审批决策可以合理地建模为决策树，它将关于申请人的各种信息-例如，“他们的年收入是多少？”；“他们在过去5年内是否拖欠贷款？”等--合并到一个单一的全局决策中，无论贷款是批准还是拒绝。决策树也是整个计算机科学中非常基本的研究对象，它们在机器学习(ML)中发挥着越来越重要的作用。这里的一个中心问题是决策树学习：高效地构建代表数据集的决策树的算法任务，自20世纪70年代以来一直研究得很好。例如，给定批准或拒绝贷款的申请者的数据集，任务将是构建一个决策树来解释这些决策。在这个项目中，研究人员将开发新的决策树学习算法，并为实际中广泛使用的现有决策树学习算法建立严格的数学保证。该项目的一个重要教育目标是通过研究合作和指导的过程培养本科生和研究生，特别是培养决策树学习和更广泛的机器学习理论方面的专业知识。研究人员还将开发新的课程材料，并与实验工作和ML实践者保持密切的反馈循环。决策树在机器学习中的流行和有效性，乃至整个计算机科学，都源于它们的简单性。它们的求值速度非常快，求值时间随其深度缩放，该数量通常比它们的整体表示大小成指数级地小。除了线性回归、k-均值、k-近邻和支持向量机等经典知识外，学习决策树的启发式算法在任何ML入门课程中都是必不可少的主题，并且它们是每个ML实践者的标准工具包的一部分。决策树的逻辑和层次结构使它们易于理解，并且它们是可解释模型的最典型的例子。最近的一项调查将决策树学习列为可解释ML这一新兴领域的“十大挑战”中的第一个。尽管决策树学习的经验重要性和成功，许多关于决策树学习的最基本的理论问题仍然悬而未决。在过去的几年里，这位研究人员和他的学生一直在努力解决这个问题，这个项目是围绕他们的研究出现的两个总体目标构建的：(I)开发新的决策树学习算法，以促进我们对问题的基本理解。(Ii)为实践中使用的标准决策树学习启发式方法建立性能保证，并将其经验上的成功建立在坚实的理论基础上。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Decision trees are logical flowcharts that specify how responses to a sequence of questions can be amalgamated into a single global decision. Decision trees are one of the most natural ways of representing decision-making processes and they pervade everyday life. For example, a loan approval decision can reasonably be modeled as a decision tree that amalgamates various information about the applicant --- for example, "What is their annual income?"; "Have they defaulted on a loan in the past 5 years?"; etc. --- into a single global decision, whether the loan is approved or denied. Decision trees are also very basic objects of study throughout computer science and they play an increasingly important role in machine learning (ML). A central problem here, well studied since the 1970s, is that of decision tree learning: the algorithmic task of efficiently building a decision tree that represents a dataset. For example, given a dataset of applicants who had approved or denied loans, the task would be to build a decision tree that explains these decisions. In this project, the investigator will develop new algorithms for decision tree learning, as well as establish rigorous mathematical guarantees for existing decision tree learning algorithms that are widely used in practice. An important educational goal of this project is to train undergraduates and graduate students through the process of research collaboration and mentorship, with a particular goal of building expertise in decision tree learning and the theory of machine learning more generally. The investigator will also develop new curricular materials and maintain a tight feedback loop with experimental work and with ML practitioners. The popularity and effectiveness of decision trees in machine learning, and throughout computer science more generally, stem from their simplicity. They are extremely fast to evaluate, with evaluation time scaling with their depth, a quantity that is often exponentially smaller than their overall representation size. Alongside other classics such as linear regression, k-means, k-nearest neighbors, and support vector machines, heuristics for learning decision trees are an essential topic in any introductory ML course, and they are part of the standard toolkit of every ML practitioner. The logical and hierarchical structure of decision trees makes them easy to understand, and they are the most canonical example of an explainable model. A recent survey lists decision tree learning as the very first of "10 grand challenges" for the emerging field of explainable ML. Despite its empirical importance and success, many of the most basic theoretical questions regarding decision tree learning remain wide open. The investigator and his students have been working on addressing this for the past couple of years, and this project is structured around two overarching goals that have emerged from their research: (i) Develop new decision tree learning algorithms that advance our fundamental understanding of the problem. (ii) Establish performance guarantees for standard decision tree learning heuristics used in practice and place their empirical success on a firm theoretical footing.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.