Publications Details

Learning one-dimensional geometric patterns under one-sided random misclassification noise

Goldberg, P.W.; Goldman, S.A.

Developing the ability to recognize a landmark from a visual image of a robot`s current location is a fundamental problem in robotics. The authors consider the problem of PAC-learning the concept class of geometric patterns where the target geometric pattern is a configuration of k points in 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. They 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.