Convex experimental design using manifold structure for image retrieval

ABSTRACT

Content Based Image Retrieval (CBIR) has become one of the most active research areas in computer science. Relevance feedback is often used in CBIR systems to bridge the semantic gap. Typically, users are asked to make relevance judgements on some query results, and the feedback information is then used to re-rank the images in the database. An effective relevance feedback algorithm must provide the users with the most informative images with respect to the ranking function. In this paper, we propose a novel active learning algorithm, called Convex Laplacian Regularized Ioptimal Design (CLapRID), for relevance feedback image retrieval. Our algorithm is based on a regression model which minimizes the least square error on the labeled images and simultaneously preserves the intrinsic geometrical structure of the image space. It selects the most informative images which minimize the average predictive variance. The optimization problem of CLapRID can be cast as a semidefinite programming (SDP) problem, and solved via interior-point methods. Experimental results on COREL database have demonstrate the effectiveness of the proposed algorithm for relevance feedback image retrieval.

REFERENCES

• 1: S. P. Asprey and S. Macchietto. Designing robust optimal dynamic experiments. Journal of Process Control, 12(4):545--556, 2002.
• 2: A. Atkinson, A. Donev, and R. Tobias. Optimum Experimental Designs, with SAS. Oxford University Press, USA, 2007.
• 3: M. Belkin, P. Niyogi, and V. Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. The Journal of Machine Learning Research, 7:2399--2434, 2006.
• 4: S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
• 5: C. J. C. Burges. A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 2(2):121--167, 1998.
• 6: C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
• 7: O. Chapelle, B. Schölkopf, and A. Zien, editors. Semi-Supervised Learning. MIT Press, Cambridge, MA, 2006.
• 8: F. R. K. Chung. Spectral Graph Theory, volume 92 of Regional Conference Series in Mathematics. American Mathematical Society, 1997.
• 9: D. A. Cohn, Z. Ghahramani, and M. I. Jordan. Active learning with statistical models. Journal of Artificial Intelligence Research, 4:129--145, 1996.
• 10: R. Datta, D. Joshi, J. Li, and J. Z. Wang. Image retrieval: Ideas, influences, and trends of the new age. ACM Computing Surveys, 40(2):1--60, 2008.
• 11: E. de Klerk. Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications, volume 65 of Applied Optimization. Kluwer Academic Publishers, Dordrecht, 2002.
• 12: R. M. Freund and S. Mizuno. Interior point methods: Current status and future directions. In High Performance Optimization, pages 441--466. H. Frenk et al. (eds.), Kluwer Academic Publishers, 2000.
• 13: T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. New York: Springer-Verlag, 2001.
• 14: X. He, W. Min, D. Cai, and K. Zhou. Laplacian optimal design for image retrieval. In SIGIR'07: Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pages 119--126, New York, NY, USA, 2007. ACM.
• 15: D. P. Huijsmans and N. Sebe. How to complete performance graphs in content-based image retrieval: Add generality and normalize scope. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(2):245--251, 2005.
• 16: Y. Rui, T. S. Huang, M. Ortega, and S. Mehrotra. Relevance feedback: a power tool for interactive content-based image retrieval. IEEE Transactions on Circuits and Systems for Video Technology, 8(5):644--655, Sep 1998.
• 17: A. W. M. Smeulders, M. Worring, S. Santini, A. Gupta, and R. Jain. Content-based image retrieval at the end of the early years. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(12):1349--1380, 2000.
• 18: K. C. Toh, M. J. Todd, and R. H. Tütüncü. Sdpt3-a matlab software package for semidefinite programming. Optimization Methods and Software, 11(1):545--581, 1999.
• 19: S. Tong and E. Chang. Support vector machine active learning for image retrieval. In MULTIMEDIA'01: Proceedings of the ninth ACM international conference on Multimedia, pages 107--118, New York, NY, USA, 2001. ACM.
• 20: S. Tong and D. Koller. Support vector machine active learning with applications to text classification. Journal of Machine Learning Research, 2:45--66, 2002.
• 21: K. Vu, K. A. Hua, and N. Jiang. Improving image retrieval effectiveness in query-by-example environment. In SAC'03: Proceedings of the 2003 ACM symposium on Applied computing, pages 774--781, New York, NY, USA, 2003. ACM.
• 22: H. Yu, M. Li, H. jiang Zhang, and J. Feng. Color texture moments for content-based image retrieval. In International Conference on Image Processing, pages 929--932, 2002.
• 23: K. Yu, J. Bi, and V. Tresp. Active learning via transductive experimental design. In ICML'06: Proceedings of the 23rd international conference on Machine learning, pages 1081--1088, New York, NY, USA, 2006. ACM.
• 24: K. Yu, S. Zhu, W. Xu, and Y. Gong. Non-greedy active learning for text categorization using convex transductive experimental design. In SIGIR'08: Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, pages 635--642, New York, NY, USA, 2008. ACM.
• 25: D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. S. Olkopf. Learning with local and global consistency. In Advances in Neural Information Processing Systems 16, pages 321--328. MIT Press, 2004.
• 26: X. S. Zhou and T. S. Huang. Relevance feedback in image retrieval: A comprehensive review. Multimedia Systems, 8(6):536--544, April 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Relevance feedback

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Experimental design

General Terms:
Algorithms, Performance, Theory

Keywords:
active learning, convex optimization, image retrieval, relevance feedback, semidefinite programming