Semi-Markov Models for Sequence Segmentation

Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 640–648, Prague, June 2007. c⃝2007 Association for Computational Linguistics Semi-Markov Models for Sequence Segmentation Qinfeng Shi NICTA, Statistical Machine Learning Australian National University Canberra, 2601 ACT qinfeng.shi@rsise.anu.edu.au Yasemin Altun Toyota Technological Institute 1427 E 60th St Chicago, IL 60637 altun@tti-c.org Alex Smola NICTA, Statistical Machine Learning Australian National University Canberra, 2601 ACT Alex.Smola@nicta.com.au S. V. N. Vishwanathan NICTA, Statistical Machine Learning Australian National University Canberra, 2601 ACT SVN.Vishwanathan@nicta.com.au Abstract In this paper, we study the problem of auto- matically segmenting written text into para- graphs. This is inherently a sequence label- ing problem, however, previous approaches ignore this dependency. We propose a novel approach for automatic paragraph segmen- tation, namely training Semi-Markov mod- els discriminatively using a Max-Margin method. This method allows us to model the sequential nature of the problem and to incorporate features of a whole paragraph, such as paragraph coherence which cannot be used in previous models. Experimental evaluation on four text corpora shows im- provement over the previous state-of-the art method on this task. 1 Introduction In this paper, we study automatic paragraph segmen- tation (APS). This task is closely related to some well known problems such as text segmentation, dis- course parsing, topic shift detection and is relevant for various important applications in speech-to-text and text-to-text tasks. In speech-to-text applications, the output of a speech recognition system, such as the output of sys- tems creating memos and documents for the Parlia- ment House, is usually raw text without any punc- tuation or paragraph breaks. Clearly, such text requires paragraph segmentations. In text-to-text processing, such as summarization, the output text does not necessarily retain the correct paragraph structure and may require post-processing. There is psycholinguistic evidence as cited by Sporleder & Lapata (2004) showing that insertion of para- graph breaks could improve the readability. More- over, it has been shown that different languages may have cross-linguistic variations in paragraph bound- ary placement (Zhu, 1999), which indicates that ma- chine translation can also benefit from APS. APS can also recover the paragraph breaks that are often lost in the OCR applications. There has been growing interest within the NLP community for APS in recent years. Previous meth- ods such as Sporleder & Lapata (2004); Genzel (2005); Filippova & Strube (2006) treat the problem as a binary classification task, where each sentence is labeled as the beginning of a paragraph or not. They focus on the use of features, such as surface features, language modeling features and syntactic features. The effectiveness of features is investi- gated across languages and/or domains. However, these approaches ignore the inherent sequential na- ture of APS. Clearly, consecutive sentences within the same paragraph depend on each other. More- over, paragraphs should exhibit certain properties such as coherence, which should be explored within an APS system. One cannot incorporate such prop- erties/features when APS is treated as a binary clas- sification problem. To overcome this …

Content truncated to 500 words