Back

Distant supervision for relation extraction without labeled data

Mike MintzSteven BillsRion SnowDan Jurafsky

article2009ACL3,227 citations

Introduces the distant supervision paradigm for relation extraction, showing how structured knowledge bases like Freebase can automatically generate training data from unlabeled text to extract millions of relation instances without manual annotation.

Listen

The paper addresses the challenge of extracting relational facts from text, such as employment or geographic containment links, at scale. Traditional supervised methods require costly hand-labeled data from narrow domains like newswire and produce classifiers that do not transfer well. Unsupervised and bootstrapping approaches can process large text collections but often yield relations that are difficult to map to a target knowledge base or suffer from semantic drift.

The work set out to test whether distant supervision from an existing database could generate large amounts of training data automatically, allowing a single classifier to learn many relations across broad domains while still outputting canonical relation names.

The authors aligned 1.8 million Freebase relation instances with sentences from 1.2 million Wikipedia articles. For every entity pair known to participate in a Freebase relation, they extracted lexical and syntactic features from all co-occurring sentences and trained a multiclass logistic regression classifier. They evaluated the resulting system both by holding out half the Freebase data and by human judgment of the top-ranked extractions.

The classifier produced 10,000 new relation instances across 102 relations at 67.6 percent precision. Combining lexical and syntactic features improved precision over either feature set alone, particularly for relations whose surface expressions are ambiguous or span many intervening words. Syntactic paths proved especially helpful for relations such as film-director and film-writer. At the 100-instance recall level, the combined feature set reached an average precision of 69 percent across the ten most frequent relations; performance remained stable near 67 percent at the 1,000-instance level.

These results show that a large semantic database can replace hand-labeled text for training relation extractors, removing the main cost and domain-bias barriers of prior supervised systems. The approach therefore makes it practical to populate or extend knowledge bases from any large unlabeled corpus while retaining interpretable output relations.

Further gains are likely from lighter syntactic approximations or coreference resolution to capture additional mentions of the same entity pair. The main limitations are dependence on Freebase coverage for both positive and negative examples and evaluation confined to Wikipedia text that aligns closely with Freebase origins; results on other genres remain untested. The reported precision figures rest on both automatic and human evaluation and appear reliable within these bounds.

Stanford Universitybiomedical textrelation extractionsupervised machine learningDistant SupervisionRelation ExtractionFreebase
Mintz et al (2009).pdf
Cover for Distant supervision for relation extraction without labeled data

Abstract

Modern models of relation extraction for tasks like ACE are based on supervised learning of relations from small hand-labeled corpora. We investigate an alternative paradigm that does not require labeled corpora, avoiding the domain dependence of ACE-style algorithms, and allowing the use of corpora of any size. Our experiments use Freebase, a large semantic database of several thousand relations, to provide distant supervision. For each pair of entities that appears in some Freebase relation, we find all sentences containing those entities in a large unlabeled corpus and extract textual features to train a relation classifier. Our algorithm combines the advantages of supervised IE (combining 400,000 noisy pattern features in a probabilistic classifier) and unsupervised IE (extracting large numbers of relations from large corpora of any domain). Our model is able to extract 10,000 instances of 102 relations at a precision of 67.6%. We also analyze feature performance, showing that syntactic parse features are particularly helpful for relations that are ambiguous or lexically distant in their expression.

Topics

biomedical textrelation extractionsupervised machine learningsvmsyntactics

Keywords

Distant SupervisionRelation ExtractionFreebaseLogistic RegressionSyntactic FeatureLexical FeatureNamed Entity TaggerWikipedia CorpusPrecisionBootstrapping

Table of Contents

  • 1 Introduction
  • 2 Previous work
  • 3 Freebase
  • 4 Architecture
  • 5 Features
  • 5.1 Lexical features
  • 5.2 Syntactic features
  • 5.3 Named entity tag features
  • 5.4 Feature conjunction
  • 6 Implementation
  • 6.1 Text
  • 6.2 Parsing and chunking
  • 6.3 Training and testing
  • 7 Evaluation
  • 7.1 Held-out evaluation
  • 7.2 Human evaluation
  • 8 Discussion
  • Acknowledgments

