Optimizing Typed Feature Structure Grammar Parsing through Non-Statistical Indexing

Optimizing Typed Feature Structure Grammar Parsing through Non-Statistical Indexing Cosmin Munteanu and Gerald Penn University of Toronto 10 King’s College Rd. Toronto M5S 3G4 Canada � mcosmin,gpenn � @cs.toronto.edu Abstract This paper introduces an indexing method based on static analysis of grammar rules and type signatures for typed feature structure grammars (TFSGs). The static analysis tries to predict at compile-time which feature paths will cause unification failure during parsing at run-time. To support the static analysis, we introduce a new classification of the instances of variables used in TFSGs, based on what type of structure sharing they create. The indexing actions that can be performed during parsing are also enu- merated. Non-statistical indexing has the advan- tage of not requiring training, and, as the evalua- tion using large-scale HPSGs demonstrates, the im- provements are comparable with those of statistical optimizations. Such statistical optimizations rely on data collected during training, and their perfor- mance does not always compensate for the training costs. 1 Introduction Developing efficient all-paths parsers has been a long-standing goal of research in computational lin- guistics. One particular class still in need of pars- ing time improvements is that of TFSGs. While simpler formalisms such as context-free grammars (CFGs) also face slow all-paths parsing times when the size of the grammar increases significantly, TF- SGs (which generally have fewer rules than large- scale CFGs) become slow as a result of the com- plex structures used to describe the grammatical cat- egories. In HPSGs (Pollard and Sag, 1994), one cat- egory description could contain hundreds of feature values. This has been a barrier in transferring CFG- successful techniques to TFSG parsing. For TFSG chart parsers, one of the most time- consuming operations is the retrieval of categories from the chart during rule completion (closing of constituents in the chart under a grammar rule). Looking in the chart for a matching edge for a daughter is accomplished by attempting unifications with edges stored in the chart, resulting in many failed unifications. The large and complex structure of TFS descriptions (Carpenter, 1992) leads to slow unification times, affecting the parsing times. Thus, failing unifications must be avoided during retrieval from the chart. To our knowledge, there have been only four methods proposed for improving the retrieval com- ponent of TFSG parsing. One (Penn and Munteanu, 2003) addresses only the cost of copying large cate- gories, and was found to reduce parsing times by an average of 25% on a large-scale TFSG (MERGE). The second, a statistical method known as quick- check (Malouf et al., 2000), determines the paths that are likely to cause unification failure by pro- filing a large sequence of parses over representa- tive input, and then filters unifications at run-time by first testing these paths for type consistency. This was measured as providing up to a 50% im- provement in parse times on the English Resource Grammar (Flickinger, 1999, ERG). The third (Penn, 1999b) is a similar but more conservative approach that uses the profile to re-order sister …

Content truncated to 500 words