# Presentation: 578347

## Boosted Decision Trees, an Alternative to Artificial Neural Networks

- B. Roe, University of Michigan

## Collaborators on this work

- H. Yang, J. Zhu, University of Michigan
- Y. Liu, I. Stancu, University of Alabama
- G. McGregor, Los Alamos National Lab.
- “and the good people of Mini-BooNE”

## What I will talk about

- I will review Artificial Neural Networks (ANN), introduce the new technique of boosted decision trees and then, using the miniBooNE experiment as a test bed compare the techniques for distinguishing signal from background

## Outline

- What is ANN?
- What is Boosting?
- What is MiniBooNE?
- Comparisons of ANN and Boosting for the MiniBooNE experiment

## Artificial Neural Networks

- Use to classify events, for example into “signal” and “noise/background”.
- Suppose you have a set of “feature variables”, obtained from the kinematic variables of the event

## Neural Network Structure

-  Combine the features in a non-linear way to a “hidden layer” and then to a “final layer”
- Use a training set to find the best *w**ik** *to distinguish signal and background

## Feedforward Neural Network--I

## Feedforward Neural Network--II

## Determining the weights

- Suppose want signal events to give output =1 and background events to give output=0
- Mean square error given *N**p* training events with desired outputs *o**i* either 0 or 1, and ANN results *t**i**.*

## Back Propagation to Determine Weights

## Boosted Decision Trees

- What is a decision tree?
- What is “boosting the decision trees”?
- Two algorithms for boosting.

## Decision Tree

- Go thru all PID variables and find the best to split events
- For each of the two subsets repeat the process
- Continuing a tree is built.  Ending nodes are called leaves

## Select signal and background leaves

- Assume an equal weight of signal and background training events
- If more than 1⁄2 of the weight in a leaf corresponds to signal events, it is a signal leaf; otherwise it is a background leaf
- Signal events on a background leaf or background events on a signal leaf are misclassified

## Criterion for “best” split

- Purity:
- Gini: Note Gini is 0 for all signal or all background
- Criterion is to minimize Gini_left + Gini_right

## Criterion for next branch to split

- Pick the branch to maximize the change in Gini,

## Boosting the Decision Tree

- Give the training events misclassified under this procedure a higher weight and  build a new tree
- Continuing, build perhaps 1000 trees and average the results (1 if signal leaf, -1 if bkrd leaf)

## Training and Testing Samples

- An ANN or boosted decision tree set are trained with a sample of events—the training sample.
- However, it would be biased to use this sample to evaluate how good the classifier is.  It is optimized for this individual set.
- A new set, the testing sample is used to evaluate the performance of the classifier after tuning.  All results quoted here are for the testing sample.

## How determine change of weights

- Two commonly used algorithms for boosting the decision trees are:
-                    AdaBoost
-                     -boost (or “shrinkage”)

## Definitions

*X**i **= *set of particle ID variables for event *i*
*Y**i **=* 1 if the *i*th event is signal,-1 if bkrd
*W**i*= weight of *i*th event
*T**m**(x**i**)*= 1 if *i*th event lands on signal leaf,    and     -1 if *i*th event lands on bkrd leaf
*I(y**i **= T**m**(x**i**))* =1 if misclassify, 0 if classify correctly

## AdaBoost

- Define
- Change weight for misclassified events

## Example

- Suppose the weighted error rate is 10%, i.e., err=0.1
- Then alpha = (1/2)ln((1-.1)/.1)= 1.1
- Weight of a misclassified event is multiplied by exp(1.1)~3

## Scoring events with AdaBoost

- Renormalize weights
- Score by summing over trees

## Epsilon Boost (shrinkage)

- After tree *m*, change weight of misclassified events, typical     ~0.01
- Renormalize weights
- Score by summing over trees

## Comparison of methods

- Epsilon boost changes weights a little at a time
- AdaBoost can be shown to try to optimize each change of weights.  Lets look a little further at that

## AdaBoost Optimization

## AdaBoost Fitting is Monotone

## References

- R.E. Schapire ``The strength of weak learnability.’’ *Machine Learning**** *****5** (2), 197-227 (1990).  First suggested the boosting approach for 3 trees taking a majority vote
- Y. Freund, ``Boosting a weak learning algorithm by majority’’, *Information and Computation ***121** (2), 256-285 (1995)  Introduced using many trees
- Y. Freund and R.E. Schapire, ``Experiments with an new boosting algorithm, *Machine Learning: Proceedings of the Thirteenth International Conference, *Morgan Kauffman, SanFrancisco, pp.148-156 (1996).  Introduced AdaBoost
- J. Friedman, T. Hastie, and R. Tibshirani, ``Additive logistic regression: a statistical view of boosting’’,* Annals of Statistics ***28 **(2), 337-407 (2000).  Showed that AdaBoost could be looked at as successive approximations to a maximum likelihood solution.* *
- T. Hastie, R. Tibshirani, and J. Friedman, ``The Elements of Statistical Learning’’ Springer (2001).  Good reference for decision trees and boosting.

## The MiniBooNE Experiment

## The MiniBooNE Collaboration

