Semi-supervised Relation Extraction with Label Propagation

Jinxiu Chen, Donghong Ji, Chew Lim Tan, Zhengyu NiuNAACL 2006

TL;DR

This paper introduces a novel semi-supervised learning approach for relation extraction, leveraging label propagation on a graph of text contexts. By effectively utilizing both labeled and unlabeled data, their method significantly outperforms traditional supervised and bootstrapping techniques, especially when labeled data is scarce, thus reducing the burden of manual annotation.

What Problem Does This Paper Address?

Relation extraction, the task of identifying semantic relationships between entities in text (e.g., "Person X works for Company Y"), typically relies on supervised machine learning models. These models require a substantial amount of manually labeled data, which is expensive and time-consuming to create. While unsupervised methods exist, they lack clear evaluation metrics. Semi-supervised learning offers a middle ground, aiming to achieve good performance with minimal manual annotation. Existing semi-supervised methods often use bootstrapping, which assumes local consistency (nearby examples have similar labels) but can miss broader patterns in the data. This paper addresses the challenge of effectively learning relation extraction models with very limited labeled data by proposing a more globally consistent approach.

Methods

The core of this paper is a label propagation (LP) algorithm adapted for relation extraction. The approach constructs a graph where each node represents an occurrence of an entity pair in text. Edges between nodes are weighted based on the similarity of their contexts, using either Cosine similarity or Jensen-Shannon divergence. The LP algorithm then iteratively propagates label information from labeled nodes to unlabeled nodes through these weighted edges. This process continues until a stable state is reached, at which point the labels of the unlabeled nodes are inferred. This method aims to achieve a "global consistency assumption," meaning similar examples (both labeled and unlabeled) should have similar labels, capturing more of the data's underlying structure than local consistency methods.

Datasets

The experiments were conducted on the ACE corpus, a widely used dataset for relation extraction tasks, comprising 519 files from broadcast, newswire, and newspaper sources. The paper provides a breakdown of relation subtypes within this corpus.

Key Insights and Ideas

  • Global Consistency is Key: The paper argues that relying solely on local consistency (as in bootstrapping) can be limiting. Label propagation, by considering the similarity between all examples (labeled and unlabeled), can better exploit the manifold structure of the data, especially when labeled data is scarce.
  • Label Propagation for Scarce Data: The LP algorithm demonstrates a significant advantage when the percentage of labeled data is low (e.g., 1% to 25%). This highlights its potential to drastically reduce annotation costs without sacrificing performance.
  • Similarity Measures Matter: The paper investigates two similarity measures (Cosine and JS divergence) and shows that while both LP variants outperform SVM, the JS divergence-based LP (LPJS) generally achieves better results, suggesting that the choice of similarity metric can impact performance.

Key Results

  • Superior Performance with Limited Labels: When only 1% of the data was labeled, the LP algorithm achieved an F-score of 57.1% (LPCosine) and 58.5% (LPJS) for relation detection, compared to SVM's 34.4%. This gap narrowed as more labeled data became available, but LP consistently performed competitively or better.
  • Improved Recall: The LP algorithms consistently achieved higher recall than SVM across various percentages of labeled data, indicating a better ability to identify all relevant relation instances.
  • Outperforming Bootstrapping: Compared to a bootstrapped SVM method from prior work (Zhang, 2004), the proposed LP algorithm achieved a 6.8% performance improvement on average across individual relation types.

Limitations and Future Work

  • Feature Engineering: The paper acknowledges that the performance is dependent on the extracted features. Future work could investigate more sophisticated feature selection methods to further enhance the LP algorithm's effectiveness.
  • Scalability: While not explicitly detailed as a limitation, the graph-based nature of LP can sometimes lead to scalability challenges with extremely large datasets, though this was not a primary concern with the ACE corpus.
  • Exploring Other Similarity Measures: The paper focused on Cosine and JS divergence. Further research could explore other similarity metrics or graph construction techniques.

Summary updated

BibTeX
@inproceedings{chen2006semi,
  author = {Jinxiu Chen and Donghong Ji and Chew Lim Tan and Zhengyu Niu},
  title = {{Semi-supervised Relation Extraction with Label Propagation}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2006},
}
Figure