Relation Mention Recognition Algorithm

A Relation Mention Recognition Algorithm is a Recognition Algorithm that can solve a Relation Mention Recognition Task.

• AKA: Relation Recognition Algorithm, Semantic Relation Mention Recognition Algorithm, Relation Extraction Algorithm, Relation Extraction from Text Algorithm.
• Context:
  • Input: a Text Corpus
    • Optionall a Recognition Model such as a Semantic Relation Description.
  • Output: an Annotated Corpus with Recognized Semantic Relation Mentions.
    • Optional Output: a Semantic Relation Recognizer.
  • It can support a Relation Mention Extraction Algorithm (as part of an Information Extraction Algorithm).
  • It can be composed of a Relation Mention Detection Algorithm and a Relation Mention Classification Algorithm.
  • It can range from
    • being a Simple Semantic Relation Recognition Algorithm
    • to being a Complex Semantic Relation Recognition Algorithm/Complex Relation Extraction Algorithm.
  • It can be:
    • a Pattern-Based Relation Mention Recognition Algorithm.
    • a Cluster-Based Relation Mention Recognition Algorithm.
  • It can be:
    • a Semi-Supervised Relation Mention Recognition Algorithm.
    • a Fully-Supervised Relation Mention Recognition Algorithm.
  • It can require Preprocessing tasks such as Chunking, Named Entity Recognition, Syntactic Parsing, Semantic Role Labeling
  • It can involve a Positive Sentence Harvesting phase.
  • Approaches include: Word-sequence Rule, Co-occurrence Pattern, Word-sequence Pattern, Syntactic Pattern.
  • It can be implemented into a Relation Mention Recognition System.
