ABSTRACT
This chapter asks whether good learning algorithms can be designed by maximizing their coverage. It extends a previous upper bound on the coverage of any Boolean concept learning algorithm and describes two algorithms— Multi-Balls and Large-Ball—whose coverage approaches this upper bound. The last problem investigated in the chapter is the evaluation of the coverage of existing learning algorithms. Due to the difficulty of performing coverage analysis for empirical algorithms, one may consider measuring the coverage experimentally by running learning algorithms on every possible training sample. The chapter suggests that an important design criterion for learning algorithms should be the coverage of the algorithm. It presents the Multi-Balls algorithm and showed that it can achieve optimal coverage with a sample size that is within a constant factor of optimal. For comparison, let people compute the coverage obtained by the balls approach under the same conditions of experiments.
