Query construction, entropy, and generalization in neural-network models
Author:
- 1 May 1994
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 49 (5) , 4637-4651
Abstract
We study query construction algorithms, which aim at improving the generalization ability of systems that learn from examples by choosing optimal, nonredundant training sets. We set up a general probabilistic framework for deriving such algorithms from the requirement of optimizing a suitable objective function; specifically, we consider the objective functions entropy (or information gain) and generalization error. For two learning scenarios, the high-low game and the linear perceptron, we evaluate the generalization performance obtained by applying the corresponding query construction algorithms and compare it to training on random examples. We find qualitative differences between the two scenarios due to the different structure of the underlying rules (nonlinear and ‘‘noninvertible’’ versus linear); in particular, for the linear perceptron, random examples lead to the same generalization ability as a sequence of queries in the limit of an infinite number of examples. We also investigate learning algorithms which are ill matched to the learning environment and find that, in this case, minimum entropy queries can in fact yield a lower generalization ability than random examples. Finally, we study the efficiency of single queries and its dependence on the learning history, i.e., on whether the previous training examples were generated randomly or by querying, and the difference between globally and locally optimal query construction.Keywords
This publication has 20 references indexed in Scilit:
- The statistical mechanics of learning a ruleReviews of Modern Physics, 1993
- Optimal generalization in perceptionsJournal of Physics A: General Physics, 1992
- Information-Based Objective Functions for Active Data SelectionNeural Computation, 1992
- Selecting examples for perceptronsJournal of Physics A: General Physics, 1992
- Query-based learning applied to partially trained multilayer perceptronsIEEE Transactions on Neural Networks, 1991
- Neural net algorithms that learn in polynomial time from examples and queriesIEEE Transactions on Neural Networks, 1991
- Improving a Network Generalization Ability by Selecting ExamplesEurophysics Letters, 1990
- Inference and sequential designBiometrika, 1985
- Developments in the Design of Experiments, Correspondent PaperInternational Statistical Review, 1982
- Optimal Design1980