Elamur Research⌕
☰
home / papers / 2013 / OntoLearn Reloaded: A Graph-Based Algorithm for Taxonomy Induction

OntoLearn Reloaded: A Graph-Based Algorithm for Taxonomy Induction

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

Summary

Most taxonomy-learning systems take a fixed set of domain concepts as given and only predict the is-a links between them. This paper, published in Computational Linguistics, presents OntoLearn Reloaded, which learns both the concepts and the relations from scratch. It replaces the authors' 2004 OntoLearn, which depended on WordNet and therefore struggled with technical domains and was tied to English. The new pipeline first extracts terminology from a domain corpus. It then repeatedly collects textual definitions from the corpus and the Web and pulls hypernyms out of them. The result is a noisy hypernym graph: dense, cyclic and possibly disconnected. An optimal branching algorithm with a new edge-weighting scheme reduces this graph to a tree-like taxonomy, and an optional recovery step adds extra hypernyms to form a DAG. The method was evaluated on six domains. It built new ARTIFICIAL INTELLIGENCE and FINANCE taxonomies and reconstructed WordNet and MeSH sub-hierarchies, with good quality overall. The work matters because it shows that usable taxonomies can be produced for domains that have no reference resource.

Key points

  • Apart from 52 manually chosen domain-independent upper terms, no prior knowledge is needed beyond a domain corpus. WordNet and the Word Sense Disambiguation step (SSI) of the original OntoLearn are no longer used.
  • Evaluation covers six domains: two new taxonomies (ARTIFICIAL INTELLIGENCE, FINANCE) and four gold-standard comparisons against WordNet and MeSH sub-hierarchies. It includes structural and manual analysis, and the authors also propose a new method for comparing a learned taxonomy against a gold standard.
  • TREE outputs are more precise, while DAG outputs achieve higher recall. Most errors occur at middle levels of the hierarchy, where ambiguity is highest.
  • Hypernyms drawn from definitions (WCLs) outperform Hearst-style patterns. The authors also report advantages over Kozareva and Hovy (2010) in sense filtering and graph pruning.
  • With a validation tool, experts can fix the output in hours instead of man-months. The software is available at ontolearn.org.

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 6The 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 worksBiochemistry, Genetics and Molecular Biology · 263 worksMolecular Biology · 260 works

Cite

Cite as Paola Velardi, Stefano Faralli and Roberto Navigli. 2013. OntoLearn Reloaded: A Graph-Based Algorithm for Taxonomy Induction. Computational Linguistics.

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

