Wide-Coverage Neural A* Parsing for Minimalist Grammars

Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2486–2505 Florence, Italy, July 28 - August 2, 2019. c⃝2019 Association for Computational Linguistics 2486 Wide-Coverage Neural A* Parsing for Minimalist Grammars John Torr Miloˇs Stanojevi´c Mark Steedman Shay B. Cohen School of Informatics University of Edinburgh 11 Crichton Street, Edinburgh, UK john.torr@cantab.net m.stanojevic@ed.ac.uk steedman@inf.ed.ac.uk scohen@inf.ed.ac.uk Abstract Minimalist Grammars (Stabler, 1997) are a computationally oriented, and rigorous for- malisation of many aspects of Chomsky’s (1995) Minimalist Program. This paper presents the first ever application of this for- malism to the task of realistic wide-coverage parsing. The parser uses a linguistically ex- pressive yet highly constrained grammar, to- gether with an adaptation of the A* search al- gorithm currently used in CCG parsing (Lewis and Steedman, 2014; Lewis et al., 2016), with supertag probabilities provided by a bi-LSTM neural network supertagger trained on MG- bank, a corpus of MG derivation trees. We report on some promising initial experimental results for overall dependency recovery as well as on the recovery of certain unbounded long distance dependencies. Finally, although like other MG parsers, ours has a high order poly- nomial worst case time complexity, we show that in practice its expected time complexity is O(n3). The parser is publicly available.1 1 Introduction Parsers based on linguistically expressive for- malisms, such as Head-Driven Phrase Structure Grammar (HPSG; Pollard and Sag 1994) and Combinatory Categorial Grammar (CCG; Steed- man 1996), were shown in Rimell et al. (2009) and Nivre et al. (2010) to be more effective at re- covering certain unbounded long-distance depen- dencies than those merely approximating human grammar with finite state or context-free covers. Such dependencies can be vital for tasks like open domain question answering, for example. Fur- thermore, as proven independently by Huybregts (1984) and Shieber (1985), some languages ex- hibit constructions which put them beyond even 1https://github.com/mgparsing/astar_ mg_parser the weak generative capacity of any context-free grammar. The investigation of parsing systems based on more powerful (mildly) context-sensitive formalisms has therefore been a very active area of research within the field of computational psy- cholinguistics over the past 35 years (see, e.g., Joshi 1985, 1990; Rambow and Joshi 1994; Steed- man 2000; Hale 2011; Stabler 2013; Stanojevi´c and Stabler 2018). Another linguistically expressive grammatical framework is Transformational Grammar (Chom- sky, 1957, 1965, 1981), the latest incarnation of which is the Minimalist Program (MP; Chomsky 1995). A defining property of MP is that con- stituents move. For example, in 1a below, what moves to the left periphery of the matrix clause from a deep subject position and will therefore be interpreted as the semantic AGENT of eat; in 1b, meanwhile, it moves from the deep object posi- tion and so is interpreted instead as the semantic PATIENT of eat. (1) a. Whati do you think ti eats mice? b. Whati do you think mice eat ti? MP continues to dominate much of theoretical syntax, and Stabler’s (1997) rigorous formalisa- tion of this framework has proven a popular choice for …

Content truncated to 500 words