Proof of Theorem 3

We use a reduction from the $NP$-Hard problem ``2-NM-Colorability'' [Kearns et al.1987]:

• Name : ``2-NM-Colorability''.
• Instance : A finite set $S=\{s_1, s_2, ..., s_{\vert S\vert}\}$ and a collection of constraints over $S$, $C=\{c_1, c_2, ..., c_{\vert C\vert}\}$, such that $\forall i\in \{1, 2, ..., \vert C\vert\}, c_i \subseteq S$.
• Question : Does there exist a 2-NM-Coloration of the elements of $S$, i.e. a function $\chi: S \rightarrow \{1,2\}$ such that
  $$\begin{eqnarray*} (\forall i \in \{1, 2, ..., \vert C\vert\}), (\exists s_k, s_l \in c_i): \chi(s_k) & \neq & \chi(s_l) \:\: ? \end{eqnarray*}$$
  
  
  
  
  

The reduction is constructed as follows : from a ``2-NM-Colorability'' instance, we build a learning sample $LS$ such that if there exists a 2-NM-Coloration of the elements of $S$, then there exists a decision committee with two rules consistent with $LS$, and, reciprocally, if there exists a decision committee with two rules consistent with $LS$, then there exists a 2-NM-Coloration of the elements of $S$. Furthermore, there never exists a decision committee with only one rule consistent with $LS$. Hence, finding the decision committee with the smallest number of rules consistent with $LS$ is at least as hard as solving ``2-NM-Colorability'', and this is intractable if $P\neq NP$.
Let $c_j$ denote the $j^{th}$ element of $C$, and $s_j$ the $j^{th}$ element of $S$. We define a set of $\vert S\vert$ Boolean variables in one to one correspondence with the elements of $S$, which we use to describe the examples of $LS$. The corresponding set of literals is denoted $\{x_1, \overline{x}_1, x_2, \overline{x}_2, ..., x_{\vert S\vert}, \overline{x}_{\vert S\vert}\}$. Our reduction is made in the two-classes framework. The sample $LS$ contains two disjoint subsets : the set of positive examples $LS^+$, and the set of negative ones $LS^-$. $LS^+$ contains $\vert S\vert$ examples, denoted by $e^+_1, e^+_2, ..., e^+_{\vert S\vert}$. We construct each positive example so that it represents an element of $S$. More precisely,

$$\forall 1\leq i\leq \vert S\vert, e^+_i = \overline{x}_i \wedge \bigwedge_{j=1, j\neq i}^{j=\vert S\vert} {\overline{x}_j} \:\:.$$ (13)

$LS^-$ contains $\vert C\vert$ examples, denoted by $e^+_1, e^+_2, ..., e^+_{\vert C\vert}$. We construct each negative example so that it encodes each of the constraints of $C$. More precisely:

