Efficient Pattern Recognition Using a New Transformation Distance

Patrice Y. Simard, Yann LeCun, John S. DenkerNeurIPS 1992 · OpenReview

The Problem with Pixel-by-Pixel Comparison

Standard machine learning classifiers often rely on "Euclidean distance"—essentially comparing images pixel-by-pixel. The problem is that Euclidean distance is incredibly brittle in image recognition. If you take a picture of a "9" and shift it just a few pixels to the right, the pixel values change so drastically that a computer might think it’s a completely different digit, like a "4". To a human, however, it is obviously the same "9."

Previously, researchers tried to fix this using "elastic matching" or complex deformable templates. Unfortunately, these methods were often slow, ad-hoc, and difficult to generalize. The core challenge remained: how can we find a distance measure that is invariant (unchanging) under common transformations like rotation or scaling, while remaining computationally efficient?

The Tangent Distance Solution

To address this, the authors propose treating an image not as a single point in a rigid space, but as a point on a manifold—a curved surface representing every possible transformed version of that image (every possible rotation, translation, etc.).

Calculating the exact distance between two complex, curved manifolds is a massive optimization problem. The breakthrough idea in this paper is to approximate the manifold with a tangent plane at the point of the original image.

Approximating image transformations with a tangent plane

Because a tangent plane is a linear surface, finding the shortest distance between two planes becomes a standard "least squares" problem that can be solved very quickly using matrix mathematics. This "Tangent Distance" is locally invariant: it ignores small rotations or shifts that don't change the identity of the digit, but it still recognizes large, identity-altering changes (like rotating a "6" into a "9") as being far apart.

To make the system fast enough for real-world use, the authors implemented a "prefilter" trick. They first use a computationally cheap Euclidean distance to find the 100 most likely candidates, and then only calculate the more expensive Tangent Distance for that narrowed-down list.

Key Insights: Seven Degrees of Freedom

High-dimensional image space is messy, but locally, it behaves linearly. By focusing on the tangent, the model captures the "direction" of a transformation without needing to model the entire transformation globally.

The authors identified seven specific transformations that do not change a digit's identity:

  1. X-translation
  2. Y-translation
  3. Rotation
  4. Scaling
  5. Hyperbolic shearing (type 1)
  6. Hyperbolic shearing (type 2)
  7. Line thickness

Interestingly, accounting for line thickness was one of the most important factors, significantly dropping the error rate on the test datasets.

Benchmark Results

The researchers evaluated their method on two major benchmarks of the era:

  • USPS Database: A notoriously difficult set of 9,709 training and 2,007 test images (16x16 pixels) of handwritten digits from US mail envelopes.
  • NIST Database: A massive competition dataset featuring 223,000 training patterns and 59,000 test patterns.

Tangent Distance achieved a 2.6% error rate on the USPS dataset, vastly outperforming standard K-Nearest Neighbors (5.9%) and even the best Neural Networks of the time (3.3%). Remarkably, this 2.6% error rate was nearly identical to the error rate of humans (2.5%) on the same difficult test set. Furthermore, out of 25 participants using the official NIST training set, the Tangent Distance method finished in first place.

Limitations and Future Work

While highly effective, the method has limitations. Because it relies on a linear approximation, if a transformation is too large (e.g., a massive rotation), the tangent plane no longer accurately represents the manifold, and the distance measure breaks down.

Additionally, even with pre-filtering, Tangent Distance is more computationally expensive than simple Euclidean distance. The authors suggest that future work could involve "learning" the prototypes or tangent vectors to reduce the number of calculations needed. Finally, while highly effective for digits, the specific tangent vectors (like line thickness) must be chosen based on prior knowledge of the task. Applying this to speech or face recognition would require identifying an entirely different set of relevant transformations.

Summary updated

Abstract

Memory-based classification algorithms such as radial basis func(cid:173) tions or K-nearest neighbors typically rely on simple distances (Eu(cid:173) clidean, dot product ... ), which are not particularly meaningful on pattern vectors. More complex, better suited distance measures are often expensive and rather ad-hoc (elastic matching, deformable templates). We propose a new distance measure which (a) can be made locally invariant to any set of transformations of the input and (b) can be computed efficiently. We tested the method on large handwritten character databases provided by the Post Office and the NIST. Using invariances with respect to translation, rota(cid:173) tion, scaling, shearing and line thickness, the method consistently outperformed all other systems tested on the same databases.
BibTeX
@inproceedings{simard1992efficient,
  author = {Patrice Y. Simard and Yann LeCun and John S. Denker},
  title = {{Efficient Pattern Recognition Using a New Transformation Distance}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1992},
  url = {https://openreview.net/forum?id=rkbHNu-dWH},
}
Figure