Speed-Accuracy Tradeoffs in Tagging with Variable-Order CRFs and Structured Sparsity

Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 1973–1978, Austin, Texas, November 1-5, 2016. c⃝2016 Association for Computational Linguistics Speed-Accuracy Tradeoffs in Tagging with Variable-Order CRFs and Structured Sparsity Tim Vieira∗and Ryan Cotterell∗and Jason Eisner Department of Computer Science Johns Hopkins University {timv,ryan.cotterell,jason}@cs.jhu.edu Abstract We propose a method for learning the structure of variable-order CRFs, a more flexible variant of higher-order linear-chain CRFs. Variable- order CRFs achieve faster inference by in- cluding features for only some of the tag n- grams. Our learning method discovers the useful higher-order features at the same time as it trains their weights, by maximizing an objective that combines log-likelihood with a structured-sparsity regularizer. An active-set outer loop allows the feature set to grow as far as needed. On part-of-speech tagging in 5 randomly chosen languages from the Universal Dependencies dataset, our method of shrink- ing the model achieved a 2–6x speedup over a baseline, with no significant drop in accuracy. 1 Introduction Conditional Random Fields (CRFs) (Lafferty et al., 2001) are a convenient formalism for sequence label- ing tasks common in NLP. A CRF defines a feature- rich conditional distribution over tag sequences (out- put) given an observed word sequence (input). The key advantage of the CRF framework is the flexibility to consider arbitrary features of the input, as well as enough features over the output structure to encourage it to be well-formed and consistent. How- ever, inference in CRFs is fast only if the features over the output structure are limited. For example, an order-k CRF (or “k-CRF” for short, with k > 1 being “higher-order”) allows expressive features over a window of k+1 adjacent tags (as well as the input), and then inference takes time O(n·|Y |k+1), where Y is the set of tags and n is the length of the input. How large does k need to be? Typically k = 2 works well, with big gains from 0 → 1 and modest ∗Equal contribution 0 1000 2000 3000 4000 5000 Number of Tag String Features 91 92 93 94 95 96 97 98 Accuracy 0-CRF 1-CRF 2-CRF Bulgarian Norwegian Hindi Slovenian Basque Figure 1: Speed-accuracy tradeoff curves on test data for the 5 languages. Large dark circles represent the k- CRFs of ascending orders along x-axis (marked on for Slovenian). Smaller triangles each represent a VoCRF discovered by sweeping the speed parameters γ. We find faster models at similar accuracy to the best k-CRFs (§5). gains from 1→2 (Fig. 1). Small k may be sufficient when there is enough training data to allow the model to attend to many fine-grained features of the input (Toutanova et al., 2003; Liang et al., 2008). For ex- ample, when predicting POS tags in morphologically- rich languages, certain words are easily tagged based on their spelling without considering the context (k=0). In fact, such languages tend to have a more free word order, making tag context less useful. We investigate a hybrid approach that gives the accuracy of higher-order …

Content truncated to 500 words