An adaptive threshold framework for event detection using HMM-based life profiles

ABSTRACT

When an event occurs, it attracts attention of information sources to publish related documents along its lifespan. The task of event detection is to automatically identify events and their related documents from a document stream, which is a set of chronologically ordered documents collected from various information sources. Generally, each event has a distinct activeness development so that its status changes continuously during its lifespan. When an event is active, there are a lot of related documents from various information sources. In contrast when it is inactive, there are very few documents, but they are focused. Previous works on event detection did not consider the characteristics of the event's activeness, and used rigid thresholds for event detection. We propose a concept called life profile, modeled by a hidden Markov model, to model the activeness trends of events. In addition, a general event detection framework, LIPED, which utilizes the learned life profiles and the burst-and-diverse characteristic to adjust the event detection thresholds adaptively, can be incorporated into existing event detection methods. Based on the official TDT corpus and contest rules, the evaluation results show that existing detection methods that incorporate LIPED achieve better performance in the cost and F1 metrics, than without.

REFERENCES

• 1: Charu C. Aggarwal, A framework for diagnosing changes in evolving data streams, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872826]
• 2: Aizen, J., Huttenlocher, D., Kleinberg, J., and Novak, A. 2004. Traffic-based feedback on the web. In Proc. Nat. Acad. Sci. 101, 525--5260.
• 3: James Allan , Ron Papka , Victor Lavrenko, On-line new event detection and tracking, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.37-45, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290954]
• 4: Allan, J., Carbonell, J., Doddington, G., Yamron, J., and Yang, Y. 1998b. Topic detection and tracking pilot study: final report. In Proceedings of the DARPA Broadcast News Transcription and Understanding Workshop. 194--218.
• 5: Allan, J., Lavrenko, V., Frey, D., and Khandelwal, V. 2000. Proceeding of the TDT Workshop.
• 6: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 7: Barlas, Y. and Kanar, K. 1999. A dynamic pattern-oriented test for model validation. In Proceedings of 4th Systems Science European Congress. 269--286.
• 8: Baum, L. E., Petrie, T., Soules, G., and Weiss, N. 1970. A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains. Ann. Math. Statist. 41, 164--171.
• 9: Chen, C. C., Chen, Y. T., Sun Y., and Chen, M. C. 2003. Life cycle modeling of news events using aging theory. In Proceedings of the 14th European Conference on Machine Learning. 47--59.
• 10: Chien Chin Chen , Meng Chang Chen , Ming-Syan Chen, LIPED: HMM-based life profiles for adaptive event detection, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081936]
• 11: Tzu-Chuan Chou , Meng Chang Chen, Using Incremental PLSI for Threshold-Resilient Online Event Analysis, IEEE Transactions on Knowledge and Data Engineering, v.20 n.3, p.289-299, March 2008 [doi>10.1109/TKDE.2007.190702]
• 12: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 13: Dempster, A. P., Laird, N. M., and Rubin, D. B. 1977. Maximum likelihood from incomplete data via the EM algorithm. J. Royal Statist. Soc. Series B 39, 1--38.
• 14: Dynamic Histograms: Capturing Evolving Data Sets, Proceedings of the 16th International Conference on Data Engineering, p.86, February 28-March 03, 2000
• 15: Jonathan G. Fiscus , George R. Doddington, Topic detection and tracking evaluation overview, Topic detection and tracking: event-based information organization, Kluwer Academic Publishers, Norwell, MA, 2002
• 16: William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 17: Martin Franz , Todd Ward , J. Scott McCarley , Wei-Jing Zhu, Unsupervised and supervised clustering for topic tracking, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.310-317, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384013]
• 18: Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, A framework for measuring changes in data characteristics, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.126-137, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303989]
• 19: Ghahramani, S. 2000. Fundamentals of Probability. Prentice Hall.
• 20: Vasileios Hatzivassiloglou , Luis Gravano , Ankineedu Maganti, An investigation of linguistic features and clustering algorithms for topical document clustering, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.224-231, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345582]
• 21: Jon Kleinberg, Bursty and hierarchical structure in streams, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775061]
• 22: Anton Leuski , James Allan, Improving realism of topic tracking evaluation, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564394]
• 23: Zhiwei Li , Bin Wang , Mingjing Li , Wei-Ying Ma, A probabilistic model for retrospective news event detection, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076055]
• 24: Juha Makkonen , Helena Ahonen-Myka , Marko Salmenkivi, Simple Semantics in Topic Detection and Tracking, Information Retrieval, v.7 n.3-4, p.347-368, September-December 2004 [doi>10.1023/B:INRT.0000011210.12953.86]
• 25: R. Manmatha , Ao Feng , James Allan, A critical examination of TDT's cost function, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564465]
• 26: Christopher D. Manning , Prabhakar Raghavan , Hinrich Schtze, Introduction to Information Retrieval, Cambridge University Press, New York, NY, 2008
• 27: Markov, A. A. 1913. An example of statistical investigation in the text of ‘Eugene Onyegin’ illustrating coupling of 'tests' in chains. In Proc. Acad. Sci. 7, 153--162.
• 28: Martin, A., Doddington, G., Kamm, T., Ordowski, M., and Przybocki, M. 1997. The DET curve in assessment of detection task performance. In Proc. EuroSpeech, 4, 1985--1898.
• 29: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 30: Myers, C., Rabiner, L. R., and Rosenberg, A. E. 1980. Performance tradeoffs in dynamic time warping algorithms for isolated word recognition. IEEE Trans. Acoust. Speech Signal Proc. 28, 6, 623--635.
• 31: Papka, R. 1999. P.h.D thesis, Department of Computer Science, University of Massachusetts.
• 32: Lawrence R. Rabiner, A tutorial on hidden Markov models and selected applications in speech recognition, Readings in speech recognition, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 33: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 34: Rocchio, J. J. 1971. Relevance feedback in information retrieval, In The SMART Retrieval System, Prentice Hall, 313--323.
• 35: Gerard Salton, Automatic text processing: the transformation, analysis, and retrieval of information by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 36: Silverman, B. 1986. Density Estimation for Statistics and Data Analysis. Chapman and Hall.
• 37: Viterbi, A. J. 1967. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Trans. Inform. Theory IT-13, 1260-1269.
• 38: Yiming Yang , Tom Pierce , Jaime Carbonell, A study of retrospective and on-line event detection, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.28-36, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290953]
• 39: Zhang, J., Ghahramani, Z., and Yang, Y. 2004. A probabilistic model for online document clustering with application to novelty detection. In Proceedings of the Conference on Neural Information Processing System. 1617--1624.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Design, Experimentation

Keywords:
Event detection, TDT, clustering, hidden Markov models, life profiles, topic detection