Information Technology Reference
In-Depth Information
There are several supplement explanations about this algorithm:
1. Understanding the set
G
and
S
. As for new instances that meet required
concepts,
is the set of necessary
conditions. For example, after the first training instance, (sm cir) is sufficient
condition. That is, small circle must meet the required concept, when program do
not know whether the large circle meets. In addition, after the second training
instance, (
S
is the set of sufficient conditions, and
G
) are necessary conditions. That is, the instance which
meets the required concept is either circle or small. When algorithm ends,
x
cir) and (sm
y
G
=
S
,
i.e. it meets the necessary and sufficient condition.
2. When learning the positive instances,
S
is generalized, and this often makes
S
enlarged. When learning the negative examples,
G
is specialized, and this often
makes
is too large which will make the
algorithm difficult to apply. Algorithm is breath-first search for the rule space
under the guide of training examples. As for large rule space, the algorithm is too
slow to accept.
G
enlarged. The scale of
G
S
7.4.2 Two improved algorithms
Basic learning algorithms of version space are very difficult to apply, so people
proposed some improved algorithms. There are two improved algorithms among
them only employ positive instance learning. They are similar to the procedure
mentioned above to modify
.
The first algorithm is collision match algorithm. It is used to learn the concept
represented by “parameterized structural representation”. In the procedure
mentioned above to modify
S
, it always do as less as possible generalization so
that it can cover new positive example. If descriptive form is predicate expression,
the procedure is equal to find the largest public sub-expression. This only needs
to eliminate the least conjunction condition. For example, set
S
S
is as follows.
S={BLOCK(
x
) BLOCK(
y
) SQUARE(
y
) RECTANGLE(
x
) ONTOP(
x,y
)}
Which means block
x
is rectangleblock
y
is square, and
x
is on
y
. If next positive
training example I 1 is as follows.
I 1 = {BLOCK( w ) BLOCK( v ) SQUARE( w ) RECTANGLE( v ) ONTOP( w, v )}
Which means block w is square, block v is rectangle, and w is on v .
Through the procedure to modify
S
, following public subset will be generated
S '={ S 1 , S 2 }
Where
S 1 =
BLOCK(
a
) BLOCK(
b
) SQUARE(
a
) RECTANGLE(
b
)
Search WWH ::




Custom Search