Elamur Research⌕
☰
home / papers / 2014 / Structured Learning for Taxonomy Induction with Belief Propagation

Structured Learning for Taxonomy Induction with Belief Propagation

Paper · 2014 · Mohit Bansal, David Burkett, Gerard de Melo et al.

Summary

The paper addresses automatic construction of hypernym taxonomies. Given a set of terms, the system must output a full tree in which each term is attached to its parent. Manually built resources such as WordNet have gaps in coverage and are expensive to extend. The authors frame the task as a log-linear factor graph with three kinds of factors:

  • first-order factors scoring individual parent–child edges;
  • second-order factors scoring pairs of edges that share a parent (siblinghood);
  • a global constraint that forces the output to be a valid directed spanning tree.

Features are surface patterns and statistics drawn from Web n-grams and Wikipedia abstracts. Inference uses loopy belief propagation, and the tree factor's messages are computed with the Matrix Tree Theorem. The model is trained discriminatively to reproduce WordNet sub-hierarchies, using adaptive subgradient optimization. On held-out WordNet fragments it roughly halves the error of a chance baseline. It also outperforms earlier systems on an animal-taxonomy benchmark. This matters because it is the first end-to-end structured model that learns relational patterns, including sibling cues, directly while training for whole-tree prediction.

Key points

  • WordNet reconstruction: ancestor-based F1 shows a 51% error reduction relative to a chance baseline. About 15% of that reduction comes from the sibling (second-order) factors.
  • Comparison with prior work: on the animal subtree used by Kozareva and Hovy (2010), the model reaches up to 29% relative error reduction in ancestor F1 under the "Fixed Prediction" setup. Results against Navigli et al. (2011) are not directly comparable, because that work used a different ground truth (Google define, which often returns WordNet glosses).
  • Inference: belief propagation is exact for the edge-only model, which has no cycles. Adding sibling factors creates loops, so inference becomes loopy BP, capped at 20 iterations. Tree-factor messages cost O(n³) via Kirchhoff's Matrix Tree Theorem.
  • Precision-oriented decoding: prior systems favour precision, while this model balances precision and recall. Thresholding edge beliefs raises precision to 90.8% while keeping F1 at 61.7%.
  • Learned patterns: the model recovers classic Hearst patterns such as "C and other P". It also finds new ones, e.g. "C, american P" and breadcrumb-style "> P > C", plus coordination cues like "either C1 or C2".

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 California, BerkeleyBerkeley · United States243 works · 251,774 citations🎓Tsinghua UniversityBeijing · China439 works · 94,783 citations🎓Toyota Technological Institute at ChicagoChicago · United States37 works · 13,529 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksArts and Humanities · 17,959 worksLanguage and Linguistics · 17,789 works

Cite

Cite as Mohit Bansal, David Burkett, Gerard de Melo and Dan Klein. 2014. Structured Learning for Taxonomy Induction with Belief Propagation. Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.3115/v1/p14-1098

