We study an interesting and challenging problem, supervised learning on a stream of features, in which the size of the feature set is unknown, and not all features are available for learning while leaving the number of observations constant. In this problem, the features arrive one at a time, and the learner's task is to train a model equivalent to a model trained from "scratch". When a new feature is inserted into the training set, a new set of trees is trained and added into the current forest. However, it is desirable to correct the selection bias: older features has more opportunities to get selected into trees than the new features. We combat the selection bias by adjusting the feature selection distribution. However, while this correction improves accuracy of the random forest, it may require training of many new trees. In order to keep the count of the new trees small, we furthermore put more weight on more recent trees than on the old trees.
Motivation Our original need for learning on a stream
of features was due to our interest into
propositionalization [
Copyright ©2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). comparable to accuracy obtained on exhaustive propositionalization). However, our former research had evident weakness: it neglected to take into account possible interactions between features. This paper attempts to address this weakness.
Why not a feature selection filter? Features that are currently unpredictive may become predictive, as new features appear. For example, consider XOR problem, in which the binary label is determined by two binary features f1 and f2: y = xor( f1; f2). Features f1 and f2 are individually unpredictive. But together, they define the label. Univariate feature selection filters (e.g.: based on information gain ratio) cannot correctly identify the change or the first feature relevance as the second feature is added in XOR problem. But models capable of modeling feature interactions (like random forests) can eventually identify these features as important.
Application Beside propositionalization, learning on a stream of features has another interesting use-case: Kaggle competitions. In these challenges, competitors are given a dataset and the team with the best model wins1. Based on the analysis of solutions of the past winners2, one of the common differentiating factors is extensive feature engineering. However, competitive feature engineering is generally not a one-time task but rather an iterative process: 1. formulate a hypothesis (e.g.: log transformation of features will improve the accuracy of the downstream model), 2. test the hypothesis (e.g.: evaluate the change of accuracy of the downstream model), where the choice of the next round of hypotheses is influenced based on the success of the previously evaluated hypotheses. Traditionally, the evaluation of the hypothesis required retraining of the model from scratch. Our solution is to update the current model. The benefit is evident: the update of the current model takes less time than retraining the model from scratch. And consequently, that gives us the freedom to test more hypotheses.
Random forest We take random forest [
The key idea behind random forest classifier is that we
make an ensemble of decision trees. In order to create
diversity between the trees, it employs two strategies: bagging
and random feature selection. Bagging is based on a
random sampling of training instances with repetition. While
random feature selection is without repetition. The count of
features to select is one of the most tunable parameters of
random forests [
1See a list of all possible challenges at https://www.kaggle.com/ competitions
2http://blog.kaggle.com/category/ winners-interviews/
Bias Whenever a new feature xnew arrives, we may train n new trees. And add the newly trained trees into the current random forest. Unfortunately, with this approach, the new features would be underrepresented in the forest in comparison to old features simply because the old features had multiple opportunities to get used in a tree while the new feature had only one opportunity to get used in a tree.
Consequently, earlier features would have a bigger impact (weight) in the forest than the newer features. This presents a bias, which is generally undesirable.
Variable count of trees The first intuitive improvement is to make sure that the new feature is actually always passed to the new trees (instead of leaving it on the chance). And instead of generating an arbitrary count of the trees, we can calculate the optimal count n that minimizes the random feature selection bias.
First, we introduce the notation. Let c be the count of how many times a feature x was passed to decision trees.
And let old subscript describe some old feature and new subscript to describe the new feature. If we want to avoid the random feature selection bias, following should hold: (1) (2) (3) (4) (5) Since because the new feature is always selected and cnew = cold :
cnew = n where dold is the count of the old features, we get: cold = mtry dold + mtry n;
n = mtry dold + mtry n: Hence, we get the optimal n with: n = mtry dold :
1 mtry
The issue with this approach is that if we keep adding d features one-by-one, the total count of the trees in the ensemble grows quadratically.
Tree weighting If we want to avoid the quadratic growth of the random forest, we may weight the late trees more than the former trees. While we could have calculated the tree weight analytically, we provide an algorithmic solution in Algorithm 1. In praxis, the advantage of the algorithmic solution is that it is self-correcting — if some of the assumptions are not fully fulfilled (e.g.: When we have 11 features and the feature selection ratio is 0.5, we can either Algorithm 1: Random forest update, when a new feature arrives. Function featureCnt() returns count of features to sample.
Input: X : training data, y: training label, col: index of the new feature, treeCnt: cnt of trees to train, weightedFeatureU seCnt: bookkeeping vector initialized to zeros, ensemble: collection of trees.
Output: ensemble, treeWeight, weightedFeatureU seCnt. 1 f eatureU seCnt = zeros (col); 2 for i=1:treeCnt do 3 oldFeatures = choice (1:col-1, featureCnt (col-1), replacement=False); 4 f eatures = [oldFeatures, col]; 5 samples = choice (nrow (x), nrow (x), replacement=True); 6 tree = fitTree (X [samples, f eatures], y[samples]); 7 ensemble = [ensemble, tree]; 8 f eatureU seCnt[ f eatures]++ ; 9 end 10 treeWeight = avg (weightedFeatureU seCnt[1:col-1]) / ( f eatureU seCnt[col] - avg ( f eatureU seCnt[1:col-1])); 11 weightedFeatureU seCnt = weightedFeatureU seCnt + treeWeight* f eatureU seCnt; select 5 or 6 features but not 5.5.), the error is not ignored (as it would be in a closed-form analytical solution) but is encoded in weightedFeatureUseCount. And each call of Algorithm 1 directly minimizes the error.
When scoring new samples, we evaluate trees in the ensemble and calculate the weighted average of the predictions (each generation of trees share the same treeWeight). 2
We compare two online random forest implementations: baseline and challenger. In baseline, features are selected with uniform probability (like in ordinary random forest). In the challenger model, the new feature is always selected while the old features are selected with uniform probability3. Furthermore, we train an offline random forest with the same meta-parameters as the online random forest in order to depict the value of the online learning. Protocol For each data set, we performed the following procedure 10 times: We randomly split the data set into training/testing subsets with stratified sampling with 2:1 ratio. Then we randomly permutate the feature order in the data set (because our proposal should work regardless of the feature ordering). Finally, on online random forests we perform incremental learning feature-by-feature (i.e.: first we train the random forest on the first feature, then we add the second feature into the forest,... and continue until the last feature is added into the forest). After adding the last feature, the final model is evaluated on the testing set with 3This probability is smaller in the challenger model than in the baseline model in order to keep the final count of features in challengers’ trees identical to the count of features in baselines’ trees.
AUC (Area Under the Receiver Operating Characteristics). In the case of the offline random forest, we train the random forest just once on all the features.
Meta-parameters At each generation (addition of a new
feature), we train 30 new trees. This value is recommended
by Breiman [
Data sets We used all 232 data sets (see Appendix A) from
OpenML [
Results In 87% (201/232), the challenger model had higher average testing AUC than the baseline. Sign test on this statistic gives one-tail P-value < 10 29. The average difference of the testing AUC across all the data sets was 2.10 percent point. Furthermore, in 71% (164/232), the challenger model had higher average testing AUC than the offline model (P-value < 10 8). The table with the results and the code that generated the table is available from https://github.com/janmotl/rf. 3
Overhead Challenger model, in comparison to baseline model, uses 3 more variables: featureUseCount, weightedFeatureUseCount and treeWeight. Each of these variables is (or fill in) a vector of length d, the count of features. Ignoring the differences in the data types, the total memory overhead is equivalent to 3 more training data samples. The computational complexity of updating these 3 variables, when a new feature is added, is O (d) since treeCount is a constant.
Limitation Our experiment suffers from one limitation: while we make sure that the feature selection rate is uniform, we ignore interactions between the features. This could be a topic of further research.
Extension One of possible extensions of our work, which we did not pursue further, is pruning of the oldest trees from the ensemble. The idea is simple: the older generations of the trees have so small weight, that they hardly influence the final prediction. 4
We have extended random forest to work on a stream of features. The idea was simple: when a new feature arrives, extend the forest with a new set of trees. However, with this strategy, older features end up used more frequently than the new features. When we fix this feature selection bias, it improves the testing AUC on average by 2 percent points. The proposed algorithm for feature selection bias correction is fast, easy to implement and robust. The code was open-sourced at https://github.com/janmotl/rf. 5
We would like to thank the anonymous reviewers, their comments helped to improve this paper. This research was supported by the Grant Agency of the Czech Technical University in Prague, grant No. SGS17/210/OHK3/3T/18.
2dplanes abalone acute-inflammations aids Amazon_employee_access analcatdata_apnea1 analcatdata_apnea2 analcatdata_apnea3 analcatdata_asbestos analcatdata_bankruptcy analcatdata_birthday analcatdata_bondrate analcatdata_boxing1 analcatdata_boxing2 analcatdata_broadway analcatdata_broadwaymult analcatdata_challenger analcatdata_chlamydia analcatdata_creditscore analcatdata_cyyoung8092 analcatdata_cyyoung9302 analcatdata_dmft analcatdata_draft analcatdata_fraud analcatdata_germangss analcatdata_gsssexsurvey analcatdata_gviolence analcatdata_japansolvent analcatdata_lawsuit analcatdata_michiganacc analcatdata_neavote analcatdata_negotiation analcatdata_olympic2000 analcatdata_reviewer analcatdata_runshoes arsenic-female-bladder arsenic-female-lung arsenic-male-bladder arsenic-male-lung autoMpg badges2 balance-scale balloon banana bank8FM banknote-authentication baskball house_8L houses humandevel hungarian hutsof99_logis ilpd iris irish jEdit_4.0_4.2 jEdit_4.2_4.3 kdd_el_nino-small kidney kin8nm lowbwt lupus machine_cpu MagicTelescope mammography mbagrade mfeat-morphological mofn-3-7-10 monks-problems-1 monks-problems-2 monks-problems-3 mozilla4 mu284 mux6 mv newton_hema no2 nursery page-blocks parity5 parity5_plus_5 pc1_req pollen postoperative-patient-data prnn_crabs prnn_fglass prnn_synth profb puma8NH pwLinear quake qualitative-bankruptcy rabe_131 rabe_148