Implementation of Valiant's learnability theory using random sets.

摘要

Valiant's theory of learnability is recast into random set terms and implemented in an efficient computer learning algorithm. A theoretical and empirical analysis is presented which improves the bounds on the number of examples needed to learn such sets. A general purpose algorithm using these bounds is then described. This algorithm is tested on the multiplexor problem analyzed by others as a benchmark for decision tree and genetic algorithms. Results for this problem show that a set-theoretic implementation of Valiant's theory is computationally competitive with these more established methods. Conclusions are drawn about potential further improvements in the efficiency of Valiant's approach.