{'fraction_non_alphanumeric': 0.03681773324223791, 'fraction_numerical': 0.013626356942230319, 'mean_word_length': 4.580809150603685, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Tuning support vector machines for biomedical named entity recognition

We explore the use of Support Vector Machines (SVMs) for biomedical named entity recognition. To make the SVM training with the available largest corpus - the GENIA corpus - tractable, we propose to split the non-entity class into sub-classes, using part-of-speech information. In addition, we explore new features such as word cache and the states of an HMM trained by unsupervised learning. Experiments on the GENIA corpus show that our class splitting technique not only enables the training with the GENIA corpus but also improves the accuracy. The proposed new features also contribute to improve the accuracy. We compare our SVM-based recognition system with a system using Maximum Entropy tagging method.


Introduction
Application of natural language processing (NLP) is now a key research topic in bioinformatics. Since it is practically impossible for a researcher to grasp all of the huge amount of knowledge provided in the form of natural language, e.g., journal papers, there is a strong demand for biomedical information extraction (IE), which extracts knowledge automatically from biomedical papers using NLP techniques (Ohta et al., 1997;Proux et al., 2000;Yakushiji et al., 2001).
The process called named entity recognition, which finds entities that fill the information slots, e.g., proteins, DNAs, RNAs, cells etc., in the biomedical context, is an important building block in such biomedical IE systems. Conceptually, named entity recognition consists of two tasks: identification, which finds the region of a named entity in a text, and classification, which determines the se-mantic class of that named entity. The following illustrates biomedical named entity recognition.
"Thus, CIITA PROTEIN not only activates the expression of class II genes DNA but recruits another B cell-specific coactivator to increase transcriptional activity of class II promoters DNA in B cells CELLTYPE ." Machine learning approach has been applied to biomedical named entity recognition (Nobata et al., 1999;Yamada et al., 2000;Shimpuku, 2002). However, no work has achieved sufficient recognition accuracy. One reason is the lack of annotated corpora for training as is often the case of a new domain. Nobata et al. (1999) and  trained their model with only 100 annotated paper abstracts from the MEDLINE database (National Library of Medicine, 1999), and Yamada et al. (2000) used only 77 annotated paper abstracts. In addition, it is difficult to compare the techniques used in each study because they used a closed and different corpus.
To overcome such a situation, the GENIA corpus (Ohta et al., 2002) has been developed, and at this time it is the largest biomedical annotated corpus available to public, containing 670 annotated abstracts of the MEDLINE database.
Another reason for low accuracies is that biomedical named entities are essentially hard to recognize using standard feature sets compared with the named entities in newswire articles . Thus, we need to employ powerful machine learning techniques which can incorporate various and complex features in a consistent way. Support Vector Machines (SVMs) (Vapnik, 1995) and Maximum Entropy (ME) method (Berger et al., 1996) are powerful learning methods that satisfy such requirements, and are applied successfully to other NLP tasks Nakagawa et al., 2001;Ratnaparkhi, 1996). In this paper, we apply Support Vector Machines to biomedical named entity recognition and train them with the GENIA corpus. We formulate the named entity recognition as the classification of each word with context to one of the classes that represent region and named entity's semantic class. Although there is a previous work that applied SVMs to biomedical named entity task in this formulation (Yamada et al., 2000), their method to construct a classifier using SVMs, one-vs-rest, fails to train a classifier with entire GENIA corpus, since the cost of SVM training is super-linear to the size of training samples. Even with a more feasible method, pairwise (Kreßel, 1998), which is employed in , we cannot train a classifier in a reasonable time, because we have a large number of samples that belong to the non-entity class in this formulation. To solve this problem, we propose to split the non-entity class to several sub-classes, using part-ofspeech information. We show that this technique not only enables the training feasible but also improves the accuracy.
In addition, we explore new features such as word cache and the states of an unsupervised HMM for named entity recognition using SVMs. In the experiments, we show the effect of using these features and compare the overall performance of our SVMbased recognition system with a system using the Maximum Entropy method, which is an alternative to the SVM method.