• Example(s):
  • TeGRR Algorithm, a Complex Semantic Relation Mention Recognition Algorithm.
  • Snowball Algorithm.
  • TextRunner Algorithm.
  • FASTUS
  • AutoSlog
  • BBN SIFT
  • DIPRE
  • (Bunescu & Mooney, 2005)
  • LEILA
  • Espresso Algorithm.
  • ZParser
  • iProLINK (http://pir.georgetown.edu/iprolink/)
  • PubGene (http://www.pubgene.org) There is no direct Co-Occurence for the gene and protein crcA to the exact keyword expression "localization" in MedLine abstracts
  • Protein-Protein Interaction Mention Recognition Algorithm.
  • Wrapper Induction Algorithm.
• Counter-Example(s):
  • a Concept Mention Recognition Algorithm, such as a Named Entity Recognition Algorithm.
  • a Relation Mention Identification Algorithm.
  • a Relation Mention Classification Algorithm.
  • a Relation Mention Grounding Algorithm.
  • a Information Extraction Algorithm,
• See: Sentence-level Analysis, Discourse-level Analysis.

References

• http://l2r.cs.uiuc.edu/~cogcomp/wpt.php?pr_key=NER

2009

• (Rajaraman & Ullman, 2009o) => Anand Rajaraman, and Jeffrey D. Ullman. (2009). "Relation Extraction. Stanford Course - CS345A, Winter 2009: Data Mining. 2/2-2/4

2008

• ?

2007

• (Busescu & Mooney, 2007) => Razvan C. Bunescu, and Raymond J. Mooney. (2007). "Learning to Extract Relations from the Web using Minimal Supervision." In: Proceedings of 2007 ACL Conference (ACL 2007).
• (Melli & al, 2007) => Gabor Melli, Martin Ester, Anoop Sarkar. (2007). "Recognition of Multi-sentence n-ary Subcellular Localization Mentions in Biomedical Abstracts." In: Proceedings of LBM-2007. ( presentation )
• (Banko & al, 2007) => M. Banko, M. J. Cafarella, S. Soderland, M. Broadhead, and Oren Etzioni. (2007). "Open Information Extraction from the Web." In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-2007).
• (NguyenMI, 2007) => Dat P.T. Nguyen, Yutaka Matsuo, and Mitsuru Ishizuka. (2007). "Relation Extraction from Wikipedia Using Subtree Mining." In: Proceedings of AAAI 2007.
• (Busescu and Mooney, 2007) => Razvan C. Bunescu and Raymond J. Mooney. (2007). "Learning to Extract Relations from the Web using Minimal Supervision." In: Proceedings of ACL-2007.
• (Bunescu and Mooney, 2007) => Razvan C. Bunescu and R. J. Mooney. (2007). "Extracting Relations from Text: From Word Sequences to Dependency Paths. In, Text Mining and Natural Language Processing, Anne Kao and Steve Poteet (eds.), pp. 29-44, Springer.
• (Fundel & al, 2007) => Katrin Fundel, R. Kuffner, and R. Zimmer. (2007). "RelEx--relation extraction using dependency parse trees. Bioinformatics. 2007 Feb 1;23(3):365-71.
  • "The simplest approach is the detection of co-occurrences of entities from within sentences or abstracts (Ding et al., 2002; Jelier et al., 2005; Jenssen et al., 2001). It relies on the hypothesis that entities which are repeatedly mentioned together are somehow related. Extracted relations exhibit high sensitivity but very low specificity. Generally, the type and direction of the relation cannot be determined."
  • "Pattern based extraction approaches (Blaschke et al., 1999; Blaschke and Valencia, 2001; Leroy and Chen, 2002; Ono et al., 2001) were set up to increase specificity, yet they achieve significantly lower recall."
  • "As an extension to standard relation extraction pipelines, we propose the use of dependency parse trees (Klein and Manning, 2002, 2003; Mel’cuk, 1988) as a means for biomedical relation extraction. Dependency parse trees reveal non-local dependencies within sentences, i.e. between words that are far apart in a sentence. Sentences of biomedical texts tend to be long and complicated and frequently mention a number of possible effectors and effectees. Dependency parse trees provide a useful structure for the sentences by annotating edges with dependency types, e.g. subject, auxiliary, modifier."
• (Jiang and Zhai, 2007) => J. Jiang and C. Zhai, (2007). "A Systematic Exploration of the Feature Space for Relation Extraction." In: Proceedings of NAACL/HLT-2007.

2006

• (Zhang & al, 2006b) => Min Zhang, Jie Zhang, and Jian Su. (2006). "Exploring Syntactic Features for Relation Extraction using a Convolution Tree Kernel." In: Proceedings of HLT Conference (HLT 2006).
• (HassanHN, 2006 => H. Hassan, A. Hassan and S. Noeman. (2006). "Graph Based Semi-Supervised Approach for Information Extraction." In: Proceedings of the Workshop on Graph-based methods for NLP at HLT/NAACL-2006.
• (Suchanek & al, 2006) => F. M. Suchanek, G. Ifrim and G. Weikum. (2006). "Combining Linguistic and Statistical Analysis to Extract Relations from Web Documents." In: Proceedings of KDD 2006.
• (Girju & al, 2006) => Roxana Girju, Adriana Badulescu, and Dan Moldovan. (2006). "Automatic Discovery of Whole-Part Relations." In: Computational Linguistics, 32(1). [doi>10.1162/coli.2006.32.1.83]
• (CulottaMB, 2006) => Aron Culotta, Andrew McCallum, and Jonathan Betz. (2006). "Integrating Probabilistic Extraction Models and Data Mining to Discover Relations and Patterns in Text." In: Proceedings of HLT-NAACL-2006.
  • Relation extraction is the task of discovering semantic connections between entities. In text, this usually amounts to examining pairs of entities in a document and determining (from local language cues) whether a relation exists between them. Common approaches to this problem include pattern matching (Brin, 1998; Agichtein and Gravano, 2000), kernel methods (Zelenko et al., 2003; Culotta and Sorensen, 2004; Bunescu and Mooney, 2006), logistic regression (Kambhatla, 2004), and augmented parsing (Miller et al., 2000).
• (Feldman & al, 2006) => Ronen Feldman, B. Rosenfeld, S. Soderland, and Oren Etzioni. (2006). "Self-Supervised Relation Extraction from the Web." In: Proceedings of ISMIS 2006.
• (Xia, 2006) => L. Xia. (2006). "Adaptive Relationship Extraction by Machine Learning. Masters Thesis, Sheffield University.
  • It reimplements Snowball and DIPRE.
• (Suchanek & al, 2006) => F. M. Suchanek and G. Ifrim and G. Weikum. (2006). "Combining Linguistic and Statistical Analysis to Extract Relations from Web Documents." In: Proceedings of KDD 2006. (paper.pdf)
• (Greenwood and Stevenson, 2006) => M. A. Greenwood and M. Stevenson. (2006). "Improving Semi-Supervised Acquisition of Relation Extraction Patterns." In: Proceedings of the Information Extraction Beyond The Document Workshop (COLING/ACL 2006). (paper.pdf)
• (Chakavarthy & al, 2006) => Venkatesan T. Chakaravarthy, H. Gupta, P. Roy, and M. Mohania. (2006). "Efficiently Linking Text Documents with Relevant Structured Information." In: Proceedings of VLDB, 2006.

2005

• (Gonzalez & al, 2005) => M. Gonzalez, V. L. S. de Lima and J. V. de Lima. (2005). "Binary Lexical Relations for Text Representation in Information Retrieval." In: Proceedings of 10th Int. Conf. on Applications of Natural Language to Information Systems (NLDB-2005). (website)
• (Harabagiu & al, 2005) => Sanda M. Harabagiu, C. A. Bejan and P. Morarescu. (2005). "Shallow Semantics for Relation Extraction." In: Proceedings of IJCAI-2005. (paper.pdf)
• (Bunescu & Mooney, 2005) =>Razvan C. Bunescu, and Raymond J. Mooney. (2005). "A Shortest Path Dependency Kernel for Relation Extraction." In: Proceedings of HLT/EMNLP-2005.
• (Moreda & al, 2005) => P. Moreda, B. Navarro and M. Palomar. (2005). "Using Semantic Roles in Information Retrieval Systems." In: Proceedings of 10th Int. Conf. on Applications of Natural Language to Information Systems (NLDB-2005). (website)
• (Harabagiu & al, 2005) => Sanda M. Harabagiu, C. A. Bejan and P. Morarescu. (2005). "Shallow Semantics for Relation Extraction." In: Proceedings of IJCAI-2005.
• (Zhao & Grishman, 2005) => Shubin Zhao, and Ralph Grishman. (2005). "Extracting Relations with Integrated Information Using Kernel Methods." In: Proceedings of ACL Conference (ACL 2005).
• (MPKWJW, 2005) => Ryan T. McDonald, Fernando C. N. Pereira, Seth Kulick, R. Scott Winters, Yang Jin, Peter S. White. (2005). "Simple Algorithms for Complex Relation Extraction with Applications to Biomedical IE. In ACL-2005.
• (Ramani & al, 2005) => A. K. Ramani, Razvan C. Bunescu, R. J. Mooney and E. M. Marcotte. (2005). "Consolidating the Set of Known Human Protein-Protein Interactions in Preparation for Large-Scale Mapping of the Human Interactome. Genome Biology , volume 6, number 5, r40.
• (Dong & al, 2005) => X. Dong, A. Halevy, and J. Madhavan. (2005). "Reference Reconciliation in Complex Information Spaces." In: Proceedings of SIGMOD, 2005.

2004

• (Rosenfeld & al, 2004) => B. Rosenfeld, Ronen Feldman, M. Fresko, J. Schler, and Y. Auman. (2004). "TEG - A Hybrid Approach to Information Extraction." In: Proceedings of the 2004 CIKM Conference (CIKM 2004).
• (Jijkoun & al, 2004) => Valentin Jijkoun, Jori Mur, and Maarten de Rijke. (2004). "Information extraction for question answering: Improving recall through syntactic patterns." In: Proceedings of COLING-2004.
• (Culotta and Sorensen, 2004) => Aron Culottaand J. S. Sorensen. (2004). "Dependency Tree Kernels for Relation Extraction." In: Proceedings ofACL 2004.

2003

• (ZelenkoAR, 2003) => D. Zelenko, C. Aone, and A. Richardella. (2003). "Kernel Methods for Relation Extraction. Journal of Machine Learning Research.
• (Arasu & Garcia-Molina, 2003) => A. Arasu, and [[Hector Garcia-Molina[[. (2003). "Extracting structured data from web pages." In: Proceedings of the 2003 ACM SIGMOD international conference (SIGMOD 2003). [doi>10.1145/872757.872799]

2001

• (Crescenzi & al, 2001) => Valter Crescenzi, Giansalvatore Mecca, Paolo Merialdo. (2001). "RoadRunner: Towards Automatic Data Extraction from Large Web Sites. In: 27th International Conference on Very Large Databases (VLDB 2001).
  • Road Runner Project.

2000

• (Agichtein and Gravano, 2000) => Eugene Agichtein and L. Gravano. (2000). ??
• (McCallum & al, 2000) => Andrew McCallum, K. Nigam, J. Rennie, and K. Seymore. (2000). "Automating the construction of internet portals with machine learning." In: Information Retrieval Journal.
• (Kushmerick, 2000) => Nicholas Kushmerick. (2000). "Wrapper induction: Efficiency and Expressiveness. In: Artificial Intelligence 118(1-2).

1999

• (Soderland, 1999) => Steven Soderland. (1999). "Learning Information Extraction Rules for Semi-Structured and Free Text.//" In: Machine learning. ** [[Wrapper Induction Algorithm, Relation Mention Pattern.

1998

• Dayne Freitag. (1998). "Information Extraction from HTML: Application of a general learning approach. Proceedings of the Fifteenth Conference on Artificial Intelligence (AAAI/IAAI 1998).
  • Wrapper Induction Algorithm, Relation Mention Pattern.
• (Giles & al, 1998) => C. L. Giles, K. Bollacker, and S. Lawrence. (1998). CiteSeer: An automatic citation indexing system. The Third ACM Conference on Digital Libraries. http://citeseer.ist.psu.edu/giles98citeseer.html
• (Craven & al, 1998) => M. Craven, D. DiPasquo, Dayne Freitag, Andrew McCallum, Tom M. Mitchell, K. Nigam, and S. Slattery. (1998). Learning to extract symbolic knowledge from the world wide web. In: Proceedings of AAAI-98.
• (Brin, 1998) => S. Brin. (1998). "Extracting patterns and relations from the World-Wide Web." In: Proceedings of on the 1998 International Workshop on Web and Databases (WebDB’98).
  • DIPRE Algorithm.

1997

• (Khoo, 1997) => C. Khoo. 1997. The Use of Relation Matching in Information Retrieval. LIBRES: Library and Information Science Research Electronic Journal, 7(2). (paper.html)
• (Kushmerick, 1995) => Nicholas Kushmerick, D. S. Weld, and R. B. Doorenhos. (1997). "Wrapper Induction for Information Extraction.]" In: Intl. Joint Conference on Artificial Intelligence (IJCAI 1997).
  • Use of Wrapper Algorithm with induction
  • Wrapper Induction Algorithm, Relation Mention Pattern.
• (Leek, 1997) => T. R. Leek. (1997). Information Extraction using Hidden Markov Models. Master's thesis, UC San Diego. http://citeseer.ist.psu.edu/leek97information.html
  • Application of Hidden Markov Models
• (Soderland, 1997) => Stephen Soderland. (1997). "Learning to extract Text Based information from the World Wide Web." In: ...?

1996

• (Michell & al, 1996) => Tom Mitchell, ...
  • WebKB

1995

• (Soderland & al, 1995) => Stephen Soderland, David Fisher, Jonathan Aseltine, and Wendy Lehnert. (1995). "CRYSTAL: Inducing a Conceptual Dictionary." In: Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence.

1993

• (Riloff, 1993) => Ellen Riloff. (1993). "Automatically Constructing a Dictionary for Information Extraction Tasks." In: Proceedings of the 11th Ann. Conference of Artificial Intelligence (AAAI 1993).

1992

• (Hearst, 1992) => Marti Hearst. (1992). "Automatic Acquisition of Hyponyms from Large Text Corpora." In: Proceedings of the 14th International Conference on Computational Linguistics (COLING-1992).(paper.pdf)

1991

• (Rau, 1991) => L. Rau. (1991). "Extracting Company Names From Text." In: Proceedings of the Sixth Conference on Artificial Intelligence Applications.

1982

• De Jong (1982)
  • FRUMP system filled in Schank-style “scripts” from newswires; DARPA’s Message Understanding Conference (MUC) [87’-95’], and TIPSTER [92’-96’]

Notes

• Early start was on news feeds and programed rules (e.g. FSM)
  • E.g. De Jong’s FRUMP [1982] that filled in Schank-style “scripts” from newswires; DARPA’s Message Understanding Conference (MUC) [87’-95’], and TIPSTER [92’-96’]
  • E.g. The finite state machines of SRI’s FASTUS
  • HMM’s in Elkan [Leek 1997]
  • BBN in [Bikel, et al, 1998]