Abstract
It is now generally recognized that user-provided image tags are incomplete and noisy. In this study, we focus on the problem of tag completion that aims to simultaneously enrich the missing tags and remove noisy tags. The novel component of the proposed framework is a noisy matrix recovery algorithm. It assumes that the observed tags are independently sampled from an unknown tag matrix and our goal is to recover the tag matrix based on the sampled tags. We show theoretically that the proposed noisy tag matrix recovery algorithm is able to simultaneously recover the missing tags and de-emphasize the noisy tags even with a limited number of observations. In addition, a graph Laplacian based component is introduced to combine the noisy matrix recovery component with visual features. Our empirical study with multiple benchmark datasets for image tagging shows that the proposed algorithm outperforms state-of-the-art approaches in terms of both effectiveness and efficiency when handling missing and noisy tags.
Chapter PDF
Similar content being viewed by others
Keywords
References
Blei, D.M.: Probabilistic topic models. Communications of the ACM (2012)
Blei, D.M., Ng, A.Y., Jordan, M.I., Lafferty, J.: Latent dirichlet allocation. Journal of Machine Learning Research (2003)
Cabral, R.S., la Torre, F.D.D., Costeira, J.P., Bernardino, A.: Matrix completion for multi-label image classification. In: NIPS, pp. 190–198 (2011)
Candès, E.J., Plan, Y.: Matrix completion with noise. Proceedings of the IEEE 98(6), 925–936 (2010)
Candès, E.J., Recht, B.: Exact matrix completion via convex optimization. Foundations of Computational Mathematics 9(6), 717–772 (2009)
Chen, M., Zheng, A., Weinberger, K.Q.: Fast image tagging. In: ICML (2013)
Chua, T.S., Tang, J., Hong, R., Li, H., Luo, Z., Zheng, Y.T.: Nus-wide: A real-world web image database from national university of singapore. In: CIVR (2009)
Davis, J.V., Kulis, B., Jain, P., Sra, S., Dhillon, I.S.: Information-theoretic metric learning. In: ICML, pp. 209–216 (2007)
Feng, Z., Jin, R., Jain, A.K.: Large-scale image annotation by efficient and robust kernel metric learning. In: ICCV (2013)
Ganesh, A., Wright, J., Li, X., Candès, E.J., Ma, Y.: Dense error correction for low-rank matrices via principal component pursuit. In: ISIT (2010)
Guillaumin, M., Mensink, T., Verbeek, J., Schmid, C.: Tagprop: Discriminative metric learning in nearest neighbor models for image annotation. In: ICCV (2009)
Ji, S., Ye, J.: An accelerated gradient method for trace norm minimization. In: ICML, pp. 457–464. ACM (2009)
Koltchinskii, V., Lounici, K., Tsybakov, A.B.: Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion. The Annals of Statistics (2011)
Krestel, R., Fankhauser, P., Nejdl, W.: Latent dirichlet allocation for tag recommendation. In: ACM Conference on Recommender Systems, pp. 61–68. ACM (2009)
Lin, Z., Ding, G., Hu, M., Wang, J., Ye, X.: Image tag completion via image-specific and tag-specific linear sparse reconstructions. In: CVPR (2013)
Liu, D., Hua, X.S., Wang, M., Zhang, H.J.: Image retagging. In: Proceedings of the International Conference on Multimedia, pp. 491–500. ACM (2010)
Liu, D., Yan, S., Hua, X.S., Zhang, H.J.: Image retagging using collaborative tag propagation. IEEE Transactions on Multimedia 13(4), 702–712 (2011)
Liu, X., Yan, S., Chua, T.S., Jin, H.: Image label completion by pursuing contextual decomposability. TOMCCAP, 21:1–21:20 (2012)
Loeff, N., Farhadi, A.: Scene discovery by matrix factorization. In: Forsyth, D., Torr, P., Zisserman, A. (eds.) ECCV 2008, Part IV. LNCS, vol. 5305, pp. 451–464. Springer, Heidelberg (2008)
Monay, F., Gatica-Perez, D.: On image auto-annotation with latent space models. In: ACM International Conference on Multimedia, pp. 275–278. ACM (2003)
Mu, Y., Dong, J., Yuan, X., Yan, S.: Accelerated low-rank visual recovery by random projection. In: CVPR, pp. 2609–2616. IEEE Computer Society (2011)
Negahban, S., Wainwright, M.J.: Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. JMLR 13, 1665–1697 (2012)
Tian, Q., Aggarwal, C., Qi, G.J., Ji, H., Huang, T.S.: Exploring context and content links in social media: A latent space method. PAMI 34(5), 850–862 (2012)
Wu, L., Jin, R., Jain, A.K.: Tag completion for image retrieval. PAMI 35(3) (2013)
Xu, H., Wang, J., Hua, X.S., Li, S.: Tag refinement by regularized lda. In: ACM International Conference on Multimedia, pp. 573–576. ACM (2009)
Zhu, G., Yan, S., Ma, Y.: Image tag refinement towards low-rank, content-tag prior and error sparsity. In: International Conference on Multimedia. ACM (2010)
Zhuang, J., Hoi, S.C.H.: A two-view learning approach for image tag ranking. In: WSDM, pp. 625–634 (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
1 Electronic Supplementary Material
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Feng, Z., Feng, S., Jin, R., Jain, A.K. (2014). Image Tag Completion by Noisy Matrix Recovery. In: Fleet, D., Pajdla, T., Schiele, B., Tuytelaars, T. (eds) Computer Vision – ECCV 2014. ECCV 2014. Lecture Notes in Computer Science, vol 8695. Springer, Cham. https://doi.org/10.1007/978-3-319-10584-0_28
Download citation
DOI: https://doi.org/10.1007/978-3-319-10584-0_28
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-10583-3
Online ISBN: 978-3-319-10584-0
eBook Packages: Computer ScienceComputer Science (R0)