Improving Neural Entity Disambiguation with Graph Embeddings

Entity Disambiguation (ED) is the task of linking an ambiguous entity mention to a corresponding entry in a knowledge base. Current methods have mostly focused on unstructured text data to learn representations of entities, however, there is structured information in the knowledge base itself that should be useful to disambiguate entities. In this work, we propose a method that uses graph embeddings for integrating structured information from the knowledge base with unstructured information from text-based representations. Our experiments confirm that graph embeddings trained on a graph of hyperlinks between Wikipedia articles improve the performances of simple feed-forward neural ED model and a state-of-the-art neural ED system.

Introduction
The inherent and omnipresent ambiguity of language at the lexical level results in ambiguity of words, named entities, and other lexical units. Word Sense Disambiguation (WSD) (Navigli, 2009) deals with individual ambiguous words such as nouns, verbs, and adjectives. The task of Entity Linking (EL) (Shen et al., 2015) is devoted to the disambiguation of mentions of named entities such as persons, locations, and organizations. Basically, EL aims to resolve such ambiguity by creating an automatic reference between an ambiguous entity mention/span in a context and an entity in a knowledge base. These entities can be Wikipedia articles and/or DBpedia (Mendes et al., 2011)/Freebase (Bollacker et al., 2008) entries. EL can be divided into two subtasks: (i) Mention Detection (MD) or Name Entity Recognition (NER) (Nadeau and Sekine, 2007) finds entity references from a given raw text; (ii) and Entity Disambiguation (ED) assigns entity references for a given mention in context. This work deals with the entity disambiguation task.
The goal of an ED system is resolving the ambiguity of entity mentions, such as Mars, Galaxy, and Bounty are all delicious. It is hard for an algorithm to identify whether the entity is an astronomical structure 1 or a brand of milk chocolate 2 .
Current neural approaches to EL/ED attempt to use context and word embeddings (and sometimes entity embeddings on mentions in text) (Kolitsas et al., 2018;Sun et al., 2015). Whereas these and most other previous approaches employ embeddings trained from text, we aim to create entity embeddings based on structured data (i.e. hyperlinks) using graph embeddings and integrate them into the ED models.
Graph embeddings aim at representing nodes in a graph, or subgraph structure, by finding a mapping between a graph structure and the points in a low-dimensional vector space (Hamilton et al., 2017). The goal is to preserve the features of the graph structure and map these features to the geometric relationships, such as distances between different nodes, in the embedding space. Using fixed-length dense vector embeddings as opposed to operating on the knowledge bases' graph structure allows the access of the information encoded in the graph structure in an efficient and straightforward manner in modern neural architectures.
Our claim is that including graph structure features of the knowledge base has a great potential to make an impact on ED. In our first experiment, we present a method based on a simple neural network with the inputs of a context, entity mention/span, explanation of a candidate entity, and a candidate entity. Each entity is represented by graph embeddings, which are created using the knowledge base, DBpedia (Mendes et al., 2011) containing hyperlinks between entities. We perform ablation tests on the types of inputs, which allows us to judge the impact of the single inputs as well as their interplay. In a second experiment, we enhance a state-of-the-art neural entity disambiguation system called end2end (Kolitsas et al., 2018) with our graph embeddings: The original system relies on character, word and entity embeddings; we replace respectively complement these with our graph embeddings. Both experiments confirm the hypothesis that structured information in the form of graph embeddings are an efficient and effective way of improving ED.
Our main contribution is a creation of a simple technique for integration of structured information into an ED system with graph embeddings. There is no obvious way to use large structured knowledge bases directly in a neural ED system. We provide a simple solution based on graph embeddings and confirm experimentally its effectiveness.

Related Work
Entity Linking Traditional approaches to EL focus on defining the similarity measurement between a mention and a candidate entity (Mihalcea and Csomai, 2007;Strube and Ponzetto, 2006;Bunescu and Paşca, 2006). Similarly, Milne and Witten (2008) define a measurement of entityentity relatedness. Current state-of-the-art approaches are based on neural networks (Huang et al., 2015;Ganea and Hofmann, 2017;Kolitsas et al., 2018;Sun et al., 2015), where are based on character, word and/or entity embeddings created by a neural network with a motivation of their capability to automatically induce features, as opposed to hand-crafting them. Then, they all use these embeddings in neural EL/ED. Yamada et al. (2016) and Fang et al. (2016) utilize structured data modelling entities and words in the same space and mapping spans to entities based on the similarity in this space. They expand the objective function of word2vec (Mikolov et al., 2013a,b) and use both text and structured information. Radhakrishnan et al. (2018) extend the work of Yamada et al. (2016) by creating their own graph based on co-occurrences statistics instead of using the knowledge graph directly. Contrary to them, our model learns a mapping of spans and entities, which reside in different spaces and use graph embeddings trained on the knowledge graph for representing structured information. Kolitsas et al. (2018) address both MD and ED in their end2end system. They build a contextaware neural network based on character, word, and entity embeddings coupled with attention and global voting mechanisms. Their entity embeddings, proposed by Ganea and Hofmann (2017), are computed by the empirical conditional wordentity distribution based on the co-occurrence counts on Wikipedia pages and hyperlinks.
Graph Embeddings There are various methods to create graph embedding, which can be grouped into the methods based on matrix factorization, random walks, and deep learning (Goyal and Ferrara, 2018). Factorization-based models depend on the node adjacency matrix and dimensionality reduction method (Belkin and Niyogi, 2001;Roweis and Saul, 2000;. Random-walk-based methods aim to preserve many properties of graph (Perozzi et al., 2014;Grover and Leskovec, 2016). Deep-learningbased ones reduce dimensionality automatically and model non-linearity Kipf and Welling, 2017). In our case, efficiency is crucial and time complexity of factorization-based models is high. The disadvantage of the deeplearning-based models is that they require extensive hyperparameter optimization. To keep it simple, efficient, and to minimize the numbers of hyperparameters to tune, yet still effective, we select random-walk-based methods, where two prominent representatives are DeepWalk (Perozzi et al., 2014) and node2vec (Grover and Leskovec, 2016).

