On Computing Optimal Tree Ensembles

Abstract

Random forests and, more generally, (deci- sion-)tree ensembles are widely used methods for classification and regression. Recent algorith- mic advances allow to compute decision trees that are optimal for various measures such as their size or depth. We are not aware of such research for tree ensembles and aim to contribute to this area. Mainly, we provide two novel algo- rithms and corresponding lower bounds. First, we are able to carry over and substantially improve on tractability results for decision trees, obtain- ing a (6δDS)S · poly-time algorithm, where S is the number of cuts in the tree ensemble, D the largest domain size, and δ is the largest num- ber of features in which two examples differ. To achieve this, we introduce the witness-tree tech- nique which also seems promising for practice. Second, we show that dynamic programming, which has been successful for decision trees, may also be viable for tree ensembles, providing an ℓn · poly-time algorithm, where ℓ is the number of trees and n the number of examples. Finally, we compare the number of cuts necessary to clas- sify training data sets for decision trees and tree ensembles, showing that ensembles may need ex- ponentially fewer cuts for increasing number of trees.