Additive Groves code

Additive Groves code: TreeExtra package

TreeExtra is a set of tools implementing the following algorithms:

Additive Groves - a supervised learning algorithm
Bagged trees with "multiple counts" feature evaluation
Interaction detection with Additive Groves
Feature selection by backward elimination with Additive Groves
Effect and interaction visualization

Additive Groves is an ensemble of regression trees developed by Daria Sorokina, Rich Caruana and Mirek Riedewald.

Feature evaluation technique referred as "multiple counts" is developed by Art Munson and all of the above.

All code is written by Daria Sorokina unless stated otherwise. The code is available under BSD license and is free to use for any purpose.

Contact: Daria Sorokina ( fi...@gmail.com )

Please e-mail me any comments, suggestions, bug reports or feature requests. I am interested in how my algorithm is doing: if you have successfully (or unsuccessfully) applied Additive Groves to your data, I'd be happy to hear about your experience with it.

Updates Manuals Downloads Research papers

Updates

21 Apr '12. TreeExtra 2.2 is released
- Tree training is now faster without any impact on performance
- Treatment of missing values is improved: both probabilistic and "missing value is a separate value" approaches are evaluated in every split.
- N - number of trees in a grove - is now increased exponentially instead of linearly. It takes on values 1,2,3,4,6,8,11,16,23,32,45,64,... - major running time savings on data sets with strong additive structure.
- Several tweaks on the original Additive Groves algorithm result in further performance improvement. Namely, in most cases convergence test and vertical vs horizontal step tests are made on training instead of validation data now.
- -x option in vis_iplot tool allows to visualize slices of n-dimensional effect plots for higher order interactions.
- Nominals are accepted in the data files as long as they are not used.
05 Oct '10. TreeExtra 2.1 is released
- More convenient interface for ag_merge: now you can run any number of iterations in parallel and merge them with a single command.
- Memory usage is decreased almost by a factor of two without any impact on performance.
13 Jun '10. Additive Groves officialy got 4th place in the main track of the Yahoo! Learning To Rank Challenge.
- Read the description of our solution.
30 Dec '09. Additive Groves got the third place in the supervised challenge of 2009 IEEE ICDM Data Mining Contest.
- Read the description of our solution.
29 Nov '09. TreeExtra 2.0 is released.
- New set of commands implements interaction detection, feature selection and effect / interaction visualization with Additive Groves.
- New training mode of Additive Groves: option -s layered invokes layered training algorithm.
- The header format of the model files has changed and is not compatible with TreeExtra 1.x versions.
- bt_train command now saves a new attribute file where only top k features are left active. Setting -k option to -1 allows to create ranking for all features.
8 Oct '09. Several updates on the web site.
- This summer, Additive Groves ensemble scored the best result on one of the tasks in KDD Cup '09. Read the detailed account.
- Another paper about Additive Groves, Detecting and Interpreting Variable Interactions in Observational Ornithology Data, is accepted to DDDM'09.
- New chapter in the manual describes the structure of the model file.
- A script by Alex Sorokin allows for an automatic run of ag_train - ag_expand - ag_save sequence.
11 Aug '09. TreeExtra 1.2 is released.
- New command ag_merge joins several model grids. Therefore it is now possible to parallelize training of Additive Groves.
- New option -l allows to control the volume of information in standard output for bagged trees commands.
- The size of temporary folder AGTemp is decreased.
08 Jun '09. TreeExtra 1.1 is released. A choice of ROC for a model evaluation metric is added for binary classification problems.

Manuals

Downloads

TreeExtra 2.2

Additional code

Automated training of Additive Groves – python script by Alex Sorokin
MatLab code for creating visualization plots.

Earlier TreeExtra versions

Research papers and presentations

Daria Sorokina.
Application of Additive Groves to the Yahoo! Learning to Rank Challenge.

Daria Sorokina.
Modeling Additive Structure and Detecting Interactions with Additive Groves of Regression Trees
CMU Machine Learning Lunch, March 2010
Video (You need to scroll down to March 1 2010 talk. Sound is bad for the first few minutes only.)
Slides (.ppt)

Daria Sorokina, Rich Caruana, Mirek Riedewald, Wes Hochachka, Steve Kelling.
Detecting and Interpreting Variable Interactions in Observational Ornithology Data.
In proceedings of the ICDM'09 Workshop on Domain Driven Data Mining (DDDM'09).

Daria Sorokina.
Application of Additive Groves Ensemble with Multiple Counts Feature Evaluation to KDD Cup'09 Small Data Set.
In proceedings of the KDD Cup 2009 workshop.

Daria Sorokina.
Modeling Additive Structure and Detecting Interactions with Groves of Trees.
PhD dissertation, Cornell University, 2008.

Daria Sorokina, Rich Caruana, Mirek Riedewald, Daniel Fink.
Detecting Statistical Interactions with Additive Groves of Trees.
In proceedings of the 25th International Conference on Machine Learning (ICML'08).
Video of ICML presentation
Slides (.ppt)

Daria Sorokina, Rich Caruana, Mirek Riedewald.
Additive Groves of Regression Trees.
In proceedings of the 18th European Conference on Machine Learning (ECML'07) (Best Student Paper award.)
Video of ECML presentation
Slides (.ppt)

R. Caruana, M. Elhawary, A. Munson, M. Riedewald, D. Sorokina, D. Fink, W. Hochachka, S. Kelling.
Mining Citizen Science Data to Predict Prevalence of Wild Bird Species. <-- feature evaluation methods described here
In proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'06).