Information Technology Reference
In-Depth Information
training instance, and no other concepts do. In actual algorithm this is taken as
initial version space, not in Figure 7.4.
(x y)
(sm y) (lg y) (x squ) (x cir) (x tri)
(sm squ) (lg squ) (sm cir) (lg cir) (sm tri) (lg tri)
Figure 7.5. Version space after the first training example
The second training instance is negative example (lg tri), which means that a
large triangle is not a circle. This step specializes the set
G
, and it can get:
G
={(
x
cir), (sm
y
)}
={(sm cir)}
Figure 7.6 shows the version space after the second training instance. At this
time
S
only includes three concepts, which meet the previous concept, but do not
meet all concepts of this negative instance.
(x y)
H
(sm y) (lg y) (x squ) (x cir) (x tri)
(sm squ)(lg squ) (sm cir) (lg cir) (sm tri) (lg tri)
Figure 7.6. Version space after the second training example
The third training instance is positive instance (lg cir), which means that large
circle is a circle. This step firstly eliminates the concepts that do not meet the
positive instance, and then generalizes
S
and the positive instance. It gets:
G
={(
x
cir)}
cir)}
The algorithm ends at this time, and outputs the concept (
S
={(
x
x
cir).
