Random forests (RF) are one of the most widely used ensemble learning methods in classification and regression tasks. Despite its impressive performance, its theoretical consistency, which would ensure that its result converges to the optimum as the sample size increases, has been left far behind. Several consistent random forest variants have been proposed, yet all with relatively poor performance compared to the original random forests. In this paper, a novel RF framework named multinomial random forests (MRF) is proposed. In the MRF, an impurity-based multinomial distribution is constructed as the basis for the selection of a splitting point. This ensures that a certain degree of randomness is achieved while the overall quality of the trees is not much different from the original random forests. We prove the consistency of the MRF and demonstrate with multiple datasets that it performs similarly as the original random forests and better than existent consistent random forest variants for both classification and regression tasks.
@cite_0: In the last years of his life, Leo Breiman promoted random forests for use in classification. He suggested using averaging as a means of obtaining good discrimination rules. The base classifiers used for averaging are simple and randomized, often based on random samples from the data. He left a few questions unanswered regarding the consistency of such rules. In this paper, we give a number of theorems that establish the universal consistency of averaging rules. We also show that some popular classifiers, including one suggested by Breiman, are not universally consistent.
@cite_5: A heuristic analysis is presented in this paper based on a simplified version of RF denoted RF0. The results from RF0 support the empirical results from RF. RF0 regression is consistent using a value of mtry that does not depend on the number of cases N The rate of convergence to the Bayes rule depends only on the number of strong variables and not on how many noise variables are also present.. This also implies consistency for the two class RF0 classification. The analysis also illuminates why RF is able to handle large numbers of input variables and what the role of mtry is.
One important property, consistency, has yet been established for random forests. The consistency of a prediction method ensures that its performance converges to the optimum as the sample size goes to infinity. This property was firstly discussed in Breiman's mathematical heuristics report @cite_5 . After that, the consistency of two directly simplified random forests was verified by Biau @cite_0 .