PaperlayerView exact revision on arXiv

Source-linked AI summary

An Introduction to Conditional Random Fields

Charles Sutton, Andrew McCallum

arXiv:1011.4088v1stat.ML

TL;DR

Structured prediction must handle outputs whose variables depend on one another while exploiting rich observed features. This tutorial presents conditional random fields, which model p(y|x) using graphical structures, and develops their modeling, inference, learning, and implementation. It also highlights computational limits, including expensive training and approximate inference in complex settings.

  • Problem

    Predicting interdependent output variables from high-dimensional inputs is difficult because joint input-output modeling can be intractable or degrade performance when input dependencies are ignored.

  • Method

    The tutorial develops conditional random fields as conditional graphical models, covering their modeling, inference, parameter estimation, and practical implementation.

  • Results

    CRFs combine compact modeling of multivariate data with large input feature sets and support structured prediction across language, vision, and bioinformatics applications.

  • Takeaways & Limitations

    CRFs provide a framework for predicting complex structured outputs while avoiding the need to model dependencies involving only observed inputs.

  • Takeaways & Limitations

    For complex graphical structures, marginal distributions and the partition function may be intractable, requiring approximate inference embedded within parameter optimization.

Abstract

from arXiv · show

Often we wish to predict a large number of variables that depend on each other as well as on other observed variables. Structured prediction methods are essentially a combination of classification and graphical modeling, combining the ability of graphical models to compactly model multivariate data with the ability of classification methods to perform prediction using large sets of input features. This tutorial describes conditional random fields, a popular probabilistic method for structured prediction. CRFs have seen wide application in natural language processing, computer vision, and bioinformatics. We describe methods for inference and parameter estimation for CRFs, including practical issues for implementing large scale CRFs. We do not assume previous knowledge of graphical modeling, so this tutorial is intended to be useful to practitioners in a wide variety of fields.

Introduction

CRFs address structured prediction by modeling interdependent outputs conditional on rich observed features. The tutorial presents their formulation, inference and learning procedures, applications, and implementation concerns.

  • Motivation: Structured prediction assigns multiple interdependent output variables from observed features, including image regions, Go positions, DNA segments, and linguistic tags.Part-of-speech tagging illustrates the setup: each word receives a tag using lexical, orthographic, lexicon, and semantic features.
  • Motivation: Independent per-position classifiers can miss dependencies between neighboring labels and long-range structural effects such as grammar-rule choices in parse trees.
  • Motivation: Generative models must represent p(y, x), but modeling input dependencies can be intractable while ignoring them can reduce performance.
  • Conditional random fields: CRFs model p(y|x) directly, combining graphical models’ compact multivariate structure with classification’s ability to use many input features.Because input-only dependencies are irrelevant to the conditional model, CRFs can have simpler structure than joint models.
  • Tutorial scope: The tutorial covers CRF modeling, inference, parameter estimation, feature engineering, numerical stability, scalability, and relationships to other model families.It is designed for practitioners without prior graphical-modeling knowledge and discusses applications in text processing, bioinformatics, and computer vision.

Modeling

The modeling framework represents distributions over observed inputs and predicted outputs using local factors and graphical structures. It connects factorization with conditional independence while exposing normalization, computational, and parameterization issues.

  • Graphical modeling: Graphical models represent distributions over many variables as products of local functions, reducing the need to represent full joint tables.For n binary variables, a joint table requires O(2^n) values, whereas local factors can depend on much smaller subsets.
  • Setup: The tutorial considers observed input variables X and discrete output variables Y, with x denoting an input assignment and y the outputs to predict.
  • Undirected models: An undirected model defines distributions that factorize over scopes using positive factors or compatibility functions.The parameterization can be expressed with feature functions and sufficient statistics, placing the resulting family in the exponential family.
  • Undirected models: The normalization constant Z, or partition function, sums over exponentially many assignments and is generally intractable to compute.
  • Graphical structure: For strictly positive distributions, the Hammersley–Clifford theorem makes Markov-network conditional independence equivalent to factorization according to the graph.A factorization induces a Markov network by connecting variables that share a local function.
  • Graphical structure: Markov-network structure does not uniquely determine the factorization, so multiple parameterizations can represent the same graph while differing in restrictiveness.
  • Directed models: Directed graphical models factorize into locally normalized conditional distributions and therefore have global normalization Z = 1.

2.2 Generative versus Discriminative Models

