Important Representation

Important Representation

1. ? indicates that any value is acceptable for the attribute.

2. Specify a single required value ( e.g., Cold ) for the attribute.

3. Φ indicates that no value is acceptable.

4. The most general hypothesis is represented by: {?, ?, ?, ?, ?, ?}

5. The most specific hypothesis is represented by: {ϕ, ϕ, ϕ, ϕ, ϕ, ϕ}

Steps involved in S

1. Initialize h to the most specific hypothesis in H [ H = {ϕ, ϕ, ϕ, ϕ, ϕ, ϕ}

2. For each positive training instance x
For each attribute constraint ai, in h.
If the constraint ai, is satisfied by x.
Then do nothing.
Else replace a, in h by the next more general constraint that is satisfied by x.

3. Output hypothesis h

Version spaces and the candidate elimination algorithm Concept learning: Concept learning is basically learning task of the machine (Learn by Train data) General Hypothesis: Not Specifying features to learn the machine. G = {‘?’, ‘?’,’?’,’?’…}: Number of attributes Specific Hypothesis: Specifying features to learn machine (Specific feature)

S= {‘pi’,’pi’,’pi’…}: Number of pi depends on number of attributes. Version Space: It is intermediate of general hypothesis and Specific hypothesis. It not only just written one hypothesis but a set of all possible hypothesis based on training data-set.

Algorithm:

Step 2: Initialize General Hypothesis and Specific Hypothesis.
Step 3: For each training example.
Step 4: If example is positive example.
if attribute_value == hypothesis_value:
Do nothing
else:
replace attribute value with '?' (Basically generalizing it)
Step 5: If example is Negative example
Make generalize hypothesis more specific.

Algorithmic steps:
Initially :
G = [[?, ?, ?, ?, ?, ?], [?, ?, ?, ?, ?, ?], [?, ?, ?, ?, ?, ?],
[?, ?, ?, ?, ?, ?], [?, ?, ?, ?, ?, ?], [?, ?, ?, ?, ?, ?]]
S = [Null, Null, Null, Null, Null, Null]
For instance 1 : <'sunny','warm','normal','strong','warm ','same'> and positive output.
G1 = G
S1 = ['sunny','warm','normal','strong','warm ','same']
For instance 2 : <'sunny','warm','high','strong','warm ','same'> and positive output.
G2 = G
S2 = ['sunny','warm',?,'strong','warm ','same']
For instance 3 : <'rainy','cold','high','strong','warm ','change'> and negative output.
G3 = [['sunny', ?, ?, ?, ?, ?], [?, 'warm', ?, ?, ?, ?], [?, ?, ?, ?, ?, ?],
[?, ?, ?, ?, ?, ?], [?, ?, ?, ?, ?, ?], [?, ?, ?, ?, ?, 'same']]
S3 = S2
For instance 4 : <'sunny','warm','high','strong','cool','change'> and positive output.
G4 = G3
S4 = ['sunny','warm',?,'strong', ?, ?]

Output:

G = [['sunny', ?, ?, ?, ?, ?], [?, 'warm', ?, ?, ?, ?]]
S = ['sunny','warm',?,'strong', ?, ?]