The tree alternating optimisation (TAO) algorithm

This page collects papers describing the "tree alternating optimisation" (TAO) algorithm, a new way to train many types of decision trees (axis-aligned, oblique, etc.) and tree-based models, so that they optimise a desired objective function and regularisation term or constraint. TAO can be used by itself to learn a single tree, or as the base learner of a forest (tree ensemble). It vastly outperforms the traditional, greedy recursive partitioning algorithms such as CART or C4.5 (in isolation or as part of a forest), and allows one to learn models that strike a good balance between accuracy and interpretability.

This work has been done in collaboration with my past and present students and collaborators Magzhan Gabidolla, Kuat Gazizov, Yerlan Idelbayev, Rasul Kairgeldin and Arman Zharmagambetov.

 

It has been funded in part by:

Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

   
Drawings by Lucía Carreira Mateos.

Selected presentations

Software

Coming soon.

References

An illustration of TAO in 2D

This animation for a 2D dataset with 6 classes shows the result of training an oblique decision tree of depth 3 (with 8 leaves), with random initial parameters, for one TAO iteration. The animation shows the result of optimizing (bottom-up, i.e., from the leaves towards the root) each node's parameters given the other nodes are fixed. The objective function over the whole tree decreases monotonically after each update. Note that some decision nodes are automatically pruned in the process. Animation done by Magzhan Gabidolla.

 

An illustration of FAO in 2D

This animation for a 2D dataset with 6 classes shows the result of training a forest of 2 oblique decision trees of depth 2 (with 4 leaves each), with random initial parameters, for 3 FAO iterations. FAO (Forest Alternating Optimization) optimizes each tree in turn using TAO, and also optimizes all leaves of all trees jointly. The objective function over the whole forest decreases monotonically after each update. Nodes can also be automatically pruned in the process (although this does not happen in this particular case). Animation done by Magzhan Gabidolla.

 


Miguel A. Carreira-Perpinan
Last modified: Tue Sep 19 14:11:19 PDT 2023

UC Merced | EECS | MACP's Home Page