A convex relaxation for weakly supervised relation extraction

Edouard GraveEMNLP 2014 · OpenReview

Abstract

A promising approach to relation extraction, called weak or distant supervision, exploits an existing database of facts as training data, by aligning it to an unlabeled collection of text documents. Using this approach, the task of relation extraction can easily be scaled to hundreds of different relationships. However, distant supervision leads to a challenging multiple instance, multiple label learning problem. Most of the proposed solutions to this problem are based on non-convex formulations, and are thus prone to local minima. In this article, we propose a new approach to the problem of weakly supervised relation extraction, based on discriminative clustering and leading to a convex formulation. We demonstrate that our approach outperforms state-of-the-art methods on the challenging dataset introduced by Riedel et al. (2012).

Introduction

Relation extraction (RE) is the task of identifying structured relationships between entities in plain text, such as recognizing that a sentence expresses a DiedIn relation between a person and a city. To scale RE to hundreds of relations, researchers utilize distant supervision: aligning an existing database of facts (e.g., Freebase) with unlabeled text. If a database contains the fact BornIn(Lichtenstein, NYC), any sentence containing both entities is treated as a potential training example.

However, this creates a "Multiple Instance Learning" (MIL) challenge. A sentence might mention both entities without expressing the target relation (e.g., "Lichtenstein's work is displayed in New York"). This results in noisy training data. Previous state-of-the-art methods relied on non-convex graphical models to handle this noise, but these are sensitive to initialization and often converge to sub-optimal local minima.

The distant supervision framework: sentence mentions (left) are mapped to entity pairs (middle), which are then associated with potential relations (right) based on knowledge base facts.

Methods

This paper proposes a shift to Discriminative Clustering. The core objective is to find a labeling of text mentions that allows a classifier to achieve the lowest possible classification error while respecting constraints provided by the knowledge base.

Convex Relaxation

The task is formulated as an integer quadratic program. By relaxing binary labels to continuous values in the interval $[0, 1]$ and using a squared loss function, the problem becomes a convex quadratic program. This ensures that optimization always finds the global optimum for the relaxed problem, removing the instability associated with initializing graphical models.

Knowledge Base Constraints

Weak supervision is incorporated through linear constraints. For instance, if a fact exists in the database, at least one sentence mentioning those entities must express that relation. If a fact does not exist, no sentence should express it.

Dual Optimization

To handle large-scale datasets, the author solves the dual problem. This is computationally efficient because natural language feature matrices are typically very sparse. The resulting algorithm has a complexity of $O(NFK)$ (where $N$ is the number of mentions, $F$ is the average number of features, and $K$ is the number of relations), making it highly scalable.

Results

The approach was evaluated on the Riedel et al. (2010) dataset, consisting of New York Times articles aligned with Freebase, and a manually labeled subset for sentential extraction.

Precision-Recall curves comparing the proposed convex approach ("This work") against previous methods by Mintz et al., Hoffmann et al., and Surdeanu et al.

As shown in the Precision-Recall curves, the convex method consistently outperformed previous models (Mintz, Hoffmann, and Surdeanu). At equivalent recall levels, it achieved up to a 5-point gain in precision. Furthermore, the model reached a maximum recall of 0.30, whereas previous methods plateaued at 0.25. On manually labeled data, the method achieved an F1 score of 0.66, significantly higher than the 0.61 achieved by the previous state-of-the-art. Despite the more complex optimization, the runtime was comparable to existing graphical models, taking roughly 3 hours for the full dataset.

Conclusion

By moving to a convex formulation, this research ensures that relation extraction models can avoid the pitfalls of local minima. The discriminative clustering approach treats distant supervision as a guided clustering problem rather than just a noisy labeling task. Future work will address the "Closed World Assumption" of current knowledge bases and explore the use of complex kernels to further improve recall.

Summary updated

Abstract

A promising approach to relation extraction, called weak or distant supervision, exploits an existing database of facts as training data, by aligning it to an unlabeled collection of text documents. Using this approach, the task of relation extraction can easily be scaled to hundreds of different relationships. However, distant supervision leads to a challenging multiple instance, multiple label learning problem. Most of the proposed solutions to this problem are based on non-convex formulations, and are thus prone to local minima. In this article, we propose a new approach to the problem of weakly supervised relation extraction, based on discriminative clustering and leading to a convex formulation. We demonstrate that our approach outperforms state-of-the-art methods on the challenging dataset introduced by Riedel et al. (2012).
BibTeX
@inproceedings{grave2014convex,
  author = {Edouard Grave},
  title = {{A convex relaxation for weakly supervised relation extraction}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2014},
  url = {https://openreview.net/forum?id=Hkbz2bfu-r},
}
Figure