Efficient Computation of Complex Distance Metrics Using Hierarchical Filtering

Abstract

By their very nature, memory based algorithms such as KNN or Parzen windows require a computationally expensive search of a large database of prototypes. In this paper we optimize the search(cid:173) ing process for tangent distance (Simard, LeCun and Denker, 1993) to improve speed performance. The closest prototypes are found by recursively searching included subset.s of the database using dis(cid:173) tances of increasing complexit.y. This is done by using a hierarchy of tangent distances (increasing the Humber of tangent. vectors from o to its maximum) and multiresolution (using wavelets). At each stage, a confidence level of the classification is computed. If the confidence is high enough, the c.omputation of more complex dis(cid:173) tances is avoided. The resulting algorithm applied to character recognition is close to t.hree orders of magnitude faster than com(cid:173) puting the full tangent dist.ance on every prot.ot.ypes .