Generative models represent the joint distribution of inputs and outputs, whereas discriminative models directly model p(y|x) for classification. The section contrasts their assumptions, feature flexibility, and potential trade-offs.

  • Naive Bayes represents a classifier with a directed model and an equivalent factor-graph representation.
  • Independent per-position classifiers are inadequate when output variables have dependencies, as in sequence labeling and structured prediction.
  • Generative models such as naive Bayes and HMMs model p(y, x), while discriminative models such as logistic regression focus on p(y|x).
  • Directly modeling p(y|x) avoids modeling dependencies among input features and supports richer, overlapping features.
  • Naive Bayes independence assumptions can hurt performance and produce overconfident probability estimates, especially when features are repeated or sequence evidence is combined.
  • Generative models may perform better on some small datasets, while discriminative models can overfit and neither approach is uniformly superior.

2.3 Linear-chain CRFs

Linear-chain CRFs arise by conditioning HMM-like sequence models and generalizing their feature functions. They retain efficient normalization through forward-backward while allowing observation-dependent transition scores and richer input features.

  • Conditioning an HMM joint distribution produces a linear-chain CRF with a particular choice of feature functions.
  • HMM-like CRFs use transition and state-observation feature functions to express the same distribution family as HMM parameterizations.
  • Linear-chain CRFs extend HMM-like models with richer features such as word prefixes, suffixes, and surrounding-word identities.
  • The normalization function sums over all state sequences but can be computed efficiently with the forward-backward algorithm.
  • Transition scores in CRFs can depend on the current observation by adding features coupling adjacent labels with the observation.
  • Feature observations at time t may include any global input components needed to compute the feature, including future words.

2.4 General CRFs

General CRFs extend linear-chain CRFs from chain factor graphs to arbitrary factor graphs. Their practical specification depends on factorization, repeated clique templates, and parameter tying.

  • General CRFs replace chain-specific forward-backward inference with inference methods suited to more general, possibly approximate, graphical structures.
  • A general CRF is a conditional distribution that factorizes according to a factor graph for every fixed input.
  • Exponential-family factors provide a parameterized representation of the conditional distribution over the graph.
  • Clique templates specify repeated factor structure and tie parameters across factors, as commonly done across positions in linear-chain CRFs.
  • Using separate clique templates assigns separate parameter sets to factors, whereas one shared template reuses parameters across the network.
  • Clique templates and the number of outputs can depend on the input, supporting structures such as multiscale image models.

2.5 Applications of CRFs

CRFs have been applied across text processing, bioinformatics, and computer vision. Applications use linear-chain, semi-Markov, grid, tree, dynamic, and fully connected structures for varied labeling and relational tasks.

  • CRFs have been applied to text processing, computer vision, and bioinformatics, including noun-phrase segmentation and protein-related tasks.
  • Semi-Markov CRFs allow features to depend on larger input segments, which can help information extraction and bioinformatics applications.
  • Dynamic CRFs can jointly model multiple labeling tasks, and one reported model improved over solving the tasks separately.
  • Fully connected CRFs have been used for proper-noun coreference, where inference corresponds to graph partitioning.
  • Grid-shaped CRFs support image labeling and segmentation, while tree-shaped CRFs use latent variables to recognize characteristic object parts.
  • CRFs have also been used for string matching and modeling distributions over grammar derivations when efficient dynamic programs are available.

2.6 Feature Engineering

CRF feature engineering uses output-configuration-specific observation functions, while balancing expressive coverage against computational cost and data representation choices.

  • Feature representation: Each feature activates for one output configuration, while its value depends only on the local input observation.This separates observation functions from output-specific weights and allows expensive input processing to be reused.
  • Feature coverage: Unsupported features can improve accuracy by assigning negative weights to unseen output configurations, but retaining them increases memory and time requirements.A standard natural-language task used 3.8 million features; unsupported features may therefore be removed to save memory.
  • Feature coverage: A heuristic reduces memory costs by adding unsupported features only for likely paths after initial CRF training.Features are added when an observed input configuration has posterior probability greater than ϵ for a training instance.
  • Feature representation: Categorical observations should be encoded as binary features, whereas real-valued features may benefit from normalization or binning.Integer vocabulary indices do not provide meaningful ordered values for learning linear weights.
  • Model design: Redundant node factors alongside edge factors provide a backoff that is useful when data are scarce relative to the number of features.The representation is especially useful in linear-chain CRFs with limited training data.

2.7 Notes on Terminology

Graphical-model terminology varies across research communities, so the tutorial distinguishes related names and avoids potentially confusing usages.

  • Terminology: Undirected models are also called Markov random fields, Markov networks, or Gibbs distributions, while “graphical model” denotes a graph-defined family of distributions.The tutorial reserves “random field” or “distribution” for a single probability distribution.
  • Terminology: Directed graphical models are commonly called Bayesian networks, but the tutorial avoids that term because it can be confused with Bayesian statistics.The literature uses “generative model,” although the term is not usually defined precisely.

Inference

