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

AF：小：构建丰富而严谨的决策树学习理论

• 批准号: 2224246
• 负责人: Li-Yang Tan
• 金额: $ 30万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-10-01 至 2025-09-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2224246&HistoricalAwards=false
• 关键词: AF; Small; Building; rich; rigorous

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.

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