Combinatorial optimization in inductive concept learning
Local optimization algorithms, standardly used in combinatorial
optimization, can be applied in inductive concept learning.
Learning can be defined as search of the space of concept descriptions,
guided by some heuristic function. The paper presents learning with
stochastic local optimization algorithms
(based on Simulated annealing)
and deterministic local optimization algorithms
(k-opt known from solving the `travelling salesman'
problem). These algorithms and some of their combinations have been tested
within the Atris shell, and their performance
compared on different real-world machine learning problems.
The rule induction shell Atris was developed to enable simple use
of existing and adding of new optimization algorithms and
noise-handling
mechanisms, to enable simple `cross validation' experiments, experiments
with different attributes considered as class and different attribute
subsets used for learning.
The main objective of this paper is an empirical analysis of different
optimization algorithms and some of their combinations
in comparison with a decision tree learning algorithm.