Data-Driven Graph Construction for Semi-Supervised Graph-Based Learning in NLP

Andrei Alexandrescu, Katrin KirchhoffNAACL 2007

TL;DR

This paper tackles the challenge of building effective graphs for semi-supervised learning in NLP, where labeled data is scarce. They propose a novel "data-driven" approach that uses a supervised classifier to transform raw features into a more informative representation, leading to significantly improved performance over traditional methods on lexicon acquisition and word sense disambiguation tasks.

What Problem Does This Paper Address?

Natural Language Processing (NLP) often suffers from a lack of labeled data, making it difficult to train accurate models. Semi-supervised learning offers a solution by leveraging large amounts of unlabeled data alongside a small labeled set. A popular class of semi-supervised algorithms are graph-based methods, which represent data points as nodes in a graph, with edge weights indicating similarity. However, the crucial step of constructing this graph is often ad-hoc and suboptimal, especially for NLP's complex, heterogeneous feature spaces. This paper addresses the gap in how to best construct these graphs, aiming to optimize the graph's structure for better label propagation.

Methods

The core contribution is a "two-pass data-driven technique" for graph construction.

  1. First Pass (Supervised Feature Transformation): Instead of directly using raw, often discrete or mixed-type NLP features (like word suffixes, capitalization, etc.), they train a supervised classifier (specifically, a multi-layer perceptron or MLP for lexicon acquisition, and an SVM for WSD) on the labeled data. This classifier transforms the original features into a continuous representation, specifically soft label predictions (e.g., probability distributions over possible labels). This transformation aims to create a more uniform and informative feature space.
  2. Second Pass (Graph Construction & Label Propagation): This new, continuous representation is then used to construct the graph. A distance measure (like Jeffries-Matusita or cosine distance) is applied to these soft label predictions to define edge weights. Finally, a standard label propagation algorithm is run on this data-driven graph to infer labels for the unlabeled data.

Key aspects of their method include:

  • Uniform Feature Space: The output of the first-pass classifier provides a consistent format (probability distributions), mitigating issues with mixed feature types and ranges.
  • Optimizing for Graph Properties: The first-pass classifier is not just concatenated; it's optimized with respect to the requirements of the second-pass label propagation, aiming for better class separation and smoother distributions.
  • Handling Data Scarcity: For the MLP, they introduce an approximation layer to handle unseen input features in the unlabeled data by finding the closest known feature vector.

Datasets

  • Wall Street Journal (WSJ) Corpus: Used for the lexicon acquisition task. Sections 0-18 were used, with a total of 44,492 words. They artificially limited the labeled set size (5000, 10000, 15000 words) to simulate data scarcity.
  • SENSEVAL-3 Corpus: Used for the word sense disambiguation (WSD) task. This corpus contains sentences for disambiguating senses of 57 words, with 7860 training and 3944 test samples.

Key Insights and Ideas

  • Raw NLP features are often suboptimal for graph construction: Traditional distance measures struggle with the discrete, heterogeneous, and correlated nature of NLP features.
  • A supervised pre-processing step can dramatically improve graph quality: Transforming features into soft label predictions creates a more amenable space for similarity calculations, leading to better graph structures.
  • Optimizing the entire pipeline matters: The first-pass classifier should be trained not just for its own accuracy, but to produce outputs that benefit the subsequent graph-based learner. This can involve regularization to encourage smoother predictions.
  • Data-driven graph construction is crucial for low-resource scenarios: The improvements were most pronounced when labeled data was scarce, highlighting the method's utility for challenging NLP problems.

Key Results

  • Lexicon Acquisition: The proposed "NN+LP" (MLP + Label Propagation) method significantly outperformed both a standard "LP" (Label Propagation on raw features) and the "NN" (supervised MLP alone) across various labeled data sizes. For instance, with 5000 labeled words, NN+LP achieved 62.45% accuracy compared to LP's 60.13% and NN's 57.67%. The improvements were more pronounced with smaller training sets.
  • Word Sense Disambiguation: The "SVM+LP" (SVM output + Label Propagation) method consistently outperformed both the "SVM" (supervised SVM alone) and "LP" (Label Propagation on raw features). The paper reports significant gains for SVM+LP over LP in the 75% and 100% labeled data cases.
  • Graph Smoothness: In both tasks, graphs constructed using their data-driven method exhibited significantly better smoothness (lower S(G) values) compared to graphs built with standard approaches, indicating better affinity between nodes of the same label.

Limitations and Future Work

  • Potential for Overfitting/Misleading Predictions: The authors acknowledge that if the first-pass classifier makes confident but incorrect predictions, especially for outliers, it could negatively impact the graph construction. This is why optimizing the first-pass classifier for the second-pass learner is important.
  • Chunking for LP: Due to the large size of the transition matrix P, they used a chunking approach for label propagation. While this yielded similar results to whole-set LP, they note that performance can degrade with larger chunk sizes, suggesting potential issues with "artifact" clusters.
  • Future Work: The paper implicitly suggests extending this approach to other NLP tasks and potentially to more complex graph structures or different semi-supervised learning algorithms. The focus on resource-poor languages for lexicon acquisition also points towards future applications.

Summary updated

BibTeX
@inproceedings{alexandrescu2007data,
  author = {Andrei Alexandrescu and Katrin Kirchhoff},
  title = {{Data-Driven Graph Construction for Semi-Supervised Graph-Based Learning in NLP}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2007},
}
Figure