CRF inference supports both most-probable labeling and marginal computation, with exact dynamic programming for linear chains and approximations needed for more complex graphs.

  • Inference tasks: Inference computes either the most likely labeling y∗ or the edge marginals and normalizer Z(x) needed during parameter estimation.These are the two central inference problems arising in CRFs.
  • Inference tasks: The two inference problems differ by semiring: replacing summation with maximization changes marginal computation into most-probable-assignment computation.Brute-force marginalization is exponential in the number of variables, and both tasks are intractable for general graphs.
  • Linear-chain inference: Linear-chain CRFs solve both tasks exactly with HMM-style dynamic programming: forward-backward computes marginals and Viterbi computes the best assignment.The same recursions apply after redefining transition weights, with forward-backward computing Z(x) rather than p(x).
  • Linear-chain inference: Caching reused intermediate sums in forward variables reduces the naive exponential computation to dynamic programming over vectors of state-specific partial sums.Backward recursions combine with forward values to obtain edge marginals, which are then renormalized.
  • General graphs: Exact inference for general graphs can use junction trees, but complex graphs generally require approximate inference and repeated inference during parameter estimation can be expensive.Approximate marginals substituted into optimization can create issues for procedures requiring accurate likelihood approximations.
  • Belief propagation: Loopy belief propagation has a variational interpretation in which fixed points correspond to constrained stationary points of the Bethe objective.Minimizing the Bethe objective provides an approximation log ZBethe to log Z for CRF parameter estimation.

Parameter Estimation

CRF parameters are estimated primarily by maximum likelihood, using inference inside optimization; tree-structured cases are tractable, whereas general graphs require approximations or alternative criteria.

  • Maximum likelihood: CRFs are trained by maximum likelihood, analogously to logistic regression but with greater computational demands from their richer structure.The model is typically trained on fully labeled independent data, though latent-variable and relational settings are also considered.
  • Structured optimization: For tree-structured CRFs, numerical optimization calls inference as a subroutine, and convex likelihood enables optimization procedures with provable convergence to the optimum.This tractability depends on the tree structure.
  • Structured optimization: Maximum-likelihood training is intractable for general CRFs, so practitioners can use approximate inference or choose a different training criterion.The tutorial also covers stochastic gradient descent and multithreaded training to accelerate parameter estimation.

4.1 Maximum Likelihood

CRF parameter estimation uses penalized conditional maximum likelihood, whose likelihood and gradient require inference over training instances. Concavity enables global optimization, while regularization and scalable second-order methods address high-dimensional models.

  • CRFs estimate parameters by maximizing the conditional log likelihood, typically with a penalty to reduce overfitting.The conditional objective models p(y|x), and regularization penalizes large weight vectors.
  • At an unregularized maximum-likelihood solution, empirical and model expectations of each feature function are equal.This follows because the gradient is zero when the two expectations match.
  • Computing the likelihood and gradient requires inference for each training instance, including partition functions and marginal distributions.These quantities depend on each input, so inference must be rerun whenever the likelihood is computed.
  • The log likelihood is concave, and regularization makes it strictly concave with exactly one global optimum.This makes second-order optimization applicable without local-optimum ambiguity.
  • Limited-memory BFGS and related approximate second-order methods avoid storing the quadratic-size Hessian required by Newton’s method.This matters because practical CRFs can have tens of thousands or millions of parameters.
  • Training a linear-chain CRF costs O(TM^2NG), with practical runtimes ranging from minutes to days depending on labels and data size.Here T is sequence length, M the number of labels, N the number of training instances, and G the number of gradient computations.

4.2 Stochastic Gradient Methods

Stochastic gradient methods update CRF parameters from individual training instances rather than full-batch scans. They trade less expensive gradient steps for step-size tuning and require iid data, but can substantially speed training on suitable datasets.

  • SGD randomly selects one training instance per iteration and updates parameters using that instance’s gradient.This reduces the data used for each gradient computation compared with batch optimization.
  • SGD trades potentially noisier update directions for gradients that can be computed much faster than batch directions.The method is motivated by updating after only a few examples rather than sweeping through the entire dataset.
  • SGD applies to arbitrary CRF graphical structures when training data are iid.The presentation uses linear-chain CRFs for notation, but the method extends beyond chains under this assumption.
  • The step size must decrease over iterations, with schedules such as α_m ∼ 1/m or α_m ∼ 1/√m supporting convergence.Poorly chosen step sizes can cause unstable updates or very slow training.
  • SGD requires tuning and is unsuitable for relational or small-data settings, but can provide considerable speedups on appropriate datasets.This is the principal trade-off relative to off-the-shelf solvers such as conjugate gradient and L-BFGS.

4.3 Parallelism

