Elamur Research⌕
☰
home / papers / 2008 / Semantic Class Learning from the Web with Hyponym Pattern Linkage Graphs

Semantic Class Learning from the Web with Hyponym Pattern Linkage Graphs

Paper · 2008 · Zornitsa Kozareva, Ellen Riloff and Eduard Hovy

Summary

The paper tackles automatic construction of semantic lexicons, meaning lists of words that belong to a given category, using the web with almost no supervision. The only input is a class name and one seed member. Candidates are harvested with a single doubly-anchored Hearst-style pattern, "<class name> such as <class member> and *", which is issued as a web query. Every newly extracted word is fed back as a new seed. This unchecked loop ("reckless bootstrapping") quickly drifts off-topic, so the authors build hyponym pattern linkage graphs (HPLGs) that record which instances discover which others. From these graphs they derive two signals: popularity (how often a word is found by others) and productivity (how often it finds new words). They propose two algorithms: one uses popularity to guide bootstrapping on the fly, and one runs an exhaustive search first and then ranks candidates by graph properties. Tested on U.S. states, countries, singers and fish, the methods achieve high accuracy, and the productivity-based ranking works best. No tagging, parsing or labelled data is needed, so the approach can be applied to arbitrary categories.

Key points

  • The authors evaluate on four classes: U.S. states (gold list of 50), countries (gold list of 194), and two large open classes, singers and fish.
  • Reckless bootstrapping loses accuracy fast as iterations pile up. Countries fall from .80 to .16 over four iterations, and states fall from .79 to .18 by the third. Singers hold up better (.91 to .83).
  • The best system is the two-step method: exhaustive search, then ranking by the Out-degree (productivity) score. Words with zero productivity are cut from the list. In the singer run seeded with Placido Domingo, 400 candidates were produced and the list was cut at 180.
  • Results are stable across seeds. All five random country seeds (e.g., Guinea-Bissau, Uganda) reached at least 92% recall with at least 90% precision.
  • Errors fall into five types:
    • faulty name extraction,
    • former or borderline members,
    • spelling and name variants,
    • factually wrong web text,
    • broken tokens in snippets.

Interesting ideas

  • I1. Double anchoring for disambiguation. Putting both the category and a known member into the query makes each one narrow the meaning of the other. This is a cheap way to steer extraction toward the intended sense of ambiguous words, and it could carry over to other languages or to search-based data collection.
  • I2. Popularity plus productivity as a check. A candidate is trusted when other members lead to it and it also leads to other members. This kind of two-directional consistency in a discovery graph could filter noise in any bootstrapped extraction pipeline.
  • I3. Zero productivity as a stopping rule. Truncating the ranked list where candidates stop yielding new instances gives a cutoff without any labelled data. It is useful when no development set exists.
  • I4. Rank overflow reveals class definition problems. The entries ranked just below the true states were former Soviet republics, which showed that the class name itself was underspecified. Inspecting the borderline region of a ranking is a handy diagnostic for how a category was defined.
  • I5. Not every error is harmful. The error analysis notes that former members and name variants may actually be useful in a dictionary or ontology. Evaluation should therefore consider what the downstream resource needs.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of Southern CaliforniaLos Angeles · United States104 works · 33,876 citations🎓University of UtahSalt Lake City · United States29 works · 5,781 citations🎓University of AlicanteAlicante · Spain14 works · 1,081 citations

📚 Shelves 5 Computer Science · 9,086 works Artificial Intelligence · 8,889 works Arts and Humanities · 9,296 works Language and Linguistics · 9,206 works Information Systems · 523 works

Appears in

Articles of ours that cite this paper.

Agglomerations Salt Lake City

Cite

