Efficient Higher-Order CRFs for Morphological Tagging

Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 322–332, Seattle, Washington, USA, 18-21 October 2013. c⃝2013 Association for Computational Linguistics Efficient Higher-Order CRFs for Morphological Tagging Thomas M¨uller†‡, Helmut Schmid†‡, and Hinrich Sch¨utze† †Center for Information and Language Processing, University of Munich, Germany ‡Institute for Natural Language Processing , University of Stuttgart, Germany muellets@cis.lmu.de Abstract Training higher-order conditional fields is prohibitive for huge tag sets.random We present an approximated conditional random field using coarse-to-fine decoding and early updating. We show that our implementation yields fast and accurate morphological taggers across six languages with different morpho- logical properties and that across languages higher-order models give significant improve- ments over 1st-order models. 1 Introduction Conditional Random Fields (CRFs) (Lafferty et al., 2001) are arguably one of the best performing se- quence prediction models for many Natural Lan- guage Processing (NLP) tasks. During CRF train- ing forward-backward computations, a form of dy- namic programming, dominate the asymptotic run- time. The training and also decoding times thus depend polynomially on the size of the tagset and exponentially on the order of the CRF. This prob- ably explains why CRFs, despite their outstanding accuracy, normally only are applied to tasks with small tagsets such as Named Entity Recognition and Chunking; if they are applied to tasks with bigger tagsets – e.g., to part-of-speech (POS) tagging for English – then they generally are used as 1st-order models. In this paper, we demonstrate that fast and accu- rate CRF training and tagging is possible for large tagsets of even thousands of tags by approximat- ing the CRF objective function using coarse-to-fine decoding (Charniak and Johnson, 2005; Rush and Petrov, 2012). Our pruned CRF (PCRF) model has much smaller runtime than higher-order CRF mod- els and may thus lead to an even broader application of CRFs across NLP tagging tasks. We use POS tagging and combined POS and morphological (POS+MORPH) tagging to demon- strate the properties and benefits of our approach. POS+MORPH disambiguation is an important pre- processing step for syntactic parsing. It is usually tackled by applying sequence prediction. POS+MORPH tagging is also a good example of a task where CRFs are rarely applied as the tagsets are often so big that even 1st-order dynamic program- ming is too expensive. A workaround is to restrict the possible tag candidates per position by using ei- ther morphological analyzers (MAs), dictionaries or heuristics (Hajiˇc, 2000). In this paper, however we show that when using pruning (i.e., PCRFs), CRFs can be trained in reasonable time, which makes hard constraints unnecessary. In this paper, we run successful experiments on six languages with different morphological prop- erties; we interpret this as evidence that our ap- proach is a general solution to the problem of POS+MORPH tagging. The tagsets in our experi- ments range from small sizes of 12 to large sizes of up to 1811. We will see that even for the smallest tagset, PCRFs need only 40% of the training time of standard CRFs. For the …

Content truncated to 500 words