# PAC learning boolean conjunctions

Kearns and Vazirani (chapter 1) describe an efficient algorithm for PAC learning conjunctions of boolean variables $x_1, x_2, \ldots, x_n$, which starts with the hypothesis $$h=x_1\wedge\overline{x_1}\wedge x_2\wedge\overline{x_2}\cdots x_n\wedge\overline{x_n},$$ and, on each call to an oracle that returns a positive example $a$, removes literals from $h$ to make it consistent with $a$. That is, if $a_i=0$, then you remove $x_i$ from $h$, otherwise you remove $\overline{x_i}$ from $h$.

However, if we don't receive enough examples, $h$ will still be unsatisfiable -- as it was at the beginning. So what are we supposed to do in this case? Remove some "problematic" literals at random?

• How does each $x_i$ get associated to the matching $a_i$? I don't understand what is being learnt, but your idea is equivalent to adding noise to your sample set, which must be a bad idea. Truncating all the inconsistent pairs sounds better. – Charles Stewart Sep 17 '10 at 12:04
• Each $a$ describes a satisfying assignment, so $a_i$ means "set variable $x_i$ to value $a_i$". – Anthony Labarre Sep 17 '10 at 12:50
The first positive example will remove enough literals so that the conjunction will become satisfiable. For example if the first positive example is $x_1\overline{x_2}x_3$ this removes $\overline{x_1}$, $x_2$ and $\overline{x_3}$. So the only time you will end up with an unsatisfiable clause is if you get only negative examples, which is okay, as the correct thing to do is to classify everything as negative anyway.