jmlr jmlr2012 jmlr2012-33 jmlr2012-33-reference knowledge-graph by maker-knowledge-mining

33 jmlr-2012-Distance Metric Learning with Eigenvalue Optimization


Source: pdf

Author: Yiming Ying, Peng Li

Abstract: The main theme of this paper is to develop a novel eigenvalue optimization framework for learning a Mahalanobis metric. Within this context, we introduce a novel metric learning approach called DML-eig which is shown to be equivalent to a well-known eigenvalue optimization problem called minimizing the maximal eigenvalue of a symmetric matrix (Overton, 1988; Lewis and Overton, 1996). Moreover, we formulate LMNN (Weinberger et al., 2005), one of the state-of-the-art metric learning methods, as a similar eigenvalue optimization problem. This novel framework not only provides new insights into metric learning but also opens new avenues to the design of efficient metric learning algorithms. Indeed, first-order algorithms are developed for DML-eig and LMNN which only need the computation of the largest eigenvector of a matrix per iteration. Their convergence characteristics are rigorously established. Various experiments on benchmark data sets show the competitive performance of our new approaches. In addition, we report an encouraging result on a difficult and challenging face verification data set called Labeled Faces in the Wild (LFW). Keywords: metric learning, convex optimization, semi-definite programming, first-order methods, eigenvalue optimization, matrix factorization, face verification


reference text

