<p>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.</p>

<p>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).</p>

CC BY-SA 2.5
2010-09-17T12:47:40.663Z
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.
Anthony Labarre
CC BY-SA 2.5
2010-09-17T13:10:20.367Z
Yea, each example uses all variables. The trick is to figure out which variables are relevant in the target conjunction.
Lev Reyzin
CC BY-SA 2.5
2010-09-17T12:24:48.427Z
2010-09-17T13:35:16.243Z
2010-09-17T13:35:16.243Z
Lev Reyzin
<p><a href="http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&amp;tid=7334" rel="nofollow">Kearns and Vazirani</a> (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 <strong>positive</strong> 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$.</p>

<p>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?</p>

<p>Thanks for your help!</p>

CC BY-SA 2.5
2010-09-17T12:04:18.320Z
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
CC BY-SA 2.5
2010-09-17T12:50:18.350Z
Each $a$ describes a satisfying assignment, so $a_i$ means "set variable $x_i$ to value $a_i$".
Anthony Labarre
<lg.learning>
PAC learning boolean conjunctions
Anthony Labarre
# PAC learning boolean conjunctions

(Asked by: username_0 on 2010-09-17)

[Kearns and Vazirani](http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=7334) (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!

**Tags:** lg.learning

> **Comments:**
> **username_1**: 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.  
> **username_0**: Each $a$ describes a satisfying assignment, so $a_i$ means "set variable $x_i$ to value $a_i$".  

---

## 1 answers

### Answer by username_2 on 2010-09-17. Score: 9 | Accepted answer

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

> **Comments:**
> **username_0**: 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.  
> **username_2**: Yea, each example uses all variables. The trick is to figure out which variables are relevant in the target conjunction.  

---

