next up previous
Next: Proof of Theorem 4 Up: Appendix A Previous: Proof of Theorem 1

Proof of Theorem 3

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

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,
$\displaystyle \forall 1\leq i\leq \vert S\vert, e^+_i$ $\textstyle =$ $\displaystyle \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:
$\displaystyle \forall 1\leq i\leq \vert C\vert, e^-_i$ $\textstyle =$ $\displaystyle \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$,
    $\displaystyle \exists o \in \{1, 2, ..., \vert C\vert\}, \{s_i,s_j\} \not\subseteq c_o$ $\textstyle \wedge$ $\displaystyle \{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
    $\displaystyle \forall o \in \{1, 2, ..., \vert C\vert\}, \{s_i,s_j\} \subseteq c_o$ $\textstyle \vee$ $\displaystyle \{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,

(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$. 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
$\displaystyle \forall i\in\{1, 2, ..., \vert S\vert\}, \chi(s_i)$ $\textstyle =$ $\displaystyle \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.


next up previous
Next: Proof of Theorem 4 Up: Appendix A Previous: Proof of Theorem 1
2002 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.