Distant Supervision for Relation Extraction with Matrix Completion

Miao Fan, Deli Zhao, Qiang Zhou, Zhiyuan Liu, Thomas Fang Zheng, Edward Y. Chang

TL;DR

This paper introduces a novel matrix completion approach for distantly supervised relation extraction, addressing the inherent noise and sparsity in automatically labeled data. By framing relation extraction as a low-rank matrix completion problem, the authors achieve state-of-the-art performance, significantly outperforming existing methods.

What Problem Does This Paper Address?

Relation Extraction (RE) aims to identify and classify relationships between entities in text. Traditional supervised methods require extensive hand-labeled data, which is costly and time-consuming to produce. Distant supervision offers a solution by automatically labeling data using existing knowledge bases (like Freebase). However, this approach introduces significant challenges:

  • Noisy Labels: The assumption that any sentence mentioning two entities expresses their relation is often false, leading to incorrect labels.
  • Sparse Features: Using a wide range of NLP features results in many features appearing only once, making them less informative.
  • Incomplete Labels: Knowledge bases themselves are incomplete, meaning not all existing relations are captured.

These issues collectively make distantly supervised RE an "incomplete multi-label classification problem with sparse and noisy features," hindering the performance of standard machine learning models.

Methods

The core innovation of this paper is framing relation extraction as a matrix completion problem with a low-rank constraint. The authors construct a large matrix where rows represent entity pairs (items) and columns represent textual features and relation labels. The goal is to "complete" the missing (testing) labels by recovering an underlying low-rank structure of this matrix.

Key techniques include:

  • Matrix Completion: The problem is formulated as finding a low-rank matrix that best approximates the observed (noisy and incomplete) data.
  • Nuclear Norm Minimization: To handle the non-convexity of rank minimization, they use the nuclear norm as a convex surrogate, a standard technique in matrix completion.
  • Two Optimization Models (DRMC-b and DRMC-1):
    • DRMC-b: Explicitly models a bias term, incorporating a logistic cost function to mitigate noise.
  • DRMC-1: Implicitly models the bias term and also enforces the first column of the matrix to be 1, representing a bias.
  • Fixed Point Continuation (FPC) Algorithm: A modified FPC algorithm is used to efficiently solve the optimization problems, ensuring convergence to a global optimum. This algorithm iteratively updates the matrix and then "shrinks" its singular values to enforce low-rankness.

Datasets

The experiments were conducted on two widely used public datasets:

  • NYT'10: Automatically generated by aligning Freebase to the New York Times corpus. It features higher-dimensional features but fewer training/testing items.
  • NYT'13: Also derived from Freebase and NYT, but uses only lexicalized dependency paths as features, resulting in lower dimensionality.

The paper does not introduce new benchmarks but uses these existing ones to demonstrate the effectiveness of their approach compared to prior work.

Key Insights and Ideas

  • Low-Rank Assumption is Key: The central idea is that despite noise and sparsity, the underlying semantic correlations between entity pairs, features, and relations exhibit a low-rank structure. Recovering this structure is crucial for accurate relation extraction.
  • Matrix Completion as a Unified Framework: This work elegantly unifies feature representation and label prediction within a single matrix completion framework, allowing for simultaneous learning and completion.
  • Robustness to Noise: The use of logistic cost functions and the inherent nature of matrix completion help to filter out noise from both features and labels, leading to more robust performance.
  • Feature Sparsity is Manageable: The proposed methods show consistent outperformance even when feature sparsity is increased (by lowering the feature filtering threshold), indicating their resilience to sparse feature sets.

Key Results

  • State-of-the-Art Performance: The proposed DRMC-b and DRMC-1 models significantly outperform several baseline and state-of-the-art methods (Mintz et al., 2009; Hoffmann et al., 2011; Surdeanu et al., 2012; Riedel et al., 2013) on both NYT'10 and NYT'13 datasets, as evidenced by precision-recall curves.
  • Precision Improvements: On the NYT'10 dataset, DRMC-b and DRMC-1 achieved substantial precision increments (24.0% and 26.6% on average) for Top-500 predicted relation instances compared to the NFE-13 method.
  • Optimal Rank Stability: The optimal rank for the matrix completion was found to be relatively stable across different feature sparsity levels, suggesting that the core semantic information remains consistent.

Limitations and Future Work

  • Scalability for New Data: The current models require reconstructing the entire data matrix (including training and testing items) for each new prediction, making them inefficient for processing new incoming testing items incrementally.
  • Dataset Size: The datasets used, while standard, are relatively small.
  • Future Directions: The authors plan to explore models capable of incremental learning to handle large-scale datasets more efficiently. They also aim to further investigate how to process new coming testing items without recomputing the entire matrix.

Summary updated

BibTeX
@inproceedings{fan2014distant,
  author = {Miao Fan and Deli Zhao and Qiang Zhou and Zhiyuan Liu and Thomas Fang Zheng and Edward Y. Chang},
  title = {{Distant Supervision for Relation Extraction with Matrix Completion}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2014},
  doi = {10.3115/v1/p14-1079},
}
Figure