Learning Graph-based Entity Vectors
In order to make information from a semantic graph available for an entity linking system, we make use of graph embeddings. We use DeepWalk (Perozzi et al., 2014) to create the representation of entities in the DBPedia. DeepWalk is scalable, which makes it applicable on a large graph. It uses random walks to learn latent representations and provides a representation of each node on the basis of the graph structure.
First, we created a graph whose nodes are unique entities; attributes are explanations of entities, i.e. long abstracts; edges are the page links between entities with the information from DBpedia. Second, a vector representation per entity is generated by training DeepWalk on the edges of this graph. For this, we used all default hyper-parameters of DeepWalk, e.g. number-  walks is 10, walk-length is 40, and window-size is 5. To exemplify the result, the most similar 3 entities of disambiguated versions of Michael Jordan, in the trained model with 400-dimension vectors are shown in Table 1. The first entity, Michael Jordan (basketball), is a well-known basketball player, and his all most similar entities are all basketball players and of similar age. The second entity, Michael I. Jordan is a scientist, and again the most similar entities are either scientists in the same field or the topics of his study field. The last entity, Michael Jordan (footballer), is a football player whose most similar entities are football clubs. This suggests that our graph entity embeddings can differentiate different entities with the same name.

Experiment 1: Entity Disambiguation with Text and Graph Embeddings
In our first experiment, we build a simple neural ED system based on a feed-forward network and test the utility of the graph embeddings as compared to text-based embeddings.

Description of the Neural ED Model
The inputs of an ED task are a context and a possibly ambiguous entity span, and the output is a knowledge base entry. For example, Desire contains a duet with Harris in the song Joey and Desire given as an input and the output is Bob Dylan's album entity 3 . Our model in this experiment is a feed-forward neural network. Its input is a concatenation of document vectors of a context, a span, and an explanation of the candidate entity, i.e. long abstract, and graph embedding of a candidate entity as in Figure 1, and output is a prediction value denoting whether the candidate entity is correct in this context. For learning representations, we employ doc2vec (Le and Mikolov, 2014) for text and DeepWalk (Perozzi et al., 2014) for graphs, both methods have shown good performance on other tasks. We will describe the input components in more detail in the following.
Creating Negative Samples: It is not computationally efficient to use all entities in our graph as a candidate for every context-span as negative examples for training because of the high number of entities (about 5 million). Thus, we need to filter some possible entities for each context-span in order to generate negative samples. We use spans to find out possible entities. If any lemma in the span is contained in an entity's name, the entity is added to the candidates for this mention. For example, if the span is undergraduates, the entity Undergraduate degree is added to the candidates.
For training, we generate negative samples by filtering this candidate list and limited the number of candidates per positive sample. We employ two techniques to filter the candidate list. First, we shuffle the candidate list and randomly select n candidates. The other is to select the closest candidates by the following score formula: score = # of intersection×page rank length , where # of intersection means the number of the common words between span/entity mention and candidate entity, page rank is the page rank value (Page et al., 1999) on the entire graph for the candidate entity, and length is the number of tokens in the entity's name/title, e.g. the length of the entity Undergraduate degree is 2. Before taking candidates with highest n scores, we have pruned the most similar candidates to the correct entity on the basis of the cosine between their respective graph embeddings. The reason for pruning is to assure that the entities are distinctive enough from each other so that a classifier can learn the distinction.
Word and Context Vectors: Document embedding techniques like doc2vec (Le and Mikolov, 2014) assign each document a single vector, which gets adjusted with respect to all words in the document and all document vectors in the dataset. Additionally, doc2vec provides the infer vector method, which takes a word sequence and returns its representation. We employ this function for representing contexts (including the entity span),

Desire contains a duet with Harris in the song Joey
Candidate entity's long abstract Figure 1: Architecture of our feed-forward neural ED system: using Wikipedia hyperlink graph embeddings as an additional input representation of entity candidates. entity explanations (long abstracts), and multiword spans.

