PAC learning boolean conjunctions

Question

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?

Thanks for your help!

Answer 1

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.

Also remember that in PAC learning, the learner gets to choose how many examples to see -- so you generally don't have to worry about "not getting enough examples" (as long as you need a number of examples polynomial in the number of relevant parameters).