TL;DR
This paper tackles a critical flaw in "distant supervision" for relation extraction: incomplete knowledge bases lead to a high rate of "false negative" labels. The authors propose a novel semi-supervised algorithm that learns from positive and unlabeled data, effectively handling this noise and outperforming existing methods.
What Problem Does This Paper Address?
Relation Extraction (RE) aims to identify and classify semantic relationships between entities in text (e.g., "Barack Obama was born in Honolulu"). Traditionally, this requires manually labeled data, which is expensive and time-consuming. "Distant supervision" offers a popular alternative: it automatically labels a large text corpus by aligning it with a knowledge base (KB). If a KB states that entity A has relation R with entity B, any sentence containing both A and B is assumed to express relation R.
However, this method suffers from a significant problem: KBs are inherently incomplete. For instance, Freebase, a large KB, is missing "place of birth" information for 93.8% of people. Distant supervision incorrectly labels sentences as negative for a relation if that relation isn't explicitly in the KB, even if the sentence does express that relation. These "false negatives" can overwhelm the training data, making it difficult for models to learn effectively. Existing approaches often try to mitigate this by heavily downsampling the negative class, which can discard valuable information.
Methods
The paper proposes a new "semi-supervised" algorithm that addresses the false negative problem by treating unlabeled data differently. Instead of assuming all unlabeled bags of mentions are negative, their model learns from both positive and unlabeled bags.
Their core contribution is a 4-layer hierarchical model that extends a state-of-the-art Multi-Instance Multi-Label (MIML) approach. The key innovation is the introduction of a set of latent variables that model the true bag-level labels, bridging the gap between the observed (potentially noisy) bag labels and the underlying MIML layers.
The model works as follows:
- Mention-level extraction: Predicts the relation type for individual mentions within a sentence.
- Aggregation: Combines mention-level predictions to infer a bag-level label.
- Latent variable modeling: Introduces hidden variables to represent the true bag-level relation, accounting for the possibility that an unlabeled bag might actually express a positive relation.
- Semi-supervised learning: The model is trained using an Expectation-Maximization (EM) algorithm, allowing it to learn from both explicitly positive and unlabeled data.
Datasets
The authors use the KBP (Knowledge Base Population) dataset, prepared and released by Surdeanu et al. (2012). This dataset is described as large, realistic, and importantly, it has associated human-labeled ground truth, which is crucial for evaluating KB-independent methods. They also analyze the incompleteness of Freebase and the false negative rate on datasets generated by Riedel et al. (2010) and Surdeanu et al. (2012).
Key Insights and Ideas
- The "false negative" problem is severe: The paper quantifies the extent of false negatives, showing they can outnumber positive examples by 3 to 10 times, posing a significant challenge for training.
- Incomplete KBs are the root cause: The incompleteness of knowledge bases is not a minor issue but a fundamental flaw in the distant supervision paradigm.
- Unlabeled data is not necessarily negative: The core idea is to leverage unlabeled data not just as a source of negatives, but as a source of potentially positive (but unconfirmed) relations.
- Latent variables are key: Introducing latent variables to represent the true bag-level labels is the mechanism that allows the model to learn from the uncertainty introduced by false negatives.
Key Results
The proposed algorithm, termed MIML-Semi, consistently outperforms existing state-of-the-art algorithms (MIML, MultiR, and Mintz++) on the KBP dataset. Specifically, Figure 2 shows that MIML-Semi achieves better precision-recall curves across almost all recall levels. The authors attribute this improvement to their ability to treat unlabeled data differently and leverage the missing positive bags.
Limitations and Future Work
- Computational Cost: While not explicitly detailed as a limitation, the EM algorithm and hierarchical structure likely increase computational complexity compared to simpler models.
- Generalizability of the Idea: The authors suggest that the core idea of treating unlabeled data differently could be incorporated into any existing algorithm that currently treats unlabeled data solely as negative examples. This points towards future work in applying their approach to a broader range of RE models.
- Further Analysis: The paper provides an analysis of KB incompleteness and false negative rates, which could be extended to other KBs and domains.
Summary updated