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 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. 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.

REFERENCES

• AL88: Dana Angluin , Philip Laird, Learning From Noisy Examples, Machine Learning, v.2 n.4, p.343-370, April 1988 [doi>10.1023/A:1022873112823]
• BEHW89: Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
• Gol92: Paul W. Goldberg. PAC Learning Geometrical Figures. PhD thesis, University of Edinburgh, 1992.
• Gol93: Paul W. Goldberg. Geometrical pattern learning. Unpublished Manuscript, April 1993.
• GJ93: Paul Goldberg , Mark Jerrum, Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers, Proceedings of the sixth annual conference on Computational learning theory, p.361-369, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168377]
• Gru83: P.M. Gruber. Approximation of convex bodies. In P.M. Gruber and P.M. Willis, editors, Convezity and its applications. Brikhauser Verlag, 1983.
• Hoe63: Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, March 1963.
• HTP+92: Jiawei Hong, Xiaonan Tan, Brian Pinette, Richard Weiss, and Edward M. Riseman. Image-based homing. IEEE Control Systems Magazine, 12(1):38-45, 1992.
• LL90: T. S. Levitt , D. T. Lawton, Qualitative navigation for mobile robots, Artificial Intelligence, v.44 n.3, p.305-360, Aug. 1990 [doi>10.1016/0004-3702(90)90027-W ]
• Lit88: Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
• Pin93: Brian Edmund Pinette, Image-based navigation through large-scale environments, University of Massachusetts, Amherst, MA, 1994
• SA88: Hisashi Suzuki and Suguru Arimoto. Visual control of autonomous mobile robot based on self-organizing model for pattern learning. Journal of Robotic Systems, 5(5):453- 470, 1988.
• Val84: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• Val91: Leslie Valiant. A view of computational learning theory. In C.W. Gear, editor, NEC Research Symposium: Computation and Cognition. SIAM, Philadelphia, 1991.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  G. Mathematics of Computing

General Terms:
Algorithms, Theory, Verification