Knowls

  1. Knowl 1 — Distant Supervision Assumption for Relation Extraction

    assumption

    The distant supervision framework operates on the assumption that if an ordered pair of entities (e1,e2)(e_1, e_2) participates in a relation RR in an external relational database (such as Freebase), then any sentence in a large unlabeled text corpus that mentions both e1e_1 and e2e_2 is likely to express the relation RR.

    While individual sentences expressing co-occurrences of e1e_1 and e2e_2 may be uninformative or misleading (introducing label noise), aggregating pattern features across all sentences mentioning (e1,e2)(e_1, e_2) allows a statistical classifier to assign high weights to reliable, discriminative patterns while downweighting noise.

  2. Knowl 2 — Distantly Supervised Relation Extraction Pipeline

    algorithm

    The distant supervision relation extraction system learns to extract relation instances from unlabeled text using supervision from an entity-relation knowledge base without requiring hand-annotated sentences.

    Input: Knowledge base relation instances D={(e1,e2,R)}\mathcal{D} = \{(e_1, e_2, R)\}, Unlabeled text corpus C\mathcal{C}
    Output: Ranked list of novel relation triples (e1,e2,R)(e_1, e_2, R) with confidence scores
    1. Preprocessing:
       a. Run a 4-class Named Entity Recognizer on all sentences in C\mathcal{C}.
       b. Parse each sentence with the MINIPAR dependency parser.
       c. Chunk consecutive tokens sharing identical NE tags if they form contiguous subtrees in the parse graph.
    2. Training Phase:
       a. For each relation triple (e1,e2,R)∈D(e_1, e_2, R) \in \mathcal{D}:
          - Locate all sentences in Ctrain\mathcal{C}_{\text{train}} containing both e1e_1 and e2e_2.
          - Extract conjunctive lexical and syntactic features from every matching sentence.
          - Aggregate all extracted features into a single sparse feature vector x(e1,e2)\mathbf{x}_{(e_1, e_2)} labeled with class RR.
       b. Sample negative training data:
          - Randomly sample 1% of entity pairs (e1′,e2′)(e'_1, e'_2) occurring in Ctrain\mathcal{C}_{\text{train}} that do not appear in any relation in D\mathcal{D}.
          - Extract and aggregate their features into a single feature vector labeled as "Unrelated".
       c. Train a multiclass logistic regression classifier with parameters W\mathbf{W} optimized via L-BFGS with Gaussian (L2L_2) prior regularization:
          P(R∣x)=exp⁡(wR⊤x)∑R′exp⁡(wR′⊤x)P(R \mid \mathbf{x}) = \frac{\exp(\mathbf{w}_R^\top \mathbf{x})}{\sum_{R'} \exp(\mathbf{w}_{R'}^\top \mathbf{x})}
    3. Inference / Testing Phase:
       a. In test text Ctest\mathcal{C}_{\text{test}}, identify all co-occurring entity pairs (u1,u2)(u_1, u_2).
       b. For each entity pair (u1,u2)(u_1, u_2), extract features from all sentences mentioning both entities and aggregate them into x(u1,u2)\mathbf{x}_{(u_1, u_2)}.
       c. Predict the relation R^=argmax⁡R≠"Unrelated"P(R∣x(u1,u2))\hat{R} = \operatorname{argmax}_{R \neq \text{"Unrelated"}} P(R \mid \mathbf{x}_{(u_1, u_2)}).
       d. Filter out entity pairs already present in the training database D\mathcal{D}.
       e. Rank novel extracted instances (u1,u2,R^)(u_1, u_2, \hat{R}) by their predicted probability P(R^∣x(u1,u2))P(\hat{R} \mid \mathbf{x}_{(u_1, u_2)}).

  3. Knowl 3 — Conjunctive Lexical Features for Relation Extraction

    model/method

    Lexical features represent surface word sequences, part-of-speech (POS) tags, and word windows around entity mentions. Rather than treating individual tokens independently, the model uses conjunctive lexical features where all constituent components must match simultaneously.

    For an entity pair (e1,e2)(e_1, e_2) appearing in a sentence, each conjunctive lexical feature consists of the combination of:

    • The exact sequence of words between e1e_1 and e2e_2.
    • The simplified POS tags of the intervening words (POS tags from a Penn Treebank maximum entropy tagger simplified into seven categories: nouns, verbs, adverbs, adjectives, numbers, foreign words, and everything else).
    • A direction flag indicating whether e1e_1 precedes e2e_2 or vice versa.
    • A left-hand context window of kk words and their POS tags immediately preceding the first entity, for k∈{0,1,2}k \in \{0, 1, 2\}.
    • A right-hand context window of kk words and their POS tags immediately following the second entity, for k∈{0,1,2}k \in \{0, 1, 2\}.
    • The named entity (NE) tags of both entities (from {person, location, organization, miscellaneous, none}).

    Each choice of k∈{0,1,2}k \in \{0, 1, 2\} produces a distinct conjunctive feature.

  4. Knowl 4 — Conjunctive Dependency Parse Features for Relation Extraction

    model/method

    Syntactic features represent structural relations between entities extracted from MINIPAR dependency trees. Prior to feature extraction, adjacent words with identical named entity tags are chunked into a single entity node if they form a contiguous subtree.

    A conjunctive syntactic feature is formed by the conjunction of:

    • The directed dependency path between e1e_1 and e2e_2, defined as the sequence of dependency relation labels, traversal directions (e.g., ⇑s\Uparrow\text{s}, ⇓pred\Downarrow\text{pred}, ⇓mod\Downarrow\text{mod}, ⇓pcomp-n\Downarrow\text{pcomp-n}), and traversed words/chunks (without POS tags).
    • An optional left window node: a dependency node linked directly to e1e_1 that is not part of the core dependency path.
    • An optional right window node: a dependency node linked directly to e2e_2 that is not part of the core dependency path.
    • The named entity tags of both e1e_1 and e2e_2.

    Distinct conjunctive features are generated for each pair of left and right window nodes, as well as features omitting one or both window nodes.

  5. Knowl 5 — Negative Training Instance Construction via Random Entity Pair Sampling

    model/method

    Because distant supervision algorithms lack explicit negative labels in the knowledge base, negative training examples are generated heuristically for the multiclass classifier's 'unrelated' class.

    In the training text corpus, co-occurring entity pairs (e1,e2)(e_1, e_2) that do not appear in any known Freebase relation are identified. A random 1%1\% sample of these unlinked pairs is selected. Features are extracted and aggregated across all sentences containing each sampled pair, and the resulting aggregated feature vector is assigned the label 'unrelated' during multiclass logistic regression training.

    In contrast to the 1%1\% training sample rate, approximately 98.7%98.7\% of all co-occurring entity pairs in the test corpus do not participate in any of the top 102 Freebase target relations.

  6. Knowl 6 — Automatic Held-Out Precision Across Feature Sets

    empirical result

    In an automatic held-out evaluation over the 102 largest Freebase relations (splitting 1.8 million relation instances 50% for training and 50% for held-out testing across 800,000 training and 400,000 test Wikipedia articles):

    • Combining both syntactic and lexical features achieved higher precision at virtually all recall levels (from 10 to 100,000 instances) compared to using lexical features alone or syntactic features alone.
    • At high confidence thresholds (low recall, e.g., recall ≤100\le 100), precision exceeded 80%80\%.
    • At the 100,000 recall cutoff, the extracted instances were heavily concentrated in three dominant relations: 60%60\% as /location/location/contains, 13%13\% as /people/person/place_of_birth, and 10%10\% as /people/person/nationality.

  7. Knowl 7 — Human Evaluation Precision for Top Predicted Relations

    data/table

    Human evaluation was conducted on Amazon Mechanical Turk using majority voting (1 to 3 annotators per sample, sample size 100) on stratified samples from the top 100 and top 1000 extracted instances for the 10 most frequent predicted relations. The table below compares models trained with Syntactic features only (Syn), Lexical features only (Lex), and Combined features (Both):

    100 instances 1000 instances
    Relation name Syn Lex Both Syn Lex Both
    /film/director/film 0.49 0.43 0.44 0.49 0.41 0.46
    /film/writer/film 0.70 0.60 0.65 0.71 0.61 0.69
    /geography/river/basin_countries 0.65 0.64 0.67 0.73 0.71 0.64
    /location/country/administrative_divisions 0.68 0.59 0.70 0.72 0.68 0.72
    /location/location/contains 0.81 0.89 0.84 0.85 0.83 0.84
    /location/us_county/county_seat 0.51 0.51 0.53 0.47 0.57 0.42
    /music/artist/origin 0.64 0.66 0.71 0.61 0.63 0.60
    /people/deceased_person/place_of_death 0.80 0.79 0.81 0.80 0.81 0.78
    /people/person/nationality 0.61 0.70 0.72 0.56 0.61 0.63
    /people/person/place_of_birth 0.78 0.77 0.78 0.88 0.85 0.91
    Average 0.67 0.66 0.69 0.68 0.67 0.67

    At the top-100 instance cutoff, the combined feature model achieved the highest average precision (0.69, compared to 0.67 for Syn and 0.66 for Lex). At the top-1000 cutoff, the Syntactic model achieved 0.68 average precision versus 0.67 for the Lex and Combined models. Across 102 relations, the distant supervision system extracted 10,000 instances at an estimated precision of 67.6%.

  8. Knowl 8 — Utility of Syntactic Dependency Paths in Ambiguous and Long-Span Relations

    empirical result

    Syntactic dependency features demonstrate distinct performance advantages over surface lexical features under two specific structural language conditions:

    1. Semantic Ambiguity: When relation types share similar lexical contexts (e.g., distinguishing /film/director/film from /film/writer/film or /film/producer/film), syntactic features outperform lexical features (e.g., 0.49 vs 0.43 precision at 100 instances for director, and 0.70 vs 0.60 for writer).
    2. Long Lexical Spans: In sentences where entity mentions are separated by long strings of intermediate words (such as appositives, studio names, or other credited roles), surface word-sequence features become too long and specific to recur in test data. Dependency parse structures abstract away extraneous intermediate modifiers, yielding short, recurrent dependency paths between the target entities.

