Structured Learning for Taxonomy Induction with Belief Propagation

Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, pages 1041–1051, Baltimore, Maryland, USA, June 23-25 2014. c⃝2014 Association for Computational Linguistics Structured Learning for Taxonomy Induction with Belief Propagation Mohit Bansal TTI Chicago mbansal@ttic.edu David Burkett Twitter Inc. dburkett@twitter.com Gerard de Melo Tsinghua University gdm@demelo.org Dan Klein UC Berkeley klein@cs.berkeley.edu Abstract We present a structured learning approach to inducing hypernym taxonomies using a probabilistic graphical model formulation. Our model incorporates heterogeneous re- lational evidence about both hypernymy and siblinghood, captured by semantic features based on patterns and statistics from Web n-grams and Wikipedia ab- stracts. For efficient inference over tax- onomy structures, we use loopy belief propagation along with a directed span- ning tree algorithm for the core hyper- nymy factor. To train the system, we ex- tract sub-structures of WordNet and dis- criminatively learn to reproduce them, us- ing adaptive subgradient stochastic opti- mization. On the task of reproducing sub-hierarchies of WordNet, our approach achieves a 51% error reduction over a chance baseline, including a 15% error re- duction due to the non-hypernym-factored sibling features. On a comparison setup, we find up to 29% relative error reduction over previous work on ancestor F1. 1 Introduction Many tasks in natural language understanding, such as question answering, information extrac- tion, and textual entailment, benefit from lexical semantic information in the form of types and hy- pernyms. A recent example is IBM’s Jeopardy! system Watson (Ferrucci et al., 2010), which used type information to restrict the set of answer can- didates. Information of this sort is present in term taxonomies (e.g., Figure 1), ontologies, and the- sauri. However, currently available taxonomies such as WordNet are incomplete in coverage (Pen- nacchiotti and Pantel, 2006; Hovy et al., 2009), unavailable in many domains and languages, and vertebrate mammal placental cow rodent squirrel rat metatherian marsupial kangaroo reptile diapsid snake crocodilian anapsid chelonian turtle 1 Figure 1: An excerpt of WordNet’s vertebrates taxonomy. time-intensive to create or extend manually. There has thus been considerable interest in building lex- ical taxonomies automatically. In this work, we focus on the task of taking col- lections of terms as input and predicting a com- plete taxonomy structure over them as output. Our model takes a loglinear form and is represented using a factor graph that includes both 1st-order scoring factors on directed hypernymy edges (a parent and child in the taxonomy) and 2nd-order scoring factors on sibling edge pairs (pairs of hy- pernym edges with a shared parent), as well as in- corporating a global (directed spanning tree) struc- tural constraint. Inference for both learning and decoding uses structured loopy belief propagation (BP), incorporating standard spanning tree algo- rithms (Chu and Liu, 1965; Edmonds, 1967; Tutte, 1984). The belief propagation approach allows us to efficiently and effectively incorporate hetero- geneous relational evidence via hypernymy and siblinghood (e.g., coordination) cues, which we capture by semantic features based on simple sur- face patterns and statistics from Web n-grams and Wikipedia abstracts. We train our model to …

Content truncated to 500 words