Learning the semantics of multimedia queries and concepts from a small number of examples

ABSTRACT

In this paper we unify two supposedly distinct tasks in multimedia retrieval. One task involves answering queries with a few examples. The other involves learning models for semantic concepts, also with a few examples. In our view these two tasks are identical with the only differentiation being the number of examples that are available for training. Once we adopt this unified view, we then apply identical techniques for solving both problems and evaluate the performance using the NIST TRECVID benchmark evaluation data [15]. We propose a combination hypothesis of two complementary classes of techniques, a nearest neighbor model using only positive examples and a discriminative support vector machine model using both positive and negative examples. In case of queries, where negative examples are rarely provided to seed the search, we create pseudo-negative samples. We then combine the ranked lists generated by evaluating the test database using both methods, to create a final ranked list of retrieved multimedia items. We evaluate this approach for rare concept and query topic modeling using the NIST TRECVID video corpus.In both tasks we find that applying the combination hypothesis across both modeling techniques and a variety of features results in enhanced performance over any of the baseline models, as well as in improved robustness with respect to training examples and visual features. In particular, we observe an improvement of 6% for rare concept detection and 17% for the search task.

REFERENCES

• 1: TREC Video Retrieval. National Institute of Standards and Technology, http://www-nlpir.nist.gov/projects/trecvid/.
• 2: Efficient Query Refinement in Multimedia Databases, Proceedings of the 16th International Conference on Data Engineering, p.196, February 28-March 03, 2000
• 3: T. S. Chua, S.-Y. Neo, K.-Y. Li, G. Wang, R. Shi, M. Zhao, and H. Xu. TREC VID 2004 search and feature extraction task by NUSPRIS. In TRECVID 2004 Workshop, Gaithersburg, MD, Nov. 2004.
• 4: Amarnath Gupta , Terry E. Weymouth , Ramesh Jain, Semantic Queries with Pictures: The VIMSYS Model, Proceedings of the 17th International Conference on Very Large Data Bases, p.69-79, September 03-06, 1991
• 5: Alexander G. Hauptmann , Michael G. Christel, Successful approaches in the TREC video retrieval evaluations, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027681]
• 6: 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
• 7: Lyndon S. Kennedy , Apostol (Paul) Natsev , Shih-Fu Chang, Automatic discovery of query-class-dependent models for multimodal search, Proceedings of the 13th annual ACM international conference on Multimedia, November 06-11, 2005, Hilton, Singapore [doi>10.1145/1101149.1101339]
• 8: C. Lin, B. Tseng, and J. Smith. Video collaborative annotation forum: Establishing ground-truth labels on large multimedia datasets. In Proc. Text Retrieval Conference (TREC), Gaithersburg, MD, Nov 2003.
• 9: Milind R. Naphade , John R. Smith, On the detection of semantic concepts at TRECVID, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027680]
• 10: M. R. Naphade, S. Basu, J. Smith, C. Y. Lin, and B. Tseng. Modeling semantic concepts to support query by keywords in video. In Proc. IEEE Intl. Conference on Image Processing (ICIP'02), Rochester, NY, Sep. 2002.
• 11: S. Nepal and M. V. Ramakrishna. Single feature query by multi examples in image databases. In Proc. SPIE Photonics East Intl. Symposium on Voice, Data and Communications, volume 4210, pages 424--435, 2000.
• 12: Kriengkrai Porkaew , Sharad Mehrotra , Michael Ortega , Kaushik Chakrabarti, Similarity Search Using Multiple Examples in MARS, Proceedings of the Third International Conference on Visual Information and Information Systems, p.68-75, June 02-04, 1999
• 13: Y. Rui, T. S. Huang, M. Ortega, and S. Mehrotra. Relevance feedback: A power tool for interactive content-based image retrieval. IEEE Trans. on Circuits and Systems for Video Technology, 8:644--656, Sep. 1998.
• 14: R. Singh and R. Kothari. Relevance feedback algorithm based on learning from labeled and unlabeled data. In IEEE ICME 2003, Baltimore, MD, July 2003.
• 15: Alan F. Smeaton , Paul Over , Wessel Kraaij, TRECVID: evaluating the effectiveness of information retrieval tasks on digital video, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027678]
• 16: D. M. J. Tax. One-Class Classification: Concept-Learning in the Absence of Counter-Examples. PhD thesis, Delft University of Technology, June 2001.
• 17: 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]
• 18: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 19: James Z. Wang , Jia Li, Learning-based linguistic indexing of pictures with 2--d MHMMs, Proceedings of the tenth ACM international conference on Multimedia, December 01-06, 2002, Juan-les-Pins, France [doi>10.1145/641007.641104]
• 20: T. Westerveld and A. P. de Vries. Multimedia retrieval using multiple examples. In CIVR, pages 344--352, 2004.
• 21: 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]
• 22: Rong Yan , Jun Yang , Alexander G. Hauptmann, Learning query-class dependent weights in automatic video retrieval, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027661]

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.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing; Multimedia databases

General Terms:
Algorithms, Design, Experimentation

Keywords:
MECBR, TRECVID, semantics, support vector machines