Efficiently learning a distance metric for large margin nearest neighbor classification

Kyoungup Park*, Chunhua Shen, Zhihui Hao, Junae Kim

*Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    16 Citations (Scopus)

    Abstract

    We concern the problem of learning a Mahalanobis distance metric for improving nearest neighbor classification. Our work is built upon the large margin nearest neighbor (LMNN) classification framework. Due to the semidefiniteness constraint in the optimization problem of LMNN, it is not scalable in terms of the dimensionality of the input data. The original LMNN solver partially alleviates this problem by adopting alternating projection methods instead of standard interior-point methods. Still, at each iteration, the computation complexity is at least O(D3) (D is the dimension of input data). In this work, we propose a column generation based algorithm to solve the LMNN optimization problem much more efficiently. Our algorithm is much more scalable in that at each iteration, it does not need full eigen-decomposition. Instead, we only need to find the leading eigenvalue and its corresponding eigenvector, which is of O(D2) complexity. Experiments show the efficiency and efficacy of our algorithms.

    Original languageEnglish
    Title of host publicationAAAI-11 / IAAI-11 - Proceedings of the 25th AAAI Conference on Artificial Intelligence and the 23rd Innovative Applications of Artificial Intelligence Conference
    Pages453-458
    Number of pages6
    Publication statusPublished - 2011
    Event25th AAAI Conference on Artificial Intelligence and the 23rd Innovative Applications of Artificial Intelligence Conference, AAAI-11 / IAAI-11 - San Francisco, CA, United States
    Duration: 7 Aug 201111 Aug 2011

    Publication series

    NameProceedings of the National Conference on Artificial Intelligence
    Volume1

    Conference

    Conference25th AAAI Conference on Artificial Intelligence and the 23rd Innovative Applications of Artificial Intelligence Conference, AAAI-11 / IAAI-11
    Country/TerritoryUnited States
    CitySan Francisco, CA
    Period7/08/1111/08/11

    Fingerprint

    Dive into the research topics of 'Efficiently learning a distance metric for large margin nearest neighbor classification'. Together they form a unique fingerprint.

    Cite this