0
$\begingroup$

I'm reading about concept learning from Mitchell, and I've been looking at the Candidate-Elimination algorithm for identifying a hypothesis to fit a set of training data with binary labels

The algorithm

Initialise the 'specific boundary', $S$, as the set of most specific hypotheses. (Initially, this will be $\{<\emptyset, \emptyset,...,\emptyset>\}$, where $\emptyset$ indicates that no value of that attribute indicates a positive classification.)

Initialise the 'general boundary', $G$, as the set of most general hypotheses. (Initially, this will be $\{<?, ?,...,?>\}$, where $?$ indicates that any value of that attribute indicates a positive classification.)

for each training instance:
    if label is positive:
        Generalise S
    elif label is negative:
        Specialise G

Example

Consider the following two instances:

$x_1=<sun, warm, normal, strong, warm, same>, positive$

$x_2 = <sun, warm, high, strong, warm, same>, positive$

$x_3 = <rain, cold, high, strong, warm, change>, negative$

(The first attribute is one of 3 possibilities, the rest are 1 of 2.)

The example can be found on page 33, section 2.5.5 here: https://www.cs.ubbcluj.ro/~gabis/ml/ml-books/McGrawHill%20-%20Machine%20Learning%20-Tom%20Mitchell.pdf

So we have

$$S_0=<\emptyset, \emptyset, \emptyset, \emptyset, \emptyset, \emptyset >$$

$$G_0=<?, ?, ?, ?, ?, ?>$$

The first instance is positive, so we want to generalise the specific boundary and leave the general boundary. So $$S_1=<sun, warm, normal, strong, warm, same>$$ $$G_1=<?, ?, ?, ?, ?, ?>$$ This makes sense to me. The second example is also positive, so we repeat this again: $$S_2=<sun, warm, ?, strong, warm, same>$$ $$G_2=<?, ?, ?, ?, ?, ?>$$ This also makes sense to me.

The next part (when we approach a negative instance) is what I'm struggling to understand and need help with. We have a negative instance, so we leave $S_2$ unchanged, but we want to specialise $G_2$ to give a new $G_3$, which is:

$$G_3=\{<sun, ?, ?, ?, ?, ?>, <?, warm, ?, ?, ?, ?>, <?, ?, ?, ?, ?, same>\}$$

My problem

Now, I can definitely appreciate that all elements of $G_3$ are less general than those in $G_2$, but I am struggling to understand why the other 3 possibilities aren't included in $G_3$. The book offers the following explanation:

Given that there are six attributes that could be specified to specialize $G_2$, why are there only three new hypotheses in $G_3$? For example, the hypothesis $h = (?, ?, Normal, ?, ?, ?)$ is a minimal specialization of $G_2$ that correctly labels the new example as a negative example, but it is not included in $G_3$. The reason this hypothesis is excluded is that it is inconsistent with the previously encountered positive examples. The algorithm determines this simply by noting that $h$ is not more general than the current specific boundary, $S_2$.

I don't understand "$h$ is not more general than the current specific boundary". How is $h=<?, ?, ?, strong, ?, ?>$ not more general than $h=<sun, warm, ?, strong, warm, same>$, but $h=<sun, ?, ?, ?, ?, ?>$ is more general? This seems to me like two of the exact same situation.

$\endgroup$
1
$\begingroup$

When the third input is entered, including h = (sun,?,?,?,?,?) without including h = (?,?,?, Strong,?,?) is a separate matter from general.

This is determined by whether or not it is consistent for the third input.

The h in the existing G is consistent hypothesis for positive input.

However, since the third input is a negative input, the h contained in G must be inconsistent to the input.

That is, G is updated with a set of hypothesis that does not satisfy the third input.

First, since G2 = (?,?,?,?,?,?), G3 is updated from G2 with only one step specific (only one ? is replaced by value).

Also, because the third input, x3 = (rain, cold, high, strong, warm, change), the hypothesis candidates that can be included in G3 are:

(sunny (not rain),?,?,?,?,?)

(cloudy (not rain),?,?,?,?,?)

(?, warm,?,?,?,?)

...

(?,?,?, weak (not strong),?,?)

...

(?,?,?,?,?, same)

Now we have to choose the hypothesis that can actually be included in the G3 among these hypothesis candidates.

The hypothesis that can be included in G3 is a more general version of S2.

Therefore, only the following list of hypothesis satisfying S2 = (sunny, warm,?, Strong, warm, same) can be included in G3.

(sunny,?,?,?,?,?)

(?, warm,?,?,?,?)

(?,?,?,?,?, same)

I have uploaded more details about the candidate elimination learning algorithm on my github homepage.

https://github.com/pod3275/Concept-Learning-Candidate-Elimination

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.