Abstract
This paper introduces a semi-supervised distance metric learning algorithm which uses pairwise equivalence (similarity and dissimilarity) constraints to discover the desired groups within high-dimensional data. In contrast to the traditional full rank distance metric learning algorithms, the proposed method can learn nonsquare projection matrices that yield low rank distance metrics. This brings additional benefits such as visualization of data samples and reducing the storage cost, and it is more robust to overfitting since the number of estimated parameters is greatly reduced. The proposed method works in both the input and kernel induced-feature space, and the distance metric is found by a gradient descent procedure that involves an eigen-decomposition in each step. Experimental results on high-dimensional visual object classification problems show that the computed distance metric improves the performances of the subsequent classification and clustering algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
An, S., Liu, W., Venkatesh, S.: Exploiting Side Information in Locality Preserving Projection. In: IEEE Computer Society Conference on Computer Vision and Pattern Recognition (2008)
Bar-Hillel, A., Hertz, T., Shental, N., Weinshall, D.: Learning Distance Functions Using Equivalence Relations. In: International Conference on Machine Learning (2003)
Basu, S., Banerjee, A., Mooney, R.J.: Active Semi-Supervision for Pairwise Constrained Clustering. In: The SIAM International Conference on Data Mining (2004)
Bilenko, M., Basu, S., Mooney, R.J.: Integrating Constraints and Metric Learning in Semi-Supervised Clustering. In: International Conference on Machine Learning (2004)
Cevikalp, H., Verbeek, J., Jurie, F., Klaser, A.: Semi-Supervised Dimensionality Reduction Using Pairwise Equivalence Constraints. In: International Conference on Computer Vision Theory and Applications (2008)
Chen, H.T., Liu, T.L., Fuh, C.S.: Learning effective Image Metrics From Few Pairwise Examples. In: IEEE International Conference on Computer Vision (2005)
Davis, J.V., Kulis, B., Jain, P., Dhillon, I.S.: Information-Theoretic Metric Learning. In: International Conference on Machine Learning (2007)
Globerson, A., Roweis, S.: Metric Learning by Collapsing Classes. In: Advances in Neural Information Processing Systems (2005)
Goldberger, J., Roweis, S., Hinton, G., Salakhutdinov, R.: Neighbourhood Component Analysis. In: Advances in Neural Information Processing Systems (2004)
Hadsell, R., Chopra, S., LeCun, Y.: Dimensionality Reduction by Learning and Invariant Mapping. In: IEEE Computer Society Conference on Computer Vision and Pattern Recognition (2006)
He, X., Niyogi, P.: Locality Preserving Directions. In: Advances in Neural Information Processing Systems (2003)
Hertz, T., Shental, N., Bar-Hillel, A., Weinshall, D.: Enhancing Image and Video Retrieval: Learning Via Equivalence Constraints. In: IEEE Computer Society Conference on Computer Vision and Pattern Recognition (2003)
Kwok, J.T., Tsan, I.W.: Learning with Idealized Kernels. In: International Conference on Machine Learning (2003)
Lazebnik, S., Schmid, C., Ponce, J.: A Maximum Entropy Framework for Part-Based Texture and Objcect Recognition. In: International Conference on Computer Vision (ICCV) (2005)
Li, Z., Liu, J., Tang, X.: Pairwise Constraint Propogation by Semidefinite Programming for Semi-Supervised Classification. In: International Conference on Machine Learning, ICML (2008)
Scholkopf, B., Smola, A.J., Muller, K.R.: Nonlinear Component Analysis as a Kernel Eigenvalue Problem. Neural Computation 10, 1299–1319 (1998)
Shalev-Shwartz, S., Singer, Y., Ng, A.Y.: Online and Batch Learning of Pseudo Metrics. In: International Conference on Machine Learning (2004)
Shental, N., Bar-Hillel, A., Hertz, T., Weinshall, D.: Computing Gaussian Mixture Modles with EM Using Equivalence Constraints. In: Advances in Neural Information Processing Systems (2003)
Shi, J., Malik, J.: Normalized Cuts and Image Segmentation. IEEE Transactions on PAMI 22, 885–905 (2000)
Torresani, L., Lee, K.C.: Large Margin Component Analysis. In: Advances in Neural Information Processing Systems (2006)
Turk, M., Pentland, A.P.: Eigenfaces for Recognition. Journal of Cognitive Neuroscience 3, 71–86 (1991)
Van de Weijer, J., Schmid, C.: Coloring Local Feature Extraction. In: Leonardis, A., Bischof, H., Pinz, A. (eds.) ECCV 2006. LNCS, vol. 3952, pp. 334–348. Springer, Heidelberg (2006)
Villegas, M., Paredes, R.: Simultaneous learning of a Discriminative Projection and Prototype for Nearest-Neighbor Classification. In: IEEE Computer Society Conference on Computer Vision and Pattern Recognition (2008)
Wagstaff, K., Rogers, S.: On subharmonic solutions of a Hamiltonian system. Constrained K-means Clustering with Background Knowledge. In: International Conference on Machine Learning (2001)
Weinberger, K.Q., Blitzer, J., Saul, L.K.: Distance Metric Learning for Large Margin Nearest Neighbor Classification. In: Advances in Neural Information Processing Systems (2005)
Xing, E.P., Ng, A.Y., Jordan, M.I., Russell, S.: Distance Metric Learning with Application to Clustering with Side-Information. In: Advances in Neural Information Processing Systems (2003)
Yan, B., Domeniconi, C.: Subspace Metric Ensembles for Semi-Supervised Clustering of High Dimensional Data. In: Fürnkranz, J., Scheffer, T., Spiliopoulou, M. (eds.) ECML 2006. LNCS (LNAI), vol. 4212, pp. 509–520. Springer, Heidelberg (2006)
Yang, L., Jin, R., Sukthankar, R.: Bayesian Active Distance Metric Learning. In: Proceedings of the 23rd Conference on Uncertainty in Artificial Intelligence (2007)
Yang, L., Jin, R.: Distance Metric Learning: A Comprehensive Survey (2006), http://wwww.cse.msu.edu/~yangliu1/framesurveyv2.pdf
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cevikalp, H. (2010). Semi-supervised Distance Metric Learning in High-Dimensional Spaces by Using Equivalence Constraints. In: Ranchordas, A., Pereira, J.M., Araújo, H.J., Tavares, J.M.R.S. (eds) Computer Vision, Imaging and Computer Graphics. Theory and Applications. VISIGRAPP 2009. Communications in Computer and Information Science, vol 68. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11840-1_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-11840-1_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11839-5
Online ISBN: 978-3-642-11840-1
eBook Packages: Computer ScienceComputer Science (R0)