The design and analysis of efficient learning algorithms

Abstract

Many of the results in this thesis are concerned with the so-called distribution-free or probably approximately correct (PAC) model of learning proposed by Valiant. In this model, the learner tries to identify an unknown concept based on randomly chosen examples of the concept. Examples are chosen according to an unchanging but unknown and arbitrary distribution on the space of instances. Following a brief introduction, this thesis begins in Chapter 2 with a study of the problem of improving the accuracy of a hypothesis output by a learning algorithm in this model. In particular, it is shown that any weak learning algorithm that performs just slightly better than random guessing can be converted into one whose error can be made arbitrarily small. Among the many consequences of this result is a technique for converting any PAC-learning algorithm into one that is highly space efficient. In Chapter 3, we next explore in detail a simple but seemingly powerful technique for discovering the of an unknown read-once formula from random examples. The method is based on sampling of the target formula's statistical behavior under various perturbations of the underlying instance-space distribution. An especially nice feature of this technique is its powerful resistance to noise. We next consider in Chapter 4 a realistic extension of the PAC model to concepts that may exhibit uncertain or probabilistic behavior. While building on the recent results of Haussler on the sample complexity of learning in probabilistic settings, this chapter focuses primarily on the design of efficient algorithms for learning probabilistic concepts. This work also extends many of the results in the standard PAC model to the new probabilistic model. In the last chapter, we present new algorithms for inferring an unknown finite-state automaton from its input-output behavior. This problem is motivated by the problem faced by a robot in unfamiliar surroundings who must, through experimentation, discover the structure of its environment. Some of our algorithms are based on Angluin's algorithm for learning finite-state automata. We also present superior algorithms for the special class of permutation automata. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.) (Abstract shortened with permission of school.)