Abstract: Tim Vieira, Ryan Cotterell, Jason Eisner. Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing.
2016.
Introduction
In natural language processing, sequence labeling tasks like Part-of-Speech (POS) tagging often rely on Conditional Random Fields (CRFs). To improve accuracy, researchers typically move from "lower-order" models (looking at tag pairs) to "higher-order" models (looking at triples or more). However, this comes with a significant computational cost: the complexity of inference in an order-$k$ CRF scales as $O(n \cdot |Y|^{k+1})$, where $|Y|$ is the tagset size. Moving from order-1 to order-2 can make a model substantially slower, even if only a few specific higher-order dependencies are actually informative. This paper introduces a framework to automatically discover and utilize only the necessary higher-order context, achieving state-of-the-art accuracy with 2–6x faster inference.
Variable-Order CRFs and Structured Sparsity
The authors propose Variable-Order CRFs (VoCRFs), which allow for features derived from tag subsequences of varying lengths. To manage the potentially massive feature space, they employ two key strategies:
- Tree-Structured Group Lasso: Tag sequences are organized into a prefix tree. For example, the trigram "A B C" is a descendant of the bigram "B C". By applying a group Lasso penalty to the training objective, the model encourages entire branches of this tree to be zeroed out. If a specific bigram is not useful, the model prunes it and all its higher-order extensions.
- Active Set Method: Rather than training on all possible features, the algorithm starts with a simple model and incrementally adds only those features that the optimization process identifies as potentially beneficial.
Experimental Setup
The method was evaluated on POS tagging using the Universal Dependencies (UD) dataset across five typologically diverse languages: Basque, Bulgarian, Hindi, Norwegian, and Slovenian. This selection ensures that the findings regarding context requirements are not specific to a single language family.
Key Results and Insights
The researchers found that the number of tag string features ($|W|$) serves as an excellent proxy for real-world speed, showing a >99% Pearson correlation with wall-clock time.
The Pareto Frontier of Accuracy
As shown in the performance plots, VoCRF models consistently form a "Pareto frontier." They provide the highest possible accuracy for any given computational budget (feature count). In many instances, the VoCRF reached the accuracy of a standard order-2 CRF (using ~4,900 features) while using a feature set only slightly larger than an order-1 CRF (~289 features).
Language-Specific Context Requirements
A notable insight is that context needs are language-dependent. For example, Hindi POS tagging reaches peak accuracy with very little tag context. Conversely, Slavic languages like Slovenian and Bulgarian show significant gains from the selective use of higher-order features. The VoCRF naturally adapts to these needs, learning to be "lazy" by using complex features only for specific, ambiguous sequences.
Conclusion
By combining Variable-Order CRFs with structured sparsity, this work demonstrates that we do not need to choose between the speed of simple models and the accuracy of complex ones. The proposed framework automatically identifies the most informative dependencies, resulting in models that are both efficient and highly accurate. Future work may extend this approach to tasks with larger label sets, such as named entity recognition or dependency parsing.
Summary updated