Noisy Or-based model for Relation Extraction using Distant Supervision

Ajay Nagesh, Gholamreza Haffari, Ganesh RamakrishnanEMNLP 2014 · OpenReview

Abstract

Distant supervision, a paradigm of relation extraction where training data is created by aligning facts in a database with a large unannotated corpus, is an attractive approach for training relation extractors. Various models are proposed in recent literature to align the facts in the database to their mentions in the corpus. In this paper, we discuss and critically analyse a popular alignment strategy called the “at least one” heuristic. We provide a simple, yet effective relaxation to this strategy. We formulate the inference procedures in training as integer linear programming (ILP) problems and implement the relaxation to the “at least one” heuristic via a soft constraint in this formulation. Empirically, we demonstrate that this simple strategy leads to a better performance under certain settings over the existing approaches.

Introduction: The Challenge of Distant Supervision

Relation Extraction (RE) is the task of identifying structured relationships, such as bornIn(Barack Obama, Hawaii), from unstructured text. Because manual annotation is prohibitively expensive, researchers often turn to Distant Supervision (DS). This technique uses a database of known facts to automatically label a large, unannotated corpus.

The standard assumption in DS is the "at least one" heuristic: if a fact exists in the database, at least one sentence in the corpus containing those entities must express that relation. However, this assumption is frequently violated. For instance, if a corpus consists of 1990s news, the fact presidentOf(Barack Obama, USA) will not be present, even if both entities appear in the text. Forcing the model to find a match where none exists injects "noise" into the training data, which ultimately degrades the performance of the resulting extractor.

Methodology: Relaxing the Heuristic with ILP

The authors build upon the multi-instance multi-label framework established by Hoffmann et al. (2011), introducing two primary innovations:

  1. Exact Inference via ILP: They replace the approximate inference methods used in previous work with Integer Linear Programming (ILP). This allows for exact inference during the training phase, providing a more robust foundation for model updates.
  2. The Noisy-OR Relaxation: The core innovation is turning the rigid "at least one" constraint into a soft constraint. In their ILP formulation, they introduce a binary slack variable ($\epsilon_i$) into the objective function. While a Deterministic OR requires at least one mention to support a database relation, the Noisy-OR allows the model to "pay a penalty" via the slack variable if it cannot find supporting evidence. This prevents the model from being forced to make incorrect associations when evidence is missing from the text.

Key Insights and Results

The paper’s primary insight is that absence of evidence is not evidence of absence. By formally recognizing that a database fact might simply be missing from a specific text collection, the model can "ignore" facts without clear textual support, reducing training noise.

Performance Metrics

The authors evaluated their model on two standard benchmarks: the KBP (Knowledge Base Population) dataset and the Riedel Dataset (NYT articles aligned with Freebase).

Precision-Recall curves for the KBP dataset show the Noisy-OR model (blue triangles) maintaining superior precision over the baseline and MIMLRE at various recall levels.

As shown in the Precision-Recall curves (Figure 4), the Noisy-OR model demonstrates a substantial jump in precision on the KBP dataset, often reaching or exceeding 0.4 in regions where other models struggle. It specifically outperforms the more complex MIMLRE (Surdeanu et al., 2012) in precision at low recall levels (recall < 0.15).

Table 1 summarizes the highest F1 points for the KBP dataset, highlighting the trade-offs between precision and recall for different models.

Table 1 highlights that while the Noisy-OR approach significantly boosts precision, it often comes with a recall penalty. Because the model is allowed to skip facts it is uncertain about, it identifies fewer total relations, leading to a lower overall F1 score compared to MIMLRE on the KBP dataset.

Computational Efficiency

While the ILP approach is computationally more intensive than the original Hoffmann baseline (8.5 hours vs. 1 hour on KBP), it is significantly faster than the EM-based MIMLRE algorithm, which required 23 hours to converge. This makes ILP a viable middle ground for achieving exact inference without the extreme overhead of more complex graphical models.

Conclusion and Future Work

The Noisy-OR relaxation proves that precision in Distant Supervision can be significantly improved by accounting for missing evidence in the corpus. While there is a trade-off in recall, the high-precision output is often more valuable for downstream knowledge base construction. Future work may involve extending the ILP framework to include more sophisticated logical constraints, such as selectional preferences, to further refine the extraction process.

Summary updated

Abstract

Distant supervision, a paradigm of relation extraction where training data is created by aligning facts in a database with a large unannotated corpus, is an attractive approach for training relation extractors. Various models are proposed in recent literature to align the facts in the database to their mentions in the corpus. In this paper, we discuss and critically analyse a popular alignment strategy called the “at least one” heuristic. We provide a simple, yet effective relaxation to this strategy. We formulate the inference procedures in training as integer linear programming (ILP) problems and implement the relaxation to the “at least one ” heuristic via a soft constraint in this formulation. Empirically, we demonstrate that this simple strategy leads to a better performance under certain settings over the existing approaches.
BibTeX
@inproceedings{nagesh2014noisy,
  author = {Ajay Nagesh and Gholamreza Haffari and Ganesh Ramakrishnan},
  title = {{Noisy Or-based model for Relation Extraction using Distant Supervision}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2014},
  url = {https://openreview.net/forum?id=HyZjC-GO-S},
}
Figure