Extracting medical events from clinical records using conditional random fields and parameter tuning for hidden Markov models

Abstract

Recently, the extraction of clinical events from unstructured medical texts has attracted much attention of the research community. Machine learning approaches are popular for this task, due to their ability to solve the problem of sequence tagging effectively. It has been suggested previously that simple features, such as word unigrams, part-of-speech tags, chunk tags, among others, are sufficient for this task. We show that more careful preprocessing and feature selection can significantly improve the results. We used conditional random field classifier with more linguistically oriented features and outperformed the current state-of-the-art approaches. We also show that the popular and much simpler Viterbi algorithm (hidden Markov model-based classification algorithm) can produce competitive results, when its parameters are tuned using specific optimization techniques. We evaluate these algorithms for the task of extraction of medical events from the corpus developed for SemEval shared Task 12: Clinical TempEval (Temporal Evaluation) 2016, namely, for its two subtasks: (i) event detection and (ii) event classification based on contextual modality.

Keywords

Clinical reports medical information extraction natural language processing machine learning feature selection conditional random field Viterbi algorithm

1 Introduction

In recent years, the analysis of clinical documents for decision making towards the improvement of patients’ treatment has gained attention of the research community. One of the important tasks of such analysis is to detect medical events in the texts. Several techniques such as machine learning, natural language processing, and medical entity recognition have been used in order to extract clinical knowledge and help physicians in decision making [13].

Studies related to clinical domain focus on medical entity recognition (MER), i.e., the process of extraction, detection and delimitation of phrasal information referring to medical entities from textual data, as well as semantic category identification of the detected entities [7 , 32].

The motivation of this work is to consider more linguistically motivated features as compared to the state-of-the-art with the CRF classifier, which usually yields the best results. We also try optimization models, which do not require analytic expressions for improving the properties of a variant of hidden Markov models (Viterbi algorithm).

As the case study, we used the annotated corpus THYME [8] (Temporal Histories of Your Medical Events) provided for the SemEval Task 12: Clinical TempEval 2016, the main international evaluation forum in this field. We used supervised machine learning techniques to identify and classify clinical events in this corpus. In particular, our event classification is based on contextual modality, when an event can be any indicator, which helps in treatment and taking care of the patient or in detection of situations that are relevant on the clinical timeline, such as tumors, illnesses, procedures, symptoms, etc. [44].

The contribution of our study is two-fold. First, we show that with careful preprocessing and feature extraction and selection, our conditional random field (CRF) classifier outperforms the current state-of-the-art methods of SemEval 2016 using the Clinical TempEval 2016 corpus. Second, we show that with suitable parameter tuning, the popular and much simpler Viterbi algorithm, a variant of hidden Markov model, gives competitive results. For parameter tuning, we analyzed two different optimization techniques: differential evolution and hill climbing.

The paper is organized as follows. In Section 2, we give literature review on clinical event extraction. In Section 3, we describe our methodology for extracting clinical events using CRFs and the Viterbi algorithm; the latter one, with two optimization techniques: hill climbing and differential evolution. In Section 4, we present the experimental results obtained with these algorithms and compare them for the SemEval 2016 Task 12 using Clinical TempEval 2016 test corpus. Finally, Section 5 concludes the paper and presents directions of future work.

2 Related work

In this section, we provide a brief overview of the existing results on the SemEval Task 12: Clinical TempEval (Clinical Temporal Evaluation) 2016 corpus and other available corpora.

Sarath et al. [21 , 46] have criticized both the dictionary-based and rules-based approaches for the lack of generalized applicability to situations not reflected in the knowledge base, since the available knowledge depends on the corpus used to extract it. Indeed, our analysis shows that the best results have been obtained with machine learning-based approaches.

Recently, machine learning approaches, such as conditional random field [1 , 18], support vector machine [24, 47], and neural networks [3 , 49] have demonstrated their ability to produce good prediction results and, thus, they have been widely used for different supervised tasks. These approaches require selection of features, such as word unigrams, syntactic and discourse-level features, as well as word representations, in combination with external resources. These features have been successfully used for several medical entity recognition tasks [24, 49].

2.1 Clinical TempEval

The Clinical TempEval 2016 shared task [8] is the main international competition on extracting temporal information from clinical notes. Approaches traditionally used for solving this task [46] are (i) dictionary-based approach, which can lead to the use of the context for detecting time expressions and words, using of ontologies such as MedLEE (a system for encoding clinical information in medical reports), MetaMap (a tool for detecting concepts in Unified Medical Language System), and CTake (a system with several dictionaries and machine learning approaches) [32]; (ii) rules-based approach to identify entities using heuristics [3, 16], and (iii) machine learning approaches, which provide powerful techniques for solving classification problems. Some of the results obtained in the Clinical TempEval 2016, as well as comparison with our own results, are given in Tables 5 and 6 below.

At Clinical TempEval 2016, the winning system UTHealth1, by Lee et al. [24] (see Tables 5 and 6), combined several features such as word unigrams (bag-of-words [38, 43]), syntactic and discourse-level features, and words representation in combination with dictionaries. It trained a hidden Markov model with support vector machine for identifying events and their types. They applied text preprocessing using several toolkits: Clamp for tokenization, OpenNLP for part-of-speech tagging and ClearNLP for dependency parsing. They reported an F-measure of 0.903 for event identification and 0.843 for detection of their contextual modality. Another their system, UTHealth2, that used slightly different features, showed the second best result, with F-measure of 0.895. Khalifa et al. [1] processed each section of the text separately. They extracted lexical and syntactic features such as lexical tokens, lemmas, part-of-speech tags, chunk labels, etc., using CTake, and word shape features such as lowercase, numeric, etc., using ClearTK. Their systems, UTAHBMI-CRF, based on CRF algorithm implemented in the CRF Suite toolkit [31], and UTAHBMI-SVM, based on SVM, both obtained an F-measure of 0.892 for detecting events, and 0.841 (UTAHBMI-CRF) and 0.836 (UTAHBMI-SVM) for identifying their types. Hansart et al. [18] in their system Cental-crf integrated statistical and linguistic approaches, combining CRF and linguistic knowledge for extracting temporal information. Specifically, they applied to clinical texts a state-of-the-art technique previously used for processing news in French, which yielded an F-measure of 0.885 for detecting events. They did not attempt to identify the types of the events. A complete description of other systems with worse performance can be found in [8].

