Optimal rate concept acquisition using version spaces and genetic algorithms
Willie G. Brown · 1994
The simplicity and elegance of version space approach have made it a pedagogical landmark in area of concept acquisition. Given an appropriate description language and sufficient training data, candidate elimination algorithm is guaranteed to converge to a correctly learned concept. However, several limitations of algorithm have prevented it from receiving widespread use in practice. One of major drawbacks is that it does not use information it has already learned to direct future learning. This leads to increased, and often unnecessary, time and space complexity. Although version spaces contain sufficient information to determine the best to examine next, algorithm does not make use of this information. This work proposes a hybrid system, candidate elimination with a genetic algorithm (GA) component, which can learn concepts at an optimal rate. Using current version space, genetic algorithm can generate models of instances and calculate their effect on size of next version space. When GA finds an instance that reduces size by one-half, this is an optimal example for a learning system that does not already know concept description.