Simple algorithms for complex relation extraction with applications to biomedical IE

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 biomedical text.

References

1. A. L. Berger, S. A. Della Pietra, and V. J. Della Pietra. 1996. A maximum entropy approach to natural language processing. Computational Linguistics, 22(1).
2. D. M. Bikel, R. Schwartz, and R. M. Weischedel. 1999. An algorithm that learns what's in a name. Machine Learning Journal Special Issue on Natural Language Learning, 34(1/3):221--231.
3. C. Bron and J. Kerbosch. 1973. Algorithm 457: finding all cliques of an undirected graph. Communications of the ACM, 16(9):575--577.
4. N. Collier, C. Nobata, and J. Tsujii. 2000. Extracting the names of genes and gene products with a hidden Markov model. In Proc. COLING.
5. D. Gildea and D. Jurafsky. 2002. Automatic labeling of semantic roles. Computational Linguistics.
6. Taku Kudo and Yuji Matsumoto. 2001. Chunking with support vector machines. In Proc. NAACL.
7. J. Lafferty, A. McCallum, and F. Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proc. ICML.
8. A. McCallum and B. Wellner. 2003. Toward conditional models of identity uncertainty with application to proper noun coreference. In IJCAI Workshop on Information Integration on the Web.
9. A. McCallum, D. Freitag, and F. Pereira. 2000. Maximum entropy Markov models for information extraction and segmentation. In Proc. ICML.
10. A. K. McCallum. 2002. MALLET: A machine learning for language toolkit.
11. D. M. McDonald, H. Chen, H. Su, and B. B. Marshall. 2004a. Extracting gene pathway relations using a hybrid grammar: the Arizona Relation Parser. Bioinformatics, 20(18):3370--78.
12. R. T. McDonald, R. S. Winters, M. Mandel, Y. Jin, P. S. White, and F. Pereira. 2004b. An entity tagger for recognizing acquired genomic variations in cancer literature. Bioinformatics, 20(17):3249--3251.
13. S. Miller, H. Fox, L. A. Ramshaw, and R. M. Weischedel. 2000. A novel use of statistical parsing to extract information from text. In Proc. NAACL.
14. V. Punyakanok, D. Roth, W. Yih, and D. Zimak. 2004. Learning via inference over structurally constrained output. In Workshop on Learning Structured with Output, NIPS.
15. Barbara Rosario and Marti A. Hearst. 2004. Classifying semantic relations in bioscience texts. In ACL.
16. D. Roth and W. Yih. 2004. A linear programming formulation for global inference in natural language tasks. In Proc. CoNLL.
17. D. Zelenko, C. Aone, and A. Richardella. 2003. Kernel methods for relation extraction. JMLR.

• Computing methodologies

  • Artificial intelligence

• Hardware

  • Power and energy

    • Power estimation and optimization