Learning One-Dimensional Geometric Patterns Under One-Sided Random Misclassification Noise

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 consider the problem of PAC-learning the concept class of geometric patterns where the target geometric pattern is a configuration of k points on the real line. Each instance is a configuration of n points on the real line, where it is labeled according to whether or not it visually resembles the target pattern. To capture the notion of visual resemblance we use the Hausdorff metric. Informally, two geometric patterns P and Q resemble each othe runder the Hausdorff metric, if every point on one pattern is "close" to some point on the other pattern. We relate the concept class of geometric patterns to the landmark recognition problem and then present a polynomial-time algorithm that PAC-learns the class of one-dimensional geometric patterns when the negative examples are corrupted by a large amount of random misclassification noise. An interesting feature of this problem is that the target concept is specified by a k-tuple of points on the real line, while the instances are specified by n-tuple of points on the real line where n is potentially much larger than k. Although there are some important distinctions, in some sense, our work illustrates a concept class in a continuous domain in which a large fractino of each instance can be viewed as "irrelevant." As in previous work on learning with a large number of irrelevant attributes in the Boolean domain, our algorithm's sample complexity depends polynomially on k and log(n).