- Y.Liu, I.Stancu*University of Alabama*
- S.Koutsoliotas*Bucknell University*
- E.Hawker, R.A.Johnson, J.L.Raaf*University of Cincinnati*
- T.Hart, R.H.Nelson, E.D.Zimmerman*University of Colorado*
- A.A.Aguilar-Arevalo, L.Bugel, J.M.Conrad, J.Link, J.Monroe, D.Schmitz, M.H.Shaevitz, M.Sorel, G.P.Zeller*Columbia University*
- D.Smith*Embry Riddle Aeronautical University*
- L.Bartoszek, C.Bhat, S.J.Brice, B.C.Brown, D.A.Finley, R.Ford, F.G.Garcia, P.Kasper, T.Kobilarcik, I.Kourbanis, A.Malensek, W.Marsh, P.Martin, F.Mills, C.Moore, E.Prebys, A.D.Russell, P.Spentzouris, R.Stefanski, T.Williams*Fermi National Accelerator Laboratory*
- D.Cox, A.Green, T.Katori, H.Meyer, R.Tayloe*Indiana University*
- G.T.Garvey, C.Green, W.C.Louis, G.McGregor, S.McKenney, G.B.Mills, H.Ray, V.Sandberg, B.Sapp, R.Schirato, R.Van de Water, N.L.Walbridge, D.H.White*Los Alamos National Laboratory*
- R.Imlay, W.Metcalf, S.Ouedraogo, M.Sung, M.O.Wascko*Louisiana State University*
- J.Cao, Y.Liu, B.P.Roe, H.J.Yang*University of Michigan*
- A.O.Bazarko, P.D.Meyers, R.B.Patterson, F.C.Shoemaker, H.A.Tanaka*Princeton University*
- P.Nienaber*St. Mary's University of Minnesota*
- B.T.Fleming*Yale University*

## Slide 30

## Ran 97 million pulses before failing

## Horn now being replaced

- It acquired eight times more pulses than any previous horn anywhere.

## Slide 33

## Slide 34

## Slide 35

## Slide 36

## Slide 37

## Examples of data events

## Comparison of Neural Nets and Boosting

## Numerical Results

- There are 2 reconstruction-particle id packages used in MiniBooNE, rfitter and sfitter
- The best results for ANN and Boosting used different numbers of variables, 21 or 22 being best for ANN and 50-52 for boosting
- Results quoted are ratios of background kept by ANN to background kept for boosting, for a given fraction of signal events kept
- Only relative results are shown

## Boosting Results versus Ntree

- Top: N_bkrd divided by N_bkrd for 1000 trees and 50% nue selection efficiency vs nue efficiency for CCQE events.
- Bottom: AdaBoost output for background and signal events for 1000 trees

## Numerical Results from rfitter

- Train against all kinds of backgrounds—21 ANN variables and 52 boosting variables: for 40-60% of signal kept, the ratio of ANN to boosting background varied from 1.5 to 1.8
- Train against nc pi0 background—22 ANN variables and 52 boosting variables: for 40-60% of signal kept, the ratio of ANN to boosting background varied from 1.3 to 1.6

## Comparison of Boosting and ANN

- A.  Bkrd are cocktail events.  Red is 21 and black is 52 training var.
- B. Bkrd are pi0 events. Red is 22 and black is 52 training variables
- Relative ratio is ANN bkrd kept/Boosting bkrd kept

- Percent nue CCQE kept

## Comparison of 21 (or 22) vs 52 variables for Boosting

- Vertical axis is the ratio of bkrd kept for 21(22) var./that kept for 52 var.
- Red is if training sample is cocktail and black is if training sample is pi0
- Error bars are MC statistical errors only

- Ratio

## AdaBoost vs Epsilon Boost and differing tree sizes

- A.  Bkrd for 8 leaves/ bkrd for 45 leaves.  Red is AdaBoost, Black is Epsilon Boost
- B. Bkrd for AdaBoost/ bkrd for Epsilon Boost Nleaves = 45.

## Numerical Results from sfitter

- Extensive attempt to find best variables for ANN and for boosting starting from about 3000 candidates
- Train against pi0 and related backgrounds—22 ANN variables and 50 boosting variables:  for the region near 50% of signal kept, the ratio of ANN to boosting background was about 1.2

## Number of parameters to fit

- In ANN if 22 input variables and a hidden layer of 22, 2X(22 X (22+1)= 1012.  ANN updates weights every few events.
- In boosting, if 1000 trees of 45 leaves, then 1000 X45 X2 (which var and cut point) = 90,000.

## For ANN

**For ANN one needs to set temperature, hidden layer size, learning rate...  There are lots of parameters to tune**
- For ANN, if one
-      a.  Multiplies a variable by a constant, var172.var 17
-       b.  Switches two variables
-    var 17var 18
-       c.  Puts a variable in twice
-   The result is very likely to change

## For boosting

- Boosting can handle more variables than ANN; it will use what it needs.
- Duplication or switching of variables will not affect boosting results.
- Suppose we make a change of variables y=f(x), such that if x_2>x_1, then y_2>y_1.  The boosting results are unchanged.  They depend only on the ordering of the events
- There is considerably less tuning for boosting than for ANN.

## Conclusions

**For MiniBooNE boosting is better than ANN by a factor of 1.2—1.8**
**AdaBoost and Epsilon Boost give comparable results within the region of interest (40%--60% nue kept)**
**Use of a larger number of leaves (45) gives 10--20% better performance than use of a small number (8).**
**It is expected that boosting techniques will have wide applications in physics.**
**Preprint Physics/0408124; submitted to Phys. Rev.**

## Slide 51

## LSND final result

## KARMEN II (1997-2001)

## Slide 54

## Slide 55

## Slide 56

## Slide 57

## Slide 58

## Slide 59

## Slide 60

## Slide 61

## Slide 62

## Slide 63