  The use of machine learning algorithms in finance, medicine, and criminal
justice can deeply impact human lives. As a consequence, research into
interpretable machine learning has rapidly grown in an attempt to better
control and fix possible sources of mistakes and biases. Tree ensembles offer a
good prediction quality in various domains, but the concurrent use of multiple
trees reduces the interpretability of the ensemble. Against this background, we
study born-again tree ensembles, i.e., the process of constructing a single
decision tree of minimum size that reproduces the exact same behavior as a
given tree ensemble in its entire feature space. To find such a tree, we
develop a dynamic-programming based algorithm that exploits sophisticated
pruning and bounding rules to reduce the number of recursive calls. This
algorithm generates optimal born-again trees for many datasets of practical
interest, leading to classifiers which are typically simpler and more
interpretable without any other form of compromise.
