Member Avatar for chixm8_49

Good day.

I would like to ask for a better and clearer explanation for the Find-S algorithm. You see, the one in Machine Learning book was not that clear to me and almost handouts I saw from the net rely on that book as well. Given target = <?, Cold, ?, ?, ?, Warm>, hypothesis = <0,0,0,0,0,0> and random generated example, how can I use them in a Find-S algorithm?

  • 2 Contributors
  • 3 Replies
  • 2K Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by Taywin

Dani AI

Generated

the key missing piece is the labels. Find-S only updates on positive examples, so if you know the true target concept you can label your randomly generated instances on the fly. Your target vector should align with the attribute order you listed. That means the intended target is probably <?, Cold, ?, ?, Warm, ?>, i.e., airtemp = Cold and water = Warm regardless of the other attributes. An instance is positive iff it matches those constrained positions.

You can implement Find-S by treating 0 as no-constraint-yet and generalizing only when two positive examples disagree on a feature.

# attributes: [sky, airtemp, humidity, wind, water, forecast]
h = [0, 0, 0, 0, 0, 0]

def is_positive(x, target):
    for i, t in enumerate(target):
        if t != '?' and x[i] != t:
            return False
    return True

for x in stream_of_random_examples():
    y = is_positive(x, target)
    if not y:
        continue           # Find-S ignores negatives
    for i in range(len(h)):
        if h[i] == 0:
            h[i] = x[i]
        elif h[i] != x[i]:
            h[i] = '?'
# h is the most specific hypothesis consistent with all positives seen

A tiny run shows how you converge to the corrected target:

  • x1 = [Sunny, Cold, Normal, Weak, Warm, Change] -> positive
    h = [Sunny, Cold, Normal, Weak, Warm, Change]
  • x2 = [Rainy, Cold, High, Weak, Warm, Same] -> positive
    h = [?, Cold, ?, Weak, Warm, ?]
  • x3 = [Cloudy, Cold, Normal, Strong, Warm, Same] -> positive
    h = [?, Cold, ?, ?, Warm, ?] which matches the target.

Two practical tips: as noted, verify the target order; a misaligned vector will never converge. Also, if your positives do not vary on some irrelevant feature, h will stay too specific. Keep sampling until each irrelevant attribute takes at least two different values among positives.

Recommended Answers

All 3 Replies

Member Avatar for Taywin

On another forum here, the person who asked gives a good example (which is very simple) and the person who answered gives a very clear explanation. You should be able to apply to your problem from looking at what he did. If not, I would like to see all the posible target & generated example.

Member Avatar for chixm8_49

I guess, the list of positive examples is my main problem of understanding the whole algorithm. We were not given a list of it or maybe I am missing something?

The examples are generated in random and the program counts the number of examples until hypothesis = given target (concept). The attributes used are the same in the Machine Learning book:

  • sky (Sunny, Cloudy, Rainy)
  • airtemp (Warm, Cold)
  • humidity (Normal, High)
  • wind (Strong, Weak)
  • water (Warm, Cool)
  • forecast (Same, Change)
Member Avatar for Taywin

It looks to me that your problem has more dimensions that the simple example on that forum. Though, I believe your target looks wrong to me because it does not match the given attributes you gave (in order). The reason is that the last attribute value of the given target is Warm but your last attribute in the list is forecase which has no warm value.

Anyway in your case, the positive example would be those attributes that match your current hypothesis. It would start from specific (look for the exactly the same) to general. The value in the hypothesis set is not 0 but an empty set.

Look at this on page 3, slide 13, you should see how the sample becomes positive & negative. If you already have a target, you could simply mark as negative if none of the attribute you are looking for is not matched...

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.