IEEE Transactions on Pattern Analysis and Machine Intelligence · 2007 · 84 citations · 63 references
ComputingComputer ScienceData MiningInformation RetrievalMachine LearningImage RetrievalMetric LearningNearest Neighbor SearchRepresentation LearningRetrieval ModelsVector Space RetrievalBoostingClassification AccuracyClassification Accuracy AnalysisClassifier FusionDistance MeasuresNearest Neighbor RetrievalRetrievalVector Space Models
This paper describes BoostMap, a method for efficient nearest neighbor retrieval under computationally expensive distance measures. Database and query objects are embedded into a vector space, in which distances can be measured efficiently. Each embedding is treated as a classifier that predicts for any three objects X, A, B whether X is closer to A or to B. It is shown that a linear combination of such embeddingbased classifiers naturally corresponds to an embedding and a distance measure. Based on this property, the BoostMap method reduces the problem of embedding construction to the classical boosting problem of combining many weak classifiers into an optimized strong classifier. The classification accuracy of the resulting strong classifier is a direct measure of the amount of nearest neighbor structure preserved by the embedding. An important property of BoostMap is that the embedding optimization criterion is equally valid in both metric and non-metric spaces. Performance is evaluated in databases of hand images, handwritten digits, and time series. In all cases, BoostMap significantly improves retrieval efficiency with small losses in accuracy compared to brute-force search. Moreover, BoostMap significantly outperforms existing nearest neighbor retrieval methods, such as Lipschitz embeddings, FastMap, and VP-trees.
63
Gradient-based learning applied to document recognition
Yann LeCun, Léon Bottou, Yoshua Bengio et al. · Proceedings of the IEEE · 1998 · 58.2K citations · Full text
Nonlinear Dimensionality Reduction by Locally Linear Embedding
Sam T. Roweis, Lawrence K. Saul · Science · 2000 · 15K citations
A Global Geometric Framework for Nonlinear Dimensionality Reduction
Joshua B. Tenenbaum, Vin de Silva, John Langford · Science · 2000 · 13.7K citations
The Hungarian method for the assignment problem
Harold W. Kuhn · Naval Research Logistics Quarterly · 1955 · 12.6K citations