Accession Number : ADA231888


Title :   The Design and Analysis of Efficient Learning Algorithms


Descriptive Note : Doctoral thesis


Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE


Personal Author(s) : Schapire, Robert E


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a231888.pdf


Report Date : Jan 1991


Pagination or Media Count : 191


Abstract : 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.


Descriptors :   *ALGORITHMS , RESISTANCE , ROBOTS , LOW STRENGTH , LEARNING MACHINES , NOISE , LEARNING , MODELS , EFFICIENCY


Subject Categories : Cybernetics


Distribution Statement : APPROVED FOR PUBLIC RELEASE