$$\forall 1\leq i\leq \vert C\vert, e^-_i = \left( \bigwedge_{j : s_j \in c_i} {\overline{x}_j} \right) \wedge \left( \bigwedge_{j : s_j \not\in c_i} {x_j} \right) \:\:.$$ (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:

1. There does not exist some element of $S$ 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 $S$.
2. $\forall (i,j,k,l) \in \{1, 2, ..., \vert S\vert\}^4$ with $i \neq j$ and $k \neq l$,
   

   $$\exists o \in \{1, 2, ..., \vert C\vert\}, \{s_i,s_j\} \not\subseteq c_o \wedge \{s_k,s_l\} \not\subseteq c_o \:\:.$$ (15)

   
   
   Otherwise indeed, there would exist $(i,j,k,l) \in \{1, 2, ..., \vert S\vert\}^4$ with $i \neq j$ and $k \neq l$ such that
   

   $$\forall o \in \{1, 2, ..., \vert C\vert\}, \{s_i,s_j\} \subseteq c_o \vee \{s_k,s_l\} \subseteq c_o \:\:,$$ (16)

   
   
   and in that case, a trivial solution to ``2-NM-Colorability'' would consist in giving to $s_i$ one color and to $s_j$ the other one, and to $s_k$ one color and to $s_l$ the other one.
3. Each element of $S$ belongs to at least one constraint in $C$. Otherwise, it can be removed.
4. Each constraint contains at least two elements from $S$. Otherwise it can be removed.

$\bullet$ 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 $LS$.
$\bullet$ Suppose that there exists a decision committee $f$ with at most two rules consistent with $LS$. We now show that there exists a valid 2-NM-Coloration of the elements of $S$. 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 $LS$. 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 $S$.

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:
  
  $$\bigwedge_{j=1}^{j=\vert S\vert} {x_j} \:\:.$$
  
  

(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).

Lemma 5   $f$ contains exactly two rules.

Proof: Suppose that $f$ contains one rule, whose monomial is called $t_1$. If the default class is ``-'', all positive examples satisfy $t_1$, which is impossible by Lemma 4: the monomial would be empty, and $f$ could not be consistent. If the default class is ``+'', the negative examples are classified by $t_1$ and therefore $\Delta_1<0$. Thus, no positive example satisfies $t_1$. From Lemma 3, either $t_1=\bigwedge_{j=1}^{j=\vert S\vert} {x_j}$ and no negative example can satisfy it (impossible), or $t_1$ contains at least two negative literals, and the constraints all have in common two elements of $S$. Thus, the instance of ``2-NM-Colorability'' is trivial, which is impossible. This ends the proof of Lemma 5. $\hbox{\vrule width 0.8pt \vbox to6pt{\hrule depth 0.8pt width 5.2pt \vfill\hrule depth 0.8pt}\vrule width 0.8pt}$
We now show that the default class of $f$ is ``-''. For the sake of simplicity, we write the two monomials of $f$ by $t_1$ and $t_2$. The default class is denoted $\beta \in \{$``-'', ``+''$\}$. Making the assumption that $\beta=$``+'' implies that all negative examples must satisfy at least one monomial in $f$.

• Suppose that $\Delta_{1}<0$ and $\Delta_{2}<0$. Then, no positive example can satisfy either $t_1$ or $t_2$. From the two possibilities of Lemma 3, only the first one is valid ( $\bigwedge_{j=1}^{j=\vert S\vert} {x_j}$ cannot be satisfied by any negative example). Thus, $t_1$ and $t_2$ contain each at least two negative literals:
  

  $$\{\overline{x}_i, \overline{x}_j\} \subseteq t_1 \:\:,$$ (17)

  $$\{\overline{x}_k, \overline{x}_l\} \subseteq t_2 \:\:.$$ (18)

  
  
  We are in the second case of triviality of the instance of ``2-NM-Colorability'', since making the assumption that $f$ is consistent implies:
  

  $$\exists o \in \{1, 2, ..., \vert C\vert\}, \{s_i,s_j\} \not\subseteq c_o \wedge \{s_k,s_l\} \not\subseteq c_o \:\:.$$ (19)

  
  

• Suppose that $\Delta_{1}<0$ and $\Delta_{2}>0$. All negative examples must satisfy $t_1$. $t_1$ is forced to be monotonous since otherwise (given that $\beta=$``+'') all negative examples would share a common negative literal, thus all constraints would share a common element of $S$, and the instance of ``2-NM-Colorability'' would be trivial. $t_2$ being satisfied by at least one positive example (otherwise, $f$ 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 $\vert S\vert-1$ positive literals (we leave empty the position of the initial negative literal). Consequently, similarly for $t_1$, we can suppose that $t_2$ is monotonous. We distinguish two cases.
  • If $\vert\Delta_{1}\vert>\vert\Delta_{2}\vert$, no positive example can satisfy $t_1$. By fact 3, $t_1=\bigwedge_{j=1}^{j=\vert S\vert} {x_j}$, and no negative example can satisfy it, a contradiction ($f$ cannot be consistent).
  • If $\vert\Delta_{1}\vert\leq \vert\Delta_{2}\vert$. $t_2$ cannot be empty; therefore it contains a certain number of positive literals. Each positive example satisfying $t_2$ must also satisfy $t_1$, since otherwise $f$ is not consistent; Since $t_1$ and $t_2$ are monotonous, $t_2$ is a generalization of $t_1$, and any example satisfying $t_1$ (in particular, the negative examples) must satisfy $t_2$, a contradiction.

Therefore $\beta=$``-''. This forces all positive examples to satisfy at least one monomial of $f$. Recall that $f$ contains two monomials. Suppose that $\Delta_{1} > 0$ and $\Delta_{2}<0$. It comes $t_1=\emptyset$ (Lemma 4). All negative examples must satisfy $t_2$, and we also have $\vert\Delta_{1}\vert\leq \vert\Delta_{2}\vert$. No positive example can satisfy $t_2$, and Lemma 3 gives either $t_1=\bigwedge_{j=1}^{j=\vert S\vert} {x_j}$ (satisfied by no example, impossible) or $t_2$ contains at least two negative literals, whose corresponding elements of $S$ are shared by all constraints, and we obtain again that the instance of ``2-NM-Colorability'' is trivial.
Therefore, $\Delta_{1} > 0$ and $\Delta_{2}>0$, and each monomial is satisfied by at least one positive example. $f$ 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 $f$ is again monotonous [Kearns et al.1987]. Then, since each positive example satisfies at least one monomial ($\beta=$``-''), then for all variable, there exists a monomial which does not contain the corresponding positive literal. The 2-Coloration is then

$$\forall i\in\{1, 2, ..., \vert S\vert\}, \chi(s_i) = \min_{j \in \{1, 2\}} {\{j : x_i \not\in t_j\}} \:\:.$$ (20)

Could this be invalid ? That would mean that there exists a constraint $c_i$ such that $\forall s_j \in c_i, \chi(s_j)=K=cst$. This would mean that the corresponding negative example satisfies $t_K$, a contradiction [Kearns et al.1987]. This ends the proof of Theorem 3.