←
^
→
Computational Learning Theory
Mistake Bound Model: Find-S
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$?
José M. Vidal
.
21 of 26