Coverage note — None was omitted; all primary contributions, algorithmic steps, feature definitions, and experimental evaluations have been captured.

References

  1. 1.Eugene Agichtein and Luis Gravano. 2000. Snowball: Extracting relations from large plain-text collections. In Proceedings of the 5th ACM International Conference on Digital Libraries.
  2. 2.Michele Banko, Michael J. Cafarella, Stephen Soderland, Matthew Broadhead, and Oren Etzioni. 2007. Open information extraction from the web. In Manuela M Veloso, editor, IJCAI-07, pages 2670–2676.
  3. 3.Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008. Freebase: a collaboratively created graph database for structuring human knowledge. In SIGMOD ’08, pages 1247–1250, New York, NY. ACM.
  4. 4.Sergei Brin. 1998. Extracting patterns and relations from the World Wide Web. In Proceedings World Wide Web and Databases International Workshop, Number 1590 in LNCS, pages 172–183. Springer.
  5. 5.Razvan Bunescu and Raymond Mooney. 2007. Learning to extract relations from the web using minimal supervision. In ACL-07, pages 576–583, Prague, Czech Republic, June.
  6. 6.Mark Craven and Johan Kumlien. 1999. Constructing biological knowledge bases by extracting information from text sources. In Thomas Lengauer, Reinhard Schneider, Peer Bork, Douglas L. Brutlag, Janice I. Glasgow, Hans W. Mewes, and Ralf Zimmer, editors, ISMB, pages 77–86. AAAI.
  7. 7.George Doddington, Alexis Mitchell, Mark Przybocki, Lance Ramshaw, Stephanie Strassel, and Ralph Weischedel. 2004. The Automatic Content Extraction (ACE) Program–Tasks, Data, and Evaluation. LREC-04, pages 837–840.
  8. 8.Oren Etzioni, Michael Cafarella, Doug Downey, Ana-Maria Popescu, Tal Shaked, Stephen Soderland, Daniel S. Weld, and Alexander Yates. 2005. Unsupervised named-entity extraction from the web: An experimental study. Artificial Intelligence, 165(1):91–134.
  9. 9.Jenny R. Finkel, Trond Grenager, and Christopher Manning. 2005. Incorporating non-local information into information extraction systems by gibbs sampling. In ACL-05, pages 363–370, Ann Arbor, MI.
  10. 10.Roxana Girju, Adriana Badulescu, and Dan Moldovan. 2003. Learning semantic constraints for the automatic discovery of part-whole relations. In HLT-NAACL-03, pages 1–8, Edmonton, Canada.
  11. 11.Marti A. Hearst. 1992. Automatic acquisition of hyponyms from large text corpora. In COLING-92, Nantes, France.
  12. 12.Dekang Lin and Patrick Pantel. 2001. Discovery of inference rules for question-answering. Natural Language Engineering, 7(4):343–360.
  13. 13.Dekang Lin. 1998. Dependency-based evaluation of minipar. In Workshop on the Evaluation of Parsing Systems.
  14. 14.Metaweb. 2008. Freebase data dumps. http://download.freebase.com/datadumps/.
  15. 15.Alexander A. Morgan, Lynette Hirschman, Marc Colosimo, Alexander S. Yeh, and Jeff B. Colombe. 2004. Gene name identification and normalization using a model organism database. J. of Biomedical Informatics, 37(6):396–410.
  16. 16.Patrick Pantel and Marco Pennacchiotti. 2006. Espresso: leveraging generic patterns for automatically harvesting semantic relations. In COLING/ACL 2006, pages 113–120, Sydney, Australia.
  17. 17.Marco Pennacchiotti and Patrick Pantel. 2006. A bootstrapping algorithm for automatically harvesting semantic relations. In in Proceedings of Inference in Computational Semantics (ICoS-06), pages 87–96.
  18. 18.Deepak Ravichandran and Eduard H. Hovy. 2002. Learning surface text patterns for a question answering system. In ACL-02, pages 41–47, Philadelphia, PA.
  19. 19.Ellen Riloff and Rosie Jones. 1999. Learning dictionaries for information extraction by multi-level bootstrapping. In AAAI-99, pages 474–479.
  20. 20.Benjamin Rozenfeld and Ronen Feldman. 2008. Self-supervised relation extraction from the web. Knowledge and Information Systems, 17(1):17–33.
  21. 21.Yusuke Shinyama and Satoshi Sekine. 2006. Preemptive information extraction using unrestricted relation discovery. In HLT-NAACL-06, pages 304–311, New York, NY.
  22. 22.Rion Snow, Daniel Jurafsky, and Andrew Y. Ng. 2005. Learning syntactic patterns for automatic hypernym discovery. In Lawrence K. Saul, Yair Weiss, and L´eon Bottou, editors, NIPS 17, pages 1297–1304. MIT Press.
  23. 23.Rion Snow, Brendan O’Connor, Daniel Jurafsky, and Andrew Ng. 2008. Cheap and fast – but is it good? evaluating non-expert annotations for natural language tasks. In EMNLP 2008, pages 254–263, Honolulu, HI.
  24. 24.Mihai Surdeanu and Massimiliano Ciaramita. 2007. Robust information extraction with perceptrons. In Proceedings of the NIST 2007 Automatic Content Extraction Workshop (ACE07), March.
  25. 25.Fei Wu and Daniel S. Weld. 2007. Autonomously semantifying wikipedia. In CIKM ’07: Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, pages 41–50, Lisbon, Portugal.
  26. 26.Guodong Zhou, Jian Su, Jie Zhang, and Min Zhang. 2005. Exploring various knowledge in relation extraction. In ACL-05, pages 427–434, Ann Arbor, MI.
  27. 27.Guodong Zhou, Min Zhang, Donghong Ji, and Qiaoming Zhu. 2007. Tree kernel-based relation extraction with context-sensitive structured parse tree information. In EMNLP/CoNLL 2007.

