Scaling Conditional Random Fields Using Error-Correcting Codes

Proceedings of the 43rd Annual Meeting of the ACL, pages 10–17, Ann Arbor, June 2005. c⃝2005 Association for Computational Linguistics Scaling Conditional Random Fields Using Error-Correcting Codes Trevor Cohn Department of Computer Science and Software Engineering University of Melbourne, Australia tacohn@csse.unimelb.edu.au Andrew Smith Division of Informatics University of Edinburgh United Kingdom a.p.smith-2@sms.ed.ac.uk Miles Osborne Division of Informatics University of Edinburgh United Kingdom miles@inf.ed.ac.uk Abstract Conditional Random Fields (CRFs) have been applied with considerable success to a number of natural language processing tasks. However, these tasks have mostly involved very small label sets. When deployed on tasks with larger label sets, the requirements for computational resources mean that training becomes intractable. This paper describes a method for train- ing CRFs on such tasks, using error cor- recting output codes (ECOC). A number of CRFs are independently trained on the separate binary labelling tasks of distin- guishing between a subset of the labels and its complement. During decoding, these models are combined to produce a predicted label sequence which is resilient to errors by individual models. Error-correcting CRF training is much less resource intensive and has a much faster training time than a standardly formulated CRF, while decoding performance remains quite comparable. This allows us to scale CRFs to previously impossible tasks, as demonstrated by our experiments with large label sets. 1 Introduction Conditional random fields (CRFs) (Lafferty et al., 2001) are probabilistic models for labelling sequential data. CRFs are undirected graphical models that define a conditional distribution over label sequences given an observation sequence. They allow the use of arbitrary, overlapping, non-independent features as a result of their global conditioning. This allows us to avoid making unwarranted independence assumptions over the observation sequence, such as those required by typical generative models. Efficient inference and training methods exist when the graphical structure of the model forms a chain, where each position in a sequence is connected to its adjacent positions. CRFs have been applied with impressive empirical results to the tasks of named entity recognition (McCallum and Li, 2003), simplified part-of-speech (POS) tagging (Lafferty et al., 2001), noun phrase chunking (Sha and Pereira, 2003) and extraction of tabular data (Pinto et al., 2003), among other tasks. CRFs are usually estimated using gradient-based methods such as limited memory variable metric (LMVM). However, even with these efficient methods, training can be slow. Consequently, most of the tasks to which CRFs have been applied are relatively small scale, having only a small number of training examples and small label sets. For much larger tasks, with hundreds of labels and millions of examples, current training methods prove intractable. Although training can potentially be parallelised and thus run more quickly on large clusters of computers, this in itself is not a solution to the problem: tasks can reasonably be expected to increase in size and complexity much faster than any increase in computing power. In order to provide scalability, the factors which most affect the resource usage and runtime of the training method 10 must be addressed …

Content truncated to 500 words