A Metric-based Framework for Automatic Taxonomy Induction

Proceedings of the 47th Annual Meeting of the ACL and the 4th IJCNLP of the AFNLP, pages 271–279, Suntec, Singapore, 2-7 August 2009. c⃝2009 ACL and AFNLP A Metric-based Framework for Automatic Taxonomy Induction Hui Yang Language Technologies Institute School of Computer Science Carnegie Mellon University huiyang@cs.cmu.edu Jamie Callan Language Technologies Institute School of Computer Science Carnegie Mellon University callan@cs.cmu.edu Abstract This paper presents a novel metric-based framework for the task of automatic taxonomy induction. The framework incrementally clus- ters terms based on ontology metric, a score indicating semantic distance; and transforms the task into a multi-criteria optimization based on minimization of taxonomy structures and modeling of term abstractness. It com- bines the strengths of both lexico-syntactic patterns and clustering through incorporating heterogeneous features. The flexible design of the framework allows a further study on which features are the best for the task under various conditions. The experiments not only show that our system achieves higher F1-measure than other state-of-the-art systems, but also re- veal the interaction between features and vari- ous types of relations, as well as the interac- tion between features and term abstractness. 1 Introduction Automatic taxonomy induction is an important task in the fields of Natural Language Processing, Knowledge Management, and Se- mantic Web. It has been receiving increasing attention because semantic taxonomies, such as WordNet (Fellbaum, 1998), play an important role in solving knowledge-rich problems, includ- ing question answering (Harabagiu et al., 2003) and textual entailment (Geffet and Dagan, 2005). Nevertheless, most existing taxonomies are ma- nually created at great cost. These taxonomies are rarely complete; it is difficult to include new terms in them from emerging or rapidly changing domains. Moreover, manual taxonomy construc- tion is time-consuming, which may make it un- feasible for specialized domains and personalized tasks. Automatic taxonomy induction is a solu- tion to augment existing resources and to pro- duce new taxonomies for such domains and tasks. Automatic taxonomy induction can be decom- posed into two subtasks: term extraction and re- lation formation. Since term extraction is rela- tively easy, relation formation becomes the focus of most research on automatic taxonomy induc- tion. In this paper, we also assume that terms in a taxonomy are given and concentrate on the sub- task of relation formation. Existing work on automatic taxonomy induc- tion has been conducted under a variety of names, such as ontology learning, semantic class learning, semantic relation classification, and relation extraction. The approaches fall into two main categories: pattern-based and clustering- based. Pattern-based approaches define lexical- syntactic patterns for relations, and use these pat- terns to discover instances of relations. Cluster- ing-based approaches hierarchically cluster terms based on similarities of their meanings usually represented by a vector of quantifiable features. Pattern-based approaches are known for their high accuracy in recognizing instances of rela- tions if the patterns are carefully chosen, either manually (Berland and Charniak, 1999; Kozare- va et al., 2008) or via automatic bootstrapping (Hearst, 1992; Widdows and Dorow, 2002; Girju et al., 2003). The approaches, however, …

Content truncated to 500 words