Concavity and Initialization for Unsupervised Dependency Parsing

Kevin Gimpel, Noah A. SmithNAACL 2012 · OpenReview

TL;DR

This paper tackles the challenge of "bumpy" objective functions in unsupervised NLP, which often lead to unstable learning and reliance on good initializations. The authors introduce novel, concave models for dependency grammar induction that provide stable, data-driven initializations, significantly improving performance when used with existing state-of-the-art models.

What Problem Does This Paper Address?

Unsupervised learning in Natural Language Processing (NLP) is notoriously difficult because the objective functions researchers try to optimize are often "bumpy," meaning they have many local maxima. This makes it hard for algorithms to find the true best solution, forcing researchers to carefully choose initial parameter values. The paper highlights that most unsupervised NLP models, including those for part-of-speech tagging and grammar induction, suffer from non-concave log-likelihood functions. This necessitates the use of ad-hoc initialization strategies, which can lead to significant performance variations, as demonstrated by the wide accuracy spread when using random initializers for dependency parsing. The authors aim to find a more principled approach by developing models with concave log-likelihood functions, which are mathematically guaranteed to have a single global maximum, thus providing stable and reliable starting points for more complex models.

Methods

The core of the paper's contribution lies in developing and applying concave log-likelihood functions to unsupervised dependency grammar induction.

  • Concavity Analysis: The authors first analyze why IBM Model 1 for word alignment is concave (its log-likelihood is a sum of concave functions) while IBM Model 2 and other common NLP models (like those for POS tagging) are not. They identify that the presence of products of parameters within a logarithm, or products of sums, typically breaks concavity.
  • Concave Dependency Grammar Models (Ccv1 and Ccv2): They propose two new models for dependency grammar induction. These models are designed to maintain concavity by carefully structuring their objective functions.
  • Ccv1: This model is a simplified generative model where a sentence is generated from a copy of itself, with constraints to ensure concavity. It allows conditioning on observed information like edge direction and word distance.
  • Ccv2: This model builds upon Ccv1 by incorporating linguistic knowledge: it adds a constraint that roots of sentences are likely to be verbs. This is achieved by restricting the possible parent-child assignments during learning.
  • Initialization Strategy: The primary application of these concave models is as initializers for the well-established Dependency Model with Valence (DMV) by Klein and Manning (2004). They demonstrate how to transfer parameters from their concave models to the DMV.

Datasets

The experiments utilize data from the CoNLL 2006/07 shared tasks on multilingual dependency parsing. For training, they use short sentences (typically < 10 or < 20 words) from specific treebanks, and for testing, they use the standard test sets. They also mention using gold POS tags for training and testing, which is a common practice in this area.

Key Insights and Ideas

  • Concavity as a Path to Stability: The paper strongly advocates for concave objective functions in unsupervised learning as a way to overcome the instability and sensitivity to initialization that plagues many existing models.
  • Linguistic Knowledge Can Enhance Concave Models: The introduction of a verb-root constraint in Ccv2 demonstrates that linguistic heuristics can be incorporated into concave models without sacrificing their desirable mathematical properties, leading to improved performance.
  • Concave Models as Superior Initializers: The most significant finding is that these simple, concave models provide demonstrably better initializations for the DMV than standard methods like uniform distributions or the K&M initializer. This suggests a generalizable approach for improving other complex unsupervised models.

Key Results

  • Improved DMV Performance: When used to initialize the DMV, Ccv2 achieved substantial improvements in accuracy across 18 languages compared to standard initializers like K&M and uniform distributions. For example, on English test sentences of length < 20 words, the DMV initialized with Ccv2 achieved an accuracy of 54.3%, rivaling more sophisticated models.
  • Competitive Performance of Concave Models: Even when used directly as parsers (without initializing DMV), Ccv1 and Ccv2 showed competitive performance, with Ccv2 often outperforming K&M.
  • Higher Log-Likelihoods: The Ccv2 model, with its verb-root constraint, achieved substantially higher average log-likelihoods during EM training, suggesting it helps the optimization process find better local optima.

Limitations and Future Work

  • Limited Scope of Concavity: The paper acknowledges that while their models are concave, they are simplified versions of more complex grammar induction systems. The concavity is maintained by restricting certain types of conditioning or constraints that would break it.
  • Future Work: The authors suggest that their work provides evidence for the general methodology of "staged training" (using simpler models to initialize more complex ones). They also propose that their concave models offer a simple and powerful initialization method for dependency grammar induction, hinting at potential applications to other unsupervised NLP tasks. They also note that while Ccv1 leads to higher accuracy, K&M reaches slightly higher likelihood, suggesting that the success of concave initializers is only partially due to reaching high training likelihood.

Summary updated

Abstract

We investigate models for unsupervised learning with concave log-likelihood functions. We begin with the most well-known example, IBM Model 1 for word alignment (Brown et al., 1993) and analyze its properties, discussing why other models for unsupervised learning are so seldom concave. We then present concave models for dependency grammar induction and validate them experimentally. We find our concave models to be effective initializers for the dependency model of Klein and Manning (2004) and show that we can encode linguistic knowledge in them for improved performance.
BibTeX
@inproceedings{gimpel2012concavity,
  author = {Kevin Gimpel and Noah A. Smith},
  title = {{Concavity and Initialization for Unsupervised Dependency Parsing}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2012},
  url = {https://openreview.net/forum?id=Sy-sp7-OZr},
}
Figure