A theoretical and empirical study of a noise-tolerant algorithm to learn geometric patterns.

Sally A. Goldman and Stephen D. Scott. A theoretical and empirical study of a noise-tolerant algorithm to learn geometric patterns. In Proceedings of ICML '96: The 13th International Conference on Machine Learning, pages 191–199, Bari, Italy, July 1996.
Abstract
70Kb compressed PostScript
Slides:

Colloquium at the Computer Science Department of the University of Nebraska. October 29, 1996. (76Kb compressed PostScript)
ICML '96 talk (57Kb compressed PostScript)
1996 Graduate Research Review, Department of Computer Science, Washington University. (40Kb compressed PostScript)

Abstract

Developing the ability to recognize a landmark from a visual image of a robot's current location is a fundamental problem in robotics. We describe a way in which the landmark matching problem can be mapped to that of learning a one-dimensional geometric pattern. We present an efficient noise-tolerant algorithm (designed using the statistical query model) to PAC-learn the class of one-dimensional geometric patterns. Then we report results from an initial empirical study of our algorithm that provides at least some evidence that statistical query algorithms may be valuable for use in practice.

Keywords: Noise-tolerant PAC-learning, statistical query model, landmark matching problem

To Stephen D. Scott's home page

Last modified 06 June 2000.