To Stephen D. Scott's home page
Abstract
Goldberg, Goldman, and Scott demonstrated how the problem of recognizing a landmark from a one-dimensional visual image can be mapped to that of learning a one-dimensional geometric pattern and gave a PAC algorithm to learn that class. In this paper, we present an efficient on-line agnostic learning algorithm for learning the class of constant-dimension geometric patterns. Our algorithm can tolerate both classification and attribute noise. By working in higher dimensional spaces we can represent more features from the visual image in the geometric pattern. Our mapping of the data to a geometric pattern, and our hence our learning algorithm, is applicable to any data representable as a constant-dimensional array of values, e.g. sonar data, temporal difference information, or amplitudes of a waveform. To our knowledge, these classes of patterns are more complex than any class of geometric patterns previously studied. Also, our results are easily adapted to learn the union of fixed-dimensional boxes from multiple-instance examples. Finally, our algorithms are tolerant of concept shift.Keywords: Learning geometric patterns, agnostic learning, landmark matching problem, Winnow, virtual weights, multiple-instance examples, concept shift, robot navigation
To Stephen D. Scott's home page
Last modified 06 June 2000.