2.2 Other corpora

López et al. [28] compared several supervised approaches, namely, expert-MLE, Naïve Bayes, Bayesian networks, Bayesian multivariate, logistic regression, neural networks, support vector machine, and random forest. They applied the Topaz system for detecting and extracting clinical concepts from medical records in the domain of influenza. This approach achieved the best performance when the Naïve Bayes algorithm was applied, with an Area Under the Curve (AUC) value of 0.930 for detecting the disease status. Liu et al. [27] trained CRF on token-level (such as bag-of-words, part-of-speech, affixes) and character-level (such as bag-of-characters, part-of-speech, section information) features for the Protected Health Information (PHI) identification. First, they used the system MedEx for tokenization and feature extraction; next, they used the CRF Suite [31] for classification. Their system achieved an F-measure result of 0.9051 using character-level features, followed by a token-level approach with an F-measure of 0.8370.

On the other hand, Li et al. [26] used CRF to identify and classify for biomedical named entity recognition task, based on several features, such as word, part-of-speech, chunk, boundary word, prefix/suffix and word shape. Moreover, they compared two label models (BIOEW and BIO), when BIOEW achieved the best performance with the F-score of 0.743.

Han-Cheol et al. [12] improved CRF by introducing multiple-segment representation for sequence labeling in the biomedical domain. First, preprocessing was used for tokenization. Then, features were extracted as tokens, lemmas, parts-of-speech, chunks and gazetteers. After this, their model was trained and tested. Furthermore, to verify the results of their algorithm, a re-sampling method was introduced.

Zhang et al. [19] provided an improvement to Hidden Markov model for a biomedical named entity recognition based on orthographic, morphological, part-of-speech and semantic trigger features. Their system used GENIA dataset and achieved the best result with the F-measure of 0.618.

In order to improve the performance of predictive models, optimization techniques have been used to facilitate the information extraction. Differential evolution is a stochastic method that allows maximization of the performance of the algorithms and reduces error rate [13]. Hill climbing is based on local search of the optimal solution. A difference between differential evolution and hill climbing is that the last works by making use of a step-size to find the best candidate solution [10]. An overview research on clinical domain using optimization techniques is presented as follows.

For evaluation of the automatic rule extraction from medical datasets, De Falco [13] introduced a novel classification tool, known as DEREx, which is based on differential evolution and rules for extracting items from clinical datasets. He presented a comparison by evaluating several supervised algorithms, where his system showed competitive results.

More recently, Kumar et al. [22] conducted a multi-objective differential evolution method for extraction of biomedical entities. Their system is subdivided into two sections: feature selection and ensemble learning. It was trained with a multi-objective differential evolution. The result was the F-measure of 0.7522, which outperformed other algorithms such as hidden Markov model, support vector machine, and CRF.

3 Methodology

In this study, two algorithms: CRF and Viterbi algorithm are trained, tested and compared. Moreover, two optimization techniques: differential evolution and hill climbing for tuning the Viterbi parameters are used.

These machine learning-based approaches are used for solving two tasks: (i) event detection and (ii) event classification. It is important to note that each experiment was performed separately. A brief description of the tasks considered in this study is provided below. Moreover, Fig. 1 illustrates the methodology used in this study and Fig. 2 fig:Heuristic shows the main procedure of optimization methods.

Fig.1

Our methodology.

Fig.2

Optimization of parameters for Viterbi algorithm.

Event detection. The goal of this task is to find whether a word is an event or not, making use of the annotated corpus, where the event span can be found.

Event classification. The aim is to classify into N/A (Not apply), actual, hedged, hypothetical and generic each token from clinical texts, according to the contextual modality. What follows are brief descriptions of the four categories based on THYME Annotation Guidelines [44]:

Actual. It is used primarily to describe the events that have occurred or have been scheduled for the future.

Hedged. The general idea of hedged is to identify all events with any sort of hedging (lexical or phrasal such as ‘seems’, ‘likely’, ‘possible’, ‘I suspect that...’, etc.). It should be noted that the events are strongly implied. However, they are not stated as fact by the physician due to lack of comprehensive evidence, safety, or liability.

Generic. These are events that are related to situations, where a physician gives a justification for certain actions and decisions, medication administration, or covering his or her back.

Hypothetical. The events in this category are based on assumptions.

3.1 Data description

The dataset used (previously reported in [8]) was collected under THYME project (Temporal Histories of Your Medical Events). This corpus consists of clinical and pathological notes of patients with colon cancer of Mayo clinic [8], which is a nonprofit organization committed to clinical practice, education and research. For a better interpretation, this annotated clinical corpus has 750 documents with approximately 211,347 tokens, where 18,989 tokens were detected as events. An overview of this corpus is presented in Table 1.

Table 1
An overview of THYME corpus used in this study

Set Documents Tokens

Train 297 131,878

Dev 300 62,159

Test 153 211,347

Total 750 405,384

Set	Documents	Tokens
Train	297	131,878
Dev	300	62,159
Test	153	211,347
Total	750	405,384

Fig.3

Detailed function description for training a Hidden Markov model.

3.2 Preprocessing

In order to enhance the clinical corpus for feature extraction and the efficiency of overall rate classification, some preprocessing techniques were applied. A list of them is depicted as follows:

