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

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

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.