Accession Number : ADA285644

Title :   Efficient Learning Algorithms.

Descriptive Note : Rept. for 1 Oct 89-30 Sep 90,

Corporate Author : CALIFORNIA UNIV SANTA CRUZ

Personal Author(s) : Haussler, David ; Warmuth, Manfred K.

Report Date : 30 SEP 1990

Pagination or Media Count : 16

Abstract : We have worked on refining and generalizing the PAC learning model introduced by Valiant. Measures of performance for learning algorithms that we have examined include computational complexity, sample complexity, probability of misclassification (learning curves) and worst case total number of misclassifications or hypothesis updates. In some cases we have been able to give theoretically optimal bounds on these performance measures, and exhibit learning algorithms that achieve these bounds. Learning problems we have examined include those for decision trees and decision lists, neural networks, finite automata, hidden Markov models, conjunctive concepts on structural domains, and various classes of Boolean functions. We have developed new techniques for boosting the accuracy of learning algorithms, further explored the relationship between learning and data compression, developed and analyzed new learning algorithms based on weighted majority voting techniques, and studied the problems of learning a probability distribution, learning multivalued functions, and learning stochastic, functions.

Descriptors :   *LEARNING MACHINES, *ALGORITHMS, OPTIMIZATION, NEURAL NETS, DATA COMPRESSION, AUTOMATA, ARTIFICIAL INTELLIGENCE, COMPUTATIONS, ACCURACY, LEARNING CURVES, HYPOTHESES, MARKOV PROCESSES, PROBABILITY DISTRIBUTION FUNCTIONS, APPROXIMATION(MATHEMATICS).

Subject Categories : Cybernetics

Distribution Statement : APPROVED FOR PUBLIC RELEASE