Taxonomy Induction Using Hierarchical Random Graphs

2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 466–476, Montr´eal, Canada, June 3-8, 2012. c⃝2012 Association for Computational Linguistics Taxonomy Induction Using Hierarchical Random Graphs Trevor Fountain and Mirella Lapata Institute for Language, Cognition and Computation School of Informatics, University of Edinburgh 10 Crichton Street, Edinburgh EH8 9AB t.fountain@sms.ed.ac.uk, mlap@inf.ed.ac.uk Abstract This paper presents a novel approach for in- ducing lexical taxonomies automatically from text. We recast the learning problem as that of inferring a hierarchy from a graph whose nodes represent taxonomic terms and edges their degree of relatedness. Our model takes this graph representation as input and fits a taxonomy to it via combination of a maximum likelihood approach with a Monte Carlo Sampling algorithm. Essentially, the method works by sampling hierarchical struc- tures with probability proportional to the like- lihood with which they produce the input graph. We use our model to infer a taxonomy over 541 nouns and show that it outperforms popular flat and hierarchical clustering algo- rithms. 1 Introduction The semantic knowledge encoded in lexical re- sources such as WordNet (Fellbaum, 1998) has been proven beneficial for several applications including question answering (Harabgiu et al., 2003), doc- ument classification (Hung et al., 2004), and tex- tual entailment (Geffet and Dagan, 2005). As the effort involved in creating such resources manu- ally is prohibitive (cost, consistency and coverage are often cited problems) and has to be repeated for new languages or domains, recent years have seen increased interest in automatic taxonomy in- duction. The task has assumed several guises, such as term extraction — finding the concepts of the taxonomy (Kozareva et al., 2008; Navigli et al., 2011), term relation discovery — learning whether any two terms stand in an semantic relation such as IS-A, or PART-OF (Hearst, 1992; Berland and Char- niak, 1999), and taxonomy construction —- creat- ing the taxonomy proper by organizing its terms hi- erarchically (Kozareva and Hovy, 2010; Navigli et al., 2011). Previous work has also focused on the complementary task of augmenting an existing tax- onomy with missing information (Snow et al., 2006; Yang and Callan, 2009). In this paper we propose an unsupervised ap- proach to taxonomy induction. Given a corpus and a set of terms, our algorithm jointly induces their re- lations and their taxonomic organization. We view taxonomy learning as an instance of the problem of inferring a hierarchy from a network or graph. We create this graph from unstructured text simply by drawing an edge between distributionally sim- ilar terms. Next, we fit a Hierarchical Random Graph model (HRG; Clauset et al. (2008)) to the observed graph data based on maximum likelihood methods and Markov chain Monte Carlo sampling. The model essentially works by sampling hierarchi- cal structures with probability proportional to the likelihood with which they produce the input graph. This is advantageous as it allows us to consider the ensemble of random graphs that are statistically sim- ilar to the original graph, and through …

Content truncated to 500 words