Support vector machine active learning for image retrieval

ABSTRACT

Relevance feedback is often a critical component when designing image databases. With these databases it is difficult to specify queries directly and explicitly. Relevance feedback interactively determinines a user's desired output or query concept by asking the user whether certain proposed images are relevant or not. For a relevance feedback algorithm to be effective, it must grasp a user's query concept accurately and quickly, while also only asking the user to label a small number of images. We propose the use of a support vector machine active learning algorithm for conducting effective relevance feedback for image retrieval. The algorithm selects the most informative images to query a user and quickly learns a boundary that separates the images that satisfy the user's query concept from the rest of the dataset. Experimental results show that our algorithm achieves significantly higher search accuracy than traditional query refinement schemes after just three to four rounds of relevance feedback.

REFERENCES

• 1: Christopher J. C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, v.2 n.2, p.121-167, June 1998 [doi>10.1023/A:1009715923555]
• 2: Colin Campbell , Nello Cristianini , Alex J. Smola, Query Learning with Large Margin Classifiers, Proceedings of the Seventeenth International Conference on Machine Learning, p.111-118, June 29-July 02, 2000
• 3: E. Chang and B. Li. Megct - the maximizing expected generalization algorithm for learning complex query concepts (extended version). Technical Report http://www-db.stanjord.edu/Nechang/mega.ps, November 2000.
• 4: E. Chrtng, B. Li, and C. Li. Towards perception-based image retrieval. IEEE Content-Based Access of Image and Video Libraries, pages 101-105, June 2000.
• 5: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, Random sampling for histogram construction: how much is enough?, ACM SIGMOD Record, v.27 n.2, p.436-447, June 1998
• 6: I. J. Cox, M. L. Miller, T. P. Minka, T. V. Papathomas, and P. N. Yianilos. The bay&an image retrieval system, pichunter: Theory, implementation and psychological experiments. IEEE Transaction on Image Processing (to appear), 2000.
• 7: I. Dagan and S. Engelson. Committee-based sampling for training probabilistic classifiers. In Proceedings of the Tweljth International Conjerence on Machine Learning, pages 150 157. Morgan Kaufmann, 1995.
• 8: Susan Dumais , John Platt , David Heckerman , Mehran Sahami, Inductive learning algorithms and representations for text categorization, Proceedings of the seventh international conference on Information and knowledge management, p.148-155, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288651]
• 9: Yoav Freund , H. Sebastian Seung , Eli Shamir , Naftali Tishby, Selective Sampling Using the Query by Committee Algorithm, Machine Learning, v.28 n.2-3, p.133-168, Aug./Sept. 1997 [doi>10.1023/A:1007330508534]
• 10: E. B. Goldstein. Sensation and Perception (5th Edition). Brooks/Cole, 1999.
• 11: R. Herbrich, T. Graepel, and C. Campbell. Bayes point machines: Estimating the bayes point in kernel space. In International Joint Conjerence on Artificial Intelligence Workshop on Support Vector Machines, pages 23-27, 1999.
• 12: Kien A. Hua , Khanh Vu , Jung-Hwan Oh, SamMatch: a flexible and efficient sampling-based image retrieval technique for large image databases, Proceedings of the seventh ACM international conference on Multimedia (Part 1), p.225-234, October 30-November 05, 1999, Orlando, Florida, United States [doi>10.1145/319463.319610]
• 13: 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
• 14: Thorsten Joachims, Text Categorization with Suport Vector Machines: Learning with Many Relevant Features, Proceedings of the 10th European Conference on Machine Learning, p.137-142, April 21-23, 1998
• 15: Thorsten Joachims, Transductive Inference for Text Classification using Support Vector Machines, Proceedings of the Sixteenth International Conference on Machine Learning, p.200-209, June 27-30, 1999
• 16: Jia-Guu Leu, Computing a shape's moments from its boundary, Pattern Recognition, v.24 n.10, p.949-957, 1991 [doi>10.1016/0031-3203(91)90092-J]
• 17: D. Lewis and J. Catlett. Heterogeneous uncertainty sampling for supervised learning. In Proceedings of the Eleventh International Conference on Machine Learning, pages 148 156. Morgan Kaufmann, 1994.
• 18: David D. Lewis , William A. Gale, A sequential algorithm for training text classifiers, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.3-12, July 03-06, 1994, Dublin, Ireland
• 19: Chen Li , Edward Chang , Hector Garcia-Molina , Gio Wiederhold, Clustering for Approximate Similarity Search in High-Dimensional Spaces, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.792-808, July 2002 [doi>10.1109/TKDE.2002.1019214]
• 20: W. Y. Ma and H. Zhang. Benchmarking of image features for content-based retrieval. Proceedings of Asilomar Conjerence on Signal, Systems & Computers, 1998.
• 21: B. Manjunath, P. Wu, S. Newsam, and II. Shin. A texture descriptor for browsing and similarity retrieval. Signal Processing Image Communication, 2001.
• 22: 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
• 23: T. Mitchell. Generalization as search. Artijiciai Intelligence, 28:203-226, 1982.
• 24: Michael Ortega , Yong Rui , Kaushik Chakrabarti , Kriengkrai Porkaew , Sharad Mehrotra , Thomas S. Huang, Supporting Ranked Boolean Similarity Queries in MARS, IEEE Transactions on Knowledge and Data Engineering, v.10 n.6, p.905-925, November 1998 [doi>10.1109/69.738357]
• 25: Constantine P. Papageorgiou , Michael Oren , Tomaso Poggio, A General Framework for Object Detection, Proceedings of the Sixth International Conference on Computer Vision, p.555, January 04-07, 1998
• 26: Kriengkrai Porkaew , Kaushik Chakrabarti, Query refinement for multimedia similarity retrieval in MARS, Proceedings of the seventh ACM international conference on Multimedia (Part 1), p.235-238, October 30-November 05, 1999, Orlando, Florida, United States [doi>10.1145/319463.319613]
• 27: Kriengkrai Porkaew , Sharad Mehrotra , Michael Ortega, Query Reformulation for Content Based Multimedia Retrieval in MARS, Proceedings of the IEEE International Conference on Multimedia Computing and Systems Volume II-Volume 2, p.747, June 07-11, 1999
• 28: 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
• 29: H. S. Seung , M. Opper , H. Sompolinsky, Query by committee, Proceedings of the fifth annual workshop on Computational learning theory, p.287-294, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130417]
• 30: John Shawe-Taylor , Nello Cristianini, Further results on the margin distribution, Proceedings of the twelfth annual conference on Computational learning theory, p.278-285, July 07-09, 1999, Santa Cruz, California, United States [doi>10.1145/307400.307470]
• 31: J. Smith and S.-F. Chang. Automated image retrieval using color and texture. IEEE Transaction on Pattern Analysis and Machine Intelligence, November 1996.
• 32: H. Tamura, S. Mori, and T. Yamawaki. Texture features corresponding to visual perception. IEEE Transaction on Systems Man Cybernet (SMC), 1978.
• 33: 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
• 34: Vladimir Vapnik, Estimation of Dependences Based on Empirical Data: Springer Series in Statistics (Springer Series in Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• 35: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 36: J. Wang, J. Li, and G. Wiederhold. Simplicity: Semantics-sensitive integrated matching for picture libraries. ACM Multimedia Conference, 2000.
• 37: Leejay Wu , Christos Faloutsos , Katia P. Sycara , Terry R. Payne, FALCON: Feedback Adaptive Loop for Content-Based Retrieval, Proceedings of the 26th International Conference on Very Large Data Bases, p.297-306, September 10-14, 2000

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Parallel and vector implementations

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Pattern analysis

General Terms:
Design, Measurement, Theory

Keywords:
active learning, image retrieval, query concept, relevance feedback, support vector machines