We use a reduction from the -Hard problem ``2-NM-Colorability'' [Kearns et al.1987]:
Name : ``2-NM-Colorability''.
Instance : A finite set
and a collection of constraints over ,
, such that
.
Question : Does there exist a 2-NM-Coloration of the elements of , i.e. a function
such that
The reduction is constructed as follows : from a ``2-NM-Colorability'' instance, we build a learning sample such that if there exists a 2-NM-Coloration of the elements of , then there exists a decision committee with two rules consistent with , and, reciprocally, if there exists a decision committee with two rules consistent with , then there exists a 2-NM-Coloration of the elements of . Furthermore, there never exists a decision committee with only one rule consistent with . Hence, finding the decision committee with the smallest number of rules consistent with is at least as hard as solving ``2-NM-Colorability'', and this is intractable if .
Let denote the element of , and the element
of . We define a set of Boolean variables in one to one
correspondence with the elements of , which we use to describe the examples
of . The corresponding set of literals is denoted
. Our reduction is
made in the two-classes framework. The sample contains two disjoint subsets : the set of positive examples , and the set of negative ones . contains examples, denoted by
. We construct each positive example so that it represents an element of . More precisely,
(13)
contains examples, denoted by
. We construct each negative example so that it encodes each of the constraints of . More precisely:
(14)
Without loss of generality, we make four assumptions on the instance of ``2-NM-Colorability'' due to the fact that it is not trivial:
There does not exist some element of present in all constraints. In this case indeed, the trivial coloration consists in giving to one of such elements one color, and the other color to all other elements of .
with and ,
(15)
Otherwise indeed, there would exist
with and such that
(16)
and in that case, a trivial solution to ``2-NM-Colorability'' would consist in giving to one color and to the other one, and to one color and to the other one.
Each element of belongs to at least one constraint in
. Otherwise, it can be removed.
Each constraint contains at least two elements from . Otherwise it
can be removed.
Suppose there exists a solution to ``2-NM-Colorability''. We build the DNF with two monomials of [Kearns et al.1987] consistent with the examples. Then, we build two rules by associating the two monomials to some (arbitrary) positive value. The default class is ``-''. This leads to a decision committee with two rules consistent with .
Suppose that there exists a decision committee with at most two rules consistent with . We now show that there exists a valid 2-NM-Coloration of the elements of . We first show three lemmas which shall be used later on. Then, we show that the decision committee is actually equivalent to a DNF with two monomials consistent with . We conclude by using previous results [Kearns et al.1987] on how to transform this DNF into a valid 2-NM-Coloration of the elements of .
Lemma 3
If a monomial is not satisfied by any positive example,
either it contains at least two negative literals, or
it is the monomial containing all positive literals:
(Proof straightforward).
Lemma 4
If a monomial is satisfied by all positive examples, it is empty.
(Indeed, for any variable, there exist two positive examples having the corresponding positive literal, and the corresponding negative literal).
Proof: Suppose that contains one rule, whose monomial is called . If the default class is ``-'', all positive examples satisfy , which is impossible by Lemma 4: the monomial would be empty, and could not be consistent. If the default class is ``+'', the negative examples are classified by and therefore . Thus, no positive example satisfies . From Lemma 3, either
and no negative example can satisfy it (impossible), or contains at least two negative literals, and the constraints all have in common two elements of . Thus, the instance of ``2-NM-Colorability'' is trivial, which is impossible. This ends the proof of Lemma 5.
We now show that the default class of is ``-''. For the sake of simplicity, we write the two monomials of by and . The default class is denoted ``-'', ``+''. Making the assumption that ``+'' implies that all negative examples must satisfy at least one monomial in .
Suppose that and . Then, no positive example
can satisfy either or . From the two possibilities of Lemma 3, only the first one is valid (
cannot be satisfied by any negative example). Thus, and contain each at least two negative literals:
(17)
(18)
We are in the second case of triviality of the instance of ``2-NM-Colorability'', since making the assumption that is consistent implies:
(19)
Suppose that and . All negative examples must satisfy . is forced to be monotonous since otherwise (given that ``+'') all negative examples would share a common negative literal, thus all constraints would share a common element of , and the instance of ``2-NM-Colorability'' would be trivial. being satisfied by at least one positive example (otherwise, would be equivalent to a single-rule decision committee, and we fall in the contradiction of Lemma 5), it contains at most one negative literal. If it contains exactly one negative literal, it is satisfied by exactly one positive example, and we can replace it by the monotonous monomial with positive literals (we leave empty the position of the initial negative literal). Consequently, similarly for , we can suppose that is monotonous. We distinguish two cases.
If
, no positive example can satisfy . By fact 3,
, and no negative example can satisfy it, a contradiction ( cannot be consistent).
If
. cannot be empty; therefore it contains a certain number of positive literals. Each positive example satisfying must also satisfy , since otherwise is not consistent; Since and are monotonous, is a generalization of , and any example satisfying (in particular, the negative examples) must satisfy , a contradiction.
Therefore ``-''. This forces all positive examples to satisfy at least one monomial of . Recall that contains two monomials. Suppose that
and
. It comes (Lemma 4). All negative examples must satisfy , and we also have
. No positive example can satisfy , and Lemma 3 gives either
(satisfied by no example, impossible) or contains at least two negative literals, whose corresponding elements of are shared by all constraints, and we obtain again that the instance of ``2-NM-Colorability'' is trivial.
Therefore, and , and each monomial is satisfied by at least one positive example. is thus equivalent to a DNF with the same two monomials, and we can use a previous solution [Kearns et al.1987] to build a valid 2-NM-Coloration. First, we can suppose that is again monotonous [Kearns et al.1987]. Then, since each positive example satisfies at least one monomial (``-''), then for all variable, there exists a monomial which does not contain the corresponding positive literal. The 2-Coloration is then
(20)
Could this be invalid ? That would mean that there exists a constraint such that
. This would mean that the corresponding negative example satisfies , a contradiction [Kearns et al.1987]. This ends the proof of Theorem 3.