Experimental Setup
Datasets We have used 80% of these data for training, 10% for development, and the remaining for testing.
Implementation Details: We fixed context, span, and long abstract embedding dimensionality to 100, the default parameter defined in the implementation of gensim (Řehůřek and Sojka, 2010). The size of the graph embeddings is 400. We optimize the graph embedding size based on the development set with the range 100 − 400. The overall input size is 700 when concatenating context, span, long abstract, and graph entity embeddings.
The number of negative samples per positive sample is 10. We have 3 hidden layers with equal sizes of 100. In the last layer, we have applied the tanh activation function. We have used Adam (Kingma and Ba, 2014) optimizer with a learning rate of 0.005 and 15000 epochs. All hyperparameters are determined by preliminary experiments.

Evaluation
The evaluation shows the impact of graph embeddings in a rather simple learning architecture.
In this experiment, an ablation test is performed to analyze the effect of graph embeddings. We have two types of training sets, where the creation of negative samples differs (in one of them, we have filtered negative samples randomly, whereas, in the other, we filtered them by selecting the closest ones, as explained in Section 4.1). In Figure 2, the upper part shows the Accuracy, Precision, Recall, and F1 values of the training set filtered randomly while the lower part results refer to the training set filtered by selecting closest neighbors. The first bar in the charts contains the result of the input, which concatenates context and long abstract embeddings (in this condition the input size becomes 200), here entity information only comes from its long abstract. The second bar presents the results of the input combination, context, word/span, and long abstract embeddings (the size of the input is 300). In the third bar, the input is the concatenation of context, long abstract, and graph embeddings (the input size is 600). Finally, the last bar indicates results for the concatenation of all types of inputs, for an input size of 700. For each configuration, we run the model 5 times and get the mean and standard deviation values. In Figure 2, charts show the mean values and the lines on the charts indicate standard deviation.
Comparing the first and third bars (or the second and last bars) in Figure 2, we can clearly see the results are increased when the input includes the graph embeddings for both variants of negative sampling. Comparing the third and last bars (or the first and second bars), we observe that including the span representation slightly decreases results for both sampling variants. We attribute this to the presence of the context embedding, which already includes the span, thus this increases the number of parameters of the network without sub-  5 Experiment 2: Integrating Graph Embeddings in the end2end ED System

Description of the Neural ED Model
For the second experiment, we have used the end2end state-of-the-art system for EL/ED (Kolitsas et al., 2018) and expanded it with our graph embeddings. In this neural end-to-end entity disambiguation system, standard text-based entity embeddings are used. In the experiment described in this section, we replace or combine them (keeping the remaining architecture unchanged) with our graph embeddings build as described in Section 3. We replaced end2end's entity vector with our graph embeddings and the concatenation of their entity vector and our graph embeddings. We use the GERBIL (Usbeck et al., 2015) benchmark platform for an evaluation.
Implementation Details: We have not changed hyper-parameters for training the end2end system 4 (We used their base model + global for ED setting). We create graph embeddings with the same technique used before, however, to keep everything the same, we decided to also use 300 dimensions for the graph embeddings in this experiment to match the dimensionality of end2end's space.
We create the embeddings file with the same format they used. They give an id for each entity and call it "wiki id". First, we generate a map between this wiki id and our graph id (id of our entity). Then, we replace each entity vector corresponding to the wiki id with our graph embeddings, which refers to the entity. Sometimes there is no corresponding graph entity for the entity in the end2end system, in this case, we supply a zero vector.
They have a stopping condition, which applies after 6 consecutive evaluations with no significant improvement in the Macro F1 score. We have changed this hyperparameter to 10, accounting for our observation that the training converges slower when operating on graph embeddings. Table 2 reports ED performance evaluated on DBpedia Spotlight and Reuters-128 datasets. There are three models, end2end trained using their text entity vectors, our graph embeddings and the combination of them. Training datasets and implementation details are the same for all models. We train  the models for 10 times and removed the models that did not converge (1 non-converging run for each single type of embedding and 2 for the combination). In the Micro-averaged evaluation, the combination model scores slightly below the model using graph embeddings alone.

Evaluation
To summarize the evaluation, our graph embeddings alone already lead to improvements over the original text-based embeddings, and their combination is even more beneficial. This suggests that test-based and graph-based representations in fact encode somewhat complementary information.

Conclusion and Future Work
We have shown how to integrate structured information into the neural ED task using two differ-ent experiments. In the first experiment, we use a simple neural network to gauge the impact of different text-based and graph-based embeddings. In the second experiment, we replace respectively complemented the representation of candidate entities in the ED component of a state-of-the-art EL system. In both setups, we demonstrate that graph embeddings lead to en par or better performance. This confirms our research hypothesis that it is possible to use structured resources for modeling entities in ED tasks and the information is complementary to a text-based representation alone. Our code and datasets are available online 5 .
For future work, we plan to examine graph embeddings on other relationships, e.g. taxonomic or otherwise typed relations such as works-for, married-with, and so on, generalizing the notion to arbitrary structured resources. It might make a training step on the distance measure depending on the relation necessary. On the disambiguation architecture, modeling such direct links could give rise to improvements stemming from the mutual disambiguation of entities as e.g. done in (Ponzetto and Navigli, 2010). We will explore ways to map them into the same space to reduce the number of parameters. In another direction, we will train task-specific sentence embeddings.


