Practical Very Large Scale CRFs

Thomas Lavergne, Olivier Cappé, François YvonACL 2010 · OpenReview

Abstract

Conditional Random Fields (CRFs) are a widely-used approach for supervised sequence labelling, notably due to their ability to handle large description spaces and to integrate structural dependency between labels. Even for the simple linear-chain model, taking structure into account implies a number of parameters and a computational effort that grows quadratically with the cardinality of the label set. In this paper, we address the issue of training very large CRFs, containing up to hundreds output labels and several billion features. Efficiency stems here from the sparsity induced by the use of a $L_1$ penalty term. Based on our own implementation, we compare three recent proposals for implementing this regularization strategy. Our experiments demonstrate that very large CRFs can be trained efficiently and that very large models are able to improve the accuracy, while delivering compact parameter sets.

Introduction

Conditional Random Fields (CRFs) are the gold standard for sequence labeling tasks like Part-of-Speech (POS) tagging or phonetization. However, they suffer from a major scaling bottleneck: the computational cost grows quadratically ($|Y|^2$) with the number of possible labels. In a standard "linear-chain" CRF, features often look at pairs of adjacent labels (bigrams). With 100 possible labels, there are 10,000 possible transitions for every observation. When combined with large input feature sets, the parameter space can explode into the billions. Traditionally, researchers avoided this by limiting label sets or using heuristics to prune features. This paper explores whether we can instead embrace these massive feature sets and leverage $L_1$ regularization to handle the complexity.

Methods and Sparse Implementation

The authors focus on $L_1$ regularization (and Elastic Net) to induce sparsity, forcing irrelevant feature weights to zero for automatic selection. They compare three optimization strategies:

  1. OWL-QN (Orthant-Wise Limited-memory Quasi-Newton): An extension of L-BFGS for non-differentiable $L_1$ penalties.
  2. SGD (Stochastic Gradient Descent): A version using "clipping" to maintain sparsity during updates.
  3. BCD (Block Coordinate Descent): Updates one "block" of features at a time.

A key innovation is the "Sparse Forward-Backward" recursion. By treating the transition matrix as sparse (due to $L_1$ zeroing out many parameters), the complexity of CRF training is reduced from $O(|Y|^2)$ to being proportional to the number of active transitions.

Figure 2: Training time comparison showing the efficiency of the sparse forward-backward implementation (l1-sparse) compared to standard l2 and l1 methods.

Experimental Results

The approach was evaluated on Nettalk (phonetization) and Penn Treebank (POS tagging). For Nettalk, feature sets reached up to 1.6 billion features.

Algorithm Trade-offs

The experiments revealed distinct characteristics for each optimizer:

  • SGD reaches a decent solution quickly but is hard to parallelize.
  • OWL-QN is robust for medium-sized problems and easily parallelized.
  • BCD is memory-efficient but slow for long sequences like those in POS tagging.
Figure 4: Performance comparison of OWL-QN, SGD, and BCD across different n-gram feature sets, showing iterations, active features, error rates, and total training time.

Key Insights

  • Bigger is Better (and Smaller): Billions of features improved accuracy, yet $L_1$ regularization kept the final models compact. For example, in a Nettalk task with 250 million potential features, only 50,000 (0.02%) remained active.
  • Sparsity Speeds Up Inference: Zeroed-out features reduce the computational load during decoding, leading to faster performance and a smaller memory footprint.
  • Competitive Accuracy: The model achieved a 2.63% error rate on Penn Treebank POS tagging, competitive with state-of-the-art results at the time.

Conclusion

Training CRFs with billions of features is feasible and beneficial when leveraging $L_1$ sparsity and optimized algorithms. While BCD has limitations with common observations in large corpora, OWL-QN and SGD provide powerful alternatives. Future work includes applying these techniques to higher-order or hierarchical CRFs where label set bottlenecks are even more pronounced. The software developed for this paper was released as the open-source toolkit Wapiti.

Summary updated

Abstract

Conditional Random Fields (CRFs) are a widely-used approach for supervised sequence labelling, notably due to their ability to handle large description spaces and to integrate structural dependency between labels. Even for the simple linear-chain model, taking structure into account implies a number of parameters and a computational effort that grows quadratically with the cardinality of the label set. In this paper, we address the issue of training very large CRFs, containing up to hundreds output labels and several billion features. Efficiency stems here from the sparsity induced by the use of a l penalty term. Based on our own implementation, we compare three recent proposals for implementing this regularization strategy. Our experiments demonstrate that very large CRFs can be trained efficiently and that very large models are able to improve the accuracy, while delivering compact parameter sets.
BibTeX
@inproceedings{lavergne2010practical,
  author = {Thomas Lavergne and Olivier Cappé and François Yvon},
  title = {{Practical Very Large Scale CRFs}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2010},
  url = {https://openreview.net/forum?id=B1-MTjgOWr},
}
Figure