Beyond the Pipeline: Discrete Optimization in NLP

Proceedings of the 9th Conference on Computational Natural Language Learning (CoNLL), pages 136–143, Ann Arbor, June 2005. c⃝2005 Association for Computational Linguistics Beyond the Pipeline: Discrete Optimization in NLP Tomasz Marciniak and Michael Strube EML Research gGmbH Schloss-Wolfsbrunnenweg 33 69118 Heidelberg, Germany http://www.eml-research.de/nlp Abstract We present a discrete optimization model based on a linear programming formulation as an alternative to the cascade of classifiers implemented in many language processing systems. Since NLP tasks are correlated with one another, sequential processing does not guarantee optimal solutions. We apply our model in an NLG application and show that it per- forms better than a pipeline-based system. 1 Introduction NLP applications involve mappings between com- plex representations. In generation a representa- tion of the semantic content is mapped onto the grammatical form of an expression, and in analy- sis the semantic representation is derived from the linear structure of a text or utterance. Each such mapping is typically split into a number of differ- ent tasks handled by separate modules. As noted by Daelemans & van den Bosch (1998), individ- ual decisions that these tasks involve can be formu- lated as classification problems falling in either of two groups: disambiguation or segmentation. The use of machine-learning to solve such tasks facil- itates building complex applications out of many light components. The architecture of choice for such systems has become a pipeline, with strict or- dering of the processing stages. An example of a generic pipeline architecture is GATE (Cunning- ham et al., 1997) which provides an infrastructure for building NLP applications. Sequential process- ing has also been used in several NLG systems (e.g. Reiter (1994), Reiter & Dale (2000)), and has been successfully used to combine standard preprocess- ing tasks such as part-of-speech tagging, chunking and named entity recognition (e.g. Buchholz et al. (1999), Soon et al. (2001)). In this paper we address the problem of aggregat- ing the outputs of classifiers solving different NLP tasks. We compare pipeline-based processing with discrete optimization modeling used in the field of computer vision and image recognition (Kleinberg & Tardos, 2000; Chekuri et al., 2001) and recently applied in NLP by Roth & Yih (2004), Punyakanok et al. (2004) and Althaus et al. (2004). Whereas Roth and Yih used optimization to solve two tasks only, and Punyakanok et al. and Althaus et al. fo- cused on a single task, we propose a general for- mulation capable of combining a large number of different NLP tasks. We apply the proposed model to solving numerous tasks in the generation process and compare it with two pipeline-based systems. The paper is structured as follows: in Section 2 we discuss the use of classifiers for handling NLP tasks and point to the limitations of pipeline processing. In Section 3 we present a general discrete optimiza- tion model whose application in NLG is described in Section 4. Finally, in Section 5 we report on the experiments and evaluation of our approach. 2 Solving NLP Tasks with Classifiers Classification can be defined …

Content truncated to 500 words