Practical Very Large Scale CRFs

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 504–513, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Practical very large scale CRFs Thomas Lavergne LIMSI – CNRS lavergne@limsi.fr Olivier Capp´e T´el´ecom ParisTech LTCI – CNRS cappe@enst.fr Franc¸ois Yvon Universit´e Paris-Sud 11 LIMSI – CNRS yvon@limsi.fr 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 be- tween labels. Even for the simple linear- chain model, taking structure into account implies a number of parameters and a computational effort that grows quadrati- cally with the cardinality of the label set. In this paper, we address the issue of train- ing very large CRFs, containing up to hun- dreds output labels and several billion fea- tures. Efficiency stems here from the spar- sity induced by the use of a ℓ1 penalty term. Based on our own implementa- tion, we compare three recent proposals for implementing this regularization strat- egy. Our experiments demonstrate that very large CRFs can be trained efficiently and that very large models are able to im- prove the accuracy, while delivering com- pact parameter sets. 1 Introduction Conditional Random Fields (CRFs) (Lafferty et al., 2001; Sutton and McCallum, 2006) constitute a widely-used and effective approach for super- vised structure learning tasks involving the map- ping between complex objects such as strings and trees. An important property of CRFs is their abil- ity to handle large and redundant feature sets and to integrate structural dependency between out- put labels. However, even for simple linear chain CRFs, the complexity of learning and inference This work was partly supported by ANR projects CroTaL (ANR-07-MDCO-003) and MGA (ANR-07-BLAN-0311- 02). grows quadratically with respect to the number of output labels and so does the number of structural features, ie. features testing adjacent pairs of la- bels. Most empirical studies on CRFs thus ei- ther consider tasks with a restricted output space (typically in the order of few dozens of output la- bels), heuristically reduce the use of features, es- pecially of features that test pairs of adjacent la- bels1, and/or propose heuristics to simulate con- textual dependencies, via extended tests on the ob- servations (see discussions in, eg., (Punyakanok et al., 2005; Liang et al., 2008)). Limitating the feature set or the number of output labels is how- ever frustrating for many NLP tasks, where the type and number of potentially relevant features are very large. A number of studies have tried to alleviate this problem. Pal et al. (2006) propose to use a “sparse” version of the forward-backward algorithm during training, where sparsity is en- forced through beam pruning. Related ideas are discussed by Dietterich et al. (2004); by Cohn (2006), who considers “generalized” feature func- tions; and by Jeong et al. (2009), who use approx- imations to simplify the forward-backward recur- sions. In this paper, we show that the sparsity that is induced by ℓ1-penalized estimation of …

Content truncated to 500 words