A. Argyriou, T. Evgeniou, and M. Pontil. Multi-task feature learning. In Advances in Neural Information Processing Systems 19, 2006. F. Bach. Consistency of trace norm minimization. Journal of Machine Learning Research, 9:10191048, 2008. M. Baes and M. B¨ rgisser. Smoothing techniques for solving semi-definite programs with u many constraints. IFOR Internal report, ETH, 2009. Available electronically via http://www. optimization-online.org/DB-FILE/2009/10/2414.pdf. A. Bar-Hillel, T. Hertz, N. Shental, and D. Weinshall. Learning a mahalanobis metric from equivalence constraints. Journal of Machine Learning Research, 6:937-965, 2005. B. Borchers. CSDP, a C library for semi-definite programming. Optimization Methods and Software, 11:613-623, 1999. S. Burer and Renato D.C. Monteiro. A nonlinear programming algorithm for solving semi-definite programs via low-rank factorization. Mathematical Programming, 95:329-357, 2003. E.J. Candes and B. Recht. Exact matrix completion via convex optimisation. arXiv:0805.4471, 2008. Available electronically via http://arxiv.org/abs/0805.4471. S. Chopra, R. Hadsell, and Y. LeCun. Learning a similarity metric discriminatively with application to face verification. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 539–546, 2005. J. Davis, B. Kulis, P. Jain, S. Sra, and I. Dhillon. Information-theoretic metric learning. In Proceedings of the Twenty-Fourth International Conference on Machine Learning, pages 209–216, 2007. M. Frank and P. Wolfe. An algorithm for quadratic programming. Naval Research Logistics Quaterly, 3:149–154, 1956. J. Goldberger, S. Roweis, G. Hinton, and R. Salakhutdinov. Neighbourhood component analysis. In Advances in Neural Information Processing Systems 17, 2004. M. Guillaumin, J. Verbeek and C. Schmid. Is that you? Metric learning approaches for face identification. In IEEE 12th International Conference on Computer Vision, pages 498–505, 2009. E. Hazan. Sparse approximation solutions to semi-definite programs. LATIN: Proceedings of the 8th Latin American Conference on Theoretical informatics, 2008. C. Helmberg and F. Rendl. A spectral bundle method for semi-definite programming. SIAM Journal on Optimization, 10(3):673-696, 1999. 24 D ISTANCE M ETRIC L EARNING WITH E IGENVALUE O PTIMIZATION S. C. H. Hoi, W. Liu, M. R. Lyu, and W.-Y. Ma. Learning distance metrics with contextual constraints for image retrieval. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 2072–2078, 2006. G. B. Huang, M. Ramesh, T. Berg and E. Learned-Miller. Labeled Faces in the Wild: A database for studying face recognition in unconstrained environments. University of Massachusetts, Amherst, Technical Report 07–49, October, 2007. R. A. Horn and C. R. Johnson. Topics in Matrix Analysis. Cambridge University Press, 1991. P. Jain, B. Kulis, I. S. Dhillon. Inductive regularized learning of kernel functions. In Advances in Neural Information Processing Systems 23, 2010. R. Jin, S. Wang and Y. Zhou. Regularized distance metric learning: theory and algorithm. In Advances in Neural Information Processing Systems 22, 2009. T. Kato and N. Nagano. Metric learning for enzyme active-site search. Bioinformatics, 26:26982704, 2010. A. S. Lewis and M. L. Overton. Eigenvalue optimization. Acta Numerica, 5:149–190, 1996. A. Nemirovski. Efficient methods in convex programming. Lecture Notes, 1994. Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Springer, 2003. Y. Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103:127152, 2005. Y. Nesterov. Smoothing technique and its applications in semi-definite optimization. Mathematical Programming, 110:245–259, 2007. T. Ojala, M. Pietikainen and T. Maenpaa. Multiresolution gray-scale and rotation invariant texture classification with local binary patterns. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(7):971–987, 2002. M. L. Overton. On minimizing the maximum eigenvalue of a symmetric matrix. SIAM. J. Matrix Anal. & Appl. 9:256–268, 1988. N. Pinto and D. Cox. Beyond simple features: a large-scale feature search approach to unconstrained face recognition. In International Conference on Automatic Face and Gesture Recognition, 2011. R. Rosales and G. Fung. Learning sparse metrics via linear programming. In Proceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2006. C. Shen, J. Kim, L. Wang and A. Hengel. Positive semi-definite metric learning with boosting. In Advances in Neural Information Processing Systems 22, 2009. S. Shalev-Shwartz, Y. Singer, and A. Y. Ng. Online and batch learning of pseudo-metrics. In Proceedings of the Twenty-first International Conference on Machine Learning, 2004. 25 Y ING AND L I N. Srebro, J.D.M. Rennie, and T.S. Jaakkola. Maximum-margin matrix factorization. In Advances in Neural Information Processing Systems 17, 2004. Y. Taigman and L. Wolf and T. Hassner. Multiple one-shots for utilizing class label information. In The British Machine Vision Conference, Sept. 2009. L. Torresani and K. Lee. Large margin component analysis. In Advances in Neural Information Processing Systems 19, 2007. J.-P. Vert, J. Qiu and W. S. Noble. A new pairwise kernel for biological network inference with support vector machines. BMC Bioinformatics, 8(Suppl 10), 2007. K. Q. Weinberger, J. Blitzer, and L. Saul. Distance metric learning for large margin nearest neighbour classification. In Advances in Neural Information Processing Systems 18, 2005. K. Q. Weinberger and L. K. Saul. Fast solvers and efficient implementations for distance metric learning. In Proceedings of the Twenty-Fifth International Conference on Machine Learning, pages 1160–1167, 2008. K. Q. Weinberger, F. Sha and L. K. Saul. Learning the kernel matrix for nonlinear dimensionality reduction. In Proceedings of the Twenty-first International Conference on Machine Learning, 2004. L. Wolf, T. Hassner and Y. Taigman. Similarity scores based on background samples. In Asian Conference on Computer Vision, 2009. L. Wolf, T. Hassner and Y. Taigman. Descriptor based methods in the wild. In Real-Life Images workshop at the European Conference on Computer Vision, October, 2008. E. Xing, A. Ng, M. Jordan, and S. Russell. Distance metric learning with application to clustering with side information. In Advances in Neural Information Processing Systems 15, 2003. L. Yang and R. Jin. Distance metric learning: A comprehensive survey. Technical report, Department of Computer Science and Engineering, Michigan State University, 2007. L. Yang, R. Jin, L. Mummert, R. Sukthankar, A. Goode, B. Zheng, S. Hoi, and M. Satyanarayanan. A boosting framework for visuality-preserving distance metric learning and its application to medical image retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence 32:30– 44, 2010. Y. Ying, K. Huang and C. Campbell. Sparse metric learning via smooth optimization. In Advances in Neural Information Processing Systems 22, 2009. Y. Ying and D.X. Zhou, Online regularized classification algorithms. IEEE Trans. Inform. Theory, 11:4775-4788, 2006. 26