Hierarchical Text Segmentation from Multi-Scale Lexical Cohesion

Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the ACL, pages 353–361, Boulder, Colorado, June 2009. c⃝2009 Association for Computational Linguistics Hierarchical Text Segmentation from Multi-Scale Lexical Cohesion Jacob Eisenstein Beckman Institute for Advanced Science and Technology University of Illinois Urbana, IL 61801 jacobe@illinois.edu Abstract This paper presents a novel unsupervised method for hierarchical topic segmentation. Lexical cohesion – the workhorse of unsu- pervised linear segmentation – is treated as a multi-scale phenomenon, and formalized in a Bayesian setting. Each word token is modeled as a draw from a pyramid of la- tent topic models, where the structure of the pyramid is constrained to induce a hierarchi- cal segmentation. Inference takes the form of a coordinate-ascent algorithm, iterating be- tween two steps: a novel dynamic program for obtaining the globally-optimal hierarchi- cal segmentation, and collapsed variational Bayesian inference over the hidden variables. The resulting system is fast and accurate, and compares well against heuristic alternatives. 1 Introduction Recovering structural organization from unformat- ted texts or transcripts is a fundamental problem in natural language processing, with applications to classroom lectures, meeting transcripts, and chat- room logs. In the unsupervised setting, a variety of successful systems have leveraged lexical cohe- sion (Halliday and Hasan, 1976) – the idea that topically-coherent segments display consistent lex- ical distributions (Hearst, 1994; Utiyama and Isa- hara, 2001; Eisenstein and Barzilay, 2008). How- ever, such systems almost invariably focus on linear segmentation, while it is widely believed that dis- course displays a hierarchical structure (Grosz and Sidner, 1986). This paper introduces the concept of multi-scale lexical cohesion, and leverages this idea in a Bayesian generative model for hierarchical topic segmentation. The idea of multi-scale cohesion is illustrated by the following two examples, drawn from the Wikipedia entry for the city of Buenos Aires. There are over 150 city bus lines called Colec- tivos ... Colectivos in Buenos Aires do not have a fixed timetable, but run from 4 to sev- eral per hour, depending on the bus line and time of the day. The Buenos Aires metro has six lines, 74 sta- tions, and 52.3 km of track. An expansion program is underway to extend existing lines into the outer neighborhoods. Track length is expected to reach 89 km... The two sections are both part of a high-level seg- ment on transportation. Words in bold are charac- teristic of the subsections (buses and trains, respec- tively), and do not occur elsewhere in the transporta- tion section; words in italics occur throughout the high-level section, but not elsewhere in the article. This paper shows how multi-scale cohesion can be captured in a Bayesian generative model and ex- ploited for unsupervised hierarchical topic segmen- tation. Latent topic models (Blei et al., 2003) provide a powerful statistical apparatus with which to study discourse structure. A consistent theme is the treat- ment of individual words as draws from multinomial language models indexed by a hidden “topic” asso- ciated with the word. In latent Dirichlet allocation (LDA) …

Content truncated to 500 words