Each document (clinical and pathological) was divided by sections (date, diseases, etc.) according to the information in the medical text. Also, the section names were replaced by a number tag with the goal of weighting all section names.

Then, a NLTK package [9] (sent_tokenize) was used to divide the documents section by sentences.

The words that are not correctly separated by a white space or combinations of words and numbers, etc. were separated by regular expressions with the aim of having correct tokens. We also used regular expressions to replace punctuation marks (.", etc.) and symbols (?,!,#, etc.) by a white space to take into account the position of these characters in the text.

Sentences were divided into tokens using another NLTK package Tokenize. This package analyzes each word in a sentence. Typically, this is applied to find further part-of-speech tags.

Furthermore, each sentence was separated into bigrams, which are added as additional features. This is useful because the combination of words can be also an event. We use the same sentence twice, first with words, then with bigrams. Note that we keep the same spans for words and bigrams (we take the span and POS tag of the first element).

3.3 Feature extraction

Per each token in the text, we used the following features: (i) wordform (the token as is); (ii) wordform in lowercase; (iii) lemma (we used the NLTK toolkit for lemmatization); (iv) part of speech (POS) of each token (we used the NLTK toolkit for tagging); (v) position in the chunk (event): Begin, Inside or Outside of an event, together with the part of speech of the token (such as Begin-Adj, Inside-NNP, etc.); (vi) type: numeric, word, or punctuation, and (vii) section identifier: the header section_id from the current section of the text.

3.4 Classifiers

3.4.1 Hidden Markov model: Viterbi algorithm

The Viterbi algorithm is distinguished for being a recursive optimal solution to find the best sequence of hidden states when a series of observations is given [4, 15, 48]. This method uses probabilistic operations of the Hidden Markov model for data training, where:

N is the number of states,

T is the number of observations,

π is the initial probabilities,

O is the sequence of observations,

S is the sequence of states,

A_ij is the probability of transition from state_i to state_j,

B_ij is the probability of emission of an observation o_j from state_i.

Figure 3 shows the architecture of the hidden Markov model, and Fig. 4 gives an example of the Viterbi function when N = 2 and T = 3 using transition probability (A_ij) and emission probability (B_ij). This means P (state_i|state_j) and P (observation_j|state_i), respectively.

Fig.4

Simple example of three observations with two states using the Viterbi algorithm. The black arrows indicate the shortest path from a state_i to state_j for each observation.

Table 2

Feature representation used in this work

Token position	Word_form	Lowercase	Lemma	POS	Chunk	Type	Section_id
1	Patient	patient	patient	NNP	Begin-NNP	word	20107
2	is	is	be	VERB	Inside-V	word	20107
3	bleeding	bleeding	bleed	VERB	Inside-V	word	20107
4	.	.	.	Punct	Outside-Punct	punct	20107
1 (2nd pass)	Patient_is	patient_is	Patient_is	NNP	Begin-NNP	word	20107
2 (2nd pass)	is_bleeding	is_bleeding	is_bleeding	VERB	Inside-V	word	20107
3 (2nd pass)	bleeding_.	bleeding_.	bleeding_.	VERB	Inside-V	word	20107...

In order to improve the results of the Viterbi method, differential evolution and hill climbing were applied over the Viterbi parameters for detecting and classifying events from cinical texts.

3.4.2 Viterbi algorithm with differential evolution

Differential evolution is a powerful algorithm for optimization, which was proposed by Storn and Price [50]. This method can be used specifically to solve problems that have several local minima or cost functions that are categorized such as non-differentiable, non-continuous, non-linear, or multi-dimensional [5 , 40]. Moreover, differential evolution is more robust to detect the global optimization than the traditional gradient-based methods. The process of this algorithm is shown as follows.

Initialization: The initial population of parents is formed by converting A_ij and B_ij into a vector called AB, and then, multiplying t random number f per AB vector, such that t represents the population size, A_ij forms a k x k matrix that describes the transition probability between state s_i and state s_j, and B_ij conforms a k x m matrix that indicates the observation probability o_j of the state s_i.

Fitness function: According to the results of the Viterbi algorithm, the fitness function used in this study is the F-measure (F₁) calculated using Equation (1): $F_{1} = 2 \times \frac{Precision \times Recall}{Precision + Recall} .$ (1)

Mutation: The purpose of mutation is to create a new parent, which might be better than the actual parents. For this reason, three random shuffle vectors from population were selected to create the mutant parent using Equation (2), multiplying a random number f by the difference of two random vectors: ${\vec{x}}_{r 2}$ and ${\vec{x}}_{r 3}$ , and the resulting vector is adding to a third random vector ${\vec{x}}_{r 1}$ [39]: ${\vec{v}}_{i} = {\vec{x}}_{r 1} + F \cdot ({\vec{x}}_{r 2} - {\vec{x}}_{r 3}) .$ (2)

Crossover: This step is introduced to exchange information between the actual parent x_i,j and mutant vector v_i,j, as in Equation (3), where rand [0, 1] _j represents a random number, and k describes a randomly chosen index to ensure the exchange of information [50]: $u_{i, j} = {\begin{matrix} v_{i, j} & if rand [0, 1]_{j} \leq orj = k, \\ x_{i, j} & otherwise, \end{matrix}$ (3)

Stop condition: Differential evolution terminates when a stopping criteria such as the number of generations (q) or the error criteria are reached.

3.4.3 Viterbi algorithm with hill climbing

Fig.5

Hill climbing example: each element of vector is modified by adding o substracting random value f; it is evaluated by the Viterbi algorithm to find the best solution.

Hill climbing is a heuristic approach that finds an optimal local minimum [51]. Figure 5 shows the architecture of the hill climbing algorithm used in this study. The goal of this local search method is to improve a candidate solution by selecting a random variable iteration [10]. In this case the fitness function is computed by the Viterbi algorithm using F-measure metric. The hill climbing algorithm is described as follows:

From the Viterbi parameters, the transition and emission probability matrices (A_ij and B_ij) are concatenated into a probability vector AB.

The elements of the AB vector are randomly placed into an array called BA, in order to reduce the computation time. The algorithm takes the first element from the BA vector, adds a random value f and forms BA₁. Simultaneously, it rests this vector element from f and produces BA₂.

The proposed methodology evaluates both produced vectors (BA₁ and BA₂) by using the Viterbi fitness function and chooses the vector that produces the least error.

If BA₁ or BA₂ gives a least error, the algorithm continues adding or resting f random numbers to this element until the error stops decreasing.

It continues with the rest of the vector elements.

The hill climbing algorithm stops when all values in the vector BA are evaluated for finding the best optimal solution.

3.4.4 Conditional random fields

CRF is considered as a powerful algorithm for solving Natural Language Processing (NLP) tasks [23]. According to Agarwal [2], this algorithm has presented better results than the hidden Markov model due to independence assumption that can be relaxed.

We therefore trained and evaluated CRF model using CRF Suite toolkit [31], which is an implementation of CRF for labeling sequential data 1 .

Table 3
Prediction results for the task of event detection

Classifier Class Train + Dev Test

Precision Recall F-measure Precision Recall F-measure

CRF event 0.999 0.999 0.999 0.981 0.950 0.965

no event 0.999 0.999 0.999 0.995 0.998 0.997

Viterbi with diferential evolution event 0.930 0.920 0.925 0.874 0.864 0.869

no event 0.992 0.993 0.996 0.987 0.988 0.987

Viterbi with hill climbing event 0.944 0.901 0.922 0.811 0.854 0.832

no event 0.990 0.995 0.992 0.986 0.980 0.983

Baseline: Viterbi event 0.429 0.974 0.595 0.402 0.943 0.563

no event 0.997 0.869 0.929 0.994 0.862 0.923

Classifier	Class	Train + Dev	Test
CRF	event	0.999	0.999	0.999	0.981	0.950	0.965
	no event	0.999	0.999	0.999	0.995	0.998	0.997
Viterbi with diferential evolution	event	0.930	0.920	0.925	0.874	0.864	0.869
	no event	0.992	0.993	0.996	0.987	0.988	0.987
Viterbi with hill climbing	event	0.944	0.901	0.922	0.811	0.854	0.832
	no event	0.990	0.995	0.992	0.986	0.980	0.983
Baseline: Viterbi	event	0.429	0.974	0.595	0.402	0.943	0.563
	no event	0.997	0.869	0.929	0.994	0.862	0.923

Fig.6

Graphical representation of average F-measure of CRF, Viterbi algorithm with differential evolution, Viterbi algorithm with hill climbing, and Viterbi algorithm in task of event detection.

4 Experimental results

In this section, we describe our experimens on the THYME corpus using the CRF and Viterbi algorithm with two optimization techniques for tuning its parameters: differential evolution and hill climbing. We use three evaluation metrics: (i) precision, the percentage of retrieved items that are in fact labeled as “event”, (ii) recall, the percentage of items labeled as “event” that were retrieved, and (iii) F-measure, the harmonic mean of recall and precision. Usually, F-measure is used for evaluation of the classifiers’ performance in the tasks of detection and classification of events.

In this case study, the algorithms are trained using the subcorpora “train” and “dev”, and are evaluated by using the “test” subcorpus. We include as the baseline method the traditional Viterbi algorithm.

Throughout the empirical study, the differential evolution parameters are based on a population size of 150 individuals with 120 generations in both tasks (event detection and event classification).

4.1 Experimental results for event detection

Here, we present our results for the task of event detection. In general, the analysis consists of training and testing the algorithms: CRF, differential evolution and hill climbing for tuning the Viterbi parameters. Furthermore, these algorithms are compared with the baseline (the Viterbi algorithm). Table 3 shows the evaluation results of the proposed algorithms.

Table 4
Evaluation results of the proposed algorithms for the task of event classification

Classifier Class Train + Dev Test

Precision Recall F-measure Precision Recall F-measure

CRF N/A 0.999 0.999 0.999 0.995 0.998 0.997

Actual 0.997 0.998 0.998 0.918 0.946 0.932

Hypothetical 0.981 0.963 0.972 0.724 0.237 0.357

Hedged 0.979 0.956 0.967 0.443 0.073 0.125

Generic 0.993 0.993 0.990 0.607 0.154 0.246

Viterbi with diferential evolution N/A 0.992 0.939 0.965 0.987 0.924 0.954

Actual 0.571 0.896 0.697 0.490 0.847 0.621

Hypothetical 0.473 0.518 0.494 0.337 0.242 0.282

Hedged 0.410 0.329 0.347 0.189 0.139 0.160

Generic 0.441 0.567 0.496 0.180 0.223 0.199

Viterbi with hill climbing N/A 0.988 0.911 0.948 0.982 0.898 0.938

Actual 0.448 0.770 0.566 0.389 0.718 0.505

Hypothetical 0.292 0.655 0.404 0.195 0.322 0.243

Hedged 0.214 0.578 0.312 0.118 0.266 0.164

Generic 0.258 0.706 0.378 0.114 0.361 0.173

Baseline: Viterbi N/A 0.997 0.867 0.928 0.994 0.857 0.921

Actual 0.383 0.857 0.530 0.348 0.826 0.489

Hypothetical 0.237 0.657 0.349 0.157 0.335 0.213

Hedged 0.184 0.583 0.280 0.101 0.270 0.147

Generic 0.208 0.716 0.322 0.089 0.361 0.142

Classifier	Class	Train + Dev	Test
CRF	N/A	0.999	0.999	0.999	0.995	0.998	0.997
	Actual	0.997	0.998	0.998	0.918	0.946	0.932
	Hypothetical	0.981	0.963	0.972	0.724	0.237	0.357
	Hedged	0.979	0.956	0.967	0.443	0.073	0.125
	Generic	0.993	0.993	0.990	0.607	0.154	0.246
Viterbi with diferential evolution	N/A	0.992	0.939	0.965	0.987	0.924	0.954
	Actual	0.571	0.896	0.697	0.490	0.847	0.621
	Hypothetical	0.473	0.518	0.494	0.337	0.242	0.282
	Hedged	0.410	0.329	0.347	0.189	0.139	0.160
	Generic	0.441	0.567	0.496	0.180	0.223	0.199
Viterbi with hill climbing	N/A	0.988	0.911	0.948	0.982	0.898	0.938
	Actual	0.448	0.770	0.566	0.389	0.718	0.505
	Hypothetical	0.292	0.655	0.404	0.195	0.322	0.243
	Hedged	0.214	0.578	0.312	0.118	0.266	0.164
	Generic	0.258	0.706	0.378	0.114	0.361	0.173
Baseline: Viterbi	N/A	0.997	0.867	0.928	0.994	0.857	0.921
	Actual	0.383	0.857	0.530	0.348	0.826	0.489
	Hypothetical	0.237	0.657	0.349	0.157	0.335	0.213
	Hedged	0.184	0.583	0.280	0.101	0.270	0.147
	Generic	0.208	0.716	0.322	0.089	0.361	0.142

Fig.7

A comparison of average F-measure for the task of event classification achieved by CRF, Viterbi algorithm with differential evolution, Viterbi algorithm with hill climbing, and Viterbi algorithm.

As it is previously mentioned, the classifiers were trained using subcorpora “train” and “dev” (corresponding to training and development). Figure 6 shows that CRF achieved the F-measure of 0.999 when the model was trained and tested on the training corpus for verification of the overfitting. The baseline, the Viterbi algorithm, reported the worst result with an average of the F-measure of 0.762. The classification process using differential evolution and hill climbing provided the F-measure of 0.959 and 0.957, respectively.

Table 5

Comparison of our results with those of SemEval: Task 12 Clinical TempEval 2016, subtask of event detection.

The rank is shown by F-measure. Some systems are omitted; see [8] for a complete list

TempEval 2016 rank	System	Precision	Recall	F-measure
–	Our: CRF	0.981	0.948	0.965
1	UTHealth1 [24]	0.915	0.891	0.903
2	UTHealth2 [24]	0.903	0.886	0.895
3	UTAHBMI-SVM [1]	0.897	0.886	0.892
4	UTAHBMI-CRF [1]	0.902	0.883	0.892
5	Cental-crf [18]	0.892	0.878	0.885
...	...	...	...	...
9	UTA-5 [25]	0.900	0.850	0.874
–	Our: Viterbi with differential evolution	0.874	0.862	0.868
10	VUACLTL-1 [11]	0.868	0.828	0.847
...	...	...	...	...
13	LIMSI-2 [17]	0.869	0.816	0.842
–	Our: Viterbi with hill climbing	0.854	0.810	0.831
14	CDE-IIITH-crf [49]	0.835	0.815
...	...	...	...	...
16	Brundlefly [3]	0.883	0.660	0.755
–	Our baseline: Viterbi	0.401	0.943	0.563

Table 6

Comparison of our results with those of SemEval: Task 12 Clinical TempEval 2016, subtask of event classification.

The rank is shown by accuracy. Some systems are omitted; see [8] for a complete list

TempEval 2016 rank	System	Precision	Recall	F-measure
–	Our: CRF	0.912	0.860	0.885
1	UTHealth1 [24]	0.866	0.843	0.855
2	UTHealth2 [24]	0.855	0.839	0.847
3	UTAHBMI-CRF [1]	0.850	0.832	0.841
4	UTAHBMI-SVM [1]	0.841	0.831	0.836
...	...	...	...	...
15	Brundlefly [3]	0.819	0.612	0.701
–	Our: Viterbi with differential evolution	0.480	0.792	0.598
–	Our: Viterbi with hill climbing	0.367	0.683	0.478
–	Our baseline: Viterbi	0.327	0.782	0.461

When the model was evaluated on the “test” subcorpus (the proper evaluation), again, CRF achieved the best result with the average F-measure of 0.981, and outperformed the Viterbi algorithm with differential evolution and hill climbing, which had the F-measure of 0.928 and 0.907, respectively. The baseline, the Viterbi algorithm, had the F-measure of 0.7431.

In analysis of the performance of the proposed algorithms, it is clear that differential evolution and hill climbing obtained better results than the baseline method. Moreover, it is important to mention that all algorithms did not show overfitting, since the evaluation at the training and testing data has almost the same results for the task of event detection.

4.2 Experimental results for event classsification

We tackled the second task (event classification) using CRF, the Viterbi algorithm tuned with differential evolution and hill climbing, and the baseline Viterbi algorithm. Table 4 shows the results in terms of precision, recall, and F-measure when the clinical corpus (training, dev and test) is used for training and testing.

As presented in Fig. 7 the average F-measure of CRF, Viterbi with differential evolution, and Viterbi with hill climbing were 0.985, 0.604, and 0.522, respectively. The baseline results using Viterbi algorithm without optimization technique was 0.482.

In our experiments with the test data, it has been observed that CRF is the best algorithm for classifying events, although the results demonstrated a low effectiveness of the classification with an average F-measure of 0.532. The second best algorithm is Viterbi and differential evolution with an average F-measure of 0.443. The third best algorithm is hill climbing where the average F-measure is 0.405. Finally, the baseline method, Viterbi, is the worst of the proposed algorithms with an average of 0.383 in F-measure.

As noticed, the performance of CRF on both training and test phases were 0.985 and 0.532, respectively. These results demonstrated that CRF algorithm had problems to generalize sufficiently to new test data in the classes: hypothetical, hedged and generic. Furthermore, we observed that although, the overall average of F-measure results are not quite high for the task of event classification, no occurred a significant difference between the results of differential evolution and hill climbing for training and test phases.

4.3 A comparison between this study and SemEval: Clinical TempEval 2016

As it was presented above, the best result in the tasks: (i) event detection and (ii) event classification was achieved by CRF, followed by Viterbi algorithm with differential evolution, and Viterbi algorithm with hill climbing. Finally, the worst algorithm was Viterbi when optimization techniques were not applied.

Based on the contributions of this study, Tables 5 and 6 show that CRF achieved a superior result according to the state-of-the-art in SemEval 2016: Task 12 Clinical TempEval 2016. The classification process was evaluated using SemEval software 2 . The results of the task of event detection are better than the task of event classification, since the classification problem when several classes are given is more difficult. Furthermore, it can be noted from the task of event classification that recall was always higher than precision, when the Viterbi algorithm was applied.

The results provided by the CRF are presented, as follows. CRF achieved the average F-measure of 0.965 for event detection, and the F-measure 0.885 for event classification. As we can see in both task, our proposal overcame the results reported for the winning approach [24], where their proposal presented the F-measure of 0.903 for the first task, and the F-measure of 0.855 for the second task.

Even though the best results were achieved by CRF, we see that Viterbi algorithms with differential evolution and with hill climbing demonstrated similar performance to the most common classifiers used in the state-of-the-art (SemEval Task 12: Clinical TempEval 2016) for extraction of clinical events. However, if the Viterbi algorithm is used without optimization techniques, the obtained results are very low as compared to the state-of-the-art. As we can see in Table 6, CRF achieved the F-measure of 0.885, whereas Viterbi algorithm with differential evolution and hill climbing got the F-measure of 0.598 and 0.478, respectively. These results are lower because the model did not include the robustness, weight assignment and data representation as it is used in conditional random fields, which optimizes the conditional probability of labels for an observation sequence [2].

5 Conclusions and future work

We have addressed two tasks of the SemEval shared Task 12: Clinical TempEval (Temporal Evaluation) 2016: (i) event detection and (ii) event classification. For evaluation, we used the corpora and the evaluation system officially provided by this competition.

We presented a method based on the CRF classifier applying the features described above (words, bigrams, POS tags, etc.). Our method outperformed all systems that participated in this competition on both tasks, thus showing the best currently known result.

For feature extraction, we used preprocessing techniques from natural language processing field. We extracted simple features such as word unigrams and part-of-speech tags, still outperforming more sophisticated systems that used the information extracted with the Unified Medical Language System (UMLS), Brown clustering, or CLAMP.

As a separate contribution, we studied the performance of another popular classification algorithm: the Viterbi algorithm, a variant of hidden Markov model. This algorithm is much simpler in implementation than CRF; however, it is known to produce results inferior to those of other classifiers such as CRF or SVM. However, we have shown that if its parameters are properly tuned, it produces competitive results. For parameter tuning, we tried two optimization techniques: differential evolution and hill climbing. While hill climbing is simpler, differential evolution gave slightly better results. These optimization techniques, however, are expensive in terms of processing time and, in case of differential evolution, memory.

As a future work, we expect to further refine our preprocessing technique and explore other types of features such as trigrams or syntactic n-grams [42]. As to the tuning of the Viterbi algorithm, we plan to explore different parameters of the optimization, such as pool size or crossover rate, as well as apply our tuning techniques to algorithms other than Viterbi. We also plan to try unsupervised pre-processing [36] and semi-supervised methods, such as fuzzy-based SVM [34], and deep-learning approaches with linguistic hierarchy and context modeling [29 , 37].

Footnotes

Acknowledgments

This work was partially supported by the Mexican Government via the CONACYT project 240844, SNI, and Instituto Politécnico Nacional grants COFAA, SIP 20171813, SIP 20171344, and SIP 20172008). It was also partially funded by CONACYT under the Thematic Networks program (Language Technologies Thematic Network project 281795).

References

Abdulrahman

, Velupillai

and Meystre

, UtahBMI at SemEval-Task 12: Extracting Temporal Information from Clinical Text, In Proc of the 10th International Workshop Semantic Evaluation, 2016, pp. 1256–1262.

Agarwal

and Yu

, Detecting hedge cues and their scope in biomedical with conditional random fields, Journal of Biomedical Informatics (2010).

Alan Fries

, Brundlefly at SemEval-Task 12: Recurrent Neural Networks vs. Joint Inference for Clinical Temporal Information Extraction, In: Proc of the 10th International Workshop Semantic Evaluation, 2016, pp. 1274–1279.

Anjum

and Lal Sabharwal

, Filtering compromised environment sensors using autoregressive hidden markov model, Polibits54 (2016), 5–10 ISSN 2395-8618.

Arce

, Zamora

, Sossa

and Barrón

, Dendrite Morphological Neural Networks Trained by Differential Evolution, In 2016 IEEE Symposium Series on Computational Intelligence (SSCI), 2016, pp. 1–8.

Barros

, Lamurias

, Antunes

, Teixeira

, Pinheiro

and Couto

F.M.

, ULISBOA at SemEval-Task 12: Extraction of Temporal Expressions, Clinical Events and Relations using IBEnt, In: Proc of the 10th International Workshop Semantic Evaluation, 2016, pp. 1263–1267.

Ben Abacha

, and Zweigenbaum

, Medical Entity Recognition: A Comparison of Semantic and Statical Methods, In 2011 Workshop on Biomedical Natural Language Processing, 2011, pp. 56–64.

Bethard

, Guergana

, Che

W.-T.

, Derczynski

, Pustejovsky

and Verhagen

, SemEval-task 12: Clinical TempEval, In Proceedings of NAACL-HLT 2016 (2016), 820–830.

Bird

, Klein

and Loper

, Natural Language Processing with Python, O’Reilly Media, Inc., 1st edition, 2009 ISBN 0596516495, 9780596516499.

10.

Brownlee

, Clever Algorithms: Nature-Inspired Programming Recipes, LuLu, 1st edition, ISBN 1446785068, 9781446785065.

11.

Caselli

and Morante

, VUACLTL at SemEval Task 12: A CRF Pipeline to Clinical TempEval, In Proc of the 10th International Workshop Semantic Evaluation, 2016, pp. 1241–1247.

12.

Cho

H.-C.

, Okazaki

, Miwa

and Tsuji

J.I.

, Named entity recognition with multiple segment representations, Information Processing and Management (2013), 954–965.

13.

De Falco

, Differential evolution for automatic rule extraction from medical databases, Applied Soft Computing13(2) (2013) 1265–1283. ISSN 1568-4946, doi: https://dx-doi-org.web.bisu.edu.cn/10.1016/j.asoc.2012.10.022.

14.

Dupont

, Dinarelli

, Tellier

and Lautier

, Structured Named Entity Recognition by Cascading CRFs, In Proceedings of the 18th International Conference on Computational Linguistics and Intelligent Text Processing, CICLing 2017, 2017.

15.

Forney

G.D.

, The viterbi algorithm, Proceedings of the IEEE61(3) (1973), 268–278. ISSN 0018-9219.

16.

Gridach

, Character-level neural network for biomedical named entity recognition, Journal of Biomedical Informatics70 (2017), 85–91.

17.

Grouin

and Moriceau

, LIMSI at SemEval-Task 12: Machine-learning and Temporal Information to Identify Clinical Events and Time Expressions, In Proc of the 10th International Workshop Semantic Evaluation (2016).

18.

Hansart

and De Meyere

, Watrin

, Bittar

and Fairon

, CENTAL at SemEval-Task 12: A Linguistically Fed CRF Model for Medical and Temporal Information Extraction, In Proc of the 10th InternationalWorkshop Semantic Evaluation, 2016, pp. 1286–1291.

19.

Jie

, Dan

, Guodong

, Jian

and Chew-Lim

, Enhancing HMM-based biomedical named entity recognition by studying special phenomena, Journal of Biomedical Informatics37(6) (2004), 411–422. ISSN 1532-0464, doi: https://dx-doi-org.web.bisu.edu.cn/10.1016/j.jbi.2004.08.005, Named Entity Recognition in Biomedicine.

20.

Keretna

, Lim

C.P.

, Creighton

, Shaban and Bashir

, Enhancing medical named entity recognition with an extended segment representation technique, Computer Methods and Programs in Biomedicine119 (2015), 88–100.

21.

Ki-Joong

, Young-Sook

, Seonho

and Hae-Chang

, Biomedical named entity recognition using two-phase model based on SVMs, Journal of Biomedical Informatics37(6) (2004), 436–447. ISSN 1532-0464, doi: https://dx-doi-org.web.bisu.edu.cn/10.1016/j.jbi.2004.08.012, Named Entity Recognition in Biomedicine.

22.

Kundeti

S.R.

, Vijayananda

, Mujjiga

and Kalyan

, Clinical Named Entity Recognition: Challenges and Opportunities, pp, In 2016 IEEE International Conference on Big Data (Big Data) (2016), pp. 1937–1945. doi: 10.1109/BigData.2016.7840814.

23.

Lark

, Morin

and Saldarriaga

, A Comparative Study of Target-based and Entity-based Opinion Extraction, CICLing, In Proceedings of the 18th International Conference on Computational Linguistics and Intelligent Text Processing 2017 (2017).

24.

Lee

H.-J.

, Xu

, Wang

, Zhang

, Moon

, Xu

and Wu

, UTHealth at SemEval-Task 12: An End-to End System for Temporal Information Extraction from Clinical Notes, In: Proc of the 10th International Workshop Semantic Evaluation, 2016, pp. 1292–1297.

25.

and Huang

, UTA DLNLP at SemEval-Task 12: Deep Learning Based Natural Language Processing System for Clinical Information Identification from Clinical Notes and Pathology Reports, In: Proc of the 10th InternationalWorkshop Semantic Evaluation, 2016, pp. 1268–1273.

26.

Lishuang

, Rongpeng

and Degen

, Two-phase biomedical named entity recognition using CRFs, Computational Biology and Chemistry33(4) (2009), 334–338. ISSN 1476-9271, doi: https://dx-doi-org.web.bisu.edu.cn/10.1016/j.compbiolchem.2009.07.004.

27.

Liu

, Tang

, Wang

and Chen

, De-identification of clinical notes via recurrent neural network and conditional random fiels, Journal of Biomedical Informatics (2017).

28.

López Pineda

, Ye

, Visweswaran

, Gregory

F.C.

, Wagner

M.M.

, and Tsui

, Comparison of machine learning classifiers for influenza detection from emergency department free-text reports, Journal of Biomedical Informatics58 (2015), 60–69. ISSN 1532-0464, doi: https://dx-doi-org.web.bisu.edu.cn/10.1016/j.jbi.2015.08.019.

29.

Majumder

, Poria

, Gelbukh

and Cambria

, Deep learning-based document modeling for personality detection from text, IEEE Intelligent Systems32 (2017), 74–79.

30.

Nunes Marques

R.Z.

, Reis Coutinho

, Bonini Borchartt

, Béliche Vale

and José da Silva e Silva

, EMiner: A tool for selecting classification algorithms and optimal parameters, Polibits52 (2015), 17–24. ISSN 2395-8618.

31.

Okazaki

, CRFsuite: A Fast Implementation of Conditional Random Fields (CRFs), 2007.

32.

Pérez

, Weegar

, Casillas

, Gojenola

, Oronoz

and Dalianis

, Semisupervised medical entity recognition: A study on spanish and swedish clinical corpora, Journal of Biomedical Informatics71 (2017), 16–30.

33.

Popescu Anastasiu

, Bold

and Nijloveanu

, A method based on genetic algorithms for generating assessment tests used for learning, Polibits54 (2016), 53–60. ISSN 2395-8618.

34.

Poria

, Gelbukh

, Das

and Bandyopadhyay

, Fuzzy Clustering for Semi-supervised Learning-case Study: Construction of an Emotion Lexicon, In Mexican International Conference on Artificial Intelligence, MICAI 2012, number 7629 in Lecture Notes in Computer Science, 2012, pp. 73–86. Springer.

35.

Poria

, Cambria

and Gelbukh

, Aspect extraction for opinion mining with a deep convolutional neural network, Knowledge-Based Systems108 (2016), 42–49.

36.

Poria

, Chaturvedi

, Cambria

and Bisio

, Sentic LDA: Improving on LDA with Semantic Similarity for Aspect-based Sentiment Analysis, In 2016 International Joint Conference on Neural Networks (IJCNN), 2016, pp. 4465–4473. IEEE.

37.

Poria

, Cambria

, Hazarika

, Majumder

, Zadeh

and MorencyL.6 , Context-dependent Sentiment Analysis in User-generated Videos, In 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), (2017), 873–883.

