nips nips2009 nips2009-191 nips2009-191-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Chunhua Shen, Junae Kim, Lei Wang, Anton Hengel
Abstract: The learning of appropriate distance metrics is a critical problem in image classification and retrieval. In this work, we propose a boosting-based technique, termed B OOST M ETRIC, for learning a Mahalanobis distance metric. One of the primary difficulties in learning such a metric is to ensure that the Mahalanobis matrix remains positive semidefinite. Semidefinite programming is sometimes used to enforce this constraint, but does not scale well. B OOST M ETRIC is instead based on a key observation that any positive semidefinite matrix can be decomposed into a linear positive combination of trace-one rank-one matrices. B OOST M ETRIC thus uses rank-one positive semidefinite matrices as weak learners within an efficient and scalable boosting-based learning process. The resulting method is easy to implement, does not require tuning, and can accommodate various types of constraints. Experiments on various datasets show that the proposed algorithm compares favorably to those state-of-the-art methods in terms of classification accuracy and running time. 1
[1] T. Hastie and R. Tibshirani. Discriminant adaptive nearest neighbor classification. IEEE Trans. Pattern Anal. Mach. Intell., 18(6):607–616, 1996.
[2] J. Yu, J. Amores, N. Sebe, P. Radeva, and Q. Tian. Distance learning for similarity estimation. IEEE Trans. Pattern Anal. Mach. Intell., 30(3):451–462, 2008.
[3] B. Jian and B. C. Vemuri. Metric learning using Iwasawa decomposition. In Proc. IEEE Int. Conf. Comp. Vis., pages 1–6, Rio de Janeiro, Brazil, 2007. IEEE.
[4] E. Xing, A. Ng, M. Jordan, and S. Russell. Distance metric learning, with application to clustering with side-information. In Proc. Adv. Neural Inf. Process. Syst. MIT Press, 2002.
[5] A. Bar-Hillel, T. Hertz, N. Shental, and D. Weinshall. Learning a Mahalanobis metric from equivalence constraints. J. Mach. Learn. Res., 6:937–965, 2005.
[6] J. Goldberger, S. Roweis, G. Hinton, and R. Salakhutdinov. Neighbourhood component analysis. In Proc. Adv. Neural Inf. Process. Syst. MIT Press, 2004.
[7] K. Q. Weinberger, J. Blitzer, and L. K. Saul. Distance metric learning for large margin nearest neighbor classification. In Proc. Adv. Neural Inf. Process. Syst., pages 1473–1480, 2005.
[8] A. Globerson and S. Roweis. Metric learning by collapsing classes. In Proc. Adv. Neural Inf. Process. Syst., 2005.
[9] C. Shen, A. Welsh, and L. Wang. PSDBoost: Matrix-generation linear programming for positive semidefinite matrices learning. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, Proc. Adv. Neural Inf. Process. Syst., pages 1473–1480, Vancouver, Canada, 2008.
[10] R. E. Schapire. Theoretical views of boosting and applications. In Proc. Int. Conf. Algorithmic Learn. Theory, pages 13–25, London, UK, 1999. Springer-Verlag.
[11] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[12] K. Q. Weinberger and L. K. Saul. Unsupervised learning of image manifolds by semidefinite programming. Int. J. Comp. Vis., 70(1):77–90, 2006.
[13] A. Demiriz, K.P. Bennett, and J. Shawe-Taylor. Linear programming boosting via column generation. Mach. Learn., 46(1-3):225–254, 2002.
[14] C. Zhu, R. H. Byrd, and J. Nocedal. L-BFGS-B: Algorithm 778: L-BFGS-B, FORTRAN routines for large scale bound constrained optimization. ACM Trans. Math. Softw., 23(4):550– 560, 1997.
[15] 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 Trans. Pattern Anal. Mach. Intell. IEEE computer Society Digital Library, November 2008, http://doi.ieeecomputersociety. org/10.1109/TPAMI.2008.273.
[16] http://code.google.com/p/boosting/.
[17] S. Rosset, J. Zhu, and T. Hastie. Boosting as a regularized path to a maximum margin classifier. J. Mach. Learn. Res., 5:941–973, 2004.
[18] B. Borchers. CSDP, a C library for semidefinite programming. Optim. Methods and Softw., 11(1):613–623, 1999.
[19] L. Fei-Fei, R. Fergus, and P. Perona. One-shot learning of object categories. IEEE Trans. Pattern Anal. Mach. Intell., 28(4):594–611, April 2006.
[20] K. Mikolajczyk and C. Schmid. Scale & affine invariant interest point detectors. Int. J. Comp. Vis., 60(1):63–86, 2004.
[21] D. G. Lowe. Distinctive image features from scale-invariant keypoints. Int. J. Comp. Vis., 60(2):91–110, 2004.