There are many unstructured text data stored in health information systems (HIS). To use this data for automatic processing it is necessary to be able to extract specific medical entities such as prescribed drugs, diagnosis, body conditions and so on. The article is concerned with building discriminatory models for solving the problem of named-entity extraction (NEE) for medical texts in Russian. Such models as Markov random fields and support vector machines (SVM) are considered. These methods showed better results in comparison with other NEE methods for English language corpuses. The application of these methods to text in Russian and moreover to medical text that burdened with specific medicine terminology is still a problem. To solve this problem the processes of feature extraction and models building are described in the context of said texts. Methods are evaluated on a corpus received from Federal Almazov North-West Medical Research Center. As a result, the most accurate method in according to F1-measure is chosen.
Natural Language Processing is a field of computer science, computational linguistics
concerned with the interactions between computers and human languages, and
concerned with programming computers to fruitfully process large natural language
corpora [
The task of the NLP for semi-structured medical texts differs from the processing of conventional texts because of the specific characteristics – absence of verbs, lack of emotional coloring, lack of homonymy, presence of standard patterns. Such properties make effective processing of available texts with the help of dictionaries and rulebased approaches. However, the perspective development direction is the use of ML methods. ML, in combination with available methods, is necessary for selecting those entities that are not in the dictionary, and can also be used to increase the prediction accuracy of entities, which are already in the dictionary.
Identifying special entities is a kind of information extraction (IE). For NLP it is one of the basic tasks. Identifying named entities in text is called Named Entity Recognition (NER). More accurate, NER is the task that seeks to locate and classify entities in text into pre-defined categories. This task is extremely significant for the processing of semi-structed medical texts. The most important difference is the obligatory presence of the context dependency. Therefore, to effectively solve this problem, we can use only those methods that take into account the context (CRF) or partially consider the context (SVM). In contrast to texts of general orientation, where we can achieve great accuracy using almost any ML method.
The objective of this research is context-dependent NER from medical texts in Russian gotten from one of the Russian medical center. Contextual dependency is provided by the type of records (diaries, complaints, etc.) and the available dictionaries obtained earlier. And also by the specific features of each named entity. For example, for drugs – this is the use of the active substance to find an analogue in the dictionary. The following requirements for NER-module can be singled out: replenishment of the dictionary (based on new entities) and integration with other classifiers and modules in the existing NLP system.
The article is organized as follows. First, the existing methods for NER are presented and the scientific researches in this area are analyzed. Specification of texts and technology – is in the third section. The description of the methods used, the construction of a feature space and the adjustment of models are presented in the fourth section. After that, the results of the experiment will be presented and conclusions will be drawn about the applicability of these methods for solving NER problem. 2
There are three main approaches for solving this problem: rule-based, ML based and mixed approach. We will consider in detail only ML methods, which are divided into generative and discriminative models (see Fig.1). Generative models randomly generate observable data values, typically given some hidden parameters. It specifies a joint probability distribution over observation and label sequences. Discriminative models directly estimate posterior probabilities, they don’t try to model underlying probability distributions. This is the key difference between them.
In [
As we can see in [
In [
In [
Thus, we can distinguish two most suitable discriminative models for NER for clinical texts – CRF, SVM.
However, these methods do not find proper reflection in research [
Research that does not relate to medical data processing deserves special attention.
In [
In article [
In [
This research [
One can draw a conclusion that CRF, SVM showed better results in comparison with other NER methods for English language corpuses. The application of these methods to text in Russian and moreover to medical text that burdened with specific medicine terminology is still a problem. So, the main goal of this article is to apply the most efficient discriminative models for increasing recognition accuracy for medical texts in Russian. The obtained results of methods evaluation can be useful for creators of modern health information systems.
In the NER task, the machine learning algorithm is used to define labels for classes of named entities for each word of the text. The label in this case can be the type of the named entity or the label "unnamed entity". However, this approach to the selection of labels does not allow us to establish the boundaries of entities in the case when two named entities of the same type are near
In the BIO representation, the region information is represented as the prefixes “B”,” I”,” O”. Prefix “B” (Beginning) means that the current word is at the beginning of a named entity, “I” (Inside) means that the current word is in a named entity, “O” (Outside) means that word does not belong to named entity.
Example (in origin language): [B-SUBSTANCE Метопролол] [O ( ] [B-DRUG: эгилок-ретард] [O ) ] [B-DOSAGE 50] [I-DOSAGE мг] [B-FREQUENCY 1] [IFREQUENCY раз] [I-FREQUENCY утром] Where FN – number of false negative samples, TP – number of true positive samples. = !"!!"!" = !"!!"!" Where FP – number of false positive samples, TP – number of true positive samples.
= !!!!"! 3.3
In the article the processing of medical texts can be represented in the form of an algorithm.
1) Manual or partially automated marking of training medical data. 2) Construction of the classification model. 3) Construction of the feature space. 4) Classifier training. 5) Classification of the test set.
6) Evaluation of the results 4
In this section, a detailed description of each method used I given. We show the implementation of this model for solving the problem and explain which features we used, in other words we discuss the 2nd-5th steps of the algorithm. For the fourth and fifth steps, we give the mathematical apparatus of the methods used. 4.1
CRF
- statistical method of classification. A distinctive feature of this method is the ability to take into account the context of an object. CRF is a discriminative non-directional probabilistic graphic model.
Formally, the Markov random field consists of the following components: - Unoriented graph or factor graph G = (V, E) , where ∀ vertex is random variable X and each edge is a relation between the random variables u and v.
- A set of potential functions {φk}, one for each clique (full subgraph G of the undirected graph) in the graph. The function φk puts each possible state of the clique elements into a certain non-negative real-valued number.
Vertexes that are not contiguous must correspond to conditionally independent random variables. The group of adjacent vertices forms a clique, the set of states of vertices is the argument of the corresponding potential function.
Potential function should be chosen equal to
φ (Yt − 1 , Yt , Xt ) = exp{ !!!! n ( Yt − 1 , Yt , Xt )} Where f (Yt-1, Yt , Xt ) is feature function, and n are the corresponding parameters of the model which should be evaluated in the learning process. Then the probability of a chain of hidden variables (Y) under the condition of a chain of observables variables (X) is:
P(y|x) = ! !!! ! (!!!! ,!! ,!! ) ! !! !!! ! ((!!!!)! ,(!!)! ,!! ) According the above, to solve NER problem we use linear CRF model with the size of the maximum clique equals 3 (see Fig.2).
Feature space. In the NER problem, features are understood as the characteristics of words used by machine learning algorithms during the learning process and entity recognition.
The following set of characteristics was proposed: Current word Xi 2 previous labels Yi-1 , Yi-2
Type of current word Xi (all letters are capitalized, the first letter is capitalized, all symbols are digits, word contains digit, word is alphanumerical, word contains dash, word contains Roman numericals, words contain one capital letter in in the middle, digits-coma-digits, digits-dot-digits, one digit, word is the first word of sentence, word contains special symbols, word contains brackets in front of, word contains brackets behind)
Part of speech Suffixes of length 2 Prefixes of length 2 Suffixes of length 3 Prefixes of length 3 Suffixes of length 4 Prefixes of length 4 Neighborhood words N = (Xi-3, Xi-2, Xi-1, Xi+1, Xi+2, Xx+3) Conjunction Yi-1 with N Type of word and POS for each word in N
The size of the admissible set of X signs is large enough, it was decided to use Random Forest algorithm for selecting the features.
(SVM) is binary classifiers, which outputs are +1 or -1 given a sample vector x. The decision bases on separating hyperplane h(x).
h(x) = +1, + > 0 ∈ , ∈ Rn
−1, ℎ The class for an input is determined by side of the space separated by the hyperplane, if h(x) = 0 it means that input sample lies on separating line. The key idea is to find optimal hyperplane with the maximum margin (distance between nearest data sample and plane). Speaking formally, we should minimize: Also, The solution of this problem is known and can be written in this form: | ! |! !
→ min
hi(w ∗ xi – b) ≥ 1, 1 ≤ i ≤ n
f(x) = w ∗ x + b =
!∈!"# yi ai x ∗ xi + b
Multi-class classifier. As we can see, classical SVM is suitable for binary
classification, but it is not our case. We should use method for constructing multi-class
classifier. The most progressive way is to use pairwise method proposed by Krebel and
extend the BIO representation to enable the training with the entire corpus. The idea of
this method is to combine a lot of binary classifiers. We construct N(N-1)/2 binary
SVMs, each of them votes (makes decision is sample belongs to i or j class). After
that we should choose class with maximum number of votes. But we can encounter
with unbalanced class distribution. Efficient way to solve it is to split the class
“Outside” into several sub- classes according to part-of-speech (POS) information of the
word. This approach was applied in the study [
Part of speech feature i, j = ℎ − ℎ 0, ℎ ℎ − ℎ 0, ℎ Prefix feature i, j =
Suffix feature i, j = ℎ − ℎ 0, ℎ
Previous class feature i, j = It’s very useful feature, we can use classes’ of already predicted words as features. Note that the selection of the first three features requires the compilation of lists of possible characteristic values (in contradistinction to CRF).
Also, we use 14 type of word features, which we described in section about CRF feature extracting.
So, after feature extracting the dimension of input vector equals 5*(19+|POS|+|Prefix|+|Suffix|). We can reduce this dimension by using Random Forest. 5
The medical corps was provided partly by Federal Almazov North-West Medical Research Center. and partly taken from open sources. The medical corps was manually marked with a BIO markup. For testing the statistical model, manual BIO-marking of about 700 sentences containing about 2000 named-entities was performed. It should be noted that we singled out in a separate class every word that did not belong to any of the entities
The table below shows the results of a computational experiment on a training set for CRF. The table below shows the results of a computational experiment on a training set for SVM. As we can see, quite good results were achieved in recognizing such entities as Drug and Substance. This is due to the fact that only one tag was used for their marking. CRF is completely superior to its competitor. Cross-validation is a model validation technique for assessing how the results of a statistical analysis will generalize to an independent data set. It is mainly used in settings where the goal is prediction, and one wants to estimate how accurately a predictive model will perform in practice.
5-fold cross-validation was used in the project. It means that the original sample is randomly partitioned into 5 equal sized subsamples. Of the 5 subsamples, a single subsample is retained as the validation data for testing the model, and the remaining 4 subsamples are used as training data. The cross-validation process is then repeated 5 times, with each of the 5 subsamples used exactly once as the validation data. The 5 results from the folds are averaged to produce a single estimation. 6
In this paper, two ML methods for solving NER problems have been described: CRF and SVM. The article describes the general model of CRF, describes the details of using and tuning the parameters of the linear model of CRF. Also, the concept of using SVM for multiclass classification taking into account the context was presented. As can be seen from the results of the experiment, CRF showed the best performance for almost all named entities due to deeper consideration of the context. But we can conclude that both approaches are applicable to the solution of our problem. Entities with the highest recognition accuracy are drugs and substances. This may be due to the fact that for markup we use, as a rule, only one tag, which essentially simplifies the task.
The results obtained tell us about the possibility of integration these methods into our NLP system as new named-entity recognizer. Of course, it’s possible to improve the results by analyzing typical classifier’s errors. This will be our further work in this area, also we are trying to test the consistency of the idea of combining classifiers in a cascade to increase the accuracy.