Title: Statistical Advantages of Oblique Randomized Decision Trees and Forests Show Chinese title

Title: 斜向随机决策树和森林的统计优势

Abstract: This work studies the statistical implications of using features comprised of general linear combinations of covariates to partition the data in randomized decision tree and forest regression algorithms. Using random tessellation theory in stochastic geometry, we provide a theoretical analysis of a class of efficiently generated random tree and forest estimators that allow for oblique splits along such features. We call these estimators \emph{oblique Mondrian} trees and forests, as the trees are generated by first selecting a set of features from linear combinations of the covariates and then running a Mondrian process that hierarchically partitions the data along these features. Generalization error bounds and convergence rates are obtained for the flexible function class of multi-index models for dimension reduction, where the output is assumed to depend on a low-dimensional relevant feature subspace of the input domain. The results highlight how the risk of these estimators depends on the choice of features and quantify how robust the risk is with respect to error in the estimation of relevant features. The asymptotic analysis also provides conditions on the consistency rates of the estimated features along which the data is split for these estimators to obtain minimax optimal rates of convergence with respect to the dimension of the relevant feature subspace. Additionally, a lower bound on the risk of axis-aligned Mondrian trees (where features are restricted to the set of covariates) is obtained, proving that these estimators are suboptimal for general ridge functions, no matter how the distribution over the covariates used to divide the data at each tree node is weighted. Show Chinese abstract

Abstract: 这项工作研究了在随机决策树和森林回归算法中使用由协变量的通用线性组合组成的特征来划分数据的统计影响。 利用随机镶嵌理论，我们提供了对一类高效生成的随机树和森林估计量的理论分析，这些估计量允许沿此类特征进行斜向分割。 我们将这些估计量称为\emph{倾斜的蒙德里安}树和森林，因为树是通过首先从协变量的线性组合中选择一组特征，然后运行一个 Mondrian 过程，在这些特征上分层划分数据而生成的。 对于降维的多指标模型的灵活函数类，获得了泛化误差界和收敛速率，其中输出被假设依赖于输入域的一个低维相关特征子空间。 结果突显了这些估计量的风险如何依赖于特征的选择，并量化了风险在相关特征估计误差方面的鲁棒性。 渐近分析还为这些估计量在数据分割所用的估计特征上的一致性速率提供了条件，以获得相对于相关特征子空间维度的最小最大最优收敛率。 此外，得到了轴对齐 Mondrian 树（其中特征仅限于协变量集合）的风险下界，证明无论在每个树节点划分数据时协变量上的分布权重如何，这些估计量对于一般的岭函数都是次优的。