38.

Poria

, Cambria

, Gelbukh

, Bisio

and Hussain

, Sentiment data flow analysis by means of dynamic linguistic patterns, IEEE Computational Intelligence Magazine10(4) (2015), 26–36.

39.

Price

, Storn

R.M.

and Lampinen

J.A.

, Differential Evolution: A Practical Approach to Global Optimization (Natural Computing Series), Springer-Verlag NewYork, Inc., Secaucus, NJ, USA, 2005, ISBN 3540209506.

40.

Rodríguez Maya

, Flores

J.J.

and Rodríguez Rangel

, Performance comparison of evolutionary algorithms for University course timetabling problem, ComputaciÓn y Sistemas, 20(4) (2016), 623–634. ISSN 2007-9737.

41.

Sarath

, Manikandar

and Niwa

, Hitachi at Eval-Task 12: A Hybrid Approach for Temporal Information Extraction from Clinical Notes, In Proc of the 10th International Workshop Semantic Evaluation, 2016, pp. 1231–1236.

42.

Sidorov

, Velasquez

, Stamatatos

, Gelbukh

and Chanona-hernández

, syntactic N-grams as machine learning features for natural language processing, Expert Systems with Applications41(3) (2014), 853–860. ISSN 0957-4174, doi:https://doi.org/10.1016/j.eswa.2013.08.015, Methods and Applications of Artificial and Computational Intelligence.

