Minimum number of training examples for Find-S/Candidate Elimination algorithms?
- by Rich
Consider the instance space consisting of integer points in the x, y plane, where 0 = x, y = 10, and the set of hypotheses consisting of rectangles (i.e. being of the form (a = x = b, c = y = d), where 0 = a, b, c, d = 10).
What is the smallest number of training examples one needs to provide so that the Find-S algorithm perfectly learns a particular target concept (e.g. (2 = x = 4, 6 = y = 9))?
When can we say that the target concept is exactly learned in the case of the Find-S algorithm, and what is the optimal query strategy?
I'd also like to know the answer w.r.t Candidate Elimination.
Thanks in advance.