Why Implementation Matters: Evaluation of an Open-source Constraint Grammar Parser

Proceedings of COLING 2014, the 25th International Conference on Computational Linguistics: Technical Papers, pages 772–780, Dublin, Ireland, August 23-29 2014. Why implementation matters: Evaluation of an open-source constraint grammar parser D´avid M´ark Nemeskey Institute for Computer Science and Control, Hungarian Academy of Sciences, H-1111 Budapest nemeskey.david@sztaki.mta.hu Francis M. Tyers HSL-fakultetet, UiT Norgga ´arktalaˇs universitehta, 9017 Romsa (Norway) francis.tyers@uit.no Mans Hulden Department of Linguistics, University of Colorado Boulder 80309 Boulder, Colorado mans.hulden@colorado.edu Abstract In recent years, the problem of finite-state constraint grammar (CG) parsing has received renewed attention. Several compilers have been proposed to convert CG rules to finite-state transducers. While these formalisms serve their purpose as proofs of the concept, the performance of the generated transducers lags behind other CG implementations and taggers. In this paper, we argue that the fault lies with using generic finite-state libraries, and not with the formalisms themselves. We present an open-source implementation that capitalises on the characteristics of CG rule application to improve execution time. On smaller grammars our implementation achieves performance comparable to the current open-source state of the art. 1 Introduction Constraint grammar (CG), described originally by Karlsson (1990), is a rule-based formalism for vari- ous linguistics tasks, including morphological analysis, clause boundary detection and surface syntactic parsing. It has been used in a wide range of application areas, such as morphological disambiguation, grammar checking and machine translation (Bick, 2011). CG owns its popularity to two reasons: first, it achieves high accuracy on free text. Second, it works for languages where the annotated corpora required by statistical parsing methods are not available, but a linguist willing to work on the rules is. The orig- inal CG has since been superseded by CG-2 (Tapanainen, 1996) and lately, the free/open-source VISL CG-3 (Bick, 2000; Didriksen, 2011). Constraint grammar, however, has its drawbacks, one of which is speed. The Apertium machine translation project (Forcada et al., 2011) uses both CG (via VISL CG-3) and n-gram based models for morphological disambiguation, and while CG achieves higher accuracy, the n-gram model runs about ten times faster. In this paper, we investigate how using finite-state transducers (FST) for CG application can help to bridge the performance gap. In recent years, several methods have been proposed for compiling a CG to FST and applying it on text: Hulden (2011) compiles CG rules to transducers and runs them on the input sentences; Peltonen (2011) converts the sentences into ambiguous automata and attempts to eliminate branches by intersecting them with the rule FSTs; finally, Yli-Jyr¨a (2011) creates a single FST from the grammar and applies it on featurised input. Unfortunately, none of the authors report exact performance measurements of their systems. Yli-Jyr¨a published promising numbers for the preprocessing step, but nothing on the overall performance. Peltonen, on the other hand, observed that “VISL CG-3 was 1,500 times faster” than his implementation (Peltonen, 2011). This work is licensed under a Creative Commons Attribution 4.0 International Licence. Page numbers and proceedings footer are added by the organisers. Licence details: http://creativecommons.org/licenses/by/4.0/ 772 We do …

Content truncated to 500 words