Agnostic learning of geometric patterns

P. W. Goldberg, S. A. Goldman, and S. D. Scott (Mach.. Learning 25, No. 1 ( 1996), 51-70) discussed how the problem of recognizing a landmark from a on e-dimensional visual image might be mapped to that of learning a one-dimens ional geometric pattern and gave a PAC algorithm to learn that class. In th is paper, we present an efficient online agnostic learning algorithm for le arning the class of constant-dimensional 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, hence, our learning algorithm are applicable to any data representable as a constant-dimensional array of values, e.g., sonar data, temporal differenc e information, amplitudes of a waveform, or other pattern recognition data. To our knowledge, these classes of patterns are more complex than any clas s of geometric patterns previously studied. Also, our results are easily ad apted to learn the union of fixed-dimensional boxes from multiple-instance examples. Finally, our algorithms are tolerant of concept shift. where the target concept that labels the examples can change over time. (C) 2001 Acad emic Press.