text: Recursive partitioning approaches producing tree-like models are a long standing staple of predictive modeling, in the last decade mostly as sub-learners'' within state of the art ensemble methods like Boosting and Random Forest. However, a fundamental flaw in the partitioning (or splitting) rule of commonly used tree building methods precludes them from treating different types of variables equally. This most clearly manifests in these methods' inability to properly utilize categorical variables with a large number of categories, which are ubiquitous in the new age of big data. Such variables can often be very informative, but current tree methods essentially leave us a choice of either not using them, or exposing our models to severe overfitting. We propose a conceptual framework to splitting using leave-one-out (LOO) cross validation for selecting the splitting variable, then performing a regular split (in our case, following CART's approach) for the selected variable. The most important consequence of our approach is that categorical variables with many categories can be safely used in tree building and are only chosen if they contribute to predictive power. We demonstrate in extensive simulation and real data analysis that our novel splitting approach significantly improves the performance of both single tree models and ensemble methods that utilize trees. Importantly, we design an algorithm for LOO splitting variable selection which under reasonable assumptions does not increase the overall computational complexity compared to CART for two-class classification. For regression tasks, our approach carries an increased computational burden, replacing a O(log(n)) factor in CART splitting rule search with an O(n) term.
  @cite_2: Feature ranking is a fundamental machine learning task with various applications, including feature selection and decision tree learning. We describe and analyze a new feature ranking method that supports categorical features with a large number of possible values. We show that existing ranking criteria rank a feature according to the training error of a predictor based on the feature. This approach can fail when ranking categorical features with many values. We propose the Ginger ranking criterion, that estimates the generalization error of the predictor associated with the Gini index. We show that for almost all training sets, the Ginger criterion produces an accurate estimation of the true generalization error, regardless of the number of values in a categorical feature. We also address the question of finding the optimal predictor that is based on a single categorical feature. It is shown that the predictor associated with the misclassification error criterion has the minimal expected generalization error. We bound the bias of this predictor with respect to the generalization error of the Bayes optimal predictor, and analyze its concentration properties. We demonstrate the efficiency of our approach for feature selection and for learning decision trees in a series of experiments with synthetic and natural data sets.
summary: In a second line of work, Sabato and Shalev-Schwartz suggest ranking categorical features according to their generalization error. However, their approach is limited to considering K-way splits (i.e., a leaf for every categorical value), as opposed to binary splits which group categories, which characterize CART and other tree methods commonly used in statistics. Their appraoch, which is also solely applicable for classification trees, offers strong theoretical results and low computational complexity (as it does not perform actual splitting), albeit in the K-way scenario which is significantly simpler theoretically than the binary split case we are considering, which requires optimizing over @math possible splits. Thus our goals are similar to theirs, but since we are dealing with a more complex problem we cannot adopt either their computational approach or their theoretical results. In our classification examples we compare our approach to theirs, demonstrating the advantage of binary splitting for attaining better predictive performance in practice. The approach of @cite_2 subsumes and improves on various previous lines of work in the machine learning literature on using cross validation to select variable in K-way splitting scenarios .