Analyzing the Performance of Learning Algorithms.
Abstract
We discuss the approach to the analysis of learning algorithms that we have taken in our laboratory and summarize the results we have obtained in the last few years. 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. We have looked for theoretically optimal bounds on these performance measures, and for learning algorithms that achieve these bounds. Learning problems we have examined include those for decision trees, neural networks, finite automata, conjunctive concepts on structural domains, and various classes of Boolean functions. We also worked on clustering data represented as sequences over a finite alphabet. Many of the new learning algorithms that we have developed have been tested empirically as well.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 14, 1993
- Accession Number
- ADA327588
Entities
People
- David Haussler
- Manfred K. Warmuth
Organizations
- University of California, Santa Cruz