# Inducing Interpretable Voting Classifiers Without Trading Accuracy For Simplicity: Theoretical Results, Approximation Algorithms, And Experiments

## Richard Nock

RNOCK@MARTINIQUE.UNIV-AG.FR
Université Antilles-Guyane GRIMAAG-Département Scientifique Interfacultaire Campus Universitaire de Schoelcher B.P. 7209 97275 Schoelcher, Martinique, France

## Abstract

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

## 1. Introduction

Recent advances in the study of voting classification algorithms have brought empirical and theoretical results clearly showing the discrimination power of ensemble classifiers (Bauer & Kohavi, 1999; Breiman, 1996; Dietterich, 2000; Opitz & Maclin, 1999; Schapire & Singer, 198). These methods basically rely on voting the decision of individual classifiers inside an ensemble. It is widely accepted, and formally proven in certain cases (Schapire, Freund, Bartlett, & Lee, 1998; Schapire & Singer, 1998), that their power actually relies on the ability to build potentially very large classifiers. It has even been observed experimentally that such an ensemble can sometimes be as large as (or larger than) the data used to build the ensemble (Margineantu & Dietterich, 1997) !  Then, a simple question arises, namely what is the interest a customer can have in using such a classifier, instead of simple