Learning from Examples and Generalization
J. Dente
Laboratorio de Mecatronica, Instituto Superior Tecnico,
Av. Rovisco Pais, 1096 Lisboa Codex, Portugal
R. Vilela Mendes
CERN, Theoretical Division,
CH-1211, Geneve 23, Switzerland
Abstract
We analyze the issue of generalization in systems that learn from examples as a problem of representation of functions in finite fields. It is shown that it is not possible to design algorithms with uniformly good generalization properties in the space of all functions. Therefore the problem of achieving good generalization properties becomes meaningful only if the functions being studied belong to restricted classes.
We then propose the implementation of systems endowed with several distinct (biased) strategies, allowing the exploration and identification of the functional classes of learning problems. Two such strategies (polynomial learning and weighed majority rule) are developed and tested on the problems of even-odd and two-or-more clusters.