Citation

MLA
Mintz, M., et al. “Distant Supervision for Relation Extraction Without Labeled Data”. Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, 2009, pp. 1003–11, https://aclanthology.org/P09-1113/.
APA
Mintz, M., Bills, S., Snow, R., & Jurafsky, D. (2009). Distant supervision for relation extraction without labeled data. Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, 1003–1011. https://aclanthology.org/P09-1113/
Chicago
Mintz, M., S. Bills, R. Snow, and D. Jurafsky. 2009. “Distant Supervision for Relation Extraction Without Labeled Data”. Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, 1003–11. https://aclanthology.org/P09-1113/.
Harvard
Mintz, M. et al. (2009) “Distant supervision for relation extraction without labeled data”, Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP. Association for Computational Linguistics, pp. 1003–1011. Available at: https://aclanthology.org/P09-1113/.
Vancouver
1. Mintz M, Bills S, Snow R, Jurafsky D (2009) Distant supervision for relation extraction without labeled data. In: Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP. Association for Computational Linguistics, pp 1003–1011

BibTeX

@inproceedings{mintz-etal-2009-distant,
    title = "Distant supervision for relation extraction without labeled data",
    author = "Mintz, Mike  and
      Bills, Steven  and
      Snow, Rion  and
      Jurafsky, Daniel",
    editor = "Su, Keh-Yih  and
      Su, Jian  and
      Wiebe, Janyce  and
      Li, Haizhou",
    booktitle = "Proceedings of the Joint Conference of the 47th Annual Meeting of the {ACL} and the 4th International Joint Conference on Natural Language Processing of the {AFNLP}",
    month = aug,
    year = "2009",
    address = "Suntec, Singapore",
    publisher = "Association for Computational Linguistics",
    url = "https://aclanthology.org/P09-1113/",
    pages = "1003--1011"
}
Metadata:ACL Anthology

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by-nc-sa/4.0/