@article{velardi2013ontolearn,
  title = {{OntoLearn Reloaded: A Graph-Based Algorithm for Taxonomy Induction}},
  author = {Paola Velardi, Stefano Faralli and Roberto Navigli},
  journal = {Computational Linguistics},
  year = {2013},
  doi = {10.1162/coli\_a\_00146},
  url = {https://doi.org/10.1162/coli_a_00146}
}

References

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

  1. Agirre, Eneko, Oier López de Lacalle, Christiane Fellbaum, Shu-Kai Hsieh, Maurizio Tesconi, Monica Monachini, Piek Vossen, and Roxanne Segers. 2010. SemEval-2010 Task 17: All-words Word Sense Disambiguation on a specific domain. In Proceedings of the 5th International Workshop on Semantic Evaluatio… find
  2. Berland, Matthew and Eugene Charniak. 1999. Finding parts in very large corpora. In Proceedings of the 27 th Annual 29 Data sets are available at: http://lcl.uniroma1.it/ontolearn reloaded. 30 For example, http://lcl.uniroma1.it/tav/. ↗
  3. Meeting of the Association for Computational Linguistics (ACL), pages 57–64, College Park, MD. find
  4. Biemann, Chris. 2005. Ontology learning from text—A survey of methods. LDV-Forum, 20(2):75–93. find
  5. Brank, Janez, Dunja Mladenic, and Marko Grobelnik. 2006. Gold standard based ontology evaluation using instance assignment. In Proceedings of 4 th Workshop Evaluating Ontologies for the Web (EON), Edinburgh. find
  6. Carpineto, Claudio and Giovanni Romano. 2012. Consensus Clustering Based on a New Probabilistic Rand Index with Application to Subtopic Retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(12):2315–2326. find
  7. Chu, Yoeng-Jin and Tseng-Hong Liu. 1965. On the shortest arborescence of a directed graph. Science Sinica, 14:1396–1400. find
  8. Cimiano, Philipp, Andreas Hotho, and Steffen Staab. 2005. Learning concept hierarchies from text corpora using formal concept analysis. Journal of Artificial Intelligence Research, 24(1):305–339. find
  9. Cohen, Trevor and Dominic Widdows. 2009. Empirical distributional semantics: Methods and biomedical applications. Journal of Biomedical Informatics, 42(2):390–405. find
  10. Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. 1990. Introduction to Algorithms. MIT Electrical Engineering and Computer Science. MIT Press, Cambridge, MA. find
  11. De Benedictis, Flavio, Stefano Faralli, and Roberto Navigli. 2013. GlossBoot: Bootstrapping Multilingual Domain Glossaries from the Web. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (ACL), Sofia. find
  12. De Nicola, Antonio, Michele Missikoff, and Roberto Navigli. 2009. A software engineering approach to ontology building. Information Systems, 34(2):258–275. find
  13. Edmonds, Jack. 1967. Optimum branchings. Journal of Research of the National Bureau of Standards, 71B:233–240. find
  14. Etzioni, Oren, Anthony Fader, Janara Christensen, Stephen Soderland, and Mausam. 2011. Open information extraction: The second generation. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), pages 3–10, Barcelona. find
  15. Fahmi, Ismail and Gosse Bouma. 2006. Learning to identify definitions using syntactic features. In Proceedings of the EACL 2006 workshop on Learning Structured Information in Natural Language Applications, pages 64–71, Trento. find
  16. Faralli, Stefano and Roberto Navigli. 2012. A new minimally supervised framework for domain Word Sense Disambiguation. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), pages 1,411–1,422, Jeju. find
  17. Fellbaum, Christiane, editor. 1998. WordNet: An Electronic Lexical Database. MIT Press, Cambridge, MA. find
  18. Fleiss, Joseph L. 1971. Measuring nominal scale agreement among many raters. Psychological Bulletin, 76(5):378–382. find
  19. Fountain, Trevor and Mirella Lapata. 2012. Taxonomy induction using hierarchical random graphs. In Proceedings of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (HLT-NAACL), pages 466–476, Montréal. find
  20. Fowlkes, Edward B. and Colin L. Mallows. 1983. A method for comparing two hierarchical clusterings. Journal of the American Statistical Association, 78(383):553–569. find
  21. Girju, Roxana, Adriana Badulescu, and Dan Moldovan. 2006. Automatic discovery of part-whole relations. Computational Linguistics, 32(1):83–135. find
  22. Gomez-Perez, Asunción and David Manzano-Mancho. 2003. A survey of ontology learning methods and techniques. OntoWeb Delieverable 1.5. Universidad Politécnica de Madrid. find
  23. Guarino, Nicola and Chris Welty. 2002. Evaluating ontological decisions with OntoClean. Communications of the ACM, 45(2):61–65. find
  24. Hearst, Marti A. 1992. Automatic acquisition of hyponyms from large text corpora. In Proceedings of the 14 th International Conference on Computational Linguistics (COLING), pages 539–545, Nantes.
  25. Hovy, Eduard, Andrew Philpot, Judith Klavans, Ulrich Germann, and Peter T. Davis. 2003. Extending metadata definitions by automatically extracting and organizing glossary definitions. In Proceedings of the 2003 Annual National Conference on Digital Government Research, pages 1–6, Boston, MA. find
  26. Ide, Nancy and Jean Véronis. 1993. Extracting knowledge bases from machine-readable dictionaries: Have we wasted our time? In Proceedings of the Workshop on Knowledge Bases and Knowledge Structures, pages 257–266, Tokyo. find
  27. Kozareva, Zornitsa and Eduard Hovy. 2010. A semi-supervised method to learn and construct taxonomies using the Web. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1,110–1,118, Cambridge, MA.
  28. Kozareva, Zornitsa, Ellen Riloff, and Eduard Hovy. 2008. Semantic class learning from the Web with hyponym pattern linkage graphs. In Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics (ACL), pages 1,048–1,056, Columbus, OH.
  29. Maedche, Alexander, Viktor Pekar, and Steffen Staab. 2002. Ontology learning part one—on discovering taxonomic relations from the Web. In N. Zhong, J. Liu, and Y. Y. Yao, editors, Web Intelligence. Springer Verlag, Berlin, pages 301–322. find
  30. Maedche, Alexander and Steffen Staab. 2009. Ontology learning. In Steffen Staab and Rudi Studer, editors, Handbook on Ontologies. Springer, Berlin, pages 245–268. find
  31. Miller, George A., R. T. Beckwith, Christiane D. Fellbaum, D. Gross, and K. Miller. 1990. WordNet: An online lexical database. International Journal of Lexicography, 3(4):235–244. find
  32. Morey, Leslie C. and Alan Agresti. 1984. The measurement of classification agreement: An adjustment to the Rand statistic for chance agreement. Educational and Psychological Measurement, 44:33–37. find
  33. Moro, Andrea and Roberto Navigli. 2012. WiSeNet: Building a Wikipedia-based semantic network with ontologized relations. In Proceedings of the 21 st ACM Conference on Information and Knowledge Management (CIKM 2012), pages 1,672–1,676, Maui, HI. find
  34. Navigli, Roberto. 2009. Word Sense Disambiguation: A survey. ACM Computing Surveys, 41(2):1–69. find
  35. Navigli, Roberto, and Simone Paolo Ponzetto. 2012. BabelNet: The automatic construction, evaluation and application of a wide-coverage multilingual semantic network. Artificial Intelligence 193, pp. 217–250. find
  36. Navigli, Roberto and Paola Velardi. 2004. Learning domain ontologies from document warehouses and dedicated websites. Computational Linguistics, 30(2):151–179. find
  37. Navigli, Roberto and Paola Velardi. 2005. Structural semantic interconnections: A knowledge-based approach to Word Sense Disambiguation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(7):1075–1088. find
  38. Navigli, Roberto and Paola Velardi. 2010. Learning Word-Class Lattices for definition and hypernym extraction. In Proceedings of the 48 th Annual Meeting of the Association for Computational Linguistics (ACL), pages 1,318–1,327, Uppsala.
  39. Navigli, Roberto, Paola Velardi, and Stefano Faralli. 2011. A graph-based algorithm for inducing lexical taxonomies from scratch. In Proceedings of the 22 nd International Joint Conference on Artificial Intelligence (IJCAI), pages 1,872–1,877, Barcelona.
  40. Newman, Mark E. J. 2010. Networks: An Introduction. Oxford University Press. find
  41. Pado, Sebastian and Mirella Lapata. 2007. Dependency-based construction of semantic space models. Computational Linguistics, 33(2):161–199.
  42. Pantel, Patrick and Marco Pennacchiotti. 2006. Espresso: Leveraging generic patterns for automatically harvesting semantic relations. In Proceedings of 44 th Annual Meeting of the Association for Computational Linguistics joint with 21 st Conference on Computational Linguistics (COLING-ACL), pages 1…
  43. Pasca, Marius. 2004. Acquisition of categorized named entities for web search. In Proceedings of the 13 th ACM International Conference on Information and Knowledge Management (CIKM), pages 137–145, Washington, DC. find
  44. Petasis, Georgios, Vangelis Karkaletsis, Georgios Paliouras, Anastasia Krithara, and Elias Zavitsanos. 2011. Ontology population and enrichment: State of the art. In Georgios Paliouras, Constantine Spyropoulos, and George Tsatsaronis, editors, Knowledge-Driven Multimedia Information Extraction and O… find
  45. Petrenz, Philipp and Bonnie L. Webber. 2011. Stable classification of text genres. Computational Linguistics, 37(2):385–393. find
  46. Ponzetto, Simone Paolo and Roberto Navigli. 2009. Large-scale taxonomy mapping for restructuring and integrating Wikipedia. In Proceedings of the 21 st International Joint Conference on Artificial Intelligence (IJCAI), pages 2,083–2,088, Pasadena, CA. find
  47. Ponzetto, Simone Paolo and Michael Strube. 2011. Taxonomy induction based on a collaboratively built knowledge repository. Artificial Intelligence, 175:1737–1756. find
  48. Poon, Hoifung and Pedro Domingos. 2010. Unsupervised ontology induction from text. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL), pages 296–305, Uppsala. find
  49. Rand, William M. 1971. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association, 66(336):846–850. find
  50. Schmid, Helmut. 1995. Improvements in part-of-speech tagging with an application to German. In Proceedings of the ACL SIGDAT-Workshop, pages 47–50, Dublin. find
  51. Sclano, Francesco and Paola Velardi. 2007. TermExtractor: A Web application to learn the shared terminology of emergent Web communities. In Proceedings of the 3 th International Conference on Interoperability for Enterprise Software and Applications (I-ESA), pages 287–290, Funchal. find
  52. Snow, Rion, Dan Jurafsky, and Andrew Ng. 2006. Semantic taxonomy induction from heterogeneous evidence. In Proceedings of 44 th Annual Meeting of the Association for Computational Linguistics joint with 21 st Conference on Computational Linguistics (COLING-ACL), pages 801–808, Sydney. find
  53. Sowa, John F. 2000. Knowledge Representation: Logical, Philosophical, and Computational Foundations. Brooks Cole Publishing Co., Pacific Grove, CA. find
  54. Storrer, Angelika and Sandra Wellinghoff. 2006. Automated detection and annotation of term definitions in German text corpora. In Proceedings of the 5 th International Conference on Language Resources and Evaluation (LREC), pages 2,373–2,376, Genova. find
  55. Suchanek, Fabian M., Gjergji Kasneci, and Gerhard Weikum. 2008. YAGO: A large ontology from Wikipedia and WordNet. Journal of Web Semantics, 6(3):203–217. find
  56. Tang, Jie, Ho Fung Leung, Qiong Luo, Dewei Chen, and Jibin Gong. 2009. Towards ontology learning from folksonomies. In Proceedings of the 21 st International Joint Conference on Artificial Intelligence (IJCAI), pages 2,089–2,094, Pasadena, CA. find
  57. Tarjan, Robert Endre. 1977. Finding optimum branchings. Networks, 7(1):25–35. find
  58. Velardi, Paola, Roberto Navigli, and Pierluigi D’Amadio. 2008. Mining the Web to create specialized glossaries. IEEE Intelligent Systems, 23(5):18–25. find
  59. Völker, Johanna, Denny Vrandečić, York Sure, and Andreas Hotho. 2008. find
  60. AEON—An approach to the automatic evaluation of ontologies. Journal of Applied Ontology, 3(1-2):41–62. find
  61. Vossen, Piek. 2001. Extending, trimming and fusing WordNet for technical documents. In Proceedings of the North American Chapter of the Association for Computational Linguistics Workshop on WordNet and Other Lexical Resources: Applications, Extensions and Customizations (NAACL), pages 125–131, Pitts… find
  62. Wagner, Silke and Dorothea Wagner. 2007. Comparing clusterings: An overview. Technical Report 2006-04, Faculty of Informatics, Universität Karlsruhe (TH). find
  63. Westerhout, Eline. 2009. Definition extraction using linguistic and structural features. In Proceedings of the RANLP Workshop on Definition Extraction, pages 61–67, Borovets. find
  64. Yang, Hui and Jamie Callan. 2008. Human-guided ontology learning. In Proceedings of Human-Computer Interaction and Information Retrieval (HCIR), pages 26–29, Redmond, WA. find
  65. Yang, Hui and Jamie Callan. 2009. A metric-based framework for automatic taxonomy induction. In Proceedings of the 47th Annual Meeting of the Association for Computational Linguistics (ACL), pages 271–279, Suntec. find
  66. Zavitsanos, Elias, Georgios Paliouras, and George A. Vouros. 2011. Gold standard evaluation of ontology learning methods through ontology transformation and alignment. IEEE Transactions on Knowledge and Data Engineering, 23(11):1635–1648. find
  67. Zhang, Chunxia and Peng Jiang. 2009. Automatic extraction of definitions. In Proceedings of 2nd IEEE International Conference on Computer Science and Information Technology (ICCSIT), pages 364–368, Beijing. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/velardi-2013-ontolearn-reloaded-graph-based-algorithm/