Classification Learning on Proximity Data

We investigate the problem of learning a classification task on data represented in terms of their pair wise proximities. This representation does not refer to an explicit feature representation of the data items and is thus more general than the standard approach of using Euclidean feature vectors, from which pair wise proximities can always be calculated. Our approach based on a linear threshold model in the proximity values themselves, which is optimized using Structural Risk Minimization. We show that prior knowledge about the problem can be incorporated by the choice of distance measures and examine different metrics w.r.t. their generalization. Finally, the algorithms are successfully applied to protein structure data and to data from the cat's cerebral cortex. They show better performance than K-nearest-neighbour classification.

References

• Thore Graepel, Ralf Herbrich, Bernhard Schölkopf, Alex Smola, Peter Bartlett, Klaus Robert-Müller, Klaus Obermayer, and Robert Williamson. Classification on Proximity Data with LP-Machines. . In Proceedings of the Ninth International Conference on Artificial Neural Networks, pages 304-309, 1999. (Gzipped PostScript).
• Thore Graepel, Ralf Herbrich, Peter Bollmann-Sdorra, and Klaus Obermayer. Classification on Pairwise Proximity Data. . In Advances in Neural Information System Processing 11, pages 438-444, 1999. (Gzipped PostScript).
• NIPS*98 Workshop