Implementation of a Native Regularization Scheme Named As Fantope for Similarity Search

Authors

  • Divya Mishra  Computer Science, Naraina Vidyapeeth Engineering and Mgmt. Institute, Kanpur, Uttar Pradesh, India

Keywords:

Distance Metric, Mahalanobis Distance Metric, Metric Learning Fantope Regularization, Ky Fan’s Theorem

Abstract

This paper introduces a regularization method to explicitly control the rank of a learned symmetric positive semidefinite distance matrix in distance metric learning. To this end, we propose to incorporate in the objective function a linear regularization term that minimizes the k smallest eigenvalues of the distance matrix. It is equivalent to minimizing the trace of the product of the distance matrix with a matrix in the convex hull of rank-k projection matrices, called a Fantope. Based on this new regularization method, we derive an optimization scheme to efficiently learn the distance matrix. We demonstrate the effectiveness of the method on synthetic and challenging real datasets of face verification and image classification with relative attributes, on which our method outperforms state-of-the-art metric learning algorithms.

References

  1. S. Avila, N. Thome, M. Cord, E. Valle, and A. de A. Arajo. Pooling in image representation: The visual codeword point of view. Computer Vision and Image Understanding (CVIU), 117(5):453 – 465, 2013. 2
  2. S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3(1):1–122, 2011. 4
  3. G. Chechik, V. Sharma, U. Shalit, and S. Bengio. Large scale online learning of image similarity through ranking. JMLR, 11:1109–1135, 2010. 1, 2
  4. M. Cord and P. Cunningham. Machine learning techniques for multimedia. Springer, 2008. 2
  5. J. Dattorro. Convex optimization and Euclidean distance geometry. Meboo Publishing USA, 2005. 3
  6. J. V. Davis, B. Kulis, P. Jain, S. Sra, and I. S. Dhillon. Information-theoretic metric learning. In ICML, 2007. 2, 3, 6
  7. K. Fan. On a theorem of weyl concerning eigenvalues of linear transformationsi. Proceedings of the National Academy of Sciences of the United States of America, 35(11):652, 1949. 3
  8. A. Frome, Y. Singer, F. Sha, and J. Malik. Learning globally-consistent local distance functions for shape-based image retrieval and classification. In ICCV, 2007. 1, 2
  9. H. Goh, N. Thome, M. Cord, and J. Lim. Unsupervised and supervised visual codes with restricted boltzmann machines. In ECCV, 2012. 2
  10. M. Guillaumin, J. Verbeek, and C. Schmid. Is that you? metric learning approaches for face identification. In ICCV, 2009. 1, 6
  11. 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. Technical Report 07-49, University of Massachusetts, Amherst, 2007. 6
  12. N. Kumar, A. Berg, P. Belhumeur, and S. Nayar. Attribute and simile classifiers for face verification. In ICCV, 2009. 7
  13.  M. T. Law, N. Thome, and M. Cord. Quadruplet-wise image similarity learning. In ICCV, 2013. 1, 2, 3
  14. D. Lim, B. McFee, and G. Lanckriet. Robust structural metric learning. In ICML, 2013. 1, 2, 4
  15. D. Lowe. Distinctive image features from scale-invariant keypoints. IJCV, 60(2):91–110, 2004. 6
  16. B. McFee and G. Lanckriet. Metric learning to rank. In ICML, 2010. 2
  17. T. Mensink, J. Verbeek, F. Perronnin, and G. Csurka. Distance-based image classification: Generalizing to new classes at near-zero cost. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(11):2624–2637, 2013. 1, 2, 5
  18.  A. Mignon and F. Jurie. Pcca: A new approach for distance learning from sparse pairwise constraints. In CVPR, 2012. 1, 2, 3, 5, 6
  19. A. Oliva and A. Torralba. Modeling the shape of the scene: A holistic representation of the spatial envelope. IJCV, 42(3):145–175, 2001. 2, 7
  20. D. Parikh and K. Grauman. Relative attributes. In ICCV, 2011. 1, 5, 7, 8
  21. M. Schultz and T. Joachims. Learning a distance metric from relative comparisons. In NIPS, 2003. 1, 2
  22. T. Serre, L. Wolf, S. Bileschi, M. Riesenhuber, and T. Poggio. Robust object recognition with cortex-like mechanisms. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(3):411–426, 2007. 2
  23. C. Shen, J. Kim, L. Wang, and A. van den Hengel. Positive semidefinite metric learning with boosting. In NIPS, 2009. 2
  24. J. Sivic and A. Zisserman. Video google: A text retrieval approach to object matching in videos. In ICCV, 2003. 2
  25. C. Theriault, N. Thome, and M. Cord. Extended coding and pooling in the hmax model. IEEE Transactions on Image Processing, 22(2):764–777, 2013.
  26. K. Weinberger and L. Saul. Distance metric learning for large margin nearest neighbor classification. JMLR, 10:207–244, 2009. 1, 2, 7
  27. E. Xing, A. Ng, M. Jordan, and S. Russell. Distance metric learning, with application to clustering with side-information. In NIPS, 2002.
  28. J. Yang, K. Yu, Y. Gong, and T. Huang. Linear spatial pyramid matching using sparse coding for image classification. In CVPR, 2009.

IInternational Journal of Scientific Research in Computer Science, Engineering and Information Technology

Downloads

Published

2017-06-30

Issue

Volume 2, Issue 3, May-June-2017

Section

Research Articles

License

Copyright (c) IJSRCSEIT

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
Divya Mishra, " Implementation of a Native Regularization Scheme Named As Fantope for Similarity Search, IInternational Journal of Scientific Research in Computer Science, Engineering and Information Technology(IJSRCSEIT), ISSN : 2456-3307, Volume 2, Issue 3, pp.634-637, May-June-2017.