The GENIA Corpus
The GENIA corpus is an annotated corpus of paper abstracts taken from the MEDLINE database. Currently, 670 abstracts are annotated with named entity tags by biomedical experts and made available to public (Ver. 1.1). 1 These 670 abstracts are a subset of more than 5,000 abstracts obtained by the query "human AND blood cell AND transcription factor" to the MEDLINE database. Table 1 shows basic statistics of the GENIA corpus. Since the GE-NIA corpus is intended to be extensive, there exist 24 distinct named entity classes in the corpus. 2 Our task is to find a named entity region in a paper abstract and correctly select its class out of these 24 classes. This number of classes is relatively large compared with other corpora used in previous studies, and compared with the named entity task for newswire articles. This indicates that the task with the GENIA corpus is hard, apart from the difficulty of the biomedical domain itself. 1 Available via http://www-tsujii.is.s.u-tokyo.ac.jp/GENIA/ 2 The GENIA corpus also has annotations for conjunctive/disjunctive named entity expressions such as "human B-or T-cell lines" (Kim et al., 2001). In this paper we ignore such expressions and consider that constituents in such expressions are annotated as a dummy class "temp".

Named Entity Recognition as Classification
We formulate the named entity task as the classification of each word with context to one of the classes that represent region information and named entity's semantic class. Several representations to encode region information are proposed and examined (Ramshaw and Marcus, 1995;Uchimoto et al., 2000;Kudo and Matsumoto, 2001). In this paper, we employ the simplest BIO representation, which is also used in (Yamada et al., 2000). We modify this representation in Section 5.1 in order to accelerate the SVM training.
In the BIO representation, the region information is represented as the class prefixes "B-" and "I-", and a class "O". B-means that the current word is at the beginning of a named entity, I-means that the current word is in a named entity (but not at the beginning), and O means the word is not in a named entity. For each named entity class C, class B-C and I-C are produced. Therefore, if we have N named entity classes, the BIO representation yields 2N + 1 classes, which will be the targets of a classifier. For instance, the following corresponds to the annotation "Number of glucocorticoid receptors

Support Vector Machines
Support Vector Machines (SVMs) (Cortes and Vapnik, 1995) are powerful methods for learning a classifier, which have been applied successfully to many NLP tasks such as base phrase chunking  and part-of-speech tagging (Nakagawa et al., 2001). The SVM constructs a binary classifier that outputs +1 or −1 given a sample vector x ∈ R n . The decision is based on the separating hyperplane as follows.
The class for an input x, c(x), is determined by seeing which side of the space separated by the hyperplane, w · x + b = 0, the input lies on.
Given a set of labeled training samples {(y 1 , x 1 ), · · · , (y L , x L )}, x i ∈ R n , y i ∈ {+1, −1}, the SVM training tries to find the optimal hyperplane, i.e., the hyperplane with the maximum margin. Margin is defined as the distance between the hyperplane and the training samples nearest to the hyperplane. Maximizing the margin insists that these nearest samples (support vectors) exist on both sides of the separating hyperplane and the hyperplane lies exactly at the midpoint of these support vectors. This margin maximization tightly relates to the fine generalization power of SVMs.
Assuming that |w·x i +b| = 1 at the support vectors without loss of generality, the SVM training can be formulated as the following optimization problem. 3 The solution of this problem is known to be written as follows, using only support vectors and weights for them.
In the SVM learning, we can use a function k(x i , x j ) called a kernel function instead of the inner product in the above equation. Introducing a kernel function means mapping an original input x using to another, usually a higher dimensional, feature space. We construct the optimal hyperplane in that space. By using kernel functions, we can construct a non-linear separating surface in the original feature space. Fortunately, such non-linear training does not increase the computational cost if the calculation of the kernel function is as cheap as the inner product. A polynomial function defined as (sx i · x j + r) d is popular in applications of SVMs to NLPs Yamada et al., 2000;Kudo and Matsumoto, 2001), because it has an intuitively sound interpretation that each dimension of the mapped space is a (weighted) conjunction of d features in the original sample.

