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!

  • $\begingroup$ 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. $\endgroup$ Sep 17, 2010 at 12:04
  • $\begingroup$ Each $a$ describes a satisfying assignment, so $a_i$ means "set variable $x_i$ to value $a_i$". $\endgroup$ Sep 17, 2010 at 12:50

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

  • $\begingroup$ My bad, their example at the beginning of that section led me to believe that the positive examples did not necessarily use all available variables. $\endgroup$ Sep 17, 2010 at 12:47
  • $\begingroup$ Yea, each example uses all variables. The trick is to figure out which variables are relevant in the target conjunction. $\endgroup$
    – Lev Reyzin
    Sep 17, 2010 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.