Feature Lattices for Maximum Entropy Modelling

Andrei MikheevACL 1998

TL;DR

This paper introduces a novel, computationally efficient method for building maximum entropy models by using a "feature collocation lattice." This approach avoids the expensive iterative scaling algorithm during feature selection, significantly speeding up model training while achieving competitive or superior performance on tasks like sentence boundary disambiguation.

What Problem Does This Paper Address?

Maximum entropy (MaxEnt) models are powerful for statistical language modeling, offering a principled way to incorporate diverse knowledge sources. However, a major bottleneck is the computational expense of the model building process, particularly the parameter estimation using iterative scaling. This expense becomes even more pronounced during feature selection, where many candidate features need to be evaluated repeatedly. Traditional feature selection methods often involve re-estimating parameters for each candidate, which is prohibitively slow. The authors aim to address this by developing a feature selection technique that bypasses iterative scaling during the selection phase, making MaxEnt model building more practical.

Methods

The core innovation is the feature collocation lattice. This lattice is built from a training sample and represents both the observed configurations and potential generalizations. It consists of nodes that can act as either configurations or features. The lattice is constructed by adding observed configurations and their shared sub-configurations, creating a structure that captures interactions between features.

The key to their approach lies in the feature selection process, which operates on this lattice. Instead of iterative scaling, they use a frequency redistribution algorithm. When a new feature (atomic or complex) is added to an "optimized lattice" (a subset of the empirical lattice), the configuration frequencies are updated. This process incrementally builds a smaller, optimized feature space. The algorithm selects features that contribute most to the model's fit by minimizing Kullback-Leibler divergence or maximizing log-likelihood, all without re-running the full iterative scaling for each candidate.

For model generalization, they apply a relaxation process. After building the optimized lattice, they constrain only nodes with reliable statistics to avoid overfitting. Then, they iteratively unconstrain less specific features, simplifying the model while maintaining performance. This process resembles backward sequential search but avoids iterative scaling for feature ranking, using it only for model recomputation.

Datasets

The paper mentions using the Wall Street Journal (WSJ) corpus for the sentence boundary disambiguation task. They also collected 51,000 samples from the WSJ corpus for training their MaxEnt model, specifically for the fullstop problem. For evaluation, they used 27,294 sentences from the same corpus, which were unseen during training.

Key Insights and Ideas

  • Feature lattices as a shortcut: The feature collocation lattice provides a rich representation of feature interactions that can be exploited for efficient feature selection, bypassing the need for repeated iterative scaling.
  • Frequency redistribution for speed: The novel frequency redistribution algorithm is the key to making feature selection computationally tractable. It allows for rapid updates of feature contributions as the model grows.
  • Generalization through relaxation: The approach to unconstraining features after initial model building is crucial for creating compact, yet powerful, models that generalize well. This is achieved by focusing on the most specific constraints and then simplifying.
  • Avoiding over-generation: The lattice construction method is designed to include only logically possible configurations and generalizations, preventing the inclusion of spurious or unhelpful features.

Key Results

The paper demonstrates significant computational savings. For the sentence boundary disambiguation task, their method reduced the lattice of 8,245 nodes to 769 nodes in 53 minutes, and then to 283 nodes (with only 31 atomic features) in a further two hours. This model achieved a 99.2477% accuracy on the test set, which they claim is the highest quoted score known to the authors for this task. They also report good generalization for part-of-speech tagging with only a tiny degradation in performance on a new domain.

Limitations and Future Work

A potential drawback acknowledged is the requirement to build the feature collocation lattice for the entire observed feature space, which might be infeasible for applications with a vast number of features.

Future work directions include:

  • Finding efficient ways to decompose the feature lattice into non-overlapping sub-lattices to handle larger feature spaces.
  • Introducing an "or" operation on lattice nodes to provide further generalization capabilities.

Summary updated

BibTeX
@inproceedings{mikheev1998feature,
  author = {Andrei Mikheev},
  title = {{Feature Lattices for Maximum Entropy Modelling}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1998},
}
Figure