Unsupervised Discovery of Generic Relationships Using Pattern Clusters and its Evaluation by Automatically Generated SAT Analogy Questions

Proceedings of ACL-08: HLT, pages 692–700, Columbus, Ohio, USA, June 2008. c⃝2008 Association for Computational Linguistics Unsupervised Discovery of Generic Relationships Using Pattern Clusters and its Evaluation by Automatically Generated SAT Analogy Questions Dmitry Davidov ICNC Hebrew University of Jerusalem dmitry@alice.nc.huji.ac.il Ari Rappoport Institute of Computer Science Hebrew University of Jerusalem arir@cs.huji.ac.il Abstract We present a novel framework for the dis- covery and representation of general semantic relationships that hold between lexical items. We propose that each such relationship can be identified with a cluster of patterns that cap- tures this relationship. We give a fully unsu- pervised algorithm for pattern cluster discov- ery, which searches, clusters and merges high- frequency words-based patterns around ran- domly selected hook words. Pattern clusters can be used to extract instances of the corre- sponding relationships. To assess the quality of discovered relationships, we use the pattern clusters to automatically generate SAT anal- ogy questions. We also compare to a set of known relationships, achieving very good re- sults in both methods. The evaluation (done in both English and Russian) substantiates the premise that our pattern clusters indeed reflect relationships perceived by humans. 1 Introduction Semantic resources can be very useful in many NLP tasks. Manual construction of such resources is la- bor intensive and susceptible to arbitrary human de- cisions. In addition, manually constructed semantic databases are not easily portable across text domains or languages. Hence, there is a need for developing semantic acquisition algorithms that are as unsuper- vised and language independent as possible. A fundamental type of semantic resource is that of concepts (represented by sets of lexical items) and their inter-relationships. While there is rel- atively good agreement as to what concepts are and which concepts should exist in a lexical re- source, identifying types of important lexical rela- tionships is a rather difficult task. Most established resources (e.g., WordNet) represent only the main and widely accepted relationships such as hyper- nymy and meronymy. However, there are many other useful relationships between concepts, such as noun-modifier and inter-verb relationships. Identi- fying and representing these explicitly can greatly assist various tasks and applications. There are al- ready applications that utilize such knowledge (e.g., (Tatu and Moldovan, 2005) for textual entailment). One of the leading methods in semantics acqui- sition is based on patterns (see e.g., (Hearst, 1992; Pantel and Pennacchiotti, 2006)). The standard pro- cess for pattern-based relation extraction is to start with hand-selected patterns or word pairs express- ing a particular relationship, and iteratively scan the corpus for co-appearances of word pairs in pat- terns and for patterns that contain known word pairs. This methodology is semi-supervised, requiring pre- specification of the desired relationship or hand- coding initial seed words or patterns. The method is quite successful, and examining its results in de- tail shows that concept relationships are often being manifested by several different patterns. In this paper, unlike the majority of studies that use patterns in order to find instances of given rela- tionships, we use sets of …

Content truncated to 500 words