43.

Sierra Martínez

L.M.

, Cobos Lozada

C.A.

and Corrales

J.C.

, Tokenizer adapted for the nasa yuwe language, ComputaciÓn y Sistemas20(3) (2016), 1405–5546.

44.

Styler

, Bethard

, Finan

, Palmer

, Pradhan

and de Groen

, Erickson

, Miller

, Lin

, Savova

and Pustejovsky

, Temporal annotation in the clinical domain, Transactions of the Association for Computational Linguistics2 (2014), 143–154. ISSN 2307-387X.

45.

Sujan Kumar

, Sudeshna

and Pabitra

, Feature selection techniques for maximum entropy based biomedical named entity recognition, Journal of Biomedical Informatics42(5) (2009), 905–911. ISSN 1532-0464, doi:https://dx-doi-org.web.bisu.edu.cn/10.1016/j.jbi.2008.12.012, Biomedical Natural Language Processing.

46.

Sun

, Guan

, Wang

and Lin

, Rich features based conditional random fields for biological named entities recognition, Computers in Biology and Medicine37 (2007), 1327–1333.

47.

Tourille

, Ferret

, Neveol

and Tannier

, LIMSI-COT at SemEval-Task 12: Temporal Relation Identification using a Pipeline of Classifiers, In: Proc. of the 10th International Workshop Semantic Evaluation, (2016), pp. 1136–1142.

