Topic segmentation with shared topic detection and alignment of multiple documents

ABSTRACT

Topic detection and tracking and topic segmentation play an important role in capturing the local and sequential information of documents. Previous work in this area usually focuses on single documents, although similar multiple documents are available in many domains. In this paper, we introduce a novel unsupervised method for shared topic detection and topic segmentation of multiple similar documents based on mutual information (MI) and weighted mutual information (WMI) that is a combination of MI and term weights. The basic idea is that the optimal segmentation maximizes MI (or WMI). Our approach can detect shared topics among documents. It can find the optimal boundaries in a document, and align segments among documents at the same time. It also can handle single-document segmentation as a special case of the multi-document segmentation and alignment. Our methods can identify and strengthen cue terms that can be used for segmentation and partially remove stop words by using term weights based on entropy learned from multiple documents. Our experimental results show that our algorithm works well for the tasks of single-document segmentation, shared topic detection, and multi-document segmentation. Utilizing information from multiple documents can tremendously improve the performance of topic segmentation, and using WMI is even better than using MI for the multi-document segmentation.

REFERENCES

• 1: Arindam Banerjee , Inderjit Dhillon , Joydeep Ghosh , Srujana Merugu , Dharmendra S. Modha, A generalized maximum entropy approach to bregman co-clustering and matrix approximation, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014111]
• 2: Ron Bekkerman , Ran El-Yaniv , Andrew McCallum, Multi-way distributional clustering via pairwise interactions, Proceedings of the 22nd international conference on Machine learning, p.41-48, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102357]
• 3: David M. Blei , Pedro J. Moreno, Topic segmentation with an aspect hidden Markov model, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.343-348, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384021]
• 4: David M. Blei , Andrew Y. Ng , Michael I. Jordan, Latent dirichlet allocation, The Journal of Machine Learning Research, 3, p.993-1022, 3/1/2003
• 5: Thorsten Brants , Francine Chen , Ioannis Tsochantaridis, Topic-based document segmentation with probabilistic latent semantic analysis, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584829]
• 6: Freddy Y. Y. Choi, Advances in domain independent linear text segmentation, Proceedings of the first conference on North American chapter of the Association for Computational Linguistics, p.26-33, April 29-May 04, 2000, Seattle, Washington
• 7: H. Christensen, B. Kolluru, Y. Gotoh, and S. Renals. Maximum entropy segmentation of broadcast news. In Proceedings of ICASSP, 2005.
• 8: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 9: S. Deerwester, S. Dumais, G. Furnas, T. Landauer, and R. Harshman. Indexing by latent semantic analysis. Journal of the American Society for Information Systems, 1990.
• 10: Inderjit S. Dhillon , Subramanyam Mallela , Dharmendra S. Modha, Information-theoretic co-clustering, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956764]
• 11: Mochizuki Hajime , Honda Takeo , Okumura Manabu, Text segmentation with multiple surface linguistic cues, Proceedings of the 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics, p.881-885, August 10-14, 1998, Montreal, Quebec, Canada
• 12: T. K. Ho. Stop word location and identification for adaptive text recognition. International Journal of Document Analysis and Recognition, 3(1), August 2000.
• 13: Thomas Hofmann, Probabilistic latent semantic indexing, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.50-57, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312649]
• 14: X. Ji and H. Zha. Correlating summarization of a pair of multilingual documents. In Proceedings of RIDE, 2003.
• 15: Xiang Ji , Hongyuan Zha, Domain-independent text segmentation using anisotropic diffusion and dynamic programming, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860494]
• 16: X. Ji and H. Zha. Extracting shared topics of multiple documents. In Proceedings of the 7th PAKDD, 2003.
• 17: John D. Lafferty , Andrew McCallum , Fernando C. N. Pereira, Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, Proceedings of the Eighteenth International Conference on Machine Learning, p.282-289, June 28-July 01, 2001
• 18: Tao Li , Sheng Ma , Mitsunori Ogihara, Entropy-based criterion in categorical clustering, Proceedings of the twenty-first international conference on Machine learning, p.68, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015404]
• 19: Andrew McCallum , Dayne Freitag , Fernando C. N. Pereira, Maximum Entropy Markov Models for Information Extraction and Segmentation, Proceedings of the Seventeenth International Conference on Machine Learning, p.591-598, June 29-July 02, 2000
• 20: Lev Pevzner , Marti A. Hearst, A critique and improvement of an evaluation metric for text segmentation, Computational Linguistics, v.28 n.1, p.19-36, March 2002 [doi>10.1162/089120102317341756]
• 21: Jeffrey C. Reynar, Statistical models for topic segmentation, Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, p.357-364, June 20-26, 1999, College Park, Maryland [doi>10.3115/1034678.1034735]
• 22: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 23: Bingjun Sun , Ding Zhou , Hongyuan Zha , John Yen, Multi-task text segmentation and alignment based on weighted mutual information, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183760]
• 24: Masao Utiyama , Hitoshi Isahara, A statistical model for domain-independent text segmentation, Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, p.499-506, July 06-11, 2001, Toulouse, France [doi>10.3115/1073012.1073076]
• 25: C. Wayne. Multilingual topic detection and tracking: Successful research enabled by corpora and evaluation. In Proceedings of LREC, 2000.
• 26: J. Yamron, I. Carp, L. Gillick, S. Lowe, and P. van Mulbregt. A hidden markov model approach to text segmentation and event tracking. In Proceedings of ICASSP, 1998.
• 27: Hongyuan Zha , Xiang Ji, Correlating multilingual documents via bipartite graph modeling, 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.564485]

INDEX TERMS

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

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

General Terms:
Algorithms, Design, Experimentation

Keywords:
multiple documents, mutual information, shared topic detection, term weight, topic alignment, topic segmentation