Efficient Learning Algorithms.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 30, 1990
- Accession Number
- ADA285644
Entities
People
- David Haussler
- Manfred K. Warmuth
Organizations
- University of California, Santa Cruz