Fast Interpretable Greedy-Tree Sums (FIGS)
  Modern machine learning has achieved impressive prediction performance, but
often sacrifices interpretability, a critical consideration in many problems.
Here, we propose Fast Interpretable Greedy-Tree Sums (FIGS), an algorithm for
fitting concise rule-based models. Specifically, FIGS generalizes the CART
algorithm to simultaneously grow a flexible number of trees in a summation. The
total number of splits across all the trees can be restricted by a
pre-specified threshold, thereby keeping both the size and number of its trees
under control. When both are small, the fitted tree-sum can be easily
visualized and written out by hand, making it highly interpretable. A partially
oracle theoretical result hints at the potential for FIGS to overcome a key
weakness of single-tree models by disentangling additive components of
generative additive models, thereby reducing redundancy from repeated splits on
the same feature. Furthermore, given oracle access to optimal tree structures,
we obtain L2 generalization bounds for such generative models in the case of C1
component functions, matching known minimax rates in some cases. Extensive
experiments across a wide array of real-world datasets show that FIGS achieves
state-of-the-art prediction performance (among all popular rule-based methods)
when restricted to just a few splits (e.g. less than 20). We find empirically
that FIGS is able to avoid repeated splits, and often provides more concise
decision rules than fitted decision trees, without sacrificing predictive
performance. All code and models are released in a full-fledged package on
Github \url{https://github.com/csinva/imodels}.
