nips nips2009 nips2009-126 nips2009-126-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Lei Wu, Rong Jin, Steven C. Hoi, Jianke Zhu, Nenghai Yu
Abstract: Learning distance functions with side information plays a key role in many machine learning and data mining applications. Conventional approaches often assume a Mahalanobis distance function. These approaches are limited in two aspects: (i) they are computationally expensive (even infeasible) for high dimensional data because the size of the metric is in the square of dimensionality; (ii) they assume a fixed metric for the entire input space and therefore are unable to handle heterogeneous data. In this paper, we propose a novel scheme that learns nonlinear Bregman distance functions from side information using a nonparametric approach that is similar to support vector machines. The proposed scheme avoids the assumption of fixed metric by implicitly deriving a local distance from the Hessian matrix of a convex function that is used to generate the Bregman distance function. We also present an efficient learning algorithm for the proposed scheme for distance function learning. The extensive experiments with semi-supervised clustering show the proposed technique (i) outperforms the state-of-the-art approaches for distance function learning, and (ii) is computationally efficient for high dimensional data. 1
[1] A. Banerjee, S. Merugu, I. Dhillon, and J. Ghosh. Clustering with bregman divergences. In Journal of Machine Learning Research, pages 234–245, 2004.
[2] A. Bar-Hillel, T. Hertz, N. Shental, and D. Weinshall. Learning a mahalanobis metric from equivalence constraints. JMLR, 6:937–965, 2005.
[3] L. Bregman. The relaxation method of finding the common points of convex sets and its application to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics, 7:200–217, 1967.
[4] J. V. Davis, B. Kulis, P. Jain, S. Sra, and I. S. Dhillon. Information-theoretic metric learning. In ICML’07, pages 209–216, Corvalis, Oregon, 2007.
[5] J. Goldberger, S. Roweis, G. Hinton, and R. Salakhutdinov. Neighborhood component analysis. In NIPS.
[6] T. Hertz, A. B. Hillel, and D. Weinshall. Learning a kernel function for classification with small training samples. In ICML ’06: Proceedings of the 23rd international conference on Machine learning, pages 401–408. ACM, 2006.
[7] S. C. H. Hoi, W. Liu, and S.-F. Chang. Semi-supervised distance metric learning for collaborative image retrieval. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR2008), June 2008.
[8] S. C. H. Hoi, W. Liu, M. R. Lyu, and W.-Y. Ma. Learning distance metrics with contextual constraints for image retrieval. In Proc. CVPR2006, New York, US, June 17–22 2006.
[9] Y. Liu, R. Jin, and A. K. Jain. Boostcluster: boosting clustering by pairwise constraints. In KDD’07, pages 450–459, San Jose, California, USA, 2007.
[10] S. Shalev-Shwartz, Y. Singer, and N. Srebro. Pegasos: Primal estimated sub-gradient solver for svm. In ICML ’07: Proceedings of the 24th international conference on Machine learning, pages 807–814, New York, NY, USA, 2007. ACM.
[11] L. Si, R. Jin, S. C. H. Hoi, and M. R. Lyu. Collaborative image retrieval via regularized metric learning. ACM Multimedia Systems Journal, 12(1):34–44, 2006.
[12] T. H. Tomboy, A. Bar-hillel, and D. Weinshall. Boosting margin based distance functions for clustering. In In Proceedings of the Twenty-First International Conference on Machine Learning, pages 393–400, 2004.
[13] K. Wagstaff, C. Cardie, S. Rogers, and S. Schr¨ dl. Constrained k-means clustering with backo ground knowledge. In ICML’01, pages 577–584, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc.
[14] K. Weinberger, J. Blitzer, and L. Saul. Distance metric learning for large margin nearest neighbor classification. In NIPS 18, pages 1473–1480, 2006.
[15] L. Wu, S. C. H. Hoi, J. Zhu, R. Jin, and N. Yu. Distance metric learning from uncertain side information with application to automated photo tagging. In Proceedings of ACM International Conference on Multimedia (MM2009), Beijing, China, Oct. 19–24 2009.
[16] E. P. Xing, A. Y. Ng, M. I. Jordan, and S. Russell. Distance metric learning with application to clustering with side-information. In NIPS2002, 2002.
[17] L. Yang, R. Jin, R. Sukthankar, and Y. Liu. An efficient algorithm for local distance metric learning. In Proceedings of the Twenty-Second Conference on Artificial Intelligence (AAAI), 2006. 9