An Empirical Study on Rule Granularity and Unification Interleaving Toward an Efficient Unification-Based Parsing System

An Empirical Study on Rule Granularity and Unification Interleaving Toward an Efficient Unification-Based Parsing System Masaaki NAGNFA ATR Interpreting Telephony Research Laboratories 2-2 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-{}2, JAI'AN nagat a@atr-la.atr.co.jp Abstract This paper describes an empirical study on the op- timal granularity of the phrase structure rules and the optimal strategy for interleaving CFG parsing with unification in order to implement an eltlcient unification-based parsing system. We claim that us- ing "medium-grained" CFG phrase structure rules, which balance tile computational cost of CI?G parsing and unification, are a cost-effective solution for mak- ing unification-based grammar both efficicnt and easy to maintain. We also claim that "late unification", which delays unification until a complete CI"G parse is found, saves unnecessary copies of DAGs for ir- relevant subparses and improves performance signifi- cantly. The effectiveness of these methods was proved in an extensive experiment. The results show that, on average, the proposed system parses 3.5 times faster than our previous one. The grammar and the parser described in this paper are fully implemented and ased as the .lapmmse analysis module in SL-TRANS, the speech-to-speech translation system of ATR. 1 Introduction Uuifieation-based framework bins been an area of ac- tive research in natural language processing. Unifi- cation, wbich is the primary operation of ibis frame.- work, provides a kind of constraint-checking mecha- nism for nlerging varioas information sources, sllcb as syntax, semantics, and pragmatics. The computa- tional inefficiency of unification, however, precludes tile development of large practical NLP systems, al- though the framework has many attractiw~ theoretical properties. The efforts made to improve tile efficiency of a uriitication-ba.sed parsing system can be classified into four categories. • CFG parsing algorithm • Graph unification algorithm • Granunar representation and organizati(m • Interaction between CFG parsing and unilication There bave been well-known efficient CFG parsing algorithms such as CKY [Aho mid UllHnm, 77], Ear~ ley [Earley, 70], CtIAffl' (Kay, 80], eatd I,R [Aho and Ullmaa L 77] ['t'omita, 86]. There have also been sev- eral recent in-depth studies into efficient graph uni- fication algoritbms, whose main concerns have been either avoiding irrelevant copies of l)AGs [Karttunen and Kay, 85] [Pereira, 85] [Karttun .... 86] [Wrob- lewski, 87] [Godden, 90] [Kogure, 90] [Tomabechi, 91] [E1aele, 91], or the exhaustive expansion of dis- junctions into their disjunctive normal forms [Kasper, 87] [Eisele mad l)Srre, 88] [Maxwell and Kaplmh 89] [l)arre and l~i,~ele, 90] ickier, 901 [Nat ...... 91]. There has, however, been litth: discussion regarding the optimal representation of a grammar, or linguis- tic knowledge, in the unification-based framework, from tile engineering point of view. Grammar or- ganization is highly flexible, as tile unification-based framework uses two different forms of knowledge rep- resentation; atomic phrase structure rules and feature structure descriptions. Method selection greatly at" facts both the computational elficieney and the maiu- tenauce cost of the system. There luL~ also been little discussion regarding optimal interaction between the CFG parsing process and the unification process in unificatlon-based parsing, which also greatly af|~ct~; overall performance. Here …

Content truncated to 500 words