48.

Van der Hoek

, and Elliott

R.J.

, A modified hidden markov model, Automatica49(12) (2013), 3509–35019. ISSN 0005-1098.

49.

Veera Raghavendra

, CDE-IIITH at SemEval-Task 12: Extraction of Temporal Information from Clinical Documents using Machine Learning Techniques, In Proc of the 10th International Workshop Semantic Evaluation2016, pp. 1237–1240.

50.

Wan-li

, Xue-lei

, Mei-qing

, Yin-zhen

and Mingxia

, An enhanced differential evolution algorithm based on multiple mutation strategies, Computational Intelligence and Neuroscience (2015).

51.

Wang

, Hussein

M.A.

and Venard

and Bau

, Optimal Sizing of Generalized Memory Polynomial Model Structure Based on Hill-Climbing heuristic, In 2016 46th European Microwave Conference (EuMC), 2016, pp. 190–193. 10.1109/EuMC.2016.7824310.

Extracting medical events from clinical records using conditional random fields and parameter tuning for hidden Markov models

Abstract

Keywords

1 Introduction

2 Related work

2.1 Clinical TempEval

2.2 Other corpora

3 Methodology

Table 1 An overview of THYME corpus used in this study Set Documents Tokens Train 297 131,878 Dev 300 62,159 Test 153 211,347 Total 750 405,384

3.3 Feature extraction

3.4 Classifiers

3.4.1 Hidden Markov model: Viterbi algorithm

4.1 Experimental results for event detection

4.3 A comparison between this study and SemEval: Clinical TempEval 2016

5 Conclusions and future work

Footnotes

Acknowledgments

References

Table 1
An overview of THYME corpus used in this study

Set Documents Tokens

Train 297 131,878

Dev 300 62,159

Test 153 211,347

Total 750 405,384