Elamur Research⌕
☰
home / papers / 2011 / A Graph-Based Algorithm for Inducing Lexical Taxonomies from Scratch

A Graph-Based Algorithm for Inducing Lexical Taxonomies from Scratch

Paper · 2011 · Roberto Navigli, Paola Velardi and Stefano Faralli

Summary

The paper tackles automatic construction of a lexical taxonomy for a domain without relying on a predefined concept set or an existing hierarchy. Only a few upper terms are given by hand. Starting from a domain corpus, the authors extract terminology with TermExtractor. They then iteratively gather definitional sentences from the corpus, the Web and Google define, and apply Word-Class Lattices (WCLs) to detect definitions and extract hypernyms. A domain-weight filter discards off-domain definitions, which implicitly handles ambiguity. The process yields a dense, cyclic and often disconnected hypernym graph. A new induction procedure then turns this graph into a taxonomy in four stages:

  • trimming spurious roots and leaves,
  • weighting edges to balance path length against node connectivity,
  • extracting an optimal branching with Edmonds' algorithm,
  • recovering over-pruned components.

The method produced a new Artificial Intelligence taxonomy and was also used to rebuild the WordNet sub-hierarchies for animals, plants and vehicles. Manually checked precision of relations absent from WordNet was high. The work matters because it builds usable taxonomies truly from scratch, learning both concepts and relations.

Key points

  • The domain filter keeps definitions with DomainWeight ≥ 0.38. This threshold was tuned on 200 manually annotated definitions.
  • In the AI hypernym graph, average node ambiguity before pruning was 1.4, and some nodes had more than 10 candidate hypernyms.
  • On the WordNet test, coverage of the initial terminology was 0.71 for animals, 0.79 for plants and 0.73 for vehicles.
  • Hand-checked precision of edges not found in WordNet was 0.76 for animals, 0.82 for plants and 0.92 for vehicles.
  • The AI taxonomy is publicly released at lcl.uniroma1.it/taxolearn.

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

🎓Sapienza University of RomeRome · Italy60 works · 10,105 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 works

Cite

Cite as Roberto Navigli, Paola Velardi and Stefano Faralli. 2011. A Graph-Based Algorithm for Inducing Lexical Taxonomies from Scratch. IJCAI-11.

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

@inproceedings{navigli2011graph,
  title = {{A Graph-Based Algorithm for Inducing Lexical Taxonomies from Scratch}},
  author = {Roberto Navigli, Paola Velardi and Stefano Faralli},
  booktitle = {IJCAI-11},
  year = {2011},
  doi = {10.5591/978-1-57735-516-8/ijcai11-313},
  url = {https://doi.org/10.5591/978-1-57735-516-8/ijcai11-313}
}

References

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

  1. Matthew Berland and Eugene Charniak. Finding parts in very large corpora. In Proceedings of ACL 1999, pages 57–64, Stroudsburg, USA, 1999.
  2. Chris Biemann. Ontology learning from text – a survey of methods. LDV-Forum, 20(2):75–93, 2005. find
  3. Trevor Cohen and Dominic Widdows. Empirical distributional semantics: Methods and biomedical applications. Journal of Biomedical Informatics, 42(2):390–405, April 2009. find
  4. J. Edmonds. Optimum branchings. J. Res. Nat. Bur. Standard, 71B:233–240, 1967. find
  5. Christiane Fellbaum, editor. WordNet: An Electronic Database. MIT Press, Cambridge, MA, 1998. find
  6. Roxana Girju, Adriana Badulescu, and Dan Moldovan. Learning semantic constraints for the automatic discovery of part-whole relations. In Proc. of NAACL-HLT 2003, pages 1–8, Canada, 2003.
  7. Marti A. Hearst. Automatic acquisition of hyponyms from large text corpora. In Proc. of COLING 1992, pages 539–545, 1992.
  8. Zornitsa Kozareva and Eduard Hovy. A semi-supervised method to learn and construct taxonomies using the web. In Proceedings of EMNLP 2010, pages 1110–1118, Cambridge, MA, October 2010.
  9. Zornitsa Kozareva, Ellen Riloff, and Eduard Hovy. Semantic class learning from the web with hyponym pattern linkage graphs. In Proceedings of ACL 2008, pages 1048– 1056, Columbus, Ohio, June 2008.
  10. Alexander Maedche and Steffen Staab. Ontology learning. In Handbook on Ontologies, pages 245–268. Springer, 2009. find
  11. Roberto Navigli and Paola Velardi. Learning Word-Class Lattices for definition and hypernym extraction. In Proceedings of ACL 2010, pages 1318–1327, Uppsala, Sweden, 2010.
  12. Roberto Navigli. Word Sense Disambiguation: A survey. ACM Computing Surveys, 41(2):1–69, 2009. find
  13. M. E. J. Newman, editor. Networks: An Introduction. Oxford University Pres, Oxford, UK, 2010. find
  14. Sebastian Pado and Mirella Lapata. Dependency-based construction of semantic space models. Computational Linguistics, 33(2):161–199, 2007.
  15. Gomez A. Perez and Manzano D. Man-cho. A Survey of Ontology Learning Methods and Techniques. OntoWeb Delieverable 1.5, May 2003. find
  16. Hoifung Poon and Pedro Domingos. Unsupervised ontology induction from text. In Proceedings of ACL 2010, pages 296–305, Stroudsburg, USA, 2010. find
  17. F. Sclano and P. Velardi. Termextractor: a web application to learn the shared terminology of emergent web communities. In Proc. of I-ESA 2007, Portugal, 2007. find
  18. Rion Snow, Dan Jurafsky, and Andrew Ng. Semantic taxonomy induction from heterogeneous evidence. In Proc. of COLING-ACL 2006, pages 801–808, 2006. find
  19. Dominic Widdows and Beate Dorow. A graph model for unsupervised lexical acquisition. In Proceedings of COLING 2002, pages 1–7, Stroudsburg, USA, 2002.
  20. Hui Yang and Jamie Callan. A metric-based framework for automatic taxonomy induction. In Proc. of ACL 2009, pages 271–279, Stroudsburg, USA, 2009. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/navigli-2011-graph-based-algorithm-inducing-lexical/