Design and Implementation of Fill-in-the-blank Questions based on Open Source Online Judge System

This report discusses the shortcomings of the existing online judge system's problem type, and describes the implementation and applicability of the fill-in-the-blank questions based on the open source online judge system. It is based on the open source online judge system named HUSTOJ, to realize the online judgment function of code-fill-in-the-blank and result-fill-in-the-blank questions by analyzing its system architecture, judgment process and redesigning its database.

Introduction
With the advent of the artificial intelligence era, programming skills have become a research hotspot of education at home and abroad [1]. Recently, in China, the Ministry of Education's newly released "Key Points of Educational Informationization and Cybersecurity in 2019" pointed out that education informationization should become the supporter and leader of education modernization, and it needs to promote the implementation of programming education in primary and secondary schools [2]. However, through years of teaching practice experience, programming education can not effectively reflect the students' programming level through the examination of the face-to-face test. For this reason, the online judge system has been developed to assist teachers in programming teaching [3].
Online judge system originated from ACM International Collegiate Programming Contest (ACM-ICPC). The user can submit the source code of various programming languages (such as C, C++) online, compile and execute it, and verify the correctness of the program source code through predesigned test data [4]. Today, quite a few universities in China have developed appropriate online judge systems, such as POJ, HUSTOJ, ZOJ, XUJCOJ, Lanqiao Cup practice system and more.
The existing online judge system has been perfected to meet the needs of programming teaching in domestic universities. Nevertheless, if these systems are deployed to primary and secondary schools and high school, there will be two obvious shortcomings: -The single type of question is easy for students to lose interest in doing the problem.
-Programming problems are so difficult that they are not suitable for beginners to practice. For the purpose of reducing the difficulty of learning programming and enhancing the interest of beginners in programming learning, this report will add code-fill-in-the-blank and result-fill-in-theblank questions based on the open source system called HUSTOJ. HUSTOJ [5][6] is the online judge system of Huazhong University of Science and Technology (HUST). It was open source under the GPL protocol at the end of 2008. The system architecture consists of two parts: web and core. This report mainly focuses on the modification and extension of the web part.

HUSTOJ System
The HUSTOJ system is deployed with using the LNMP (Linux + Nginx + MySQL + PHP) architecture. The structure of the system consists of a front end and a core judge end, and the two ends share a database to realize data communication between them. The answer submitted by the user will be stored in the database through the web side, and afterward the core will read the data from the database to judge the problem and write the result to the database. This is beneficial to achieve centralized control of data and to ensure data consistency and maintainability. The programming problem of the HUSTOJ system is judged at the core end. The core end polls the queue of pending questions from the database. When the length of the queue is greater than 0, the answer code will be extracted for compilation. If the compilation error occurs, an error is returned. After the compilation is successful, the system will use the test data to verify the correctness of the compiled program, and only when all the test data has passed will it return success. When the answer is completely correct, the system will also check the code for plagiarism.

Design of Fill-in-the-blank Questions
The result-fill-in-the-blank questions are dissimilar from the code-fill-in-the-blank questions. The answer to the result-fill-in-the-blank question is a string, which requires the user to submit a string that cannot contain any other characters including spaces and newlines. It does not require being compiled and it can be directly judged at the web end. It can effectively save system resources and improve the efficiency of judgment. The answer to the code-fill-in-the-blank question is a code. And the system fills it into the missing piece of pre-prepared compilable code and writes it to the database. Therefore, the code-fill-in-the-blank problem needs to be compiled, and the judgment is the same as the programming problem. Both of them are read by the core to evaluate the database.

Design of the Database
There are more than 20 tables in the database of HUSTOJ system. The tables used at the core end are the solution, the problem, the compileinfo, the sim, the users, the custominput, the runtimeinfo, and the source_code . The solution table holds the answers submitted by the user, and the problem  table holds the details of the problem, and the source_code table holds the codes submitted by the  user. Since the table for recording the fill-in-the-blank information cannot affect the original database, in order to effectively manage the fill-in-the-blank problem, the problem_fill and solution_fill tables are added to the original database.
The problem_fill table records the mark of the fill-in-the-blank question, the correct answer to the result-fill-in-the-blank question, the missing code for the code-fill-in-the-blank question, and the missing mark.

The Code Design of the Judgment
After filling the answer of the missing code, the code-fill-in-the-blank passes it to the core end for judgment. When there is more than one code filled in, the system uses md5 to distinguish each answer of the fill-in-the-blank question. The key code is as follows: $

