Learning the Structure of Variable-Order CRFs: a finite-state perspective

Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 433–439 Copenhagen, Denmark, September 7–11, 2017. c⃝2017 Association for Computational Linguistics Learning the Structure of Variable-Order CRFs: a Finite-State Perspective Thomas Lavergne and François Yvon LIMSI, CNRS, Univ. Paris-Sud, Université Paris Saclay Campus Universitaire, F-91 403 Orsay, France {lavergne,yvon}@limsi.fr Abstract The computational complexity of linear- chain Conditional Random Fields (CRFs) makes it difficult to deal with very large label sets and long range dependencies. Such situations are not rare and arise when dealing with morphologically rich languages or joint labelling tasks. We ex- tend here recent proposals to consider vari- able order CRFs. Using an effective finite- state representation of variable-length de- pendencies, we propose new ways to per- form feature selection at large scale and re- port experimental results where we outper- form strong baselines on a tagging task. 1 Introduction Conditional Random Fields (CRFs) (Lafferty et al., 2001; Sutton and McCallum, 2006) are a method of choice for many sequence labelling tasks such as Part of Speech (PoS) tagging, Text Chunking, or Named Entity Recognition. Linear- chain CRFs are easy to train by solving a convex optimization problem, can accomodate rich fea- ture patterns, and enjoy polynomial exact infer- ence procedures. They also deliver state-of-the-art performance for many tasks, sometimes surpass- ing seq2seq neural models (Schnober et al., 2016). A major issue with CRFs is the complexity of training and inference procedures, which are quadratic in the number of possible output la- bels for first order models and grow exponen- tially when higher order dependencies are consid- ered. This is problematic for tasks such as precise PoS tagging for Morphologically Rich Languages (MRLs), where the number of morphosyntactic la- bels is in the thousands (Hajiˇc, 2000; Müller et al., 2013). Large label sets also naturally arise when joint labelling tasks (eg. simultaneous PoS tag- ging and text chunking) are considered, For such tasks, processing first-order models is demanding, and full size higher-order models are out of the question. Attempts to overcome this difficulty are based on a greedy approach which starts with first- order dependencies between labels and iteratively increases the scope of dependency patterns under the constraint that a high-order dependency is se- lected only if it extends an existing lower order feature (Müller et al., 2013). As a result, fea- ture selection may only choose only few higher- order features, motivating the need for an effec- tive variable-order CRF (voCRF) training proce- dure (Ye et al., 2009).1 The latest implementation of this idea (Vieira et al., 2016) relies on (struc- tured) sparsity promoting regularization (Martins et al., 2011) and on finite-state techniques, han- dling high-order features at a small extra cost (see § 2). In this approach, the sparse set of label de- pendency patterns is represented in a finite-state automaton, which arises as the result of the fea- ture selection process. In this paper, we somehow reverse the perspec- tive and consider VoCRF training mostly as an au- tomaton inference problem. This …

Content truncated to 500 words