{'fraction_non_alphanumeric': 0.02690189191346691, 'fraction_numerical': 0.009539394907000879, 'mean_word_length': 4.909198113207547, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Exploiting Shallow Linguistic Information for Relation Extraction from Biomedical Literature

We propose an approach for extracting relations between entities from biomedical literature based solely on shallow linguistic information. We use a combination of kernel functions to integrate two different information sources: (i) the whole sentence where the relation appears, and (ii) the local contexts around the interacting entities. We performed experiments on extracting gene and protein interactions from two different data sets. The results show that our approach outperforms most of the previous methods based on syntactic and semantic information.


Introduction
Information Extraction (IE) is the process of finding relevant entities and their relationships within textual documents. Applications of IE range from Semantic Web to Bioinformatics. For example, there is an increasing interest in automatically extracting relevant information from biomedical literature. Recent evaluation campaigns on bio-entity recognition, such as BioCreAtIvE and JNLPBA 2004 shared task, have shown that several systems are able to achieve good performance (even if it is a bit worse than that reported on news articles). However, relation identification is more useful from an applicative perspective but it is still a considerable challenge for automatic tools.
In this work, we propose a supervised machine learning approach to relation extraction which is applicable even when (deep) linguistic processing is not available or reliable. In particular, we explore a kernel-based approach based solely on shallow linguistic processing, such as tokeniza-tion, sentence splitting, Part-of-Speech (PoS) tagging and lemmatization.
Kernel methods (Shawe-Taylor and Cristianini, 2004) show their full potential when an explicit computation of the feature map becomes computationally infeasible, due to the high or even infinite dimension of the feature space. For this reason, kernels have been recently used to develop innovative approaches to relation extraction based on syntactic information, in which the examples preserve their original representations (i.e. parse trees) and are compared by the kernel function (Zelenko et al., 2003;Culotta and Sorensen, 2004;Zhao and Grishman, 2005).
Despite the positive results obtained exploiting syntactic information, we claim that there is still room for improvement relying exclusively on shallow linguistic information for two main reasons. First of all, previous comparative evaluations put more stress on the deep linguistic approaches and did not put as much effort on developing effective methods based on shallow linguistic information. A second reason concerns the fact that syntactic parsing is not always robust enough to deal with real-world sentences. This may prevent approaches based on syntactic features from producing any result. Another related issue concerns the fact that parsers are available only for few languages and may not produce reliable results when used on domain specific texts (as is the case of the biomedical literature). For example, most of the participants at the Learning Language in Logic (LLL) challenge on Genic Interaction Extraction (see Section 4.2) were unable to successfully exploit linguistic information provided by parsers. It is still an open issue whether the use of domainspecific treebanks (such as the Genia treebank 1 ) can be successfully exploited to overcome this problem. Therefore it is essential to better investigate the potential of approaches based exclusively on simple linguistic features.
In our approach we use a combination of kernel functions to represent two distinct information sources: the global context where entities appear and their local contexts. The whole sentence where the entities appear (global context) is used to discover the presence of a relation between two entities, similarly to what was done by Bunescu and Mooney (2005b). Windows of limited size around the entities (local contexts) provide useful clues to identify the roles of the entities within a relation. The approach has some resemblance with what was proposed by Roth and Yih (2002). The main difference is that we perform the extraction task in a single step via a combined kernel, while they used two separate classifiers to identify entities and relations and their output is later combined with a probabilistic global inference.
We evaluated our relation extraction algorithm on two biomedical data sets (i.e. the AImed corpus and the LLL challenge data set; see Section 4). The motivations for using these benchmarks derive from the increasing applicative interest in tools able to extract relations between relevant entities in biomedical texts and, consequently, from the growing availability of annotated data sets. The experiments show clearly that our approach consistently improves previous results. Surprisingly, it outperforms most of the systems based on syntactic or semantic information, even when this information is manually annotated (i.e. the LLL challenge).

Problem Formalization
The problem considered here is that of identifying interactions between genes and proteins from biomedical literature. More specifically, we performed experiments on two slightly different benchmark data sets (see Section 4 for a detailed description). In the former (AImed) gene/protein interactions are annotated without distinguishing the type and roles of the two interacting entities. The latter (LLL challenge) is more realistic (and complex) because it also aims at identifying the roles played by the interacting entities (agent and target). For example, in Figure 1 three entities are mentioned and two of the six ordered pairs of GENIA/topics/Corpus/GTB.html entities actually interact: (sigma(K), cwlH) and (gerE, cwlH).
Figure 1: A sentence with two relations, R 12 and R 32 , between three entities, E 1 , E 2 and E 3 .
In our approach we cast relation extraction as a classification problem, in which examples are generated from sentences as follows.
First of all, we describe the complex case, namely the protein/gene interactions (LLL challenge). For this data set entity recognition is performed using a dictionary of protein and gene names in which the type of the entities is unknown.
We generate examples for all the sentences containing at least two entities. Thus the number of examples generated for each sentence is given by the combinations of distinct entities (N ) selected two at a time, i.e. N C 2 . For example, as the sentence shown in Figure 1 contains three entities, the total number of examples generated is 3 C 2 = 3. In each example we assign the attribute CANDIDATE to each of the candidate interacting entities, while the other entities in the example are assigned the attribute OTHER, meaning that they do not participate in the relation. If a relation holds between the two candidate interacting entities the example is labeled 1 or 2 (according to the roles of the interacting entities, agent and target, i.e. to the direction of the relation); 0 otherwise. Figure   Note that in generating the examples from the sentence in Figure 1 we did not create three neg-ative examples (there are six potential ordered relations between three entities), thereby implicitly under-sampling the data set. This allows us to make the classification task simpler without loosing information. As a matter of fact, generating examples for each ordered pair of entities would produce two subsets of the same size containing similar examples (differing only for the attributes CANDIDATE and OTHER), but with different classification labels. Furthermore, under-sampling allows us to halve the data set size and reduce the data skewness.
For the protein-protein interaction task (AImed) we use the correct entities provided by the manual annotation. As said at the beginning of this section, this task is simpler than the LLL challenge because there is no distinction between types (all entities are proteins) and roles (the relation is symmetric). As a consequence, the examples are generated as described above with the following difference: an example is labeled 1 if a relation holds between the two candidate interacting entities; 0 otherwise.

Kernel Methods for Relation Extraction
The basic idea behind kernel methods is to embed the input data into a suitable feature space F via a mapping function φ : X → F, and then use a linear algorithm for discovering nonlinear patterns. Instead of using the explicit mapping φ, we can use a kernel function K : X × X → R, that corresponds to the inner product in a feature space which is, in general, different from the input space. Kernel methods allow us to design a modular system, in which the kernel function acts as an interface between the data and the learning algorithm. Thus the kernel function is the only domain specific module of the system, while the learning algorithm is a general purpose component. Potentially any kernel function can work with any kernel-based algorithm. In our approach we use Support Vector Machines (Vapnik, 1998).
In order to implement the approach based on shallow linguistic information we employed a linear combination of kernels. Different works (Gliozzo et al., 2005;Zhao and Grishman, 2005;Culotta and Sorensen, 2004) empirically demonstrate the effectiveness of combining kernels in this way, showing that the combined kernel always improves the performance of the individual ones.
In addition, this formulation allows us to evaluate the individual contribution of each information source. We designed two families of kernels: Global Context kernels and Local Context kernels, in which each single kernel is explicitly calculated as follows where φ(·) is the embedding vector and · is the 2-norm. The kernel is normalized (divided) by the product of the norms of embedding vectors. The normalization factor plays an important role in allowing us to integrate information from heterogeneous feature spaces. Even though the resulting feature space has high dimensionality, an efficient computation of Equation 1 can be carried out explicitly since the input representations defined below are extremely sparse.

Global Context Kernel
In (Bunescu and Mooney, 2005b), the authors observed that a relation between two entities is generally expressed using only words that appear simultaneously in one of the following three patterns: Our global context kernels operate on the patterns above, where each pattern is represented using a bag-of-words instead of sparse subsequences of words, PoS tags, entity and chunk types, or Word-Net synsets as in (Bunescu and Mooney, 2005b). More formally, given a relation example R, we represent a pattern P as a row vector where the function tf (t i , P ) records how many times a particular token t i is used in P . Note that, this approach differs from the standard bag-ofwords as punctuation and stop words are included in φ P , while the entities (with attribute CANDI-DATE and OTHER) are not. To improve the classification performance, we have further extended φ P to embed n-grams of (contiguous) tokens (up to n = 3). By substituting φ P into Equation 1, we obtain the n-gram kernel K n , which counts common uni-grams, bi-grams, . . . , n-grams that two patterns have in common 2 . The Global Context kernel K GC (R 1 , R 2 ) is then defined as where K F B , K B and K BA are n-gram kernels that operate on the Fore-Between, Between and Between-After patterns respectively.

Local Context Kernel
The type of the candidate interacting entities can provide useful clues for detecting the agent and target of the relation, as well as the presence of the relation itself. As the type is not known, we use the information provided by the two local contexts of the candidate interacting entities, called left and right local context respectively. As typically done in entity recognition, we represent each local context by using the following basic features: Token The token itself. Lemma The lemma of the token. PoS The PoS tag of the token. Orthographic This feature maps each token into equivalence classes that encode attributes such as capitalization, punctuation, numerals and so on.
Formally, given a relation example R, a local context L = t −w , . . . , t −1 , t 0 , t +1 , . . . , t +w is represented as a row vector where f i is a feature function that returns 1 if it is active in the specified position of L, 0 otherwise 3 . The Local Context kernel K LC (R 1 , R 2 ) is defined as where K lef t and K right are defined by substituting the embedding of the left and right local context into Equation 1 respectively. 2 In the literature, it is also called n-spectrum kernel. 3 In the reported experiments, we used a context window of ±2 tokens around the candidate entity.
Notice that K LC differs substantially from K GC as it considers the ordering of the tokens and the feature space is enriched with PoS, lemma and orthographic features.

Shallow Linguistic Kernel
Finally, the Shallow Linguistic kernel It follows directly from the explicit construction of the feature space and from closure properties of kernels that K SL is a valid kernel.

Data sets
The two data sets used for the experiments concern the same domain (i.e. gene/protein interactions). However, they present a crucial difference which makes it worthwhile to show the experimental results on both of them. In one case (AImed) interactions are considered symmetric, while in the other (LLL challenge) agents and targets of genic interactions have to be identified.

AImed corpus
The first data set used in the experiments is the AImed corpus 4 , previously used for training protein interaction extraction systems in (Bunescu et al., 2005;Bunescu and Mooney, 2005b). It consists of 225 Medline abstracts: 200 are known to describe interactions between human proteins, while the other 25 do not refer to any interaction. There are 4,084 protein references and around 1,000 tagged interactions in this data set. In this data set there is no distinction between genes and proteins and the relations are symmetric.

LLL Challenge
This data set was used in the Learning Language in Logic (LLL) challenge on Genic Interaction extraction 5 (Nedéllec, 2005). The objective of the challenge was to evaluate the performance of systems based on machine learning techniques to identify gene/protein interactions and their roles, agent or target. The data set was collected by querying Medline on Bacillus subtilis transcription and sporulation. It is divided in a training set (80 sentences describing 271 interactions) and a test set (87 sentences describing 106 interactions). Differently from the training set, the test set contains sentences without interactions. The data set is decomposed in two subsets of increasing difficulty. The first subset does not include coreferences, while the second one includes simple cases of coreference, mainly appositions. Both subsets are available with different kinds of annotation: basic and enriched. The former includes word and sentence segmentation. The latter also includes manually checked information, such as lemma and syntactic dependencies. A dictionary of named entities (including typographical variants and synonyms) is associated to the data set.

Experiments
Before describing the results of the experiments, a note concerning the evaluation methodology.
There are different ways of evaluating performance in extracting information, as noted in (Lavelli et al., 2004) for the extraction of slot fillers in the Seminar Announcement and the Job Posting data sets. Adapting the proposed classification to relation extraction, the following two cases can be identified: • One Answer per Occurrence in the Document -OAOD (each individual occurrence of a protein interaction has to be extracted from the document); • One Answer per Relation in a given Document -OARD (where two occurrences of the same protein interaction are considered one correct answer). Figure 3 shows a fragment of tagged text drawn from the AImed corpus. It contains three different interactions between pairs of proteins, for a total of seven occurrences of interactions. For example, there are three occurrences of the interaction between IGF-IR and p52Shc (i.e. number 1, 3 and 7). If we adopt the OAOD methodology, all the seven occurrences have to be extracted to achieve the maximum score. On the other hand, if we use the OARD methodology, only one occurrence for each interaction has to be extracted to maximize the score.
On the AImed data set both evaluations were performed, while on the LLL challenge only the OAOD evaluation methodology was performed because this is the only one provided by the evaluation server of the challenge.

Implementation Details
All the experiments were performed using the SVM package LIBSVM 6 customized to embed our own kernel. For the LLL challenge submission, we optimized the regularization parameter C by 10-fold cross validation; while we used its default value for the AImed experiment. In both experiments, we set the cost-factor W i to be the ratio between the number of negative and positive examples.

Results on AImed
K SL performance was first evaluated on the AImed data set (Section 4.1). We first give an evaluation of the kernel combination and then we compare our results with the Subsequence Kernel for Relation Extraction (ERK) described in (Bunescu and Mooney, 2005b). All experiments are conducted using 10-fold cross validation on the same data splitting used in (Bunescu et al., 2005;Bunescu and Mooney, 2005b). Table 1 shows the performance of the three kernels defined in Section 3 for protein-protein interactions using the two evaluation methodologies described above.
We report in Figure 4 the precision-recall curves of ERK and K SL using OARD evaluation methodology (the evaluation performed by Bunescu and Mooney (2005b)). As in (Bunescu et al., 2005;Bunescu and Mooney, 2005b), the graph points are obtained by varying the threshold on the classifi-  Table 1: Performance on the AImed data set using the two evaluation methodologies, OAOD and OARD.
cation confidence 7 . The results clearly show that K SL outperforms ERK, especially in term of recall (see Table 1). Finally, Figure 5 shows the learning curve of the combined kernel K SL using the OARD evaluation methodology. The curve reaches a plateau with around 100 Medline abstracts.

Results on LLL challenge
The system was evaluated on the "basic" version of the LLL challenge data set (Section 4.2). Table 2 shows the results of K SL returned by the scoring service 8 for the three subsets of the training set (with and without coreferences, and with their union). Table 3 shows the best results obtained at the official competition performed in April 2005. Comparing the results we see that K SL trained on each subset outperforms the best 7 For this purpose the probability estimate output of LIB-SVM is used. 8 http://genome.jouy.inra.fr/texte/ LLLchallenge/scoringService.php   systems of the LLL challenge 9 . Notice that the best results at the challenge were obtained by different groups and exploiting the linguistic "enriched" version of the data set. As observed in (Nedéllec, 2005), the scores obtained using the training set without coreferences and the whole training set are similar. We also report in Table 4 an analysis of the kernel combination. Given that we are interested here in the contribution of each kernel, we evaluated the experiments by 10-fold cross-validation on the whole training set avoiding the submission process.

Discussion of Results
The experimental results show that the combined kernel K SL outperforms the basic kernels K GC and K LC on both data sets. In particular, precision significantly increases at the expense of a lower recall. High precision is particularly advantageous when extracting knowledge from large corpora, because it avoids overloading end users with too many false positives.
Although the basic kernels were designed to model complementary aspects of the task (i.e.   presence of the relation and roles of the interacting entities), they perform reasonably well even when considered separately. In particular, K GC achieved good performance on both data sets. This result was not expected on the LLL challenge because this task requires not only to recognize the presence of relationships between entities but also to identify their roles. On the other hand, the outcomes of K LC on the AImed data set show that such kernel helps to identify the presence of relationships as well.
At first glance, it may seem strange that K GC outperforms ERK on AImed, as the latter approach exploits a richer representation: sparse sub-sequences of words, PoS tags, entity and chunk types, or WordNet synsets. However, an approach based on n-grams is sufficient to identify the presence of a relationship. This result sounds less surprising, if we recall that both approaches cast the relation extraction problem as a text categorization task. Approaches to text categorization based on rich linguistic information have obtained less accuracy than the traditional bag-of-words approach (e.g. (Koster and Seutter, 2003)). Shallow linguistics information seems to be more effective to model the local context of the entities.
Finally, we obtained worse results performing dimensionality reduction either based on generic linguistic assumptions (e.g. by removing words from stop lists or with certain PoS tags) or using statistical methods (e.g. tf.idf weighting schema). This may be explained by the fact that, in tasks like entity recognition and relation extraction, useful clues are also provided by high frequency tokens, such as stop words or punctuation marks, and by the relative positions in which they appear.

Related Work
First of all, the obvious references for our work are the approaches evaluated on AImed and LLL challenge data sets.
In (Bunescu and Mooney, 2005b), the authors present a generalized subsequence kernel that works with sparse sequences containing combinations of words and PoS tags.
The best results on the LLL challenge were obtained by the group from the University of Edinburgh (Reidel and Klein, 2005), which used Markov Logic, a framework that combines loglinear models and First Order Logic, to create a set of weighted clauses which can classify pairs of gene named entities as genic interactions. These clauses are based on chains of syntactic and semantic relations in the parse or Discourse Representation Structure (DRS) of a sentence, respectively.
Other relevant approaches include those that adopt kernel methods to perform relation extraction. Zelenko et al. (2003) describe a relation extraction algorithm that uses a tree kernel defined over a shallow parse tree representation of sentences. The approach is vulnerable to unrecoverable parsing errors. Culotta and Sorensen (2004) describe a slightly generalized version of this kernel based on dependency trees, in which a bag-ofwords kernel is used to compensate for errors in syntactic analysis. A further extension is proposed by Zhao and Grishman (2005). They use composite kernels to integrate information from different syntactic sources (tokenization, sentence parsing, and deep dependency analysis) so that processing errors occurring at one level may be overcome by information from other levels. Bunescu and Mooney (2005a) present an alternative approach which uses information concentrated in the shortest path in the dependency tree between the two entities.
As mentioned in Section 1, another relevant approach is presented in (Roth and Yih, 2002). Classifiers that identify entities and relations among them are first learned from local information in the sentence. This information, along with constraints induced among entity types and relations, is used to perform global probabilistic inference that accounts for the mutual dependencies among the entities.
All the previous approaches have been evaluated on different data sets so that it is not possible to have a clear idea of which approach is better than the other.

Conclusions and Future Work
The good results obtained using only shallow linguistic features provide a higher baseline against which it is possible to measure improvements obtained using methods based on deep linguistic processing. In the near future, we plan to extend our work in several ways.
First, we would like to evaluate the contribution of syntactic information to relation extraction from biomedical literature. With this aim, we will integrate the output of a parser (possibly trained on a domain-specific resource such the Genia Treebank). Second, we plan to test the portability of our model on ACE and MUC data sets. Third, we would like to use a named entity recognizer instead of assuming that entities are already extracted or given by a dictionary. Our long term goal is to populate databases and ontologies by extracting information from large text collections such as Medline.