Simple Algorithms for Complex Relation Extraction with Applications to Biomedical IE

Proceedings of the 43rd Annual Meeting of the ACL, pages 491–498, Ann Arbor, June 2005. c⃝2005 Association for Computational Linguistics Simple Algorithms for Complex Relation Extraction with Applications to Biomedical IE Ryan McDonald1 Fernando Pereira1 Seth Kulick2 1CIS and 2IRCS, University of Pennsylvania, Philadelphia, PA {ryantm,pereira}@cis.upenn.edu, skulick@linc.cis.upenn.edu Scott Winters Yang Jin Pete White Division of Oncology, Children’s Hospital of Pennsylvania, Philadelphia, PA {winters,jin,white}@genome.chop.edu Abstract A complex relation is any n-ary relation in which some of the arguments may be be unspecified. We present here a simple two-stage method for extracting complex relations between named entities in text. The first stage creates a graph from pairs of entities that are likely to be related, and the second stage scores maximal cliques in that graph as potential complex relation instances. We evaluate the new method against a standard baseline for extracting genomic variation relations from biomed- ical text. 1 Introduction Most research on text information extraction (IE) has focused on accurate tagging of named entities. Successful early named-entity taggers were based on finite-state generative models (Bikel et al., 1999). More recently, discriminatively-trained models have been shown to be more accurate than generative models (McCallum et al., 2000; Lafferty et al., 2001; Kudo and Matsumoto, 2001). Both kinds of mod- els have been developed for tagging entities such as people, places and organizations in news mate- rial. However, the rapid development of bioinfor- matics has recently generated interest on the extrac- tion of biological entities such as genes (Collier et al., 2000) and genomic variations (McDonald et al., 2004b) from biomedical literature. The next logical step for IE is to begin to develop methods for extracting meaningful relations involv- ing named entities. Such relations would be ex- tremely useful in applications like question answer- ing, automatic database generation, and intelligent document searching and indexing. Though not as well studied as entity extraction, relation extraction has still seen a significant amount of work. We dis- cuss some previous approaches at greater length in Section 2. Most relation extraction systems focus on the spe- cific problem of extracting binary relations, such as the employee of relation or protein-protein in- teraction relation. Very little work has been done in recognizing and extracting more complex rela- tions. We define a complex relation as any n-ary relation among n typed entities. The relation is defined by the schema (t1, . . . , tn) where ti ∈ T are entity types. An instance (or tuple) in the rela- tion is a list of entities (e1, . . . , en) such that either type(ei) = ti, or ei =⊥ indicating that the ith ele- ment of the tuple is missing. For example, assume that the entity types are T = {person, job, company} and we are interested in the ternary relation with schema (person, job, company) that relates a person to their job at a particular company. For the sentence “John Smith is the CEO at Inc. Corp.”, the system would ideally extract the tu- ple (John Smith, …

Content truncated to 500 words