CRF gradient computation can be parallelized because the gradient is a sum over training instances. Multicore execution is straightforward, whereas distributing computation across machines introduces communication overhead.

  • Gradient computation divides naturally across threads because each thread can process a subset of training instances.The approach is especially direct on multicore machines.
  • Distributing gradients across machines can incur substantial overhead from transferring large parameter vectors over the network.Asynchronous parameter updates are suggested as one possible way to reduce this issue.

4.4 Approximate Training

Approximate CRF training is needed when complex graphical structures make partition functions and marginals intractable. Methods either optimize a surrogate likelihood or substitute approximate marginals, offering different optimization and flexibility trade-offs.

  • Tractable training methods assume the partition function and marginal distributions can be computed efficiently, as in chains and trees.More complex graphs, including grids and global language models, generally violate this assumption.
  • When inference is intractable, CRF training must use approximations embedded within the outer parameter-optimization procedure.The interaction between approximate inference and parameter estimation creates additional considerations beyond ordinary inference.
  • Approximate training either replaces the likelihood with a computable surrogate or directly approximates the marginal distributions.Surrogate likelihoods retain an explicit objective, whereas approximate-marginal methods are more flexible about the inference algorithm.
  • Approximate-inference interactions are not completely understood, including reported pathological behavior for perceptron training with max-product belief propagation.Convex surrogate likelihoods are described as avoiding this particular pathology.
  • Pseudolikelihood uses local conditional distributions, avoiding computation of the partition function and marginals.Its computational efficiency can come with poor performance, although larger blockwise conditionals typically improve parameter estimates.
  • Loopy belief propagation can provide approximate marginals for gradient updates or define a Bethe surrogate likelihood optimized as a saddlepoint problem.The approximate-gradient method substitutes BP marginals, while the surrogate approach optimizes max_θ min_q ℓ_Bethe(θ,q).

4.5 Implementation Concerns

The tutorial uses three NLP sequence-labeling tasks to illustrate CRF scale, reporting model sizes, dataset sizes, label counts, and training times. Training ranges from minutes to days, with the number of labels appearing to influence training time most.

  • Example tasks: CRF scale is illustrated through NP chunking, named-entity recognition, and part-of-speech tagging.These tasks involve identifying noun phrases, named entities, and each word’s part of speech.
  • Feature sets: The example feature sets include current and previous words, prefixes, suffixes, automatically generated tags, and lists of places and names.The authors present these features as useful for estimating scale, not as optimal task-specific sets.
  • Reported scale: Table 4.1 reports model parameters, training-set size, possible labels per position, and training time for each dataset.Training times range from minutes in the best case to days in the worst case.
  • Training cost: The number of labels seems to influence training time more than the other factors discussed.The text states this as an apparent influence rather than an experimentally isolated causal effect.
  • Training cost: The reported timings depend heavily on implementation and hardware, using MALLET, a 2.4 GHz Intel Xeon, batch L-BFGS, and no multithreading or stochastic training.These details bound how directly the example timings can be compared with other implementations.

Related Work and Future Directions

The tutorial situates CRFs among structured prediction, neural, directed, Bayesian, and structure-learning methods. It highlights practical trade-offs while identifying limited comparisons, computational demands, and unresolved structure-learning challenges.

  • Structured prediction: Structured prediction combines classification’s input features with graphical modeling of complex outputs through factorized local functions.The framework covers outputs such as sequences, trees, and other structured objects.
  • Alternative methods: Structured prediction methods differ in parameter-selection strategies, including maximum-margin optimization, search-based learning, and probabilistic marginalization.Maximum-margin methods optimize over assignments, while search-based methods learn during heuristic output search.
  • Open questions: The tutorial reports that careful comparisons among structured prediction methods, especially CRFs and max-margin approaches, remain limited across structures and domains.It also states that feature selection has more effect on performance than the differences among methods.
  • Neural networks: The tutorial presents structured output connections as sometimes reducing the need for hidden layers when features are strong, while hidden state generally sacrifices convexity.The text expects hidden state may still benefit harder problems.
  • MEMMs and directed models: MEMM training avoids sequence-level inference because its normalization sums over labels at one position, unlike CRF normalization over entire sequences.This makes directed-model training less computationally demanding in the described comparison.
  • MEMMs and directed models: The tutorial notes that directed conditional training still requires a marginal over inputs and can impose probability constraints that complicate optimization.Thus, conditional training of a directed model offers no strong computational benefit over CRFs in this discussion.
  • Bayesian CRFs: Bayesian methods for undirected CRFs are difficult to formulate efficiently and are not commonly used at the scale of current CRF applications.Approximate Bayesian inference is described as computationally demanding even for linear-chain models.
  • Open questions: All described methods assume the model structure is fixed, while learning conditional structure is difficult because pairwise marginals depend on the entire input.The conditional analogue of efficient tree-structure learning therefore requires difficult distribution estimates.
Loading 1011.4088v1…