Random Forest - univ-toulouse.fr

1 An introductionto Random forestsEric Debreuve / Team MorphemeInstitutions: University Nice Sophia Antipolis / CNRS / InriaLabs: I3S / Inria CRI SA-M / iBVOutline Machine learning Decision tree Random Forest Bagging Random decision trees Kernel-Induced Random Forest (KIRF) Byproducts Out-of-bag error Variable importance2 Machine learning Learning/training: build a classification or regression rule from a set of samples Prediction: assign a class or value to new samplesMachine learning algorithmSamples(learning set)class/category = rule(sample)orvalue = rule(sample)3 Learned ruleNew samplespredicted classorpredicted value(Un)Supervised learning Supervised Learning set = { (sample [acquisition], class [expert]) } Unsupervised Learning set = unlabeled samples Semi-supervised Learning set = some labeled samples + many unlabeled samples4 Ensemble learning Combining weak classifiers (of the same type).

2 In order to produce a strong classifier Condition: diversity among the weak classifiers Example: Boosting Train each new weak classifier focusing on samples misclassified by previous ones Popular implementation: AdaBoost Weak classifiers: only need to be better than Random guess5 Outline Machine learning Decision tree Random Forest Bagging Random decision trees Kernel-Induced Random Forest (KIRF) Byproducts Out-of-bag error Variable importance6 Decision tree Root node Entry point to a collection of data Inner nodes (among which the root node) A question is asked about data One child node per possible answer Leaf nodes Correspond to the decision to take (or conclusion to make) if reached Example.

3 CART - Classification and Regression Tree Labeled sample Vector of variable/feature values + class label Binary decision tree Top-down, greedy .. by recursively partitioning the feature space into hyper-rectangles Similarity with weighted kNN Normally, pruning To avoid over-fitting of learning data To achieve a trade-off between prediction accuracy and complexityQ1Q2D1D2Q3D3D4D57 Decision tree > CART > Building All labeled samples initially assigned to root node N root node With node N do Find the feature F + threshold value .. that split the samples assigned to N into 2 subsets Sleft and.

4 So as to maximize the label purity within these subsets Assign (F,T) to N If Sleft and Sright too small to be splitted Attach child leaf nodes Lleft and Lright to N Tag the leaves with the most present label in Sleft and Sright, resp. else Attach child nodes Nleft and Nright to N Assign Sleft and Sright to them, resp. Repeat procedure for N = Nleft and N = Nright8 Decision tree > CART > Building > Purity (Im)Purity Quality measure applied to each subset Sleft and Sright Combination of the measures ( , weighted average) Examples Gini index = Entropy = Misclassification error =9 Decision tree > CART > Properties Intrinsically multiclass Handles Apple and Orange features Robustness to outliers Works w/ "small" learning set Scalability (large learning set)

5 Prediction accuracy Parameter tuningCART kNN SVM10 Outline Machine learning Decision tree Random Forest Bagging Random decision trees Kernel-Induced Random Forest (KIRF) Byproducts Out-of-bag error Variable importance11 Random Forest Definition Collection of unpruned CARTs Rule to combine individual tree decisions Purpose Improve prediction accuracy Principle Encouraging diversity among the tree Solution: randomness Bagging Random decision trees (rCART)12 Random Forest > Bagging Bagging: Bootstrap aggregation Technique of ensemble .. to avoid over-fitting Important since trees are unpruned.

6 To improve stability and accuracy Two steps Bootstrap sample set Aggregation13 Random Forest > Bagging > Bootstrap L: original learning set composed of p samples Generate K learning sets .. composed of q samples, q p,.. obtained by uniform sampling with replacement from L In consequences, Lk may contain repeated samples Random Forest : q = p Asymptotic proportion of unique samples in Lk = 100 (1 - 1/e) ~ 63% The remaining samples can be used for testing14 Random Forest > Bagging > Aggregation Learning For each Lk, one classifier Ck (rCART) is learned Prediction S.

7 A new sample Aggregation = majority vote among the K predictions/votes Ck(S)15 Random Forest > Random decision tree All labeled samples initially assigned to root node N root node With node N do Find the feature F among a Random subset of features + threshold value .. that split the samples assigned to N into 2 subsets Sleft and .. so as to maximize the label purity within these subsets Assign (F,T) to N If Sleft and Sright too small to be splitted Attach child leaf nodes Lleft and Lright to N Tag the leaves with the most present label in Sleft and Sright, resp. else Attach child nodes Nleft and Nright to N Assign Sleft and Sright to them, resp.

8 Repeat procedure for N = Nleft and N = Nright Random subset of features Random drawing repeated at each node For D-dimensional samples, typical subset size = round(sqrt(D)) (also round(log2(x))) Increases diversity among the rCARTs + reduces computational load Typical purity: Gini index16 Random Forest > Properties17 Intrinsically multiclass Handles Apple and Orange features Robustness to outliers Works w/ "small" learning set Scalability (large learning set) Prediction accuracy Parameter tuningRF CART kNN SVMR andom Forest > Illustration1 rCART100 rCARTs10 rCARTs500 rCARTs18 Random Forest > Limitations Oblique/curved frontiers Staircase effect Many pieces of hyperplanes Fundamentally discrete Functional data?

9 (Example: curves)19 Outline Machine learning Decision tree Random Forest Bagging Random decision trees Kernel-Induced Random Forest (KIRF) Byproducts Out-of-bag error Variable importance20 Kernel-Induced Random Forest (KIRF) Random Forest Sample S is a vector Features of S = components of S Kernel-induced features Learning set L = { Si, i [ ] } Kernel K(x,y) Features of sample S = { Ki(S) = K(Si, S), i [ ] } Samples S and Si can be vectors or functional data21 Kernel > Kernel trick Kernel trick Maps samples into an inner product .. usually of higher dimension (possibly infinite).

10 In which classification (or regression) is easier Typically linear Kernel K(x,y) Symmetric Positive semi-definite (Mercer's condition): Note: mapping needs not to be known (might not even have an explicit representation; , Gaussian kernel)22 Kernel > Examples Polynomial (homogeneous): Polynomial (inhomogeneous): Hyperbolic tangent: Gaussian: Function of the distance between samples Straightforward application to functional data of a metric space , curves23 KIRF > Illustration Gaussian kernel Some similarity with vantage-point treeReminder: RF w/ 100 rCARTsKIRF w/ 100 rCARTs24 KIRF > Limitations Which kernel?