A Rapid Graph-based Method for Arbitrary Transformation-Invariant Pattern Classification

Part of Advances in Neural Information Processing Systems 7 (NIPS 1994)

Bibtex Metadata Paper


Alessandro Sperduti, David Stork


We present a graph-based method for rapid, accurate search through prototypes for transformation-invariant pattern classifica(cid:173) tion. Our method has in theory the same recognition accuracy as other recent methods based on ''tangent distance" [Simard et al., 1994], since it uses the same categorization rule. Nevertheless ours is significantly faster during classification because far fewer tan(cid:173) gent distances need be computed. Crucial to the success of our system are 1) a novel graph architecture in which transformation constraints and geometric relationships among prototypes are en(cid:173) coded during learning, and 2) an improved graph search criterion, used during classification. These architectural insights are applica(cid:173) ble to a wide range of problem domains. Here we demonstrate that on a handwriting recognition task, a basic implementation of our system requires less than half the computation of the Euclidean sorting method.