Bayesian video search reranking

ABSTRACT

Content-based video search reranking can be regarded as a process that uses visual content to recover the "true" ranking list from the noisy one generated based on textual information. This paper explicitly formulates this problem in the Bayesian framework, i.e., maximizing the ranking score consistency among visually similar video shots while minimizing the ranking distance, which represents the disagreement between the objective ranking list and the initial text-based. Different from existing point-wise ranking distance measures, which compute the distance in terms of the individual scores, two new methods are proposed in this paper to measure the ranking distance based on the disagreement in terms of pair-wise orders. Specifically, hinge distance penalizes the pairs with reversed order according to the degree of the reverse, while preference strength distance further considers the preference degree. By incorporating the proposed distances into the optimization objective, two reranking methods are developed which are solved using quadratic programming and matrix computation respectively. Evaluation on TRECVID video search benchmark shows that the performance improvement up to 21% on TRECVID 2006 and 61.11% on TRECVID 2007 are achieved relative to text search baseline.

REFERENCES

• 1: Trec-10 proceedings appendix on common evaluation measures. http://trec.nist.gov/pubs/trec10/appendices/measures.pdf.
• 2: Zhe Cao , Tao Qin , Tie-Yan Liu , Ming-Feng Tsai , Hang Li, Learning to rank: from pairwise approach to listwise approach, Proceedings of the 24th international conference on Machine learning, p.129-136, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273513]
• 3: J. G. Carbonell, Y. Yang, R. E. Frederking, R. D. Brown, Y. Geng, and D. Lee. Translingual information retrieval: A comparative evaluation. In IJCAI (1), pages 708--715, 1997.
• 4: L. B. Cremeant and R. M. Murra. Stability analysis of interconnected nonlinear systems under matrix feedback. In Proceedings of the 42nd IEEE Conference on Decision and Control, Maui, Hawaii USA, 2003.
• 5: R. Fergus, P. Perona, and A. Zisserman. A visual category filter for google images. In ECCV (1), pages 242--256, 2004.
• 6: R. Herbrich, T. Graepel, and K. Obermayer. Large margin rank boundaries for ordinal regression. In Advances in Large Margin Classifiers, pages 115--132. MIT Press, Cambridge, MA, 2000.
• 7: Winston H. Hsu , Lyndon S. Kennedy , Shih-Fu Chang, Video search reranking via information bottleneck principle, Proceedings of the 14th annual ACM international conference on Multimedia, October 23-27, 2006, Santa Barbara, CA, USA [doi>10.1145/1180639.1180654]
• 8: Winston H. Hsu , Lyndon S. Kennedy , Shih-Fu Chang, Video search reranking through random walk over document-level context graph, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany [doi>10.1145/1291233.1291446]
• 9: Lyndon S. Kennedy , Shih-Fu Chang, A reranking approach for context-based concept fusion in video indexing and retrieval, Proceedings of the 6th ACM international conference on Image and video retrieval, p.333-340, July 09-11, 2007, Amsterdam, The Netherlands [doi>10.1145/1282280.1282331]
• 10: Jingjing Liu , Wei Lai , Xian-Sheng Hua , Yalou Huang , Shipeng Li, Video search re-ranking via multi-graph propagation, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany [doi>10.1145/1291233.1291279]
• 11: Y. Liu, T. Mei, J. Tang, X. Wu, and X.-S. Hua. Learning to video search rerank via pseudo preference feedback. In ICME, 2008.
• 12: T. Mei, X.-S. Hua, W. Lai, L. Yang, Z.-J. Zha, Y. Liu, Z. Gu, G.-J. Qi, M. Wang, J. Tang, X. Yuan, Z. Lu, and J. Liu. Msra-ustc-sjtu at trecvid 2007: High-level feature extraction and search. In TREC Video Retrieval Evaluation Online Proceddings, 2007.
• 13: Apostol (Paul) Natsev , Alexander Haubold , Jelena Tešić , Lexing Xie , Rong Yan, Semantic concept-based query expansion and re-ranking for multimedia retrieval, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany [doi>10.1145/1291233.1291448]
• 14: S. E. Robertson, S. Walker, M. Hancock-Beaulieu, M. Gatford, and A. Payne. Simple, proven approaches to text retrieval. In Cambridge University Computer Laboratory Technical Report TR356, 1997.
• 15: Alan F. Smeaton , Paul Over , Wessel Kraaij, Evaluation campaigns and TRECVid, Proceedings of the 8th ACM international workshop on Multimedia information retrieval, October 26-27, 2006, Santa Barbara, California, USA [doi>10.1145/1178677.1178722]
• 16: A. J. Smola. Pr_LOQO, http://www.kernel-machines.org/code/prloqo.tar.gz.
• 17: TRECVID. TREC Video Retrieval Evaluation. http://www-nlpir.nist.gov/projects/trecvid/.
• 18: R. Yan and A. G. Hauptmann. Co-retrieval: A boosted reranking approach for video retrieval. In CIVR, pages 60--69, 2004.
• 19: R. Yan, A. G. Hauptmann, and R. Jin. Multimedia search with pseudo-relevance feedback. In CIVR, pages 238--247, 2003.
• 20: L. Yang and R. Jin. Distance metric learning: A comprehensive survey. http://www.cse.msu.edu/~yangliu1/frame_ survey_v2.pdf. 2006.
• 21: D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. Scholkopf. Learning with local and global consistency. In NIPS, 2003.
• 22: X. Zhu, Z. Ghahramani, and J. D. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In ICML, pages 912--919, 2003.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
bayesian reranking, pair-wise, video search reranking