Semisupervised SVM batch mode active learning with applications to image retrieval

ABSTRACT

Support vector machine (SVM) active learning is one popular and successful technique for relevance feedback in content-based image retrieval (CBIR). Despite the success, conventional SVM active learning has two main drawbacks. First, the performance of SVM is usually limited by the number of labeled examples. It often suffers a poor performance for the small-sized labeled examples, which is the case in relevance feedback. Second, conventional approaches do not take into account the redundancy among examples, and could select multiple examples that are similar (or even identical). In this work, we propose a novel scheme for explicitly addressing the drawbacks. It first learns a kernel function from a mixture of labeled and unlabeled data, and therefore alleviates the problem of small-sized training data. The kernel will then be used for a batch mode active learning method to identify the most informative and diverse examples via a min-max framework. Two novel algorithms are proposed to solve the related combinatorial optimization: the first approach approximates the problem into a quadratic program, and the second solves the combinatorial optimization approximately by a greedy algorithm that exploits the merits of submodular functions. Extensive experiments with image retrieval using both natural photo images and medical images show that the proposed algorithms are significantly more effective than the state-of-the-art approaches. A demo is available at http://msm.cais.ntu.edu.sg/LSCBIR/.

REFERENCES

• 1: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 2: Brinker, K. 2003. Incorporating diversity in active learning with support vector machines. In Proceedings of the International Conference on Machine Learning (ICML).
• 3: Chapelle, O., Schölkopf, B., and Zien, A. 2006. Semisupervised Learning. MIT Press, Cambridge, MA.
• 4: Cohn, D. A., Ghahramani, Z., and Jordan, M. I. 1995. Active learning with statistical models. In Proceedings of the NIPS.
• 5: Dagli, C. K., Rajaram, S., and Huang, T. S. 2006. Leveraging active learning for relevance feedback using an information theoretic diversity measure. In Proceedings of the ACM Conferece on Image and Video Retrieval (CIVR), Lecture Notes in Computer Science, vol. 4071. Springer, Berlin, Germany, 123--132.
• 6: King-Shy Goh , Edward Y. Chang , Wei-Cheng Lai, Multimodal concept-dependent active learning for image retrieval, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027664]
• 7: Steven C. H. Hoi , Rong Jin , Jianke Zhu , Michael R. Lyu, Batch mode active learning and its application to medical image classification, Proceedings of the 23rd international conference on Machine learning, p.417-424, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143897]
• 8: Chu-Hong Hoi , Michael R. Lyu, A novel log-based relevance feedback technique in content-based image retrieval, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027533]
• 9: Steven C. H. Hoi , Rong Jin , Michael R. Lyu, Large-scale text categorization by batch mode active learning, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135870]
• 10: Steven C. H. Hoi , Michael R. Lyu, A Semi-Supervised Active Learning Framework for Image Retrieval, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 2, p.302-309, June 20-26, 2005 [doi>10.1109/CVPR.2005.44]
• 11: Steven C. H. Hoi , Michael R. Lyu , Edward Y. Chang, Learning the unified kernel machines for classification, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150426]
• 12: Steven C. H. Hoi , Michael R. Lyu , Rong Jin, A Unified Log-Based Relevance Feedback Scheme for Image Retrieval, IEEE Transactions on Knowledge and Data Engineering, v.18 n.4, p.509-524, April 2006 [doi>10.1109/TKDE.2006.53]
• 13: Hong, P., Tian, Q., and Huang, T. S. 2000. Incorporate support vector machines to content-based image retrieval with relevant feedback. In Proceedings of the IEEE International Conference on Image Processing (ICIP). Vol. 3. 750--753.
• 14: Huang, T. S. and Zhou, X. S. 2001. Image retrieval by relevance feedback: From heuristic weight adjustment to optimal learning methods. In Proceedings of the IEEE International Conference on Image Processing (ICIP). Vol. 3. 2--5.
• 15: Yoshiharu Ishikawa , Ravishankar Subramanya , Christos Faloutsos, MindReader: Querying Databases Through Multiple Examples, Proceedings of the 24rd International Conference on Very Large Data Bases, p.218-227, August 24-27, 1998
• 16: King, I. and Zhong, J. 2003. Integrated probability function and its application to content-based image retrieval by relevance feedback. Patt. Recog. 36, 9, 2177--2186.
• 17: Laaksonen, J., Koskela, M., and Oja, E. 1999. Picsom: Self-organizing maps for content-based image retrieval. In Proceedings of the International Joint Conference on Neural Networks (IJCNN, Washington, DC).
• 18: Michael S. Lew , Nicu Sebe , Chabane Djeraba , Ramesh Jain, Content-based multimedia information retrieval: State of the art and challenges, ACM Transactions on Multimedia Computing, Communications, and Applications (TOMCCAP), v.2 n.1, p.1-19, February 2006 [doi>10.1145/1126004.1126005]
• 19: Li, J., Allinson, N., Tao, D., and Li, X. 2006. Multitraining support vector machine for image retrieval. IEEE Trans. Image Process. 15, 11, 3597--3601.
• 20: Liere, R. and Tadepalli, P. 1997. Active learning with committees for text categorization. In Proceedings of AAAI.
• 21: S. MacArthur , C. Brodley , C. Shyu, Relevance Feedback Decision Trees in Content-Based Image Retrieval, Proceedings of the IEEE Workshop on Content-based Access of Image and Video Libraries (CBAIVL'00), p.68, June 16-16, 2000
• 22: B. S. Manjunath , W. Y. Ma, Texture Features for Browsing and Retrieval of Image Data, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.8, p.837-842, August 1996 [doi>10.1109/34.531803]
• 23: Andrew McCallum , Kamal Nigam, Employing EM and Pool-Based Active Learning for Text Classification, Proceedings of the Fifteenth International Conference on Machine Learning, p.350-358, July 24-27, 1998
• 24: Muller, H., Deselaers, T., Lehmann, T., Clough, P., and Hersh, W. 2007. Overview of the imageclefmed 2006 medical retrieval annotation tasks. In Proceedings of the 7th Workshop of Cross-Language Evaluation Forum (CLEF).
• 25: Nemhauser, G., Wolsey, L., and Fisher, M. 1978. An analysis of the approximations for maximizing submodular set functions. Math. Program. 14, 265--294.
• 26: Navneet Panda , King-Shy Goh , Edward Y. Chang, Active learning in very large databases, Multimedia Tools and Applications, v.31 n.3, p.249-267, December 2006 [doi>10.1007/s11042-006-0043-1]
• 27: Qian, F., Li, M., Zhang, L., Zhang, H.-J., and Zhang, B. 2002. Gaussian mixture model for relevance feedback in image retrieval. In Proceedings of the International Conference on Multimedia and Expo (ICME). Vol. 1. 229--232.
• 28: Rui, Y., Huang, T., and Mehrotra, S. 1997. Content-based image retrieval with relevance feedback in mars. II. In Proceedings of the IEEE International Conference on Image Processing. 815--818.
• 29: Rui, Y., Huang, T. S., Ortega, M., and Mehrotra, S. 1998. Relevance feedback: A power tool in interactive content-based image retrieval. IEEE Trans. Circ. Syst. Vid. Tech. 8, 5 (Sept.), 644--655.
• 30: Greg Schohn , David Cohn, Less is More: Active Learning with Support Vector Machines, Proceedings of the Seventeenth International Conference on Machine Learning, p.839-846, June 29-July 02, 2000
• 31: Vikas Sindhwani , Partha Niyogi , Mikhail Belkin, Beyond the point cloud: from transductive to semi-supervised learning, Proceedings of the 22nd international conference on Machine learning, p.824-831, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102455]
• 32: Arnold W. M. Smeulders , Marcel Worring , Simone Santini , Amarnath Gupta , Ramesh Jain, Content-Based Image Retrieval at the End of the Early Years, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.12, p.1349-1380, December 2000 [doi>10.1109/34.895972]
• 33: Dacheng Tao , Xuelong Li , Stephen J. Maybank, Negative Samples Analysis in Relevance Feedback, IEEE Transactions on Knowledge and Data Engineering, v.19 n.4, p.568-580, April 2007 [doi>10.1109/TKDE.2007.1003]
• 34: Dacheng Tao , Xiaoou Tang, Nonparametric Discriminant Analysis in Relevance Feedback for Content-Based Image Retrieval, Proceedings of the Pattern Recognition, 17th International Conference on (ICPR'04) Volume 2, p.1013-1016, August 23-26, 2004 [doi>10.1109/ICPR.2004.626]
• 35: Tao, D. and Tang, X. 2004b. Random sampling based svm for relevance feedback image retrieval. In Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition (CVPR).
• 36: Tao, D., Tang, X., Li, X., and Rui, Y. 2006. Direct kernel biased discriminant analysis: A new content-based image retrieval relevance feedback algorithm. IEEE Trans. Image Process. 8, 4, 716--727.
• 37: Tieu, K. and Viola, P. 2000. Boosting image retrieval. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Vol. 1. 228--235.
• 38: Simon Tong , Edward Chang, Support vector machine active learning for image retrieval, Proceedings of the ninth ACM international conference on Multimedia, September 30-October 05, 2001, Ottawa, Canada [doi>10.1145/500141.500159]
• 39: Simon Tong , Daphne Koller, Support Vector Machine Active Learning with Application sto Text Classification, Proceedings of the Seventeenth International Conference on Machine Learning, p.999-1006, June 29-July 02, 2000
• 40: Vapnik, V. N. 1998. Statistical Learning Theory. Wiley, New York, NY.
• 41: Vasconcelos, N. and Lippman, A. 1999. Learning from user feedback in image retrieval systems. In Proceedings of NIPS.
• 42: Wang, L., Chan, K. L., and Zhang, Z. 2003. Bootstrapping SVM active learning by incorporating unlabelled images for image retrieval. In Proceedings of the CVPR.
• 43: Wu, Y., Tian, Q., and Huang, T. S. 2000. Discriminant-EM algorithm with application to image retrieval. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR).
• 44: Rong Yan , Alexander G. Hauptmann , Rong Jin, Negative pseudo-relevance feedback in content-based video retrieval, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA [doi>10.1145/957013.957087]
• 45: Yuhong Guo, D. S. 2007. Discriminative batch mode active learning. In Proceedings of the Conference on Advances in Neural Information Processing Systems (NIPS).
• 46: Zhang, L., Lin, F., and Zhang, B. 2001. Support vector machine learning for image retrieval. In Proceedings of the International Conference on Image Processing (ICIP). Vol. 2. 721--724.
• 47: Zhang, T. and Ando, R. K. 2005. Analysis of spectral kernel design based semisupervised learning. In Proceedings of the Conference on Advances in Neural Information Processing Systems (NIPS).
• 48: Zhou, X. S. and Huang, T. S. 2001. Small sample learning during multimedia retrieval using biasmap. In Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition (CVPR).
• 49: Zhou, X. S. and Huang, T. S. 2003. Relevance feedback for image retrieval: a comprehensive review. ACM Multimed. Syst. 8, 6, 536--544.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.0 General

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
Content-based image retrieval, active learning, batch mode active learning, human-computer interaction, semisupervised learning, support vector machines