Inducing Features of Random Fields

By Stephen Della Pietra, V. D. Pietra, John D. Lafferty. 1995

We present a technique for constructing random fields from a set of training samples. The learning paradigm builds increasingly complex fields by allowing potential functions, or features, that are supported by increasingly large subgraphs. Each feature has a weight that is trained by minimizing the Kullback-Leibler divergence between the model and the empirical distribution of the training data. A greedy algorithm determines how features are incrementally added to the field and an iterative scaling algorithm is used to estimate the optimal values of the weights. The random field models and techniques introduced in this paper differ from those common to much of the computer vision literature in that the underlying random fields are non-Markovian and have a large number of parameters that must be estimated. Relations to other learning approaches, including decision trees, are given. As a demonstration of the method, we describe its application to the problem of automatic word classification in natural language processing.

Subfields: Probabilistic & Bayesian Methods

How researchers see this paper

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

In Probabilistic & Bayesian Methods

Citations in the corpus

Learning Non-Convergent Non-Persistent Short-Run MCMC Toward Energy-Based Model (2019, positive): “For any pθ ∈ Θ and for any p ∈ Ω, we have the Pythagorean property [36]: KL(p|pθ ) = KL(p|p̂)+KL(p̂|pθ ).”
Classes for fast maximum entropy training (2001, methodology): “GIS uses the maximum of this value to slow learning, while IIS slows learning on a case-by-case basis.”
Thumbs up? Sentiment Classification using Machine Learning Techniques (2002, methodology): “We use ten iterations of the improved iterative scaling algorithm (Della Pietra et al., 1997) for parameter training (this was a sufficient number of iterations for convergence of training-data accuracy), together with a Gaussian prior to prevent overfitting (Chen and Rosenfeld, 2000).”
Incorporating Non-local Information into Information Extraction Systems by Gibbs Sampling (2005, methodology): “1Prior uses in NLP of which we are aware include: Kim et al. (1995), Della Pietra et al. (1997) and Abney (1997).”
Kernel methods in machine learning (2007, neutral): “• For the parametric case, Lafferty et al. [90] have employed variants of improved iterative scaling (Darroch and Ratcliff [40] and Della Pietra [46]) to optimize equation (72), whereas Sha and Pereira [122] have investigated preconditioned conjugate gradient descent and limited memory quasi-Newton ”
A Comprehensive Survey on Transfer Learning (2019, methodology): “Therefore, in the final step, the crossdomain dense correspondences are established between the test image and the retrieved best matching image at first, and then the annotations of the best matching image are transferred to the test image via the Markov random field model [180], [181].”
Wasserstein Introspective Neural Networks (2017, background): “Before the deep learning era [16], generative modeling had been an area with a steady pace of development [1, 6, 52, 34, 47, 51].”
Shallow Parsing with Conditional Random Fields (2003, methodology): “Lafferty et al. (2001) used iterative scaling algorithms for CRF training, following earlier work on maximumentropy models for natural language (Berger et al., 1996; Della Pietra et al., 1997).”
StatSnowball: a statistical approach to extracting entity relationships (2009, background): “Pattern selection in StatSnowball is the problem of structure learning in Markov logic networks [12] or the problem of feature induction in Markov random fields [19, 16].”
Learning how to inpaint from global image statistics (2003, methodology): “Typically, one chooses the features based on a notion of informativeness and then chooses the tables based on the maximum likelihood or maximum entropy criterion [22, 7].”
Dual coordinate descent methods for logistic regression and maximum entropy models (2011, background): “Darroch and Ratcliff (1972), Della Pietra et al. (1997), Goodman (2002), Jin et al. (2003) and many others have proposed iterative scaling methods.”
Conditional random fields for activity recognition (2007, background): “incrementally added features to Markov random fields for text classification [21].”
Structured Sparsity in Structured Prediction (2011, background): “The fact that models with few features (“sparse” models) are desirable for several reasons (compactness, interpretability, good generalization) has stimulated much research work which has produced a wide variety of methods (Della Pietra et al., 1997; Guyon and Elisseeff, 2003; McCallum, 2003).”
Applying Conditional Random Fields to Japanese Morphological Analysis (2004, methodology): “, IIS or GIS (Pietra et al., 1997)) or more efficient quasi-Newton methods (e.”