Comparing Constraints for Taxonomic Organization

Proceedings of NAACL-HLT 2018, pages 323–333 New Orleans, Louisiana, June 1 - 6, 2018. c⃝2018 Association for Computational Linguistics Comparing Constraints for Taxonomic Organization Anne Cocos∗, Marianna Apidianaki∗†, and Chris Callison-Burch∗ ∗ Department of Computer and Information Science, University of Pennsylvania † LIMSI, CNRS, Universit´e Paris-Saclay, 91403 Orsay {acocos,marapi,ccb}@seas.upenn.edu Abstract Building a taxonomy from the ground up in- volves several sub-tasks: selecting terms to in- clude, predicting semantic relations between terms, and selecting a subset of relational in- stances to keep, given constraints on the tax- onomy graph. Methods for this final step – taxonomic organization – vary both in terms of the constraints they impose, and whether they enable discovery of synonymous terms. It is hard to isolate the impact of these factors on the quality of the resulting taxonomy because organization methods are rarely compared di- rectly. In this paper, we present a head-to-head comparison of six taxonomic organization al- gorithms that vary with respect to their struc- tural and transitivity constraints, and treatment of synonymy. We find that while transitive algorithms out-perform their non-transitive counterparts, the top-performing transitive al- gorithm is prohibitively slow for taxonomies with as few as 50 entities. We propose a simple modification to a non-transitive opti- mum branching algorithm to explicitly incor- porate synonymy, resulting in a method that is substantially faster than the best transitive al- gorithm while giving complementary perfor- mance. 1 Introduction Many words and phrases fit within a natural se- mantic hierarchy: a mobile is a type of telephone, which in turn is a communications device and an object. Taxonomies, which encode this knowl- edge, are important resources for natural language understanding systems. There is ongoing interest in developing methods to build taxonomic resources automatically (Bor- dea et al., 2015, 2016). Although several widely- used general ontologies (e.g. WordNet (Miller, 1995)) and domain-specific ontologies (e.g. Uni- fied Medical Language System (UMLS) (Boden- Taxonomic Organization Common Initialization Entity Extraction Relation Prediction NOCYC NOCYC+CLUS DMST DMST+CLUS MAXTRANSGRAPH MAXTRANSFOREST bus vehicle trainer car person bus vehicle person car trainer a) b) Figure 1: In this study we compare algorithms for tax- onomic organization. We first (a) run entity extraction and pairwise relation prediction as a common initial- ization; we then (b) feed the resulting graphs as identi- cal input to six taxonomic organization algorithms. We evaluate the impact of varied structural constraints be- tween algorithms. reider, 2004)) exist, these resources are hand- crafted and therefore expensive to update or ex- pand. Automatic taxonomy induction enables the construction of taxonomic resources at scale in new languages and domains. Further, there is evi- dence that it is useful to build dynamic or context- specific taxonomies extemporaneously for some applications (Do and Roth, 2010). 323 Taxonomy induction involves three sub-tasks: entity extraction, relation prediction, and taxo- nomic organization. In many cases these subtasks are undertaken sequentially to build a taxonomy from the ground up. While many works directly compare methods for relation prediction (e.g. Tur- ney and Mohammad (2015), Shwartz et al. (2017) and others), …

Content truncated to 500 words