Instances drawn at random from $X$ according to
distribution $\cal{D}$
Learner must classify each instance before receiving correct
classification from teacher.
Consider Find-S when $H=$ conjunction of boolean
literals.
Initialize $h$ to the most specific hypothesis $l_{1} \wedge \neg l_{1} \wedge l_{2} \wedge \neg l_{2}
\ldots l_{n} \wedge \neg l_{n}$
For each positive training instance $x$, remove from $h$ any literal that is not satisfied by $x$
Output hypothesis $h$.
How many mistakes before converging to correct $h$?
$n+1$. The first hypothesis eliminates $n$ terms,
each subsequent mistake will eliminate at least one more
term.