System Testing
The system's judgment is based on the black box test method, and the report will also use the black box test method to test the system. From the test results in Figure 4, it is known that the system after the extended fill-in-the-blank question can achieve the desired effect.

Summary
This paper deeply studied the working principle of the open source online judge system, and added the function of setting the fill-in-the-blank question. The questioner could not only set the programming problem, but also set the result-fill-in-the-blank and the code-fill-in-the-blank question. The system source code after the extended fill-in-the-blank question was stored in the GitHub code repository [7]. In the following research, we could continue to expand other types of questions such as multiple-choice questions and judgment questions. And you could also add other practical features such as school-level exams and contests.


Semi-Automated Sleep EEG Scoring with Active Learning and HMM-Based Deletion of Ambiguous Instances †

: Sleep scoring is an important tool for physicians. Assigning of segments of long biomedical signal into sleep stages is, however, a very time consuming, tedious and expensive task which is performed by an expert. Automatic sleep scoring is not well accepted in clinical practice because of low interactivity and unacceptable error, which is often caused by inter-patient variability. This is solved by proposing a semi-automatic approach, where parts of the signal are selected for manual labeling by active learning and the resulting classiﬁer is used for automatic labeling of the remaining signal. The active learning is disturbed by noisy ambiguous data instances caused by continuous character of the sleep stage transitions and a removal of such transitional instances from the training set prior to active learning can improve the efﬁciency of the method. This paper proposes to use the hidden Markov model for the detection of the transitional instances. It shows experimentally on 35 sleep EEG recordings that such a method signiﬁcantly improves the semi-automatic method. A complete methodology for semi-automatic sleep scoring is proposed and evaluated, which can be better accepted as a decision support tool for sleep scoring experts.

Introduction
Generally, sleep scoring can be defined as an assignment of segments of some biomedical signal into sleep stages. Most typically, the signal is electroencephalogram (EEG) or polysomnogram (PSG) and the sleep scoring is performed manually by an expert. A sleep scoring process produces a sequence of sleep stage labels which can be very useful in evaluation of various disorders like sleep disorders, neurological and cardiological diseases or diabetes. An example of such a sequence, called hypnogram, is depicted in the upper subfigure of Figure 1. The sleep scoring expert must have sufficient skills and practice and thus the sleep scoring task is very time-consuming, tedious, and expensive. Moreover, the expert's fatigue causes labeling errors, subjectivity and higher inter-expert variability. An automatic computer-based sleep scoring system could help to avoid and reduce many of mentioned drawbacks. It can significantly reduce the time requirements, personal costs and errors. After decades of research devoted to automatic sleep scoring, automatic systems are, however, still not widely accepted by physicians and electrophysiologists. This is caused by insufficient accuracy, which is partly caused by high inter-personal variability, where recordings come from different measurement devices and training data are labeled by different experts. Another reason for limited acceptance of fully automated systems is lack of interpretability and interactivity, where the physicians cannot make serious decisions on the basis of non-interactive computer systems not well supported by an interpretable evidence. This paper combines a manual and fully automated system, which makes a trade-off between savings of manual labeling effort and accuracy of the scoring system. By training and operating the automatic classifier on the data from the same patient, the approach removes the problem of inter-personal variability at the expense of an increased manual labeling effort. While there is no manual labeling effort in conventional automatic systems, in the proposed semi-automatic system, part of the signal is labeled manually and used as a training data set for a pattern classifier, which is finally used for automatic labeling of the rest of the signal.
The approach is depicted in Figure 2. It starts with an initial data set consisting of segments of EEG signal that are not scored (are unlabeled). The first step is an initial selection of segments that should be manually labeled by the expert. This initialization is out of scope of this paper and one data segment from each class is randomly sampled at the beginning. Next, an iterative loop runs, where unlabeled segments are selected one by one and manually labeled until a certain sufficiency criterion is met and sufficient training data are formed consisting of a subset of signal segments and their corresponding labels. The sufficiency criterion is irrelevant here because we compare the methods during the first 150 iterations. Nevertheless, it can be an achievement of some validation error threshold. Finally, a classifier is trained and used for classification of remaining segments. Since only a subset of the signal segments is labeled, this approach can significantly reduce the labeling effort and labeling costs, and improve the final scoring result by eliminating mistakes caused by expert's fatigue.  Figure 2. The flow diagram of semi-automated scoring of EEG data.
The main problem of such a semi-automatic method is how to select the signal segments that should be labeled manually. This problem can be solved by active learning approaches well known in pattern classification area [1]. An active learning method typically selects data instances that are worth to be labeled. For example, it reduced labeling time for a clinical concept extraction in [2]. In [3], active learning was used for an efficient labeling of artifacts in EEG signal. The following advantages of involving active learning can be expected: First, a proper selection of training instances can reduce the generalization error, only a subset of available training data need to be labeled which reduces the labeling effort. Second, if the annotator is human, the reduced labeling effort leads to less fatigue-based errors. Third, a smaller training set can significantly reduces the training time and memory requirements.
Active learning has been applied to EEG data in the area of Brain Computer Interface (BCI) [4], where it typically improved classification performance and reduced training set that lead to reduced time and memory requirements. Typically, the active learning is not used in a semi-automatic manner, where the inter-personal variability issue can be overcame or labeling effort reduced. Those two problems are focused in [5], where transfer learning together with semi-supervised learning was considered to calibrate a pre-trained classifier to a specific subject and thus avoid error related to inter-personal variability. The active learning was also used for regression task in [6], where driver drowsiness was predicted from EEG, but its main purpose was an improvement of training set and not reduction of data acquisition costs.
In [7], we proposed an active learning based semi-automatic sleep scoring approach. It was found that the training data instances whose labels differ from the labels of their adjacent instances tend to be noisy since they are hard to be assigned clearly to one of sleep stages. Such ambiguous instances can disrupt the training procedure and especially the active learning approaches, which have a tendency to prefer them by selecting data close to the decision boundaries. Although it was demonstrated that removal of such instances from the training set improves the performance of the semi-automatic system, a crucial problem related to detection of such instances was pointed out. Since the active learning starts with partly unlabeled data, the complete sequence of target labels is unknown and the transitional instances cannot be found by observing difference of the labels of adjacent segments. The paper thus theoretically demonstrated a potential improvement, but did not provide solution for its practical realization. This point is focused in this paper, which proposes to detect the transitions via hidden Markov models (HMMs). The paper follows the experimental scenario from [7], but describes the removal of HMM based transitions instead of label-based transitions. The difference is shown in Figure 1. The instances corresponding to the label transitions are marked as black circles in the upper subfigure. They are simply detected from the sequence of labels provided by expert in fully automatic approaches. This sequence is, however, not available in our approach and thus we propose to train HMM and label the EEG time series by its most probable states. Such an approach detects data instances that correspond to natural transitions in EEG signals and does not need the labeled training data.