@inproceedings{bansal2014structured,
  title = {{Structured Learning for Taxonomy Induction with Belief Propagation}},
  author = {Mohit Bansal, David Burkett, Gerard {de Melo} and Dan Klein},
  booktitle = {Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2014},
  doi = {10.3115/v1/p14-1098},
  url = {https://doi.org/10.3115/v1/p14-1098}
}

References

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

  1. Mohit Bansal and Dan Klein. 2011. Web-scale features for full-scale parsing. In Proceedings of ACL. find
  2. Marco Baroni, Brian Murphy, Eduard Barbu, and Massimo Poesio. 2010. Strudel: A corpus-based semantic model based on properties and types. Cognitive Science, 34(2):222–254. find
  3. Thorsten Brants and Alex Franz. 2006. The Google Web 1T 5-gram corpus version 1.1. LDC2006T13. find
  4. Yoeng-Jin Chu and Tseng-Hong Liu. 1965. On the shortest arborescence of a directed graph. Science Sinica, 14(1396-1400):270. find
  5. Philipp Cimiano and Steffen Staab. 2005. Learning concept hierarchies from text with a guided agglomerative clustering algorithm. In Proceedings of the ICML 2005 Workshop on Learning and Extending Lexical Ontologies with Machine Learning Methods. find
  6. Philipp Cimiano, 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
  7. Dmitry Davidov and Ari Rappoport. 2006. Efficient unsupervised discovery of word categories using symmetric patterns and high frequency words. In Proceedings of COLING-ACL. find
  8. John Duchi, Elad Hazan, and Yoram Singer. 2011. Adaptive subgradient methods for online learning and stochastic optimization. The Journal of Machine Learning Research, 12:2121–2159. find
  9. Jack Edmonds. 1967. Optimum branchings. Journal of Research of the National Bureau of Standards B, 71:233–240. find
  10. 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. find
  11. David Ferrucci, Eric Brown, Jennifer Chu-Carroll, James Fan, David Gondek, Aditya A Kalyanpur, Adam Lally, J William Murdock, Eric Nyberg, John Prager, Nico Schlaefer, and Chris Welty. 2010. Building watson: An overview of the DeepQA project. AI magazine, 31(3):59–79. find
  12. Trevor Fountain and Mirella Lapata. 2012. Taxonomy induction using hierarchical random graphs. In Proceedings of NAACL. find
  13. Leonidas Georgiadis. 2003. Arborescence optimization problems solvable by edmonds algorithm. Theoretical Computer Science, 301(1):427–437. find
  14. Roxana Girju, Adriana Badulescu, and Dan Moldovan. 2003. Learning semantic constraints for the automatic discovery of part-whole relations. In Proceedings of NAACL.
  15. Joshua Goodman. 1996. Parsing algorithms and metrics. In Proceedings of ACL. find
  16. Zellig Harris. 1954. Distributional structure. Word, 10(23):146–162. find
  17. Marti Hearst. 1992. Automatic acquisition of hyponyms from large text corpora. In Proceedings of COLING.
  18. Eduard Hovy, Zornitsa Kozareva, and Ellen Riloff. 2009. Toward completeness in concept extraction and classification. In Proceedings of EMNLP. find
  19. Boris Katz and Jimmy Lin. 2003. Selectively using relations to improve precision in question answering. In Proceedings of the Workshop on NLP for Question Answering (EACL 2003). find
  20. Terry Koo, Amir Globerson, Xavier Carreras, and Michael Collins. 2007. Structured prediction models via the matrix-tree theorem. In Proceedings of EMNLP-CoNLL. find
  21. Zornitsa Kozareva and Eduard Hovy. 2010. A semi-supervised method to learn and construct taxonomies using the Web. In Proceedings of EMNLP.
  22. Zornitsa Kozareva, Ellen Riloff, and Eduard Hovy. 2008. Semantic class learning from the web with hyponym pattern linkage graphs. In Proceedings of ACL.
  23. Ni Lao, Amarnag Subramanya, Fernando Pereira, and William W. Cohen. 2012. Reading the web with learned syntactic-semantic inference rules. In Proceedings of EMNLP. find
  24. Dekang Lin and Patrick Pantel. 2002. Concept discovery from text. In Proceedings of COLING. find
  25. Dekang Lin. 1998. Automatic retrieval and clustering of similar words. In Proceedings of COLING.
  26. Ryan McDonald, Fernando Pereira, Kiril Ribarov, and Jan Hajič. 2005. Non-projective dependency parsing using spanning tree algorithms. In Proceedings of HLT-EMNLP.
  27. Roberto Navigli and Paola Velardi. 2010. Learning word-class lattices for definition and hypernym extraction. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics.
  28. Roberto Navigli, Paola Velardi, and Stefano Faralli. 2011. A graph-based algorithm for inducing lexical taxonomies from scratch. In Proceedings of IJCAI.
  29. Patrick Pantel and Marco Pennacchiotti. 2006. Espresso: Leveraging generic patterns for automatically harvesting semantic relations. In Proceedings of COLING-ACL.
  30. Marius Paşca. 2004. Acquisition of categorized named entities for web search. In Proceedings of CIKM. find
  31. Marco Pennacchiotti and Patrick Pantel. 2006. On-tologizing semantic relations. In Proceedings of COLING-ACL. find
  32. William Phillips and Ellen Riloff. 2002. Exploiting strong syntactic heuristics and co-training to learn semantic lexicons. In Proceedings of EMNLP. find
  33. Simone Paolo Ponzetto and Michael Strube. 2011. Taxonomy induction based on a collaboratively built knowledge repository. Artificial Intelligence, 175(9):1737–1756. find
  34. Hoifung Poon and Pedro Domingos. 2010. Unsupervised ontology induction from text. In Proceedings of ACL. find
  35. Ellen Riloff and Jessica Shepherd. 1997. A corpus-based approach for building semantic lexicons. In Proceedings of EMNLP.
  36. Alan Ritter, Stephen Soderland, and Oren Etzioni. 2009. What is this, anyway: Automatic hypernym discovery. In Proceedings of AAAI Spring Symposium on Learning by Reading and Learning to Read. find
  37. David A. Smith and Jason Eisner. 2008. Dependency parsing by belief propagation. In Proceedings of EMNLP.
  38. Rion Snow, Daniel Jurafsky, and Andrew Y. Ng. 2006. Semantic taxonomy induction from heterogenous evidence. In Proceedings of COLING-ACL. find
  39. Fabian M. Suchanek, Gjergji Kasneci, and Gerhard Weikum. 2007. Yago: a core of semantic knowledge. In Proceedings of WWW. find
  40. Partha Pratim Talukdar, Joseph Reisinger, Marius Paşca, Deepak Ravichandran, Rahul Bhagat, and Fernando Pereira. 2008. Weakly-supervised acquisition of labeled class instances using graph random walks. In Proceedings of EMNLP. find
  41. Robert E. Tarjan. 1977. Finding optimum branchings. Networks, 7:25–35. find
  42. William T. Tutte. Wesley. 1984. Graph theory. find
  43. Addison-Dominic Widdows. 2003. Unsupervised methods for developing taxonomies by combining syntactic and statistical information. In Proceedings of HLT-NAACL. find
  44. Ichiro Yamada, Kentaro Torisawa, Jun’ichi Kazama, Kow Kuroda, Masaki Murata, Stijn De Saeger, Francis Bond, and Asuka Sumida. 2009. Hypernym discovery based on distributional similarity and hierarchical structures. In Proceedings of EMNLP. find
  45. Hui Yang and Jamie Callan. 2009. A metric-based framework for automatic taxonomy induction. In Proceedings of ACL-IJCNLP. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/bansal-2014-structured-learning-taxonomy-induction-belief/