Connectivity in Bag Generation

Connectivity in Bag Generation Arturo Trujillo and Simon Berry* School of Computer and Mathem~tical Sciences The Robert Gordon University, St Andrew Street Aberdeen Al/l 1fig Scotland {iat,cs5s by } (c~_ sct us. vgu.ac, ul< Abstract 'Fhis l)aper presents a pruning tech- nique which can bc used to reduce the number of paths searched in rule-based b~g generators of the type proposed by (Poznafiski el; al., 1!)95) and (l'opowMl, 1995). Pruning the search space in these generators is important given the. com- putational cost of bag generation. 'rhe technique relies on a connectivity con- straint between the semantic indices as- sociated with each lexical sign in a ba R. Testing the algorithm on a range of sen- tences shows reductions in the~ genera- tion time and the nmnber of edges con- stru cl.cd. 1 Introduction Bag generation is a form of natural language gel> er;ttion in which the input is ;~ bag (Mso known as a inultiset: a set in which rcpe~ted elements are significant) of lexicM elements and the output is a grammatical sentence or a statistically most prob- able permutation with respect to some. bmguage model. Bag generation has been considered within the st~tistieal and rule-based paradigms of computa- tional linguistics, and catch has handled this prob- lem differently (Chen and Lee, 1994; Whitelock, 1994; Popowich, 1995; Tn0illo , 1995). This pa- per only considers ruh' based approaches to this problem. Bag generation has received particulm: atten- tion in lexicalist approaches to MT, as exempli- tied by Shake-and-Bake generation (Beaven, 1992; Whitelock, 1994). One can also envisage applica- tions of bag generation to generation fi'om mini- *Now at S[1ARP L~tboral, ories of I"mrope, Ox- h)rd Science [)ark, Oxford OX4 4CA. E-ma~il: simon~sh~Lrp.co, nk tmdly recursiw', semantic ropresentactions (Cope.s- take ct al., 1995) and other semantic fi'ameworks which separate scoping fi'om content information (l{eyle, 1995). ht these frameworks, the unordered natllFe ()f predicate or relation sets makes the aI> plict~tion o[' bag generation techniques attra.ctiw:. A notational convention used in the I)al)er is that items such as 'dogt' stand for simplitied lex- ical signs of the. form (Shieber, 198(0: SI'M -- [ ttl/I,N = dog ] .... [ attc:~l = 1 J In such signs, the semantic argument will be re- ferred to as an qndex' and will be shown as n subscril)t to a lexeme; in the above exmnple, the index has been giwm the unique type 1. The term index is borrowed rl'Olll IIPSG (Pol- lard and Sag, 1994) where indices ~u'e used as ar- guments to relations; however these indices tnay also be equated with dis(-onrse referents in l)lt:I' (Kamp and I{eyle, 1993). As with most lexical- ist generators, semantic variables ttttlSl; [)c distin- guished in order to disallow tr;mslationally incor- rect permutations of the target bag. We distin- guish variables by uniquely typing them. Two assumptions are made regarding [cxieal- semantic indexing. Assmnption 1 All lea'teal signs must be indexed, including fltnetional and nonprcdicative elements (Calder cl al., 1989). Assumption 2 All le.~ical signs must be …

Content truncated to 500 words