Active Learning and Ambiguous Instances
As in [7], this paper focuses on a pool-based sampling scenario of active learning [1], where a pool of unlabeled instances (feature vectors) is given and instances for labeling are sequentially selected. An uncertainty sampling is the most popular and the simplest strategy [8]. It was proposed by Lewis et al. [9]. It is particularly suitable for probabilistic classification models, but it might also be applied to non-probabilistic classifiers [8]. Uncertainty sampling approaches typically use posterior probability p(ω|x) estimating probability that object described by feature vector x comes from the class with label ω. At each iteration of the sampling process, an uncertainty measure is computed from the posterior probabilities. Next, an instance or instances with minimum uncertainty, whose label the classifier is least certain of, is queried. In margin uncertainty sampling proposed by Scheffer et al. [10] the algorithm selects an instance with the smallest difference of the highest and the second highest posterior probability: x * = arg min x p(ω 1 |x) − p(ω 2 |x), where ω 1 and ω 2 is the most probable and the second most probable label of the feature vector x, respectively. Many other variants of uncertainty sampling exist [8] based on entropy or posterior probability. Moreover, many other types of query selection strategies exist like query-by-committee strategy, whose higher time complexity can be an important problem for the user of the semi-automated system.
In many real world pattern classification problems, the labels are often assigned to objects with a certain level of uncertainty. This can happen if the oracle makes mistakes (noisy oracles) or the classes are ambiguously defined (e.g., there are objects belonging to multiple classes and crisp labeling is not sufficient). Such an erroneous labeling can confuse the training procedure and increases a lower boundary for the classification error. Moreover, it causes a high inter-and intra-expert variability. Consequently, it leads to lower acceptance of automatic pattern classification systems by their potential users. Such issues can be solved by the use of soft labels and fuzzy methods. In active learning scenarios, several approaches relevant to such issues were also proposed [11][12][13][14][15].
A typical example of such an issue is the application of active learning to the sleep EEG processing. It is a well known problem that sleep is a process with continuous transitions. Then, the labeling expert (physician) has problems with assignment of the transitional parts of the EEG signal into one particular sleep stage (i.e., to use crisp labels). Such state transitions correspond to the ambiguous data instances. In [7], we observed that such instances are located on the border between different classes. An example is depicted in Figure 3, where a data set with 2 features and four classes is depicted in a scatter plot. Instances corresponding to label transitions from upper part of Figure 1 are highlighted in Figure 3a as black circles. It can be seen that such instances often appear close to the borders between classes. Unfortunately, the majority of current AL techniques (especially most popular query-by-committee and uncertainty sampling) prioritize the border instances and thus the ambiguous instances are often queried for labeling. This can lead to the failure of AL methods.
In [7], only an unrealistic method for detection of transitions based on apriori known labels was considered. Its purpose was to demonstrate that the transitional instances disturb the iterative learning process and their removal can improve the learning. It was assumed that such noisy segments are those, whose labels differ from one of its adjacent segments. Based on this assumptions, all such training instances can be removed, which occur before or after a transition of class labels. However, the unrealistic nature of such an approach is caused by the fact that in the proposed iterative expert-in-the-loop scenario, one does not dispose of labels in advance and cannot use such a detection rule. In [7], this problem was intentionally postponed for future work. Here we provide and analyse a solution of such a problem, based on detection of real transitions directly from unlabeled time series of feature values. To find the unlabeled training instances that correspond to potential transitions between sleep stages, we propose to use HMMs that are popular in EEG and PSG signals processing [16]. Recently, HMMs were used in different manners for sleep EEG artefact detection [17], sleep stage classification [18] or post-hoc refinement of classification results [19].
In our approach, HMM is trained on multidimensional time-series composed of unlabeled training data. It is trained on extracted features rather then on original EEG signals due to much smaller computational requirements. The main aim is to identify inherent state transitions no matter what is the real interpretation of the states. HMM with five states and Gaussian emission distributions was trained using Expectation-Maximization (EM) algorithm. The number of states was chosen empirically corresponding to original number of sleep stages in Rechtschaffen and Kales scoring manual, although the method does not need a clear correspondence between sleep stages and HMM states. After the model is trained, the most probable state sequence is computed from the feature time series using Viterbi algorithm [16]. Regardless of the interpretation of HMM states, the instances whose states labels differ from state labels of adjacent instances are considered as transitions and removed from the training set. An example of such HMM states is shown in the lower part of Figure 1, where the HMM-based transitions are highlighted by black circles. In Figure 3b, the scatter plot with such transitions is demonstrated. One can see that data in stances corresponding to those HMM-based transitions also exhibit a tendency to appear close to the class borders. On the other hand, when comparing the two subfigures of Figure 1, the HMM-based transitions do not fully correspond to label-based transitions both in number and positions. Nevertheless, some similarities can be visually observed.

