where c = 2, the two classes are noted "-" (co = 0) and "+" (co = 1), and called respectively the negative and positive class. The learning sample is the union of two samples, noted LS- and LS+, containing respectively the negative and positive examples. It is worthwhile to think the positive examples as belonging to a subset of X containing all possible positive examples, usually called the target concept.

As part of our goal in machine learning, is the need to build a reliable approximation to the true classification of the examples in X, that is, a good approximation of the target concept, by using only the examples in LS .  Good approximations shall have a high accuracy over X , although we do not have access to this quantity, but rather to its estimator: a more or less reliable accuracy computable over LS . We refer the reader to standard machine learning books (Mitchell, 1997) for further considerations about this issue. A DC contains two parts:

- A set of unordered pairs (or rules) {(ti, vi)}i=1,2,... where each ti is a monomial (a conjunction of literals) over { x 1 , x 1 , x 2 , x 2 , . . , x n , x n } n (n being the number of description variables, each xj is a positive literal and each xj is a negative literal), and each vj is a vector in R c . For the sake of readability, this vectorial notation shall be kept throughout all the paper, even for problems with only two classes. One might choose to add a single real rather than a 2-component vector in that case.

- A Default Vector D in [0, 1] c. Again, in the two-class case, it is sufficient to replace D by a default class in {+, -}.
For any observation o and any monomial t i , the proposition "o satisfies t i " is denoted by o ⇒ t i . The opposite proposition "o does not satisfy t i " is denoted by "o ̸ = t i ". The classification of any observation o is made in the following way: define Vo as follows

![0_image_0.png](0_image_0.png)

The class assigned to o is then:

$$\bullet\;\arg\operatorname*{max}_{j}\,\vec{V}_{o}\;\mathrm{if}\;\big|\;\arg\operatorname*{max}_{j}\,\vec{V}_{o}\,\big|=1,\;\mathrm{and}\;$$
$\mathbf{a}\mathbf{p}\;\mathbf{w}$ ... 
- arg max j Earg max j V o D otherwise.

In other words, if the maximal component of  o is unique, then the index gives the class assigned to o. Otherwise, we take the index of the maximal component of D corresponding to the maximal component of    (ties are solved by a random choice among the maximal components).

DC contains a subclass which is among the largest classes of Boolean formulas to be PAC-learnable (Nock & Gascuel, 1995), however this class is less interesting from a practical viewpoint since rules can be numerous and hard to interpret. Nevertheless, a subclass of DC (Nock & Gascuel, 1995) presents an interesting compromise between representational power and interpretability power. In this class, which is used by WIDC, each of the vector components are restricted to {-1,0, +1} and each monomial is present at most once.