Implementing Valiant's Learnability Theory Using Random Sets

摘要

A general learning framework which uses random sets is introduced for solving discrete-space classification problems. This framework is based on the pac-learning formalism introduced by Valiant (1984) and generalized in set-theoretic terms by Blumer, et al., (1989). The random set version of this theory is used to develop an algorithm which is a particularly efficient search scheme. This is accomplished by recasting the representational class and constructive proof presented in Valiant (1984) into random set terms and implementing it as an exhaustive search algorithm. The algorithm is a problem-specific incremental (psi) approach in that it satisfies learnability criteria for distribution-specific problems as examples are being sampled. Some theoretical and empirical analyses are presented to demonstrate the convergent pac-learnability and sample complexity of this psi-algorithm. Its performance is then tested on the multiplexor class of problems. This class has been analyzed by others as a benchmark for decision trees and genetic classifiers. Results from these test cases show that, despite using an exhaustive search, this random set implementation is computationally competitive with these more established methods (which use empirically proven heuristics). Conclusions are drawn about potential further improvements in the efficiency of this approach.