Stochastic search in inductive concept learning
Concept learning can be viewed as search of the space of
concept descriptions. The hypothesis language determines the search space.
In standard inductive learning algorithms, the structure of the search space
is determined by generalization/specialization operators. Algorithms perform
locally optimal search by using a hill-climbing and/or a
beam-search strategy. To overcome this limitation, concept learning can be
viewed as stochastic search of the space of concept descriptions.
The proposed stochastic search method is based on simulated annealing
which is known as a successful means for solving combinatorial optimization
problems. The stochastic search method, implemented in a rule learning
system ATRIS, is based on a compact and efficient
representation of the problem and the appropriate operators for
structuring the search space. Furthermore, by heuristic pruning of the
search space, the method enables also handling of
imperfect data. The paper introduces the stochastic search method,
describes the ATRIS learning algorithm and gives results of
the experiments.