Classification with nonmetric distances: Image retrieval and class representation

One of the key problems in appearance-based vision is understanding how to use a set of labeled images to classify new images. Classification systems that can model human performance, or that use robust image matching methods , often make use of similarity judgments that are nonmetric; but when the t riangle inequality is not obeyed, most existing pattern recognition techniq ues are not applicable. We note that exemplar-based (or nearest-neighbor) m ethods can be applied naturally when using a wide class of nonmetric simila rity functions. The key issue, however, is to find methods for choosing goo d representatives of a class that accurately characterize it. We show that existing condensing techniques for finding class representatives are ill-su ited to deal with nonmetric dataspaces. We then focus on developing techniq ues for solving this problem, emphasizing two points: First, we show that t he distance between two images is not a good measure of how well one image can represent another in nonmetric spaces. Instead, we use the vector corre lation between the distances from each image to other previously seen image s. Second, we show that in nonmetric spaces, boundary points are less signi ficant for capturing the structure of a class than they are in Euclidean sp aces. We suggest that atypical points may be more important in describing c lasses. We demonstrate the importance of these ideas to learning that gener alizes from experience by improving performance using both synthetic and re al images. In addition, we suggest ways of applying parametric techniques t o supervised learning problems that involve a specific nonmetric distance f unctions, showing in particular how to generalize the idea of linear discri minant functions in a way that may be more useful in nonmetric spaces.