Experimental Setting
This section first describes the two classification methods that were used -one very simple and one very popular classifier. Further, the EEG data, their acquisition and their processing including feature extraction are described. The methodology of evaluation and comparison of methods is finally described in detail.

Classifiers
Two classifiers were assumed -linear Bayes classifier (LB) and support vector machine (SVM). Observing a feature vector x, Bayes classifiers use Bayes theorem to compute a posteriori probability p(ω|x) of each class from likelihood p(x|ω) and class prior probability p(ω) as p(ω|x) = p(x|ω)p(ω)/p(x). The feature vector x is further assigned into the class that maximizes the a posteriori probability, i.e., the result of classification by classifier γ is γ(x) = arg max ω∈Ω p(ω|x). Uniform prior probabilities and Gaussian likelihoods with equal covariance matrices are assumed that lead to linear decision boundary.
SVM classifier with linear kernel was tested, because of its popularity and reasonable computational time. The training procedure uses quadratic programming to maximize margin, which is a width of the largest 'tube' not containing samples that can be drawn around the decision boundary. For linearly separable data, it can be proven that this particular solution has the highest generalization ability [20] among all linear separating boundaries.

Sleep EEG Data
The recorded data set contains 36 EEG recordings acquired in the National Institute of Mental Health of Czech Republic (NIMH-CZ). Recordings on 18 healthy subjects and 18 insomniac patients are available, while the membership of the patients within those two groups is ignored, but it corresponds to realistic assumption that the semi-automatic labeling will be performed within a clinical practice, where both types of people can occur. Some details about the recorded data can be found in [7].
All data were measured using standard 10-20 montage referenced to mastoids (M1, M2). 19 EEG channels were used for further feature extraction and are also summarized in [7]. All EEG recordings were completely and manually labeled, i.e., sleep classes were assigned to all samples of the signals, by accredited sleep neurologist according to the American Association of Sleep Medicine Scoring Manual (AASM 2012) [21] (classes Wake, N1, N2, N3 and REM). N1 and N2 were merged into one class.
Within the feature extraction, the signals were split to 30 s long segments and 21 features commonly used in EEG sleep staging were extracted for each segment of each channel. This gives 21 × 19 = 399 features in total. The complete list of features and their more detailed description can be found in [7,22]. To increase a robustness and resistance to artifacts we used a median operation over each feature across all EEG channels. Through this process we reduced the number of features from 399 to 21.

