Information Technology Reference
In-Depth Information
When searching rule space, we use a possible rational set of hypothesis rule
H
is the subset of rule space. It is a segment of rule space. The subset
composed of most general elements of
.
H
H
is referred to as set
G
; the subset
composed of most specific elements of
H
is referred to as set
S
. In rule space,
H
is a segment between upper bound
G
and lower bound
S
. So set
H
can be
represented by
G
and
S
.
No description
More general
G
S
More special
Figure 7.3. Sketch map of general rule space ordering
Initial set
G
of version space is the highest point (the most general concept);
initial set
S
is points of the lowest line (positive training examples); initial set
H
is the whole rule space. In the search procedure, set
G
increasingly drops
(specialization); set
S
increasingly rises (generalization);
H
increasingly reduces.
Finally
is converged into a request concept. Several algorithms are introduced
as follows.
H
7.4.1
Candidate-elimination algorithm
Mitchell proposed an algorithm named candidate-elimination algorithm. It
represents set
H
using bound set
G
and
S
. Set
H
called version space. All concept
description in
meet all positive examples provided, and do not meet any
negative example provided.
At beginning,
H
is the whole rule space. After accepting positive training
instances, the program is generalized. Through eliminating some specific
concepts, set S rises. After accepting negative training instances, the program is
specialized. Through eliminating some general concepts, set
H
drops. Both of
them eliminate some candidate concepts. The procedure can be divided into four
steps(Mitchell, 1977).
Algorithm 7.1
Candidate-elimination Algorithm.
G
