On the Robust Splitting Criterion of Random Forest Splitting criteria have played an important role in the construction of decision trees, and various trees have been developed based on different criteria. This work presents a unified framework on various splitting criteria from the perspective of loss functions, and most classical splitting criteria can be viewed essentially as the optimizations of loss functions in this framework. We further introduce a new splitting criterion, named pairwise gain, which is motivated from a lower bound on the mutual coupling of pairwise loss. Theoretically, we prove that this new criterion is robust to symmetric and asymmetric label noises simultaneously. Based on this new criterion, we develop another variant of random forests, and extensive experiments are provided to verify its robustness.

Nearest Neighbor Classifiers Versus Random Forests and Support Vector Machines Recent experimental studies have shown that the support vector machine and the random forest are stand out models that outperform most other supervised learning methods in benchmarked evaluations on realworld data sets. Studies have also established that both these models are closely related to nearest neighbor classifiers. Due to this connection, one would expect a similar performance from a nearest neighbor classifier; however, the latter lags greatly behind the support vector machine and the random forest in most evaluations. On the contrary, the nearest neighbor classifier has great theoretical potential because of its ability to model complex decision boundaries with low bias. Furthermore, it theoretically guarantees an error of no more than twice the Bayes error rate on an infinite data set. In this paper, we examine this obvious disconnect between the great theoretical promise and empirical reality of the nearest neighbor classifier. An additional point is that the random forest and support vector machine can be considered eager forms of the (lazy) nearest neighbor classifier. Inspired by the connections between nearest neighbor classifiers, support vector machines and random forest models, we propose a nearest neighbor classifier that is competitive to these models.