Concept detectors: how good is good enough?

ABSTRACT

Today, semantic concept based video retrieval systems often show insufficient performance for real-life applications. Clearly, a big share of the reason is the lacking performance of the detectors of these concepts. While concept detectors are on their endeavor to improve, following important questions need to be addressed: "How good do detectors need to be to produce usable search systems?" and "How does the detector performance influence different concept combination methods?". We use Monte Carlo Simulations to provide answers to the above questions. The main contribution of this paper is a probabilistic model of detectors which outputs confidence scores to indicate the likelihood of a concept to occur. This score is also converted into a posterior probability and a binary classification. We investigate the influence of changes to the model's parameters on the performance of multiple concept combination methods. Current web search engines produce a mean average precision (MAP) of around 0.20. Our simulation reveals that the best performing video search method achieve this performance using detectors with 0.60 MAP and is therefore usable in real-life. Furthermore, perfect detection allows the best performing combination method to produce 0.39 search MAP in an artificial environment with Oracle settings. We also find that MAP is not necessarily a good evaluation measure for concept detectors since it is not always correlated with search performance.

REFERENCES

• 1: Robin Aly, Djoerd Hiemstra, and Arjen P. de Vries. Reusing annotation labor for concept selection. In CIVR '09: Proceedings of the International Conference on Content-Based Image and Video Retrieval 2009. ACM, 2009.
• 2: Robin Aly, Djoerd Hiemstra, Arjen P. de Vries, and Franciska de Jong. A probabilistic ranking framework using unobservable binary events for video search. In CIVR '08: Proceedings of the International Conference on Content-Based Image and Video Retrieval 2008, pages 349--358, 2008.
• 3: C. Arndt. Information Measures: Information and its description in Science and Engineering. Springer, 2001.
• 4: Javed A. Aslam and Mark Montague. Models for metasearch. In SIGIR '01: Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, pages 276--284, New York, NY, USA, 2001. ACM.
• 5: J. Bather. Decision Theory. An Introduction to Dynamic Programming and Sequential Decisions. Wiley-Interscience Series in Systems and Optimisation. John Wiley and Sons, West Sussex, England, 2000.
• 6: Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/ cjlin/libsvm.
• 7: A. Hauptmann, Rong Yan, Wei-Hao Lin, M. Christel, and H. Wactlar. Can high-level concepts fill the semantic gap in video retrieval? a case study with broadcast news. In IEEE Transactions on Multimedia, volume 9-5, pages 958--966, August 2007.
• 8: J.R. Kender and M.R. Naphade. Visual concepts for news story tracking: analyzing and exploiting the nist tresvid video annotation experiment. In TODO FILL IN, volume 1, pages 1174--1181, June 2005.
• 9: Hsuan-Tien Lin, Chih-Jen Lin, and Ruby C. Weng. A note on platt's probabilistic outputs for support vector machines. Machine Learning, 68(3):267--276, October 2007.
• 10: Nicholas Metropolis and S. Ulam. The monte carlo method. Journal of the American Statistical Association, 44(247):335--341, 1949.
• 11: Milind Naphade, John R. Smith, Jelena Tesic, Shih-Fu Chang, Winston Hsu, Lyndon Kennedy, Alexander Hauptmann, and Jon Curtis. Large-scale concept ontology for multimedia. IEEE MultiMedia, 13(3):86--91, 2006.
• 12: Apostol (Paul) Natsev, Alexander Haubold, Jelena Tesic, Lexing Xie, and Rong Yan. Semantic concept-based query expansion and re-ranking for multimedia retrieval. In MULTIMEDIA '07: Proceedings of the 15th international conference on Multimedia, pages 991--1000, New York, NY, USA, 2007. ACM.
• 13: J. Platt. Advances in Large Margin Classifiers, chapter Probabilistic outputs for support vector machines and comparison to regularized likelihood methods, pages 61--74. MIT Press, Cambridge, MA, 2000.
• 14: W.H. Press, S.A. Teukolsky, W.T. Vetterling, and B.P. Flannery. Numerical Recipes in C, The Art of Scientific Computing. Cambridge University Press use, 2nd edition, 1992.
• 15: S. E. Robertson, C. J. van Rijsbergen, and M. F. Porter. Probabilistic models of indexing and searching. In SIGIR '80: Proceedings of the 3rd annual ACM conference on Research and development in information retrieval, pages 35--56, Kent, UK, 1981. Butterworth & Co.
• 16: S.E. Robertson. The probability ranking principle in ir. Journal of Documentation, 33:294--304, 1977.
• 17: A. Sangswang and C.O. Nwankpa. Justification of a stochastic model for a dc-dc boost converter. In Industrial Electronics Society, 2003. IECON '03. The 29th Annual Conference of the IEEE, volume 2, pages 1870--1875 Vol.2, Nov. 2003.
• 18: A.F. Smeaton, P. Over, and W. Kraaij. High level feature detection from video in TRECVid: a 5-year retrospective of achievements. In Ajay Divakaran, editor, Multimedia Content Analysis, Theory and Applications. Springer, 2008.
• 19: Alan F. Smeaton, Paul Over, and Wessel Kraaij. Evaluation campaigns and trecvid. In MIR '06: Proceedings of the 8th ACM International Workshop on Multimedia Information Retrieval, pages 321--330, New York, NY, USA, 2006. ACM Press.
• 20: Cees G. M. Snoek, Marcel Worring, Jan C. van Gemert, Jan-Mark Geusebroek, and Arnold W. M. Smeulders. The challenge problem for automated detection of 101 semantic concepts in multimedia. In MULTIMEDIA '06: Proceedings of the 14th annual ACM international conference on Multimedia, pages 421--430, New York, NY, USA, 2006. ACM Press.
• 21: Cees G.M. Snoek, K.E.A. van de Sande, O. de Rooij, B. Huurnink, J.C. van Gemert, J.R.R. Uijlings, J. He, X. Li, I. Everts, V. Nedovic, M. van Liempt, R. van Balen, M. de Rijke, J.M. Geusebroek, Th. Gevers, M. Worring, A.W.M. Smeulders, D.C. Koelma, F. Yan, M.A. Tahir, K. Mikolajczyk, and J. Kittler. The mediamill trecvid 2008 semantic video search engine. In Proceedings of the 8th TRECVID Workshop, Gaithersburg, USA, November 2008.
• 22: Hastie T. and Tibshirani R. Classification by pairwise coupling. Technical report, Standford University and University of Torronto, 1996.
• 23: Rong Yan. Probabilistic Models for Combining Diverse Knowledge Sources in Multimedia Retrieval. PhD thesis, Canegie Mellon University, 2006.
• 24: Rong Yan and Alexander G. Hauptmann. The combination limit in multimedia retrieval. In MULTIMEDIA '03: Proceedings of the eleventh ACM international conference on Multimedia, pages 339--342, New York, NY, USA, 2003. ACM.
• 25: Rong Yan and Alexander G. Hauptmann. A review of text and image retrieval approaches for broadcast news video. Information Retrieval, 10(4-5):445--484, October 2007.
• 26: Jun Yang and Alexander G. Hauptmann. (un)reliability of video concept detection. In CIVR'08: Proceedings of the 2008 international conference on Content-based image and video retrieval, pages 85--94, New York, NY, USA, 2008. ACM.
• 27: Wujie Zheng, Jianmin Li, Zhangzhang Si, Fuzong Lin, and Bo Zhang. Using high-level semantic features in video retrieval. In Image and Video Retrieval, volume Volume 4071/2006, pages 370--379. Springer Berlin / Heidelberg, 2006.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
detector simulation, video information retrieval