Improving text categorization methods for event tracking

ABSTRACT

Automated tracking of events from chronologically ordered document streams is a new challenge for statistical text classification. Existing learning techniques must be adapted or improved in order to effectively handle difficult situations where the number of positive training instances per event is extremely small, the majority of training documents are unlabelled, and most of the events have a short duration in time. We adapted several supervised text categorization methods, specifically several new variants of the k-Nearest Neighbor (kNN) algorithm and a Rocchio approach, to track events. All of these methods showed significant improvement (up to 71% reduction in weighted error rates) over the performance of the original kNN algorithm on TDT benchmark collections, making kNN among the top-performing systems in the recent TDT3 official evaluation. Furthermore, by combining these methods, we significantly reduced the variance in performance of our event tracking system over different data collections, suggesting a robust solution for parameter optimization.

REFERENCES

• 1: James Allan, Jaime Carbonell, George Doddington, Jonathan Yamron, and Yiming Yang. Topic detection and tracking pilot study: Final report. In ProceedIngs of the DARPA Broadcast News Transcription and Understanding Workshop, pages 194- 218, San Francisco, CA, 1998. Morgan Kaufmann Publishers, Inc.
• 2: 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]
• 3: Jaime Carbonell, Yiming Yang, John Lafferty, Ralf D.Brown, Tom Pierce, and Xin Liu. Cmu report on tdt-2: Segmentation, detection and tracking. In Proceedzngs of the DARPA Broadcast News Workshop, pages 117-120, San Francisco, CA, 1999. Morgan Kaufmann Publishers, Inc.
• 4: William W. Cohen , Yoram Singer, Context-sensitive learning methods for text categorization, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.307-315, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243278]
• 5: Jon Fiscus. A post-processing system to yield reduced word error rates: Recognizer output voting error reduction (rover). In IEEE Workshop on Automatzc Speech Recognitzon and Understandzng, Piscataway, N J, 1997. IEEE Signal Processing Society.
• 6: Jon Fiscus, George Doddington, John Garofolo, and Alvin Martin. Nist's 1998 topic detection and tracking evaluation (tdt2). In Proceedings of the DARPA Broadcast News Transcrzption and Understanding Workshop, pages 19-26, San Francisco, CA, 1999. Morgan Kaufmann Publishers, Inc.
• 7: Wai Lam , Chao Yang Ho, Using a generalized instance set for automatic text categorization, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.81-89, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290961]
• 8: Leah S. Larkey , W. Bruce Croft, Combining classifiers in text categorization, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.289-297, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243276]
• 9: Joon Ho Lee, Combining multiple evidence from different properties of weighting schemes, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.180-188, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215358]
• 10: David D. Lewis , Robert E. Schapire , James P. Callan , Ron Papka, Training algorithms for linear text classifiers, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.298-306, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243277]
• 11: A. Martin, G. Doddington, T. Kamm, M. Ordowski, and M. Przybocki. The det curve in assessment of detection task performance. In EuroSpeech 1997 Proceedings, volume 4, 1997.
• 12: J. J. Rocchio-Jr. Relevance feedback in information retrieval. In G. Salton, editor, The SMART Retrzeval System: Experzments in Automatzc Document Processzng, pages 313-323. Prentice-Hall, Inc., Englewood Cliffs, New Jersay, 1971.
• 13: G. Salton and C. Buckley. Improving retrieval performance by relevance feedback. Journal of American Soczety for Information Sczences, 41:288-297, 1990.
• 14: Robert E. Schapire , Yoram Singer , Amit Singhal, Boosting and Rocchio applied to text filtering, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.215-223, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290996]
• 15: J. Michael Schultz and Mark Liberman. Topic detection and tracking using idf-weighted cosine coefficient. In Proceedings of the DARPA Broadcast News Workshop, pages 189-192, San Francisco, CA, 1999. Morgan Kaufmann Publishers, Inc.
• 16: R. Schwartz, T. Imai, L. Nguyen, and J. Makhoul. A maximum likelihood model for topic classification of broadcast news. In Proceedzngs of Eurospeech, Rhodes, Greece, 1997.
• 17: Joeseph A. Shaw and Edward A. Fox. Combination of multiple searches. In The Second Text REtrzeval Conference, pages 243-252, 1994.
• 18: F. Walls, H. Jin, S. Sista, and R. Schwartz. Topic detection in broadcast news. In Proceedzngs of the DARPA Broadcast News Workshop, pages 193-198, San Francisco, CA, 1999. Morgan Kaufmann Publishers, Inc.
• 19: Sholom M. Weiss , Chidanand Apte , Fred J. Damerau , David E. Johnson , Frank J. Oles , Thilo Goetz , Thomas Hampp, Maximizing Text-Mining Performance, IEEE Intelligent Systems, v.14 n.4, p.63-69, July 1999 [doi>10.1109/5254.784086]
• 20: Yiming Yang, Expert network: effective and efficient learning from human decisions in text categorization and retrieval, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.13-22, July 03-06, 1994, Dublin, Ireland
• 21: Yiming Yang, An Evaluation of Statistical Approaches to Text Categorization, Information Retrieval, v.1 n.1-2, p.69-90, 1999 [doi>10.1023/A:1009982220290]
• 22: Yiming Yang , Jaime G. Carbonell , Ralf D. Brown , Thomas Pierce , Brian T. Archibald , Xin Liu, Learning Approaches for Detecting and Tracking News Events, IEEE Intelligent Systems, v.14 n.4, p.32-43, July 1999 [doi>10.1109/5254.784083]
• 23: Yiming Yang , Xin Liu, A re-examination of text categorization methods, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.42-49, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312647]
• 24: 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]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.7 Natural Language Processing
          Subjects: Text analysis

General Terms:
Algorithms, Design, Experimentation, Theory

Keywords:
evaluation, event detection and tracking, machine learning and IR, statistical&slash;probabilistic models, text categorization