📄 Learning to Extract Relations from the Web using Minimal Supervision

Summary

The paper addresses relation extraction (RE) when almost no labeled data exist. The only supervision is a few entity pairs known to hold or not hold a target binary relation, such as Google/YouTube for corporate acquisition. For each pair, a search engine collects web sentences that mention both entities. A positive pair's bag of sentences should contain at least one sentence asserting the relation, while all sentences in a negative bag are assumed negative. This makes the task a multiple instance learning (MIL) problem with an unusual shape: very few bags, each very large.

The authors simplify MIL by labeling every sentence in a positive bag as positive. They then train an SVM that penalizes errors on positive-bag sentences less, using a parse-free subsequence kernel anchored on the two entities. They also add token weights to reduce bias toward words tied to the individual entities rather than to the relation.

On Corporate Acquisitions and Person-Birthplace data, the weighted kernel (SSK–T1) clearly beats a bag-of-words baseline. It even matches a model trained on manually labeled sentences. This shows that web-scale RE can be bootstrapped from a handful of seed pairs.

Key points

• Supervision is tiny. For corporate acquisitions there are 4 positive pairs (e.g., Google–YouTube, Adobe Systems–Macromedia) and 2 negative pairs (Yahoo–Microsoft, Pfizer–Teva).

• MIL is reduced to standard supervised learning. Training uses an SVM with cost C normalized by the total number of instances and an asymmetric weight c_p. Setting c_p = 0.1 worked better than the balanced 0.5, and lower values gave no further gain.

• The kernel is a subsequence kernel from Bunescu and Mooney (2006):

  • patterns are anchored at the two entity placeholders;
  • gaps are penalized via λ;
  • patterns made only of stop words and punctuation can optionally be ignored;
  • no syntactic parsing is used, since web text parses poorly.

• Area under the precision-recall curve (Corporate Acquisitions / Person-Birthplace):

  System	Corporate Acquisitions	Person-Birthplace
  SSK–T1	81.1%	78.2%
  SSK–MIL	76.9%	72.5%
  BW–MIL	45.9%	69.2%
  SSK–SIL (manual sentence labels)	80.4%	73.4%

• The approach is cheap compared with KnowItAll. It needs only one search query per seed pair plus one per individual argument.

Interesting ideas

• I1. Seed pairs plus a search engine as a distant labeler. Instead of annotating sentences, you list a few known facts and harvest the sentences that mention them. This could quickly build noisy RE training data for low-resource languages such as Ukrainian, where annotated corpora are scarce.
• I2. Collapsing MIL into ordinary classification with asymmetric costs. Every instance in a positive bag is treated as positive, but false negatives cost less than false positives. This simple trick handles label noise without specialized MIL algorithms and fits any weakly labeled setup.
• I3. Questioning bag-level kernels when bags are few. The authors argue that bag-level multi-instance kernels limit the number of support vectors to the number of bags, which gives too little model capacity. Checking how many effective parameters a design allows is a useful sanity test for any learning setup with very few examples.
• I4. Down-weighting entity-correlated vocabulary. Words like "search" or "video" co-occur with Google or YouTube regardless of the relation. Penalizing such features keeps the model focused on relation cues, which applies to any task where training examples cluster around a few specific entities.
• I5. Implicit negatives from other entity pairs. Other entity pairs in a positive sentence are very likely not in the relation, so they can serve as free negative examples. The paper proposes this as future work, but it could also let users supply only positive seeds.