Agnostic learning of geometric patterns (extended abstract)
1 INTRODUCTION 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. We present an on-line agnostic learning algorithm for learning the class of one-dimensional geometric patterns. Since, when moving from the processed visual image to a one-dimensional pattern some key information is lost, we define a class of two-dimensional geometric patterns for which the important features from the visual image are incorporated in the geometric pattern, and show how to extend our agnostic learning algorithm to this class of two-dimensional patterns. Consider a robot designed to navigate through a large-scaled environment'. Suppose a set of key " landmarks " have already been selected (by another component of the navigation system). It is crucial that the robot be able to recognize whether or not it is in the vicinity of a given landmark from data taken at the robot's current location. We refer to this problem as the landmark matching problem. The landmark matching algorithm should run in real-time and be noise-tolerant. Next, we extend our construction to obtain an efficient agnostic learning algorithm (that tolerate classification and attribute noise) for the class of geometric patterns of arbitrary (constant) dimension d. This mapping and learning algorithm is applicable to any data rep-resentable 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 can be made to tolerate concept shift. Much work on designing landmark matching algorithms uses a pattern matching approach to match the visual image (or whatever form of data is available) to the data taken at landmark position L. The matching algorithm must determine if the robot is near L (i.e. in a small circle centered around L). Because the visual image may change significantly as small movements around L are made, the pattern matching ap preach encounters difficulties. Goldberg, Goldman and Scott [5, 7] proposed using a learning algorithm to construct an accurate hypothesis for performing landmark matching. They obtained their training data by converting the visual data into one-dimensional geometric patterns. Then by applying …