RTG based surface realisation for TAG

Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 367–375, Beijing, August 2010 RTG based surface realisation for TAG Claire Gardent CNRS/LORIA claire.gardent@loria.fr Laura Perez-Beltrachini Universit´e Henri Poincar´e/LORIA laura.perez@loria.fr Abstract Surface realisation with grammars inte- grating flat semantics is known to be NP complete. In this paper, we present a new algorithm for surface realisation based on Feature Based Tree Adjoining Grammar (FTAG) which draws on the observation that an FTAG can be translated into a Reg- ular Tree Grammar describing its deriva- tion trees. We carry out an extensive test- ing of several variants of this algorithm using an automatically produced testsuite and compare the results obtained with those obtained using GenI, another FTAG based surface realiser. 1 Introduction As shown in (Brew, 1992; Koller and Striegnitz, 2002), Surface Realisation is NP-complete. Var- ious optimisation techniques have therefore been proposed to help improve practical runtimes. For instance, (Kay, 1996) proposes to reduce the num- ber of constituents built during realisation by only considering for combination constituents with non overlapping semantics and compatible indices. (Kay, 1996; Carroll and Oepen, 2005; Gardent and Kow, 2007) propose various techniques to re- strict the combinatorics induced by intersective modifiers all applying to the same structure. And (Koller and Striegnitz, 2002; Gardent and Kow, 2007) describe two alternative techniques for re- ducing the initial search space. In this paper, we focus on the optimisation mechanisms of two TAG based surface realisers namely, GENI (Gardent and Kow, 2007) and the algorithm we present in this paper namely, RT- GEN (Perez-Beltrachini, 2009). GENI’s optimisa- tion includes both a filtering process whose aim is to reduce the initial search space and a two step, “substitution before adjunction”, tree combination phase whose effect is to delay modifier adjunc- tion thereby reducing the number of intermediate structures being built. In RTGEN on the other hand, the initial FTAG is converted to a Regu- lar Tree Grammar (RTG) describing its derivation trees and an Earley algorithm, including sharing and packing, is used to optimise tree combination. We compare GENI with several variants of the proposed RTGEN algorithm using an automati- cally produced testsuite of 2 679 input formulae and relate the RTGEN approach to existing work on surface realisation optimisation. The paper is structured as follows. We first present the grammar used by both GENI and RT- GEN, namely SEMXTAG (Section 2). We then de- scribe the two surface realisation algorithms (Sec- tion 3). In Section 4, we describe the empirical evaluation carried out and present the results. Fi- nally, Section 5 situates RTGEN with respect to related work on surface realisation optimisation. 2 SemXTag The grammar (SEMXTAG) used by GENI and RTGEN is a Feature-Based Lexicalised Tree Adjoining Grammar (FTAG) augmented with a unification-based semantics as described in (Gar- dent and Kallmeyer, 2003). We briefly introduce each of these components and describe the gram- mar coverage. We then show how this FTAG can be converted to an RTG describing its derivation trees. 367 2.1 FTAG. A …

Content truncated to 500 words