199), branching programs (Mansour & McAllester, 2000), etc. . There exists, however, a type of classifiers on which related papers appear to be generally unanimous on their mining abilities : disjunctive normal form formulas (DNFs, and their numerous extensions), that is, disjunctions of conjunctions. Interestingly enough, this is the class which motivated early works (and a great amount of works afterwards) on the well-known PAC theory of learning (Valiant, 1984, 1985), partly because of the tendency humans seem to have to represent knowledge using similarly shaped rules (Valiant, 1985). This class is also the dual of the one implicitly used by Buja & Lee (2001) to cast their size measure for decision trees (to state whether the concept represented is simple or not).

It is our aim in this paper to propose theoretical results and approximation algorithms related to the induction of very particular voting classifiers, drawing their roots on simple rule sets (like DNF), with the objective to keep a tradeoff between simplicity and accuracy. Our aim is also to prove that, in the numerous induction algorithms already proposed throughout the machine learning and data mining communities, some of them, previously used in decision trees and decision lists induction, can be easily adapted to cope with this objective, thereby leading to easy-to-implement (and compare) algorithms.  The next section presents a synthesis of our contribution, which is detailed in the rest of the paper.

## 2. Our Contribution

This paper is principally concerned with the theoretical and experimental study of a set of voting classifiers which we think is likely to provide an accurate answer to the simplicityaccuracy tradeoff: decision committees (DC) (Nock & Gascuel, 1995). DC is informally the Boolean multiclass extension of polynomial discriminant functions. A decision committee contains rules, each of these being a pair (monomial, vector). Each monomial is a condition that, when fired, returns its vector. After each monomial has been tested, the sum of the returned vectors is used to take the decision.  This additive fashion for combining rules is absent from classical Boolean classifiers such as Decision Trees (DT) or Decision Lists (DL). Furthermore, unlike these two latter classes, the classifier contains absolutely no ordering, neither on variables (unlike DT), nor on monomials (unlike DL). When sufficiently small DCs are built and adequate restrictions are taken, a new dimension in interpreting the classifier is obtained, whi does not exist for DT or DL. Namely, any example can stisfy more than one rule, and a DC can therefore be interpreted by means of various rule subsets (in a naive conversion of a DT or a DL into rule sets, any example satisfies exactly one rule).  Decision committees resemble or generalize other rule sets (Cohen & Singer, 199). In this paper, the authors consider DNF-shaped formulas, in which the output of a monomial is not a class (called "positive"), but a (non-negative) confidence in the classification as positive. A default class predicts the other class, called "negative" (this is a setting with two classes).  Computing the class of an observation boils down to summing the confidences of the rules it satisfies, and then deciding the positive class if the sum is greater than zero, and the negative class otherwise. Decision committees are a generalization of these formulas, in which we remove the setting's constraint (two classes) and authorize the membership prediction to arbitrary classes, thereby leading to a true voting classifier.  This voting fashion is a feature that decision committees share with decision tables (Kohavi &
Sommerfield, 1998).  However, decision tables classifiers are based on majority voting of the