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:
- 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.
- 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).
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 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