Inductive Learning - Advanced Artificial Intelligence - page 274

1. Initialize the sets S and G respectively. At this time S includes all possible positive
training instances (the most specific concept), and the scale of S is too great. Initial set S
of the actual algorithm only includes the first positive training instance, and this kind of
H is not whole space.
2. Accepting a new training instance. If it is positive instance, firstly eliminate the
concept that does not cover new positive instance from G , then modify S to the most
specific result generalized from new positive instances and original elements of S (that is,
as less as possible modifying S , but S is required to cover the new positive instances). If it
is negative instances, firstly eliminate the concept that covers the new negative instance
from S , then modify G to the most general result specialized from new negative instances
and original elements of G (that is, as less as possible modifying G , but G is required not
to cover the new negative examples).
3. If G = S and it is single element set, go to step 4, otherwise go to step 2.
4. Output the concept in H (i.e. G and S ).

The following is an example. We use feature vectors to describe object.
Every object has two features: size and shape. Size of object could be large (lg)
or small (sm). Shape of object could be circle (cir), square (squ) or triangular (tri).
To let the program know the concept “circle”, this can be represented as (x, cir),
where x represents any size.
Initial set H is rule space. Set G and S are as follows respectively:

G ={( x,y )}

={(sm squ), (sm cir),(sm tri),(lg squ), (lg cir), (lg tri)}
Initial version space H is shown at figure 7.4.
The first training example is positive example (sm cir), which means that a
small circle is a circle. After modifying algorithm

S

S we can get

)}
S ={(sm cir)}

G ={( x y

(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.4. Initial version space

Figure 7.5 shows the version space after the first training instance. Four
concepts linked by arrows construct version space. These concepts meet the first