Graph-based Local Coherence Modeling

Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 93–103, Sofia, Bulgaria, August 4-9 2013. c⃝2013 Association for Computational Linguistics Graph-based Local Coherence Modeling Camille Guinaudeau and Michael Strube Heidelberg Institute for Theoretical Studies gGmbH Schloss-Wolfsbrunnenweg 35 69118 Heidelberg, Germany (camille.guinaudeau|michael.strube)@h-its.org Abstract We propose a computationally efficient graph-based approach for local coherence modeling. We evaluate our system on three tasks: sentence ordering, summary coherence rating and readability assess- ment. The performance is comparable to entity grid based approaches though these rely on a computationally expensive train- ing phase and face data sparsity problems. 1 Introduction Many NLP applications which process or gener- ate texts rely on information about local coher- ence, i.e. information about which entities occur in which sentence and how the entities are dis- tributed in the text. This led to the development of many theories and models accounting for lo- cal coherence. One popular model, the center- ing model (Grosz et al., 1995), uses a ranking of discourse entities realized in particular sentences and computes transitions between adjacent sen- tences to provide insight in the felicity of texts. Centering models local coherence rather generally and has been applied to the generation of refer- ring expressions (Kibble and Power, 2004), to re- solve pronouns (Brennan et al., 1987, inter alia), to score essays (Miltsakaki and Kukich, 2004), to arrange sentences in the correct order (Karamanis et al., 2009), and to many other tasks. Poesio et al. (2004) observe that it is not clear how to set parameters in the centering model so that optimal performance in different tasks and languages can be achieved. Barzilay and Lapata (2008) criticize research on centering to be too dependent on man- ually annotated input. This led them to propose a local coherence model relying on a more parsimo- nious representation, the entity grid model. The entity grid is a two dimensional array where the rows represent sentences and the columns dis- course entities. From this grid Barzilay and La- pata (2008) derive probabilities of transitions be- tween adjacent sentences which are used as fea- tures for machine learning algorithms. They eval- uate this approach successfully on sentence order- ing, summary coherence rating, and readability as- sessment. However, their approach has some dis- advantages which they point out themselves: data sparsity, domain dependence and computational complexity, especially in terms of feature space is- sues while building their model (Barzilay and La- pata (2008, p.8, p.10, p.30), Elsner and Charniak (2011, p.126, p.127)). In order to overcome these problems we pro- pose to represent entities in a graph and then model local coherence by applying centrality mea- sures to the nodes in the graph (Section 3). We claim that a graph is a more powerful representa- tion for local coherence than the entity grid (Barzi- lay and Lapata, 2008) which is restricted to transi- tions between adjacent sentences. The graph can easily span the entire text without leading to com- putational complexity and data sparsity problems. Similar to the application …

Content truncated to 500 words