Inducing Interpretable Voting Classifiers without Trading Accuracy for
  Simplicity: Theoretical Results, Approximation Algorithms
  Recent advances in the study of voting classification algorithms have brought
empirical and theoretical results clearly showing the discrimination power of
ensemble classifiers. It has been previously argued that the search of this
classification power in the design of the algorithms has marginalized the need
to obtain interpretable classifiers. Therefore, the question of whether one
might have to dispense with interpretability in order to keep classification
strength is being raised in a growing number of machine learning or data mining
papers. The purpose of this paper is to study both theoretically and
empirically the problem. First, we provide numerous results giving insight into
the hardness of the simplicity-accuracy tradeoff for voting classifiers. Then
we provide an efficient "top-down and prune" induction heuristic, WIDC, mainly
derived from recent results on the weak learning and boosting frameworks. It is
to our knowledge the first attempt to build a voting classifier as a base
formula using the weak learning framework (the one which was previously highly
successful for decision tree induction), and not the strong learning framework
(as usual for such classifiers with boosting-like approaches). While it uses a
well-known induction scheme previously successful in other classes of concept
representations, thus making it easy to implement and compare, WIDC also relies
on recent or new results we give about particular cases of boosting known as
partition boosting and ranking loss boosting. Experimental results on
thirty-one domains, most of which readily available, tend to display the
ability of WIDC to produce small, accurate, and interpretable decision
committees.
