The Design And Analysis Of Efficient Learning Algorithms

The Design and Analysis of Efficient Learning Algorithms

This thesis explores various theoretical aspects of machine learning with particular emphasis on techniques for designing and analyzing computationally efficient learning algorithms. Many of the results in this thesis are concerned with a model of concept learning proposed by Valiant. The thesis begins in Chapter 2 with a proof that any 'weak' learning algorithm in this model that performs slightly better than random guessing can be converted into one whose error can be made arbitrarily small. Several interesting consequences of this result are also described. Chapter 3 next explores in detail a simple but powerful technique for discovering the structure of an unknown read-once formula from random examples. An especially nice feature of this technique is its powerful resistance to noise. Chapter 4 considers a realistic extension of the PAC model to concepts that may exhibit uncertain or probabilistic behavior. A range of techniques are explored for designing efficient algorithms for learning such probabilistic concepts. In the last chapter, we present new algorithms for inferring an unknown finite-state automation from its input-output behavior. This problem is motivated by that faced by a robot in unfamiliar surroundings who must, through experimentation, discover the structure of its environment.

The Design and Analysis of Efficient Learning Algorithms

This monograph describes results derived from the mathematically oriented framework of computational learning theory.

Scientific and Technical Aerospace Reports