  We present a theory of boosting probabilistic classifiers. We place ourselves
in the situation of a user who only provides a stopping parameter and a
probabilistic weak learner/classifier and compare three types of boosting
algorithms: probabilistic Adaboost, decision tree, and tree of trees of ... of
trees, which we call matryoshka. "Nested tree," "embedded tree" and "recursive
tree" are also appropriate names for this algorithm, which is one of our
contributions. Our other contribution is the theoretical analysis of the
algorithms, in which we give training error bounds. This analysis suggests that
the matryoshka leverages probabilistic weak classifiers more efficiently than
simple decision trees.
