Information Technology Reference
In-Depth Information
S
2
=BLOCK(
c
)
∧
BLOCK(
d
)
∧
ONTOP(
c,d
)
S
1
equals to assume that position ONTOP is not related to required concept.
S
2
equals to assume that block shape is not related to required concept. It should be
noticed that, when
x
correspond to
w
and
y
correspond to
v
, position relations
between
and I
1
are matched while shape features are not matched. On the
contrary, when
S
x
correspond to
v
and
y
correspond to
w,
shape features are
matched while position relations between
and I
1
are not matched. This
phenomenon is collision in match. In order to solve the collision, we use two
elements in
S
' to consider these two sides respectively.
The second approach is to maximize unified generalization. This algorithm is
used to find the maximum unified generalization of predicate expression. It is
similar to collision match algorithm, but the representative language it uses allow
many-to-one argument link in match.
Version space has two main shortages:
1. Lack anti-noise ability
All data-driven algorithms (include version space) are hard to handle training
instances with noise. Since concepts gotten from algorithms should meet request
of every training instance, a training instance would make a big influence.
Sometimes wrong instances make program get wrong concepts, sometimes even
no concepts. At this time H becomes empty set.
In order to solve the problem Mitchell proposed an approach to save multiple
sets of
S
G
and
S
. For example,
S
0
meets all positive instances, and
S
1
meets all
other positive instances except one,
0
is
empty set. This means that no concept meets all instances. So program finds
S
2
etc. are similar. If
G
0
exceeds
S
H
0
G
1
and
S
1
, so that we can get
H
1
. If
H
1
is empty too, it gets
H
2
.
2. Learn disjunction concept
Version space cannot discover disjunction concept. Some concepts are
disjunction form. For example, PARENT maybe father or mother. This can be
represented as PARENT(
x
)=FATHER(
x)
∨
PARENT(
x
)=MOTHER(
x
). Since
set
are conjunction form, above-mentioned algorithm cannot find
disjunction concepts.
The first solution uses representation language without disjunction connective.
It repeats many times to eliminate candidate elements so that it can find many
conjunction descriptions covered all examples.
G
and
S
Algorithm 7.2
Algorithm to Learn Disjunction Concept
1. Set
S
is initialized to include one positive instance, and set
G
is initialized to include no
description.
2. As for every negative instance, modify set
G
.
