RI: Small: The TAO algorithm: principled, efficient optimization of decision trees, forests, tree-based neural nets, and beyond

决策树是最早的机器学习模型之一。他们通过问一系列简单的问题来预测给定的输入，从而得出预测值。这种离散结构使得决策树非常特别：它们是所有模型中最可解释的（因为可以检查树以理解或操纵其预测），而且它们非常快（因为只遵循一条根叶路径来对给定输入进行预测）。树也可以模拟高度非线性的函数。然而，决策树的理论能力与其实际性能之间存在很大差距，这是由于缺乏一种从数据中学习决策树的有效方法。这个问题比学习其他模型要困难得多，因为树定义了一个不连续的函数，基于梯度的节点参数优化是不适用的。今天用来学习树的算法是大约50年前发明的，结果是精度低的次优树，这使得它们无法与核机器或神经网络等模型竞争，而这些模型已经存在许多有效的优化算法。本项目旨在通过开发一种有效的决策树优化算法来纠正这种情况。这将使得在更多的应用程序中部署决策树并将它们与其他模型结合起来成为可能。该项目将为决策树开发开源软件和教材，并在机器学习和优化方面培训研究生和本科生。该项目开发了“树交替优化（TAO）”算法，该算法基于在固定结构树的非后代节点子集上迭代优化节点参数。TAO避开了对梯度的需要，并利用现有算法来训练单个节点。从任意给定的初始树开始，每次TAO迭代单调地减小训练损失函数。这使得树像其他参数模型（如核机器或神经网络）一样可训练。该项目将为不同的损失函数和机器学习任务（传统的分类和回归，以及降维、半监督学习、结构化输入等）开发TAO；对于不同的正则化通过惩罚或约束（如那些促进稀疏或非负参数）；对于不同的节点模型（如线性、核机、神经网络甚至决策树本身）。此外，该项目将探索TAO来学习树的结构，将树整合成森林，并调查树结构模型的可解释性和公平性。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Decision trees are one of the earliest machine learning models. They make a prediction for a given input by asking a series of simple questions that lead to a predicted value. This discrete structure makes decision trees very special: they are among the most interpretable of all models (in that the tree can be inspected to understand or manipulate its predictions), and they are very fast (since only one root-leaf path is followed to make a prediction for a given input). Trees can also model highly nonlinear functions. However, there is a large gap between the theoretical power of decision trees and their practical performance, which is due to the lack of an effective way to learn a decision tree from data. This problem is much harder than learning other models because the tree defines a discontinuous function and gradient-based optimization over the nodes' parameters is not applicable. The algorithms used today to learn trees were invented about 50 years ago, and result in suboptimal trees with low accuracy, which makes them not competitive with models such as kernel machines or neural nets, for which a number of effective optimization algorithms exist. This project seeks to redress this situation by developing an effective optimization algorithm for decision trees. This will make it possible to deploy decision trees in far more applications and to combine them with other models. The project will develop open-source software and teaching materials for decision trees, and train graduate and undergraduate students in machine learning and optimization.The project develops the "tree alternating optimization (TAO)" algorithm, based on iteratively optimizing the node parameters over subsets of nondescendant nodes in a tree of fixed structure. TAO sidesteps the need for gradients and capitalizes on existing algorithms to train individual nodes. Starting from any given initial tree, each TAO iteration monotonically decreases the training loss function. This makes trees trainable like other parametric models (such as kernel machines or neural nets). The project will develop TAO for different loss functions and machine learning tasks (the traditional classification and regression, but also dimensionality reduction, semisupervised learning, structured inputs and others); for different regularization via penalty or constraints (such as those promoting sparse or nonnegative parameters); and for different node models (such as linear, kernel machines, neural nets or even decision trees themselves). Further, the project will explore TAO to learn the structure of a tree, to ensemble trees into forests, and to investigate interpretability and fairness of tree-structured models.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.