Towards Convergence Rate Analysis of Random Forests for Classification

Random forests have been one of the successful ensemble algorithms in machine learning, and the basic idea is to construct a large number of random trees individually and make predictions based on an average of their predictions. The great successes have attracted much attention on theoretical understandings of random forests, mostly focusing on regression problems. This work takes one step towards the convergence rates of random forests for classification. We present the first finite-sample rate O (n -1/(8d+2) ) on the convergence of purely random forests for binary classification, which can be improved to be of O (n -1/(3.87d+2) ) by considering the midpoint splitting mechanism. We introduce another variant of random forests, which follows Breiman's original random forests but with different mechanisms on splitting dimensions and positions. We present the convergence rate O (n -1/(d+2) (ln n) 1/(d+2) ) for the variant of random forests, which reaches the minimax rate, except for a factor (ln n) 1/(d+2) , of the optimal plug-in classifier under the L-Lipschitz assumption. We achieve the tighter convergence rate O ( ln n/n) under some assumptions over structural data. This work also takes one step towards the convergence rate of random forests for multi-class learning, and presents the same convergence rates of random forests for multi-class learning as that of binary classification, yet with different constants. We finally provide empirical studies to support the theoretical analysis.