Cite as Zornitsa Kozareva, Ellen Riloff and Eduard Hovy. 2008. Semantic Class Learning from the Web with Hyponym Pattern Linkage Graphs. Proceedings of ACL-08: HLT.

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{kozareva2008semantic,
  title = {{Semantic Class Learning from the Web with Hyponym Pattern Linkage Graphs}},
  author = {Zornitsa Kozareva, Ellen Riloff and Eduard Hovy},
  booktitle = {Proceedings of ACL-08: HLT},
  year = {2008},
  url = {https://aclanthology.org/P08-1119/}
}

References

28 references, 9 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. M. Berland and E. Charniak. 1999. Finding Parts in Very Large Corpora. In Proc. of the 37th Annual Meeting of the Association for Computational Linguistics. our card
  2. S. Borgatti and M. Everett. 2006. A graph-theoretic perspective on centrality. Social Networks, 28(4). find
  3. S. Caraballo. 1999. Automatic Acquisition of a Hypernym-Labeled Noun Hierarchy from Text. In Proc. of the 37th Annual Meeting of the Association for Computational Linguistics, pages 120–126. find
  4. P. Cimiano and J. Volker. 2005. Towards large-scale, open-domain and ontology-based named entity classification. In Proc. of Recent Advances in Natural Language Processing, pages 166–172. find
  5. D. Davidov and A. Rappoport. 2006. Efficient unsupervised discovery of word categories using symmetric patterns and high frequency words. In Proc. of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the ACL. find
  6. O. Etzioni, M. Cafarella, D. Downey, A. Popescu, T. Shaked, S. Soderland, D. Weld, and A. Yates. 2005. Unsupervised named-entity extraction from the web: an experimental study. Artificial Intelligence, 165(1):91–134, June. find
  7. M.B. Fleischman and E.H. Hovy. 2002. Fine grained classification of named entities. In Proc. of the 19th International Conference on Computational Linguistics, pages 1–7. find
  8. C. Freeman. 1979. Centrality in social networks: Conceptual clarification. Social Networks, 1:215–239. find
  9. R. Girju, A. Badulescu, and D. Moldovan. 2003. Learning semantic constraints for the automatic discovery of part-whole relations. In Proc. of Conference of HLT / North American Chapter of the Association for Computational Linguistics. our card
  10. M. Hearst. 1992. Automatic acquisition of hyponyms from large text corpora. In Proc. of the 14th conference on Computational linguistics, pages 539–545. find
  11. D. Lin and P. Pantel. 2002. Concept discovery from text. In Proc. of the 19th International Conference on Computational linguistics, pages 1–7. find
  12. D. Lin. 1998. Automatic retrieval and clustering of similar words. In Proc. of the 17th international conference on Computational linguistics, pages 768–774. our card
  13. G. Mann. 2002. Fine-grained proper noun ontologies for question answering. In Proc. of the 19th International Conference on Computational Linguistics, pages 1–7. find
  14. G. Miller. 1990. Wordnet: An On-line Lexical Database. International Journal of Lexicography, 3(4). find
  15. R. Navigli and M. Lapata. 2007. Graph connectivity measures for unsupervised word sense disambiguation. In Proc. of the 20th International Joint Conference on Artificial Intelligence, pages 1683–1688. our card
  16. M. Paşca. 2004. Acquisition of categorized named entities for web search. In Proc. of the Thirteenth ACM International Conference on Information and Knowledge Management, pages 137–145. find
  17. M. Paşca. 2007a. Organizing and searching the world wide web of facts – step two: harnessing the wisdom of the crowds. In Proc. of the 16th International Conference on World Wide Web, pages 101–110. find
  18. M. Paşca. 2007b. Weakly-supervised discovery of named entities using web search queries. In Proc. of the sixteenth ACM conference on Conference on information and knowledge management, pages 683–690. find
  19. L. Page, S. Brin, R. Motwani, and T. Winograd. 1998. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project. our card
  20. P. Pantel and D. Ravichandran. 2004. Automatically labeling semantic classes. In Proc. of Conference of HLT / North American Chapter of the Association for Computational Linguistics, pages 321–328. our card
  21. P. Pantel, D. Ravichandran, and E. Hovy. 2004. Towards terascale knowledge acquisition. In Proc. of the 20th international conference on Computational Linguistics, page 771. find
  22. W. Phillips and E. Riloff. 2002. Exploiting Strong Syntactic Heuristics and Co-Training to Learn Semantic Lexicons. In Proc. of the 2002 Conference on Empirical Methods in Natural Language Processing. find
  23. E. Riloff and R. Jones. 1999. Learning Dictionaries for Information Extraction by Multi-Level Bootstrapping. In Proc. of the Sixteenth National Conference on Artificial Intelligence. find
  24. E. Riloff and J. Shepherd. 1997. A Corpus-Based Approach for Building Semantic Lexicons. In Proc. of the Second Conference on Empirical Methods in Natural Language Processing, pages 117–124. our card
  25. B. Roark and E. Charniak. 1998. Noun-phrase Co-occurrence Statistics for Semi-automatic Semantic Lexicon Construction. In Proc. of the 36th Annual Meeting of the Association for Computational Linguistics, pages 1110–1116. find
  26. H. Tanev and B. Magnini. 2006. Weakly supervised approaches for ontology population. In Proc. of 11st Conference of the European Chapter of the Association for Computational Linguistics. find
  27. M. Thelen and E. Riloff. 2002. A Bootstrapping Method for Learning Semantic Lexicons Using Extraction Pattern Contexts. In Proc. of the 2002 Conference on Empirical Methods in Natural Language Processing. our card
  28. D. Widdows and B. Dorow. 2002. A graph model for unsupervised lexical acquisition. In Proc. of the 19th International Conference on Computational Linguistics, pages 1–7. our card

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/kozareva-2008-semantic-class-learning-web-hyponym/