Have Geek Brain

Minimum number of training examples for Find-S / Candidate Elimination algorithms?

Consider a space of instances consisting of integer points in the x, y plane, where 0 ≤ x, y ≤ 10, and a set of hypotheses consisting of rectangles (i.e. having the form (a ≤ x ≤ b, c ≤ y ≤ d) , where 0 ≤ a, b, c, d ≤ 10).

What is the smallest number of training examples to provide for the Find-S algorithm to perfectly learn a specific target concept (for example, (2 ≤ x ≤ 4, 6 ≤ y ≤ 9))? When can it be said that the target concept is accurately learned in the case of the Find-S algorithm and what is the optimal query strategy?

I would also like to know the answer wrt Candidate Elimination.

Thanks in advance.

+2


a source to share


2 answers


You need two positive examples: (2.6) (2 <= x <= 2.6 <= y <= 6) and then (4.9) (2 <= x <= 4, 6 <= y <= 9) This is done by S and this is the end of the learn / learn answer with FIND-S

With the candidate eliminated, we must give negative examples to assemble the set G. We need four negative examples to define the four bounds of the rectangle:

  • G starts like (-Inf <= x <= Inf, -Inf <= y <= Inf)

Add (3,5) - and we get a hypothesis:

  • (- Inf <= x <= Inf, 6 <= y <= Inf)

Add (3.10) -

  • (- Inf <= x <= Inf, 6 <= y <= 9)


Add (1.7) -

  • (2 <= x <= Inf, 6 <= y <= 9)

Add (5.7) -

  • (2 <= x <= 4, 6 <= y <= 9)

So now S = G = {(2 <= x <= 4, 6 <= y <= 9)}. As S = G, he learned the concept well. I have seen this question in different formats. Replace -Inf with 0 and Inf with 10 if it specifies the problem area as such.

This is the best way to apply for training. The worst order is to run the G set first, since you will create four different candidate hypotheses that will merge to three with the second example, and then merge with one with the third example. It is helpful to illustrate CE with a tree, as in Mitchell's book, and perhaps jot down a hypothesis graph next to each.

This answer is confirmed here: http://ssdi.di.fct.unl.pt/scl/docs/exercises/Clemens%20Dubslaff%20hm4.pdf

+2


a source


Assuming all ranges a ≤ x ≤ b

and a

and and b

are integers, then ...

In the one-dimensional case (x only) there would be 4 samples (a-1, a, b, b + 1) that would prove it.



If you expand this to 2 dimensions (x and y), it should be 16 samples which are listed above as x, and (c-1, c, d, d + 1) for y with all possible combinations.

Please correct me if I don't understand the problem.

0


a source






More articles:


All Articles