Multi-Class SVMs
As described above, the standard SVM learning constructs a binary classifier. To make a named entity recognition system based on the BIO representation, we require a multi-class classifier. Among several methods for constructing a multi-class SVM (Hsu and Lin, 2002), we use a pairwise method proposed by Kreßel (1998) instead of the one-vs-rest method used in (Yamada et al., 2000), and extend the BIO representation to enable the training with the entire GENIA corpus. Here we describe the one-vs-rest method and the pairwise method to show the necessity of our extension. Both one-vs-rest and pairwise methods construct a multi-class classifier by combining many binary SVMs. In the following explanation, K denotes the number of the target classes.
one-vs-rest Construct K binary SVMs, each of which determines whether the sample should be classified as class i or as the other classes. The output is the class with the maximum f (x) in Equation 1.
pairwise Construct K(K − 1)/2 binary SVMs, each of which determines whether the sample should be classified as class i or as class j. Each binary SVM has one vote, and the output is the class with the maximum votes.
Because the SVM training is a quadratic optimization program, its cost is super-linear to the size of the training samples even with the tailored techniques such as SMO (Platt, 1998) and kernel evaluation caching (Joachims, 1998). Let L be the number of the training samples, then the one-vs-rest method takes time in K × O S V M (L). The BIO formulation produces one training sample per word, and the training with the GENIA corpus involves over 100,000 training samples as can be seen from Table 1. Therefore, it is apparent that the one-vsrest method is impractical with the GENIA corpus.
On the other hand, if target classes are equally distributed, the pairwise method will take time in This method is worthwhile because each training is much faster, though it requires the training of (K − 1)/2 times more classifiers. It is also reported that the pairwise method achieves higher accuracy than other methods in some benchmarks (Kreßel, 1998;Hsu and Lin, 2002).

Input Features
An input x to an SVM classifier is a feature representation of the word to be classified and its context. We use a bit-vector representation, each dimension of which indicates whether the input matches with a certain feature. The following illustrates the wellused features for the named entity recognition task.
In the above definitions, k is a relative word position from the word to be classified. A negative value represents a preceding word's position, and a positive value represents a following word's position. Note that we assume that the classification proceeds left to right as can be seen in the definition of the preceding class feature. For the SVM classification, we does not use a dynamic argmax-type classification such as the Viterbi algorithm, since it is difficult to define a good comparable value for the confidence of a prediction such as probability. The consequences of this limitation will be discussed with the experimental results.

Named Entity Recognition Using ME Model
The Maximum Entropy method, with which we compare our SVM-based method, defines the probability that the class is c given an input vector x as follows. a normalization constant, and f i (c, x) is a feature function. A feature function is defined in the same way as the features in the SVM learning, except that it includes c in it like f (c, x) = (c is the jth class) ∧ w i,k (x). If x contains previously assigned classes, then the most probable class sequence,ĉ T 1 = argmax c 1 ,··· ,c T T t=1 P(c t |x t ) is searched by using the Viterbi-type algorithm. We use the maximum entropy tagging method described in (Kazama et al., 2001) for the experiments, which is a variant of (Ratnaparkhi, 1996) modified to use HMM state features.

Class Splitting Technique
In Section 3.3, we described that if target classes are equally distributed, the pairwise method will reduce the training cost. In our case, however, we have a very unbalanced class distribution with a large number of samples belonging to the class "O" (see Table  1). This leads to the same situation with the one-vsrest method, i.e., if L O is the number of the samples belonging to the class "O", then the most dominant part of the training takes time in K × O S V M (L O ).
One solution to this unbalanced class distribution problem is to split the class "O" into several subclasses effectively. This will reduce the training cost for the same reason that the pairwise method works.
In this paper, we propose to split the non-entity class according to part-of-speech (POS) information of the word. That is, given a part-of-speech tag set POS, we produce new |POS| classes, "Op" p ∈ POS. Since we use a POS tagger that outputs 45 Penn Treebank's POS tags in this paper, we have new 45 sub-classes which correspond to nonentity regions such as "O-NNS" (plural nouns), "O-JJ" (adjectives), and "O-DT" (determiners).
Splitting by POS information seems useful for improving the system accuracy as well, because in the named entity recognition we must discriminate between nouns in named entities and nouns in ordinal noun phrases. In the experiments, we show this class splitting technique not only enables the feasible training but also improves the accuracy.

