Coordination Structure Analysis using Dual Decomposition

Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 430–438, Avignon, France, April 23 - 27 2012. c⃝2012 Association for Computational Linguistics Coordination Structure Analysis using Dual Decomposition Atsushi Hanamoto 1 Takuya Matsuzaki 1 1. Department of Computer Science, University of Tokyo, Japan 2. Web Search & Mining Group, Microsoft Research Asia, China {hanamoto, matuzaki}@is.s.u-tokyo.ac.jp jtsujii@microsoft.com Jun’ichi Tsujii 2 Abstract Coordination disambiguation remains a dif- ficult sub-problem in parsing despite the frequency and importance of coordination structures. We propose a method for disam- biguating coordination structures. In this method, dual decomposition is used as a framework to take advantage of both HPSG parsing and coordinate structure analysis with alignment-based local features. We evaluate the performance of the proposed method on the Genia corpus and the Wall Street Journal portion of the Penn Tree- bank. Results show it increases the per- centage of sentences in which coordination structures are detected correctly, compared with each of the two algorithms alone. 1 Introduction Coordination structures often give syntactic ambi- guity in natural language. Although a wrong anal- ysis of a coordination structure often leads to a totally garbled parsing result, coordination disam- biguation remains a difficult sub-problem in pars- ing, even for state-of-the-art parsers. One approach to solve this problem is a gram- matical approach. This approach, however, of- ten fails in noun and adjective coordinations be- cause there are many possible structures in these coordinations that are grammatically correct. For example, a noun sequence of the form “n0 n1 and n2 n3” has as many as five possible struc- tures (Resnik, 1999). Therefore, a grammatical approach is not sufficient to disambiguate coor- dination structures. In fact, the Stanford parser (Klein and Manning, 2003) and Enju (Miyao and Tsujii, 2004) fail to disambiguate a sentence I am a freshman advertising and marketing major. Ta- ble 1 shows the output from them and the correct coordination structure. The coordination structure above is obvious to humans because there is a symmetry of conjuncts (-ing) in the sentence. Coordination structures of- ten have such structural and semantic symmetry of conjuncts. One approach is to capture local symmetry of conjuncts. However, this approach fails in VP and sentential coordinations, which can easily be detected by a grammatical approach. This is because conjuncts in these coordinations do not necessarily have local symmetry. It is therefore natural to think that consider- ing both the syntax and local symmetry of con- juncts would lead to a more accurate analysis. However, it is difficult to consider both of them in a dynamic programming algorithm, which has been often used for each of them, because it ex- plodes the computational and implementational complexity. Thus, previous studies on coordina- tion disambiguation often dealt only with a re- stricted form of coordination (e.g. noun phrases) or used a heuristic approach for simplicity. In this paper, we present a statistical analysis model for coordination disambiguation that uses the dual decomposition as a framework. We con- sider both of …

Content truncated to 500 words