How Text Segmentation Algorithms Gain from Topic Models

2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 553–557, Montr´eal, Canada, June 3-8, 2012. c⃝2012 Association for Computational Linguistics How Text Segmentation Algorithms Gain from Topic Models Martin Riedl and Chris Biemann Ubiquitous Knowledge Processing Lab Computer Science Department, Technische Universit¨at Darmstadt Hochschulstrasse 10, D-64289 Darmstadt, Germany riedl@ukp.informatik.tu-darmstadt.de, biem@cs.tu-darmstadt.de Abstract This paper introduces a general method to in- corporate the LDA Topic Model into text seg- mentation algorithms. We show that seman- tic information added by Topic Models signifi- cantly improves the performance of two word- based algorithms, namely TextTiling and C99. Additionally, we introduce the new TopicTil- ing algorithm that is designed to take better advantage of topic information. We show con- sistent improvements over word-based meth- ods and achieve state-of-the art performance on a standard dataset. 1 Introduction Texts are often structured into segments to ease un- derstanding and readability of texts. Knowing about sentence boundaries is advantageous for natural lan- guage processing (NLP) tasks such as summariza- tion or indexing. While many genres such as en- cyclopedia entries or scientific articles follow rather formal conventions of breaking up a text into mean- ingful units, there are plenty of electronically avail- able texts without defined segments, e.g. web doc- uments. Text segmentation is the task of automati- cally segmenting texts into parts. Viewing a well- written text as sequence of subtopics and assuming that subtopics correspond to segments, a segmenta- tion algorithm needs to find changes of subtopics to identify the natural division of an unstructured text. In this work, we utilize semantic information from Topic Models (TMs) to inform text segmen- tation algorithms. For this, we compare two early word-based algorithms with their topic-based vari- ants, and construct our own algorithm called Topic- Tiling. We show that using topics estimated by La- tent Dirichlet Allocation (LDA) in lieu of words sub- stantially improves earlier segmentation algorithms. In comparison to TextTiling (TT), neither smoothing nor a blocksize or window size is needed. TT using TMs and our own algorithm improve on the state-of- the-art for a standard dataset, while being conceptu- ally simpler and computationally more efficient than other topic-based segmentation algorithms. 2 Related Work Based on the observation of Halliday and Hasan (1976) that the density of coherence relations is higher within segments than between segments, most algorithms compute a coherence score to mea- sure the difference of textual units for informing a segmentation decision. TextTiling (TT) (Hearst, 1994) relies on the simplest coherence relation – word repetition – and computes similarities between textual units based on the similarities of word space vectors. With C99 (Choi, 2000) an algorithm was introduced that uses a matrix-based ranking and a clustering approach in order to relate the most sim- ilar textual units and to cluster groups of consecu- tive units into segments. Both TT and C99 charac- terize textual units by the words they contain. Gal- ley et al. (2003) showed that using TF-IDF term weights in the term vector …

Content truncated to 500 words