Word Cache and HMM Features
In addition to the standard features, we explore word cache feature and HMM state feature, mainly to solve the data sparseness problem.
Although the GENIA corpus is the largest annotated corpus for the biomedical domain, it is still small compared with other linguistic annotated corpora such as the Penn Treebank. Thus, the data sparseness problem is severe, and must be treated carefully. Usually, the data sparseness is prevented by using more general features that apply to a broader set of instances (e.g., disjunctions). While polynomial kernels in the SVM learning can effectively generate feature conjunctions, kernel functions that can effectively generate feature disjunctions are not known. Thus, we should explicitly add dimensions for such general features.
The word cache feature is defined as the disjunction of several word features as: We intend that the word cache feature captures the similarities of the patterns with a common key word such as follows.
(a) "human W −2 W −1 W 0 " and "human W −1 W 0 " (b) "W 0 gene" and "W 0 W 1 gene" We use a left word cache defined as lwc k,i ≡ wc {−k,··· ,0},i , and a right word cache defined as rwc k,i ≡ wc {1,··· ,k},i for patterns like (a) and (b) in the above example respectively. Kazama et al. (2001) proposed to use as features the Viterbi state sequence of a hidden Markov model (HMM) to prevent the data sparseness problem in the maximum entropy tagging model. An HMM is trained with a large number of unannotated texts by using an unsupervised learning method. Because the number of states of the HMM is usually made smaller than |V|, the Viterbi states give smoothed but maximally informative representations of word patterns tuned for the domain, from which the raw texts are taken.
The HMM feature is defined in the same way as the word feature as follows.
the ith state in the HMM's states H 0 otherwise (HMM feature) In the experiments, we train an HMM using raw MEDLINE abstracts in the GENIA corpus, and show that the HMM state feature can improve the accuracy.

Implementation Issues
Towards practical named entity recognition using SVMs, we have tackled the following implementation issues. It would be impossible to carry out the experiments in a reasonable time without such efforts. Parallel Training: The training of pairwise SVMs has trivial parallelism, i.e., each SVM can be trained separately. Since computers with two or more CPUs are not expensive these days, parallelization is very practical solution to accelerate the training of pairwise SVMs. Fast Winner Finding: Although the pairwise method reduces the cost of training, it greatly increases the number of classifications needed to determine the class of one sample. For example, for our experiments using the GENIA corpus, the BIO representation with class splitting yields more than 4,000 classification pairs. Fortunately, we can stop classifications when a class gets K − 1 votes and this stopping greatly saves classification time (Kreßel, 1998). Moreover, we can stop classifications when the current votes of a class is greater than the others' possible votes. Support Vector Caching: In the pairwise method, though we have a large number of classifiers, each classifier shares some support vectors with other classifiers. By storing the bodies of all support vectors together and letting each classifier have only the weights, we can greatly reduce the size of the classifier. The sharing of support vectors also can be exploited to accelerate the classification by caching the value of the kernel function between a support vector and a classifiee sample.

Experiments
To conduct experiments, we divided 670 abstracts of the GENIA corpus (Ver. 1.1) into the training part (590 abstracts; 4,487 sentences; 133,915 words) and the test part (80 abstracts; 622 sentences; 18,211 words). 6 Texts are tokenized by using Penn Treebank's tokenizer. An HMM for the HMM state features was trained with raw abstracts of the GENIA corpus (39,116 sentences). 7 The number of states is 160. The vocabulary for the word feature is constructed by taking the most frequent 10,000 words from the above raw abstracts, the prefix/suffix/prefix list by taking the most frequent 10,000 prefixes/suffixes/substrings. 8 The performance is measured by precision, recall, and F-score, which are the standard measures for the named entity recognition. Systems based on the BIO representation may produce an inconsistent class sequence such as "O B-DNA I-RNA O". We interpret such outputs as follows: once a named entity starts with "B-C" then we interpret that the named entity with class "C" ends only when we see another "B-" or "O-" tag.
We have implemented SMO algorithm (Platt, 1998) and techniques described in (Joachims, 1998) for soft margin SVMs in C++ programming language, and implemented support codes for pairwise classification and parallel training in Java programming language. To obtain POS information required for features and class splitting, we used an English POS tagger described in (Kazama et al., 2001).

Class Splitting Technique
First, we show the effect of the class splitting described in Section 5.1. Varying the size of training data, we compared the change in the training time and the accuracy with and without the class splitting. We used a feature set { w, pre, suf , sub, pos [−2,··· ,2] , pc [−2,−1] } and the inner product kernel. 9 The training time was measured on a machine with four 700MHz PentiumIIIs and 16GB RAM. Table 2 shows the results of the experiments. Figure 1 shows the results graphically. We can see that without splitting we soon suffer from super-linearity of the SVM training, while with splitting we can handle the training with over 100,000 samples in a reasonable time. It is very important that the splitting technique does not sacrifice the accuracy for speed, rather improves the accuracy.

