Decision trees and randomized forests are widely used in computer vision and
machine learning. Standard algorithms for decision tree induction optimize the
split functions one node at a time according to some splitting criteria. This
greedy procedure often leads to suboptimal trees. In this paper, we present an
algorithm for optimizing the split functions at all levels of the tree jointly
with the leaf parameters, based on a global objective. We show that the problem
of finding optimal linear-combination (oblique) splits for decision trees is
related to structured prediction with latent variables, and we formulate a
convex-concave upper bound on the tree's empirical loss. The run-time of
computing the gradient of the proposed surrogate objective with respect to each
training exemplar is quadratic in the the tree depth, and thus training deep
trees is feasible. The use of stochastic gradient descent for optimization
enables effective training with large datasets. Experiments on several
classification benchmarks demonstrate that the resulting non-greedy decision
trees outperform greedy decision tree baselines.

该论文提出了一种算法，该算法能够基于全局目标同时优化决策树的所有级别的分裂函数和叶参数，使用随机梯度下降进行优化，实验结果表明，该算法相比贪心算法在分类任务的表现优秀。