Efficiently Inducing Features of Conditional Random Fields

By Andrew McCallum. Conference on Uncertainty in Artificial Intelligence, 2002

482 citations recorded by the source corpus.

Conditional Random Fields (CRFs) are undirected graphical models, a special case of which correspond to conditionally-trained finite state machines. A key advantage of CRFs is their great flexibility to include a wide variety of arbitrary, non-independent features of the input. Faced with this freedom, however, an important question remains: what features should be used? This paper presents an efficient feature induction method for CRFs. The method is founded on the principle of iteratively constructing feature conjunctions that would significantly increase conditional log-likelihood if added to the model. Automated feature induction enables not only improved accuracy and dramatic reduction in parameter count, but also the use of larger cliques, and more freedom to liberally hypothesize atomic input variables that may be relevant to a task. The method applies to linear-chain CRFs, as well as to more arbitrary CRF structures, such as Relational Markov Networks, where it corresponds to learning clique templates, and can also be understood as supervised structure learning. Experimental results on named entity extraction and noun phrase segmentation tasks are presented.

Subfields: Artificial Intelligence, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/55c200c363a0e07b7260022c18efe67d60926c13

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Conditional models for contextual human motion recognition (2006, background): “By virtue of the global normalization, entire state sequences are interpreted jointly, and this allows individual states to boost or damp the probability mass transferred to their successive states.”
Applying Conditional Random Fields to Japanese Morphological Analysis (2004, background): “For this challenge, McCallum proposes an interesting research avenue to explore (McCallum, 2003).”
Discriminatively trained Markov model for sequence classification (2005, methodology): “McCallum [13] described discriminative probabilistic graphical models in the form of Conditional Random Fields (CRFs) for speech recognition.”
BANNER: An Executable Survey of Advances in Biomedical Named Entity Recognition (2007, methodology): “Finally, entity names in biomedical text are longer on average than names from other domains, it is generally much easier – for both humans and automated systems – to determine whether an entity name is present than it is to detect its boundaries [7, 19, 20].”
Web-scale information extraction in knowitall: (preliminary results) (2004, unknown): “Much of the previous work on Information Extraction (IE) has focused on the use of supervised learning techniques such as hidden Markov Models [12, 25], rule learning [27, 26], or Conditional Random Fields [ 20 ].”
Conditional random fields for activity recognition (2007, methodology): “, [39]), and a CRF-specific feature induction algorithm due to McCallum [73].”
Identifying Sources of Opinions with Conditional Random Fields and Extraction Patterns (2005, methodology): “We developed our CRF model using the MALLET code from McCallum (2002).”
Accurate Information Extraction from Research Papers using Conditional Random Fields (2004, unknown): “Feature induction (McCallum, 2003) has been shown to provide significant improvements in CRFs performance.”
Semi-Supervised Learning for Natural Language (2005, background): “Instead of working with a fixed feature vector representation (x, y), we can induce the most useful features at training time (Pietra et al., 1997; McCallum, 2003).”
Efficient Structure Learning of Markov Networks using L1-Regularization (2006, background): “One approach [6, 14] adds features so as to greedily improve t he model likelihood; once a feature is added, it is never removed.”
Relational Dependency Networks (2007, methodology): “Recent work on conditional random fields for sequence analysis includes a feature selection algorithm (McCallum, 2003) that could be extended for RMNs.”
Extracting Places and Activities from GPS Traces Using Hierarchical Conditional Random Fields (2007, background): “The feature functions, which are often binary or real valued, are typically designed by the user (combinations of such functions can be learned from data [24]).”
Interactive Information Extraction with Constrained Conditional Random Fields (2004, unknown): “CRFs have been shown to perform well on information extraction tasks (McCallum & Li 2003; Pinto et al. 2003; McCallum 2003; Sha & Pereira 2003), and are well-suited for interactive information extraction since the confi dence of the labels can be estimated and there is a natural scheme for…”
A Brief Survey of Text Mining (2005, methodology): “The unknown parameter values ‚jr and „jr are usually estimated using conjugate gradient optimization routines [ McC03 ].”
Semi-supervised learning with graphs (2005, methodology): “Following McCallum (2003), we make a set of speed up approximations.”
Discriminative Training of Markov Logic Networks (2005, methodology): “(McCallum 2003)), maximum-margin learning of MLN parameters (cf.”
Learning to Combine Bottom-Up and Top-Down Segmentation (2006, background): “Similar ideas in other contexts have be en proposed by [23, 9, 13].”
Learning Setting-Generalized Activity Models for Smart Spaces (2010, methodology): “These weights are learned through an expectation maximization process based on the training data [10].”