Word Cache and HMM State Features
In this experiment, we see the effect of the word cache feature and the HMM state feature described in Section 3.4. The effect is assessed by the accuracy gain observed by adding each feature set to a base feature set and the accuracy degradation observed by subtracting it from a (com-9 Soft margin constant C is 1.0 throughout the experiments.  w, pre, suf , sub, pos, hmm [−k,··· ,k] , lwc k , rwc k , pc [−2,−1] } with k = 2 and k = 3 respectively. The kernel function is the inner product. We can see that word cache and HMM state features surely improve the recognition accuracy. In the table, we also included the accuracy change for other standard features. Preceeding classes and suffixes are definitely helpful. On the other hand, the substring feature is not effective in our setting. Although the effects of part-of-speech tags and prefixes are not so definite, it can be said that they are practically effective since they show positive effects in the case of the maximum performance.

Comparison with the ME Method
In this set of experiments, we compare our SVM-based system with a named entity recognition system based on the Maximum Entropy method. For the SVM system, we used the feature set { w, pre, suf , pos, hmm [−3,··· ,3] , lwc 3 , rwc 3 , pc [−2,−1] }, which is shown to be the best in the previous experiment. The compared system is a maximum entropy tagging model described in (Kazama et al., 2001). Though it supports several character type features such as number and hyphen and some conjunctive features such as word n-gram, we do not use these features to compare the performance under as close a condition as possible. The feature set used in the maximum entropy system is expressed as { w, pre, suf , pos, hmm [−2,··· ,2] , pc [−2,−1] }. 10 Both systems use the BIO representation with splitting. Table 4 shows the accuracies of both systems. For the SVM system, we show the results with the inner product kernel and several polynomial kernels. The row "All (id)" shows the accuracy from the view- point of the identification task, which only finds the named entity regions. The accuracies for several major entity classes are also shown. The SVM system with the 2-dimensional polynomial kernel achieves the highest accuracy. This comparison may be unfair since a polynomial kernel has the effect of using conjunctive features, while the ME system does not use such conjunctive features. Nevertheless, the facts: we can introduce the polynomial kernel very easily; there are very few parameters to be tuned; 11 we could achieve the higher accuracy; show an advantage of the SVM system.
It will be interesting to discuss why the SVM systems with the inner product kernel (and the polynomial kernel with d = 1) are outperformed by the ME system. We here discuss two possible reasons. The first is that the SVM system does not use a dynamic decision such as the Viterbi algorithm, while the ME system uses it. To see this, we degrade the ME system so that it predicts the classes deterministically without using the Viterbi algorithm. We found that this system only marks 51.54 in F-score. Thus, it can be said that a dynamic decision is important for this named entity task. However, although a method to convert the outputs of a binary SVM to probabilistic values is proposed (Platt, 1999), the way to obtain meaningful probabilistic values needed in Viterbitype algorithms from the outputs of a multi-class SVM is unknown. Solving this problem is certainly a part of the future work. The second possible reason is that the SVM system in this paper does not use any cut-off or feature truncation method to remove data noise, while the ME system uses a simple feature cut-off method. 12 We observed that the ME system without the cut-off only marks 49.11 in 11 C, s, r, and d 12 Features that occur less than 10 times are removed. F-score. Thus, such a noise reduction method is also important. However, the cut-off method for the ME method cannot be applied without modification since, as described in Section 3.4, the definition of the features are different in the two approaches. It can be said the features in the ME method is "finer" than those in SVMs. In this sense, the ME method allows us more flexible feature selection. This is an advantage of the ME method.
The accuracies achieved by both systems can be said high compared with those of the previous methods if we consider that we have 24 named entity classes. However, the accuracies are not sufficient for a practical use. Though higher accuracy will be achieved with a larger annotated corpus, we should also explore more effective features and find effective feature combination methods to exploit such a large corpus maximally.

Conclusion
We have described the use of Support Vector Machines for the biomedical named entity recognition task. To make the training of SVMs with the GE-NIA corpus practical, we proposed to split the nonentity class by using POS information. In addition, we explored the new types of features, word cache and HMM states, to avoid the data sparseness problem. In the experiments, we have shown that the class splitting technique not only makes training feasible but also improves the accuracy. We have also shown that the proposed new features also improve the accuracy and the SVM system with the polynomial kernel function outperforms the ME-based system.