An efficient sparse metric learning in high-dimensional space via l1-penalized log-determinant regularization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An efficient sparse metric learning in high-dimensional space via l₁-penalized log-determinant regularization

Full text

Pdf (1.10 MB)

Source

ACM International Conference Proceeding Series; Vol. 382 archive
Proceedings of the 26th Annual International Conference on Machine Learning table of contents

Montreal, Quebec, Canada

Pages 841-848

Year of Publication: 2009

ISBN:978-1-60558-516-1

Authors

Guo-Jun Qi	University of Illinois at Urbana-Champaign, Urbana, IL
Jinhui Tang	National University of Singapore, Singapore
Zheng-Jun Zha	National University of Singapore, Singapore
Tat-Seng Chua	National University of Singapore, Singapore
Hong-Jiang Zhang	Microsoft Advanced Technology Center, Beijing, China

Sponsors

: MITACS
: NSF
Microsoft Research : Microsoft Research

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 36, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1553374.1553482 What is a DOI?

ABSTRACT

This paper proposes an efficient sparse metric learning algorithm in high dimensional space via an l₁-penalized log-determinant regularization. Compare to the most existing distance metric learning algorithms, the proposed algorithm exploits the sparsity nature underlying the intrinsic high dimensional feature space. This sparsity prior of learning distance metric serves to regularize the complexity of the distance model especially in the "less example number p and high dimension d" setting. Theoretically, by analogy to the covariance estimation problem, we find the proposed distance learning algorithm has a consistent result at rate O (√m² log d)/n) to the target distance matrix with at most m nonzeros per row. Moreover, from the implementation perspective, this l₁-penalized log-determinant formulation can be efficiently optimized in a block coordinate descent fashion which is much faster than the standard semi-definite programming which has been widely adopted in many other advanced distance learning algorithms. We compare this algorithm with other state-of-the-art ones on various datasets and competitive results are obtained.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Onureena Banerjee , Laurent El Ghaoui , Alexandre d'Aspremont, Model Selection Through Sparse Maximum Likelihood Estimation for Multivariate Gaussian or Binary Data, The Journal of Machine Learning Research, 9, p.485-516, 6/1/2008
	2	Jason V. Davis , Brian Kulis , Prateek Jain , Suvrit Sra , Inderjit S. Dhillon, Information-theoretic metric learning, Proceedings of the 24th international conference on Machine learning, p.209-216, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273523]
	3	Donoho, D. (2006). For most large undertermined systems of linear equations the minimum l1-norm is also the sparsest solution. Comm. On Pure and Applied Math, 59, 797--829.
	4	Friedman, J., Hastie, T., & Tibshirani, R. (2007). Sparse inverse covariance estimation with the graphical lasso. Biostat.
	5	Hansen, M., & Yu, B. (2001). Model selection and the minimum description length principle. Journal of the American Statistical Association, 96, 746--774.
	6	Hoi, S. C. H., Liu, W., & Chang, S.-F. (2008). Semisupervised distance learning for collaborative image retrieval. Proc. of IEEE CVPR.
	7	Ravikumar, P., Wainwright, M. J., Raskutti, G., & Yu, B. (2008). High-dimensional covariance estimation by minimizing l₁-penalized log-determinant divergence (Technical Report 767). Department of Statistics, University of California, Berkeley.
	8	Schultz, M., & Joachims, T. (2004). Learning a distance metric from relative comparisons. Proc. of NIPS.
	9	Todd, M. (2001). Semidefinite optimization. Acta Numerica, 515--560.
	10	Weinberger, K. Q., Blitzer, J., & Saul, L. K. (2005). Distance metric learning for large margin nearest neighbor classification. Proc. of NIPS.
	11	John Wright , Allen Y. Yang , Arvind Ganesh , S. Shankar Sastry , Yi Ma, Robust Face Recognition via Sparse Representation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.31 n.2, p.210-227, February 2009 [doi>10.1109/TPAMI.2008.79]
	12	Xing, E. P., Ng, A. Y., Jordan, M. I., & Russell, S. (2003). Distance metric learning, with application to clustering with side-information. Proc. of NIPS.
	13	Wei Zhang , Xiangyang Xue , Zichen Sun , Yue-Fei Guo , Hong Lu, Optimal dimensionality of metric space for classification, Proceedings of the 24th international conference on Machine learning, p.1135-1142, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273639]