Evaluation of Classification Performance
To compare active learning approaches to random sampling strategy (RS) and evaluate the influence of the proposed removal of transitions (RT), we used a mean class error defined as the ratio of incorrectly classified instances from particular class averaged over all four classes. This is actually analogical to 1−sensitivity in binary classification cases. The estimation of true mean class error is performed via hold-out estimate, where all the data instances are randomly split to two disjunctive subsets of the same size that are called training and testing subset. Since our classifier will be used in an intra-personal manner-trained on labeled segments and applied to classification of the rest-the testing is performed on each of 36 patient records separately which gives 36 values of the mean class error for each of the evaluated methods. The methods are further compared using average computed over all patient records. Let e ij is the relative missclassification error obtained for patient i on class j. The mean class error averaged over all 36 patients is defined as: E = 1/36 ∑ 36 i=1 1/4 ∑ 4 j=1 e ij . For a statistical comparison of four active learning strategies on multiple data sets, we use the Friedman test. The test and its application on comparison of classifiers is described in [23]. It is a non-parametric equivalent of the "repeated-measures ANOVA". It can be used for comparison of our 4 algorithms on 36 data sets. The null hypothesis is that there are no differences between the algorithms. For each data set, the algorithms are ranked according to the performance. The best performing algorithm has rank 4 and the worst performing algorithm has rank 1. The Friedman statistics is computed from the average ranks and corresponding p-value is found. If the p-value is lower then a significance level α, the null hypothesis can be rejected.
Once the Friedman test rejects its null hypothesis, one can use a post-hoc procedure to find the particular pairwise differences [24]. According to [25], the Bergmann-Hommel procedure [26] is the most powerful one for pairwise comparisons of classification methods, although it requires more intensive computation. In our experiments, we used an implementation from [25].

Experimental Results
The average learning curves that show the dependence of the performance criterion defined above on the number of labeled instances are depicted in Figure 4. The curve is plotted only for the first 150 sampling iterations. The first reason is that it does not make a sense to use the semiautomatic scenario if the user must label too many segments since the reduction of labeling effort would be too small. The second reason is a better visualization of differences. The following conclusions can be made about the average behavior. First, the random sampling without the removal of transitions (RS) is the worst method during the first 150 sampling iterations for both tested classifiers. On the other hand, the active learning with the removal of transitions (AL/RT) is the best among all tested methods for all tested sampling iterations. For LB classifier, there seems to be nearly no difference between active learning without transitions removal (AL) and random sampling with transitions removal (RS/RT). This means that the removal of transitions makes the random sampling comparable to active learning. Such results show that both the active learning strategy and transitions removal bring some additive benefits. The reduction of labeling effort depends on the user's tolerance of an error. If the user can tolerate 18% error (average error on completely labeled dataset is about 17%), one can see that such an error is reached approximately after 100 iterations. Since the actual number of segments in each record is about 700, the user could label only 15% of segments and 85% of the labeling effort would be saved.  We should point out that all the mentioned observations are the same as those made in our previous paper [7]. Although there is no clear correspondence between HMM-based transitions and label-based transitions (as can be seen in Figure 1), the newly proposed method keeps the main advantages while being practically implementable.
For a better clearness, there were no standard deviations or confidence intervals depicted in Figure 4. To make more credible statistical evaluation, the Friedman test accompanied by Bergmann-Hommel posthoc procedure was used. The average rankings of the particular methods and particular iteration of the sampling process are summarized in Table 1 for both classifiers. It can be clearly observed for LB classifier that the combination of active learning and transitions removal leads to the best average rank for all three tested moments of the sampling process and both classifiers.
For all columns of the table, the p-value computed by the Friedman test suggests that at least one of the four tested methods gives significantly different median than the others at level of significance α = 0.01. When performing pairwise comparisons using the Bergmann-Hommel procedure several statistically significant conclusions can be drawn at level of significance 0.1. First, both AL methods were significantly better than simple random sampling at all three moments of the sampling procedure. Second, AL/RT method outperformed RS/RT method for all moments. Although for SVM there is no sufficient experimental data to reach statistically significant conclusion that AL was improved by transitions removal, for LB classifier AL/RT was significantly better than AL after 40 and 60 iterations. This statistically supports our original hypothesis that the removal of instances that correspond to HMM-based transitions can improve the semi-automatic sleep scoring. This is statistically stronger outcome than in [7] and thus the removal of HMM-based transitional instances seems to be even more promising than the unrealistic removal of label-based transitions.

Conclusions
The paper confirms one conclusion from [7], that the active learning outperforms the random sampling in semi-automatic EEG-based sleep scoring in terms of mean class error. Its main conclusion is, however, a solution of problem of detection of potentially ambiguous data instances that should be not queried for labeling. It was shown that the method based on most probable state sequence of HMM can find data instances whose deletion from training set can statistically significantly improve both the random sampling and the active learning procedure.
An interesting finding is that the HMM-based method supports the active learning better than label-based method. It means that even if all labels would be theoretically known (which does not make a sense), the deletion of label transitions improves the semi-automatic scoring less than the deletion of HMM state transitions. This can be caused by the fact that the transitions provided by human expert do not correspond to real transitions that exist in EEG signal. Such transitions are better detected by HMM method.
Although we demonstrated the use of our method in the sleep staging application, it can be relevant to many other fields. First, if a time series is classified and classes change continuously in transitional manner, the problem with ambiguity can be avoided by the proposed detection and removal of transitions. Second, if it is needed to minimize an interaction with human oracle during training data acquisition, active learning can help to choose data to be labeled efficiently. The combination of those two properties is common in ambient intelligence applications, where adaptive models of time series coming from sensors are often required that avoid an excessive disturbance of human users.