Semi-automatic classification: using active learning for efficient class coverage

FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO Semi-automatic classification: using active learning for efficient class coverage Nuno Filipe Fonseca Vasconcelos Escudeiro Programa Doutoral em Engenharia Informática Supervisor: Prof. Doutor Alípio Mário Jorge Second Supervisor: Prof. Doutor Rui Carlos Camacho October, 2012 Semi-automatic classification: using active learning for efficient class coverage Nuno Filipe Fonseca Vasconcelos Escudeiro Programa Doutoral em Engenharia Informática October, 2012 Resumo Alguns problemas de classificação automática, tais como a classificação de texto, exigem um grande esforço para a etiquetação dos exemplos necessários para treinar um classificador apesar da facilidade e baixo custo envolvidos na recolha de exemplos não etiquetados. Contrariamente à aprendizagem supervisionada, que exige que os exemplos do conjunto de treino sejam todos previamente etiquetados, a aprendizagem ativa é um paradigma em que os exemplos são etiquetados em função da sua utilidade para o fim em vista. Para além da seleção criteriosa dos exemplos a etiquetar, a aprendizagem ativa é um processo iterativo que pode ser interrompido quando o valor acrescentado dos exemplos ainda não etiquetados fôr baixo. De uma forma geral, a aprendizagem ativa requer um esforço de etiquetagem inferior ao da aprendizagem supervisionada. A maioria das abordagens correntes da aprendizagem ativa aplicadas a problemas de classificação assume a existência de um conjunto de exemplos previamente etiquetados, cobrindo todas as classes de interesse. O processo de aprendizagem é inicializado a partir deste conjunto. O esforço necessário para a etiquetação destes exemplos não é, de uma forma geral, contabilizado para efeitos do cálculo do esforço total de etiquetação. No entanto, a identificação de exemplos representativos de todas as classes pode exigir um esforço significativo, em particular, no que refere à identificação de exemplos representativos de classes minoritárias. Acresce que, em alguns domínios, tais como a deteção de fraude e o diagnóstico de doenças raras, por exemplo, estas classes minoritárias podem ser as mais críticas. Nestas circunstâncias, conduzir e avaliar o processo de aprendizagem com base exclusivamente em critérios de precisão, como é comum em problemas de classificação, pode não ser suficiente. De facto, dependendo do enviesamento da distribuição das classes, um classificador pode apresentar uma taxa de erro baixa mesmo desconhecendo por completo as classes minoritárias. O tratamento adequado destes casos requer uma abordagem diferente que assegure, para além da precisão, também a capacidade de reconhecimento de todas as classes independentemente da sua distribuição. Entendemos que é possível desenvolver uma estratégia de aprendizagem ativa que permita construir classificadores precisos, com conhecimento de todas as classes, com um esforço de etiquetação (custo) inferior ao das abordagens atuais. Nesta tese propomos uma estratégia de aprendizagem ativa que inclui um critério de seleção dos exemplos a etiquetar e um critério de paragem que interrompe o processo de aprendizagem quando o valor acrescentado dos exemplos disponíveis para etiquetar é baixo. Esta estratégia promove a eficiência do processo de aprendizagem, focando-se nos exemplos mais informativos e unicamente enquanto o seu valor acrescentado o justifique. O critério de seleção proposto, d-Confidence, agrega a confiança do classificador com a distância entre os exemplos não etiquetados e as classes conhecidas. É um critério que tende a selecionar exemplos de classes desconhecidas, em que o classificador tenha confiança reduzida, que se localizam em regiões inexploradas do espaço de exemplos, a uma grande distância das classes conhecidas. O critério de paragem proposto, hcw, combina dois indicadores do valor acrescentado do i ii conjunto dos exemplos ainda não etiquetados: o gradiente de classificação e um indicador da estabilidade da distribuição da entropia das previsões. O gradiente de classificação fornece informação sobre a diferença nas predições entre duas iterações consecutivas. O indicador de estabilidade da distribuição da entropia das previsões fornece indicações sobre a igualdade das medianas dessas distribuições entre duas iterações consecutivas. Espera-se que esta estratégia permita identificar exemplos de todas as classes, independentemente da sua distribuição, sendo capaz de gerar classificadores precisos com um esforço de etiquetação inferior ao das abordagens atuais. Os resultados da avaliação efetuada mostram que o d-Confidence supera outras abordagens na identificação de exemplos cobrindo todas as classes. Os ganhos são particularmente notórios em presença de distribuições enviesadas. Os classificadores construídos com o d-Confidence apresentam também ganhos ao nível da precisão na maioria dos casos. No entanto, em algumas situações, a redução do esforço de etiquetação necessário para cobrir todas as classes é obtida à custa de uma precisão mais baixa. O critério de paragem aqui proposto apresenta um desempenho superior às restantes abordagens analisadas. É um critério robusto que gera indicações de paragem de forma consistente quando a utilidade dos exemplos não etiquetados ainda disponíveis é baixa. A estratégia de aprendizagem ativa proposta nesta tese, como um todo, incluíndo o critério de seleção e o critério de paragem, gera classificadores precisos, capazes de reconhecer todas as classes, a um custo reduzido em comparação com outras abordagens atuais. Abstract In some classification tasks, such as those related to the automatic building and maintenance of text resources, it is expensive to obtain labeled instances to train a classifier although it is common to have massive amounts of data available at low cost. Unlike supervised learning, that requires a fully pre-labeled training set, active learning allows asking an oracle to label only the most informative instances given the specific purpose of the learning task and the available data. Moreover, active learning is an iterative process that may be halted when the potential utility of the unlabeled instances remaining in the working set is low. Active learning generally requires a lower labeling effort to build accurate classifiers than supervised learning. However, common active learning approaches assume the availability of a pre-labeled set, covering all the target classes, to initialize the learning process. The labeling effort required to build this initialization set is not generally considered when analyzing the performance of the learning process. When in presence of imbalanced class distributions, identifying labeled instances from minority classes might be very demanding, requiring extensive labeling, if queries are randomly selected. Nevertheless, these minority classes are the most critical to certain classification tasks, such as, detection of fiscal fraud and rare diseases diagnosis. In such circumstances, evaluating the performance and building a classifier based exclusively in accuracy might not be appropriate since an accurate classifier might still fail to identify minority classes – the critical ones – with a little impact in accuracy. A novel approach to active learning is required in order to comply with these cases. Besides accuracy, it is also important to assure that the classifier being built is aware of all target classes irrespectively of their distribution. It is our belief that it is possible to develop an active learning strategy that builds accurate classifiers being aware of all the target classes at a reduced labeling effort – that is, at low cost – when compared to current approaches. In this thesis we propose a strategy for active learning that comprises an active learning criterion to select queries and a stopping criterion to halt the learning process when the utility of the remaining unlabeled instances is low. D-Confidence, our query selection approach, is based on a query selection criterion that aggregates the posterior classifier confidence and the distance between unlabeled instances and known classes. This criterion is biased towards instances belonging to unknown classes – low confidence – that are located in unexplored regions in the input space – high distance to known classes. The stopping criterion in our strategy, hcw, is an ensemble of classification gradient and steady entropy mean, two base indicators of the utility of unlabeled instances. Classification gradient provides evidence on the differences of the predicted labels between two consecutive iterations of the learning process. Steady entropy mean provides information on the stability of the distribution of the entropy of predictions between two consecutive iterations. This strategy is expected to identify exemplary instances from all the target classes, independently of their frequency, being able to train an accurate classifier while requiring a reduced labeling effort when compared to common active learning approaches. iii iv The main results from our evaluation show that d-Confidence outperforms state-of-the-art approaches in the identification of exemplary instances from all classes. The improvements are mainly evident in imbalanced data. The accuracy of the classifiers built with d-Confidence improves over other approaches in most situations. However, in some cases, the improved representativeness is obtained at the cost of accuracy. The hcw stopping criterion significantly outperforms other state-of-the-art approaches used for evaluation. It is a robust criterion, triggering consistent stop signs when the utility of the remaining unlabeled instances is low. The d-Confidence strategy as a whole – including both query selection and stopping criteria – generates accurate classifiers, being able to recognize all target classes, with a reduced cost when compared to state-of-the-art approaches. Acknowledgements The last but not the least. One of the first thoughts that came into my mind a few years ago, when I began my PhD, was how nice it must be to have the research concluded, the thesis written and, finally, just have to write the acknowledgments. By that time, I had not a clue on the amount of contributions without which I would have never reached this point. Now, that I am, finally, really writing the acknowledgments, I am experiencing an intense mixture of feelings. I am thrilled for having finished writing, I am nostalgic because one important period in my life is coming to an end and I am anxious waiting for the jury day. For all this, these last pages are as important as the rest (except that I am more relaxed since it will not be subject to review from my supervisors nor will it be subject to discussion with my jury). My name is written in the front page of this thesis. That is a great responsibility. I am just the lucky one representing the efforts from many people who made this possible. My deep thanks, my deep recognition forever are due: To Alípio Jorge, my supervisor, for the opportunity, for all the advice, patience, unconditional support and sharing. To Rui Camacho, my co-supervisor, for all the effort and availability to promptly answer to any request. To Professor Eugénio Oliveira, the Director of the Doctoral Program in Informatics Engineering, for welcoming me and for being always available to solve any problem. To the School of Engineering of the Polytechnic of Porto, ISEP, for granting the funds and the working conditions required to support this thesis. To the Laboratory of Artificial Intelligence and Decision Support, LIAAD-INESC Porto L.A., for hosting me as a researcher and supporting this thesis. To Fernanda Moura, and Embrapa, Empresa Brasileira de Pesquisa Agropecuária, in general for organizing and supporting my stay there, in October 2008, and for the invitation to join the TIENA research project. To Sarabjot Anand and Tao Li, from the Warwick University, for supporting my stay there, in June 2008, and for all our debates and sharing. To Robson Motta, from the Instituto de Ciências Matemáticas e de Computação of the University of São Paulo, for the fruitful cooperation and for being always available to discuss and to share. To Zélia Prior, from the Academic Services of the Faculty of Engineering of the University of Porto, for all the precious help with the bureaucratic hurdles. To Paulo Ferreira, my colleague, for the providential help when I was about to desperate with L A T EX. To my wife, for the constant encouragement, for making me believe when things look unattainable, for teaching me setting priorities, for sustaining everything despite my absence during many important moments. v xii CONTENTS List of Figures 6.1 Uncertainty region (shaded). nrepresents labeled instances from class cnand x represents unlabeled instances. We assume that the concept to learn has three distinct classes, one of which has not yet been identified . . . . . . . . . . . . . . 90 6.2 For equally confident instances prefer those that are far from previously explored regionsininstancespace .............................. 91 6.3 Effect of d-Confidence for class +1 with an SVM classifier. We assume we have labeled instances near the point (0,0)of the bi-dimensional input space. The decision boundary is the diagonal line from (−10,10)to (10,−10)......... 96 6.4 Artificialdatasets .................................. 102 6.5 Class distributions in text corpora . . . . . . . . . . . . . . . . . . . . . . . . . 104 6.6 Progression of instance space coverage as new queries are added. cstands for confidence; dc stands for d-Confidence . . . . . . . . . . . . . . . . . . . . . . . 106 6.7 Instance space coverage on the Iris dataset as new queries are added . . . . . . . 108 6.8 Known classes and generalization error in tabular data (when using SVM as the baseclassifier).................................... 114 6.9 Evolution of the percentage of common selected queries throughout the learning cycle. Each line represents the percentage of common instances for a given pair of strategies (dc-c, dc-ff, c-ff) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 6.10 Known classes and generalization error . . . . . . . . . . . . . . . . . . . . . . 121 6.11 Queries required to identify bunches of distinct classes in NG dataset . . . . . . . 125 6.12 Queries required to identify bunches of distinct classes in R52 dataset . . . . . . 125 6.13 Average gain of d-Confidence over its baseline criteria to first hit classes on R52. Classes are sorted by increasing frequency . . . . . . . . . . . . . . . . . . . . . 126 6.14 Number of classes of a given frequency first found by each criteria on R52 . . . . 127 6.15 Evolution of known classes and error (results from Motta et al.) . . . . . . . . . . 134 6.16 Exploration-Exploitation trade-off . . . . . . . . . . . . . . . . . . . . . . . . . 137 7.1 Total cost sensitivity to B/A, w.r.t. known classes . . . . . . . . . . . . . . . . . 162 7.2 Penaltycostspace.................................. 164 7.3 Symbols representing stopping criteria . . . . . . . . . . . . . . . . . . . . . . . 164 7.4 CostsensitivitytoB/A ............................... 165 7.5 Mean number of iterations, after the first stop has been triggered, required to trigger the stop sign for the third and fifth time . . . . . . . . . . . . . . . . . . . . 168 xiii xiv LIST OF FIGURES List of Tables 6.1 Artificial datasets and their properties . . . . . . . . . . . . . . . . . . . . . . . 103 6.2 Class distribution in tabular datasets . . . . . . . . . . . . . . . . . . . . . . . . 103 6.3 Coverage (Cov), mean number of queries to identify one instance from the unknown class (LDC) and error (Err) with an SVM classifier on artificial data. Mean coverage and error are computed over all iterations in all cross validation folds for every artificial dataset. ff stands for farthest-first, cstands for confidence and dc standsford-Confidence............................... 106 6.4 Artificial datasets sorted by decreasing order of farthest-first coverage . . . . . . 110 6.5 Percentage of inter-cluster to total variance . . . . . . . . . . . . . . . . . . . . 111 6.6 Correlation between inter-cluster/total variance and coverage . . . . . . . . . . . 111 6.7 Micro-averaged number of known classes and error. Means have been computed over all iterations from all cross validation folds for each combination of dataset, classifier and query selection criteria . . . . . . . . . . . . . . . . . . . . . . . . 113 6.8 Mean number of queries required to first hit unknown classes . . . . . . . . . . . 115 6.9 LDCfortabulardatasets .............................. 116 6.10 Average first-hit over under-represented classes at the Poker dataset . . . . . . . 118 6.11 LDC under different imbalance levels. SVM as base classifier. Imbalance is the ratio of the frequency of the minority classes to the rest . . . . . . . . . . . . . . 119 6.12 Micro-averaged number of known classes and error. Means have been computed over all iterations from all cross validation folds for each combination of dataset, imbalance level and query selection criteria. Bold faced values are statistically significantat5% .................................. 120 6.13 Micro-averaged number of known classes and error. Means have been computed over all iterations from all cross validation folds for each combination of dataset, classifier and query selection criteria . . . . . . . . . . . . . . . . . . . . . . . . 122 6.14 First-hit for the NG dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 6.15 First-hit for the R52 dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 6.16 Relative contrast using Euclidean distance . . . . . . . . . . . . . . . . . . . . . 129 6.17 Datasets used by Motta et al. to evaluate active learning criteria . . . . . . . . . . 131 6.18 Mean number of know classes throughout the learning process (Motta et al.) . . . 132 6.19 Mean error throughout the learning process (Motta et al.) . . . . . . . . . . . . . 132 7.1 Drawback of entropy as a stopping criteria . . . . . . . . . . . . . . . . . . . . . 146 7.2 Datasets used to evaluate stopping criteria . . . . . . . . . . . . . . . . . . . . . 149 7.3 Class distribution skewness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 7.4 Tuning process for sek ............................... 151 7.5 Stopping criteria parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 7.6 Ideal iteration to stop querying . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 xv xvi LIST OF TABLES 7.7 Number of iterations to stop . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 7.8 Penalty iterations w.r.t. error . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 7.9 Number of datasets where stopping occurs before/after ideal w.r.t. error . . . . . 155 7.10 Penalty iterations w.r.t. known classes . . . . . . . . . . . . . . . . . . . . . . . 155 7.11 Number of datasets where stopping occurs before/after ideal w.r.t. known classes 156 7.12 Total cost w.r.t. error when A = B = 1 . . . . . . . . . . . . . . . . . . . . . . . 157 7.13 Total cost w.r.t. known classes when A = B = 1 . . . . . . . . . . . . . . . . . . 158 7.14 Criteria rank of penalty cost w.r.t. error . . . . . . . . . . . . . . . . . . . . . . . 158 7.15 P-value for equal means of error penalty cost w.r.t. hcw .............. 159 7.16 Percentage of instances in Wthat are queried before stopping . . . . . . . . . . . 160 7.17 Criteria rank of penalty cost w.r.t. known classes . . . . . . . . . . . . . . . . . 160 7.18 P-value for equal medians of known classes penalty cost w.r.t. hcw ........ 161 7.19 P-value of t-test for equal means of penalty cost w.r.t. hcw ............ 162 7.20 Stopping criteria top performers . . . . . . . . . . . . . . . . . . . . . . . . . . 166 7.21 Ratio between average negative by average positive differences to ideal stop . . . 167 7.22 Query utility as potential error improvement . . . . . . . . . . . . . . . . . . . . 169 7.23 Query utility as potential known classes improvement . . . . . . . . . . . . . . . 169 List of Algorithms 2.1 GeneralALalgorithm................................ 12 3.1 Uncertainty sampling (adapted from (Lewis and Gale, 1994)) . . . . . . . . . . . 36 3.2 Representative sampling (adapted from (Xu et al., 2003)) . . . . . . . . . . . . . 42 3.3 Prototype Based Active Classification (adapted from (Cebron and Berthold, 2009)) 44 6.1 D-Confidencealgorithm .............................. 92 xvii xviii LIST OF ALGORITHMS Abbreviations and Symbols A Cost of querying the oracle for one label A2Agnostic Active learning AL Active learning αSignificance level for statistical tests B Utility of one unlabeled instance in U, the value of the improvement in the performance of the classifier induced by adding a new query to the training set. Opportunity cost for not querying balee BalancedEE C Set of target classes c Refers to confidence in Tables and Figures C4.5 Algorithm to generate decision trees CART Algorithm to generate decision trees cgr Classification gradient stopping criterion CHAD Algorithm to generate decision trees CiSet of target classes known at iteration i,Ci⊆C ckA specific target class, an element of C ClassDist(xj,ck)Aggregation function. Computes dk j, the distance between unlabeled instance xjand all labeled instances belonging to class ck con fi(uj,ck)Posterior confidence on class ckgiven uj cvar Variance model stopping criterion d-Confidence Refers to both the active learning criterion and the active learning strategy proposed in this thesis dc Refers to d-Confidence in Tables and Figures dcon fi(xj,ck)Marginal posterior d-Confidence of class ckgiven xj dCon fi(xj)D-Confidence of instance xjat iteration i dk jDistance between one unlabeled instance xjand all labeled instances belonging to class ck E Oracle, domain expert providing labels on request e Refers to error in Tables and Figures ECOC Error Correcting Output Code EM Expectation Maximization ff Refers to farthest-first in Tables and Figures f hkNumber of queries required to identify the first instance belonging to class ck; first-hit of ck h Hypothesis generated by the learning algorithm, a classifier learned for C HCAC Hierarchical Confidence-based Active Clustering hck Hybrid Classification gradient Kolmogorov-smirnov stopping criterion xix xx ABBREVIATIONS AND SYMBOLS hcw Hybrid Classification gradient Wilcoxon stopping criterion HKLD History Kullback-Leibler Divergence hs Hierarchical Sampling HUS History Uncertainty Sampling i Learning process iteration index IBL Instance Based Learning ID3 Algorithm to generate decision trees IE Information Extraction IR Information Retrieval ISC Intrinsic Stopping Criterion K Number of target classes, #C kc Number of known classes; number of classes that have representative instances in the labeled set, L kff Kernel Farthest First KNN K-Nearest-Neighbors KQBC Kernel Query By Committee LLabeled set, set of labeled instances L1Labeled set at iteration 1, set of pre-labeled instances used to initialize the learning process LDC Label Disclosure Complexity ldc Refers to LDC in Tables and Figures Lk iSet of labeled instances known at iteration ithat belong to class ck maxc Max-confidence stopping criterion MI Exploitation mode mine Min-error stopping criterion MMC Maximal loss reduction with Maximal Confidence MR Exploration mode NNumber of instances in the working set, #W N1Number of pre-labeled instances used to initialize the learning process NER Named Entity Recognition NG Newsgroup dataset nkNumber of instances in the training set that belong to class ck NNET Neural Network ovru Overall uncertainty stopping criterion PBAC Prototype Based Active Classification POS Part-Of-Speech QBC Query By Committee qiQuery selected at iteration i R52 Reuters-21578 dataset RBF Radial Basis Function RPART Decision tree base classifier sek Steady Entropy Kolmogorov-smirnov stopping criterion sew Steady Entropy Wilcoxon stopping criterion simple Query selection criterion that selects the query lying in the SVM margin closest to the dividing hyperplane SVM Support Vector Machine TF×IDF Term Frequency Inverse Document Frequency weighting UUnlabeled set, set of unlabeled instances UCI UCI machine learning repository ABBREVIATIONS AND SYMBOLS xxi V() Variance WWorking set, set of all instances available to learn xjInstance in W yjTrue label of instance xj ˆyjPredicted label of instance xj 6Introduction a necessary stopping condition but not a sufficient one. The ensemble of the two is expected to be sufficient. Our hypotheses were investigated through an empirical research methodology. 1.4 Main results The main results from our experimental evaluation show that d-Confidence exhibits a significant potential to the early coverage of input space. D-Confidence retrieves exemplary instances from all the target classes at a lower cost than its baseline criteria and other state-of-the-art AL approaches. This improvement, in general, has no negative impact on accuracy. In fact, in many cases, there is an improvement in accuracy. In some other cases, the improvement in class coverage is made at the cost of accuracy. D-Confidence is characterized by a dynamic shift between exploration and exploitation that arises from its nature and does not require any tuning, that is, no overhead cost. The compromise between exploration and exploitation is balanced by the geometrical properties of the input space itself. This characteristic of d-Confidence gears a faster coverage of the input space while simultaneously generating accurate models. Concerning the stopping criteria, our evaluation indicates that the hybrid criteria proposed in this thesis outperform the other stopping criteria under evaluation. There is a clear dominance of hybrid criteria, notably hcw, regarding both cost and predictive ability. 1.5 Thesis structure The remaining of this thesis is organized in seven chapters. Chapters 2 and 3 refer to the stateof-the-art of the AL field. In Chapter 2 we review this field of machine learning analyzing its evolution from its inception in the 80s. Then, in Chapter 3 we describe in more detail two aspects of AL that are fundamental to our work – query selection strategies and stopping criteria. Chapter 4 reviews the main techniques in text classification. We refer to the pre-processing phase, reviewing the preliminary aspects required for the automatic processing of text documents. These include text preparation and models for text representation. Next, we review common text classification settings, text classifiers and performance indicators. 1.5 Thesis structure 7 Chapter 5 elaborates a formal description of the problem studied in this thesis, providing a general setting to promote discussion and further developments. Chapters 6 and 7 are core to this thesis. They describe in detail our main contributions and the evaluation of d-Confidence and the stopping criteria. The reader is assumed to be familiar with the formal description of d-Confidence provided in Chapter 5. In Chapter 8 we review the main contributions and describe opportunities for further research arising from our work. 8Introduction Chapter 2 Active Learning Retrospective Machine learning (Mitchell, 1997) is a scientific field of artificial intelligence. It covers the research and development of models and computer algorithms based on patterns extracted from empirical data. In this thesis we address one of the major areas of machine learning: classification problems. In a classification problem, labels – the classes – are assigned to instances. Class labels come from a predefined set, previously established by the user. The assignment of classes to a given instance is done by a classifier, based on a classification model. The classifier is inferred by a learning algorithm from the empirical data. The models1are constructed from a subset of the instance space – the training set. Classification models are hypotheses of the target concept that are consistent with the observed training instances – as perceived by the learner given evidence on the target concept. In the context of this thesis we assume that instances are described by a set of features. 2.1 Machine learning settings There are several machine learning settings suited for classification each with its own pros and cons given the specific problem at hand. 1Instance based learning (IBL) is a specific learning setting that does not require the induction of a model. IBL just stores the training set that, in classification problems, is somehow used to assign labels to instances. 9 10 Active Learning Retrospective Supervised learning This is a setting where the learner generates hypotheses mapping the input features – the set of features describing instances – to a pre-established set of classes (Cunningham P, 2008). Supervised learning algorithms require a set of pre-classified (pre-labeled) instances from which the learner generates the hypotheses. The need to have a fully labeled training set is a major drawback of such a setting, especially when the cost of labeling is high. Unsupervised learning This setting does not require any pre-labeling; learning is achieved exclusively from the input features (Ghahramani, 2004). Unsupervised algorithms seek to realize what is the underlying structure governing the input features’ space. Unsupervised learning generates models relying on the most salient patterns found in the input feature space which may not properly map the target concept. Unsupervised classification algorithms (Karakos et al., 2005; Sona et al., 2006; Sigogne and Constant, 2009) are commonly based on clustering techniques which, in the specific field of text categorization, assume the clustering hypothesis (van Rijsbergen, 1979) – documents having similar content are also relevant to the same topic. Unsupervised learning does not require any labeling but users have no chance to tailor clusters to their specific needs and there is no guarantee that the induced clusters will be aligned with the classes to learn. This lack of guidance towards user needs during the training phase is a major drawback of unsupervised algorithms from the point of view of the work presented in this thesis. Semi-supervised learning The learning settings above rely exclusively on a fully labeled dataset – in the case of supervised learning – or on a completely unlabeled one – unsupervised learning. Combining both labeled and unlabeled data to take advantage of this combination, and to leverage the information contained in unlabeled data, is the goal of semi-supervised learning (Nigam et al., 2000; Chapelle et al., 2006; Zhu, 2008; Zhu and Goldberg, 2009). Semi-supervised algorithms usually rely on a small set of labeled data and a large set of unlabeled data. A simple heuristic approach to semi-supervised learning consists in a two step learning process. In the first step a classifier is trained based on the labeled data only. This classifier is then used to classify unlabeled data. The instances where the current classifier is most confident about are added to the labeled set assuming the predicted labels are correct. 2.2 Active learning 11 Active learning In supervised learning the training set can be obtained by some method, such as random sampling, without any arbitration by the learning algorithm, in which case we refer to passive learning, or by some specific sampling criterion under control of the learning algorithm, biased according to some desirable properties of the training set, in which case we refer to active learning. Active learning (Angluin, 1988; Cohn et al., 1994; Roy and McCallum, 2001; Muslea et al., 2006) is a particular form of supervised learning where instances to label are selected by the learner through some criteria aimed at reducing the labeling complexity (Hanneke, 2007). Labeling complexity is defined as the number of label requests that are necessary and sufficient to learn the target concept. 2.2 Active learning Several classification tasks – for instance those involving unstructured data, such as, speech recognition, text and Web pages (Settles, 2009) categorization, images and music retrieval and filtering – require efficient classification algorithms due to the high labeling cost, on one side, and the vast amount of available, but unlabeled, data, on the other. Efficiency in such circumstances refers to a trade-off solution between high accuracy and comprehensiveness, on one hand, and low labeling effort, on the other. Active learning (AL) is an appropriate learning setting for this scenario given the chance to develop learning strategies aiming at a desirable trade-off. In AL, the learner is allowed to ask an oracle (typically a human) to label instances – these requests are called queries. The most informative queries, given the goals of the classification task, are selected by the learning algorithm unlike passive learning where training instances are selected at random. AL can be performed in several distinct settings which will be covered in Chapter 3. The core idea in AL is to estimate the value of labeling unlabeled instances. The general learning process in Algorithm 2.1 is the basis for AL classification. Referring to Algorithm 2.1, Wis the working set, a representative sample of instances from the problem space. Liis a subset of W. Members of Liare the instances in Wwhose labels are known at iteration i. At iteration i,Uiis the (set) difference between Wand Li,Ui=W\Li, i.e., the set of unlabeled instances in the working set; hirepresents the classifier learned at iteration i; qiis the query selected by the active learner at iteration i. A specific instance is represented by 12 Active Learning Retrospective Algorithm 2.1 General AL algorithm 1: Input: W, set of unlabeled instances xj;fq() query utility function 2: Output: hi, learned classifier 3: 4: Initialize L1,U1from W 5: i=1 6: while stopping criteria does not hold do 7: hi=learn(Li), generate classifier hiusing current labeled set Li 8: Use hito classify instances in the current unlabeled set Ui 9: qi=argmax xj fq(xj),xj∈Ui, select qi=xj∈Uimaximizing query utility 10: Ask the oracle for the label of xj,yj 11: Li+1=Li∪<xj,yj> 12: Ui+1=Ui\xj 13: i++ 14: end while 15: return hi <xj,yj>where xjis the set of descriptive features and yjis its true class (label). All AL approaches analyze unlabeled instances and select the most useful ones once labeled. The general idea of AL is to estimate the value of labeling unlabeled instances, i.e., the value of queries. Query selection may be based either on a generative strategy (Angluin, 1988) or on a discriminative strategy (Li et al., 2010). In a generative strategy – the query construction paradigm – queries are artificially synthesized (Angluin, 1988; Baum, 1991). Generative strategies are suitable for the case where artificially synthesized instances make sense to the oracle providing labels. This assumption makes generative AL strategies unsuited for the generality of unstructured data domains as is the case of text corpora. Discriminative strategies – the query filtering paradigm – select queries from a given distribution. These strategies are suitable when the distribution of the available data might be different from the target distribution and also when artificially synthesized instances are not meaningful to the oracle as is usual in text categorization relying on the bag-of-words model (Harris, 1954). Two approaches are common under the query filtering paradigm: pool based active learning (Lewis and Gale, 1994; McCallum and Nigam, 1998) – where queries are selected from a static pool of data – and stream based active learning (Zhu et al., 2007, 2010c; Chu et al., 2011) – processing data streams and deciding online whether or not to query each new incoming instance. Applying AL techniques to classification involves a set of specific challenges that add to the 2.3 A retrospective view 13 common issues arising in general classification problems. In general, automatic classification involves a number of distinct tasks, including the definition of the main goal of the learning process, setting the evaluation procedure, gathering training and test sets, defining the data representation model, selecting and tuning the most adequate learner. Specific AL challenges include: retrieving an initial set of labeled instances, establishing the query selection criteria, establishing the stopping criteria, agreeing on a compromise between exploration – finding representative samples in the dataset that are useful to label, focusing on completeness – and exploitation – sharpening the classification boundaries, focusing on accuracy. Decisions on these issues are directed by the goals of the classification problem at hand. These aspects of AL are addressed in the following sections. 2.3 A retrospective view Research in AL became popular in recent years. The massive quantity of digital information that has become widely available during the last years triggered its popularity. Nevertheless, the AL paradigm, applied to machine learning, has been in use for over 30 years. In 1984, Valiant describes machine learning – the process of “knowledge acquisition in the absence of explicit programming” – as consisting of (i) an information gathering mechanism and (ii) a process to explore the concept space that can be learned in a reasonable (polynomial) number of steps (Valiant, 1984). Performance and learnability are concerns already perceived from this remark on “reasonable” complexity. It is worthwhile noting the core role assumed by the information gathering mechanism in machine learning, from its inception. AL contributes to the feasibility of the learning process by reducing the extent of the input needed to learn. In this work from Valiant, the learning paradigm is extended to include queries, in the current sense of the term in AL – the learner supplies a set of feature’s values and asks for an output that is provided by an oracle. In the following we will describe the most relevant landmarks of AL in the machine learning field. 14 Active Learning Retrospective 2.3.1 Inception, 1980’s The term active learning has been originally coined in the educational field in 1991, as a corollary of the broad discussion around instructional paradigms that occurred during the 80’s, referring to the instructional activities involving students in doing things and thinking about what they are doing (Bonwell and Eison, 1991). In the educational field, AL has always been associated to seeking new information, organizing it in meaningful ways and further exploiting it (Allen D., 2005), the very same concerns of the machine learning field. Learning from queries, 1981 A few years earlier, during the 80’s, the paradigm had already been applied to machine learning, although not explicitly tagged as AL. In 1988, Dana Angluin (Angluin, 1988) proposes a formal framework to organize and study several types of queries and their value for machine learning tasks. Six distinct types of queries were established: membership, equivalence, subset, superset, disjointness, and exhaustiveness queries. The answer for each one of these queries, except for the membership type which returns a single Boolean (True/False), is composed by a Boolean result and a counterexample in case of a negative answer. Before that, a few learning systems based on queries had been proposed. For instance, in 1981, Shapiro (Shapiro, 1981) and, in 1986, Sammut et al. (Sammut and Banerji, 1986) both propose generative approaches to learn new concepts from previous knowledge. However, Dana Angluin did the first formal description of the AL paradigm in the machine learning field. Farthest-first, 1985 One of the baseline criteria in our work, farthest-first was introduced in 1985 (Hochbaum and Shmoys, 1985) to find an efficient sub-optimal solution to the k-center problem2. In this approach, an initial instance is selected at random. From there on, we select the instance that is farther apart from the previously fetched instances until we have kinstances. These kinstances – collectively known as the farthest-first traversal of the data – are set as cluster centers. The remaining instances are then assigned to the closest center. The distance between 2The k-center problem is defined as follows (Miheliˇ c and Robiˇ c, 2005): Let G = (V, E) be a complete undirected graph with edge costs satisfying the triangle inequality, and k be a positive integer not greater than |V|. For any set S⊆Vand vertex v∈V, define d(v, S) to be the length of a shortest edge from v to any vertex in S. The problem is to find such a set S⊆V, where |S|≤k, which minimizes maxv∈Vd(v,S) 2.3 A retrospective view 15 an instance and a set is the minimum distance between the instance at hand and each of the instances belonging to the set. Farthest-first traversal may provide a set of seeds to build hierarchical clustering with certain performance guarantees (Dasgupta and Long, 2005). Learnability, 1988 In 1998, Pitt et al. focus on learnability issues, stating that some concepts are not learnable just by instances when we have no prior knowledge on the base distribution (Pitt and Valiant, 1988). This same problem is discussed by Eisenberg and Rivest (Eisenberg, 1991), that set a bound on the degree to which membership queries (Angluin, 1988) may improve generalization when the underlying distribution is unknown. 1988 was also the year of the seminal paper from Dana Angluin (Angluin, 1988) setting for the first time a formal framework for AL in the field of machine learning. In 1990, Kinzel et al. (Kinzel and Ruján, 1990) show evidence on the ability of simple perceptron learners3to strongly enhance generalization by allowing the network itself to select the training examples. In 1991, Baum (Baum, 1991) proposes a hybrid algorithm that learns a binary classifier from pre-labeled instances and artificially synthesized queries. Two groundwork instances – one positive and one negative example – are randomly selected from the pre-labeled set to start with. Then, a query is generated half way between those two. This generated instance is labeled by the oracle and replaces the previous groundwork instance with the same label. The process iterates reducing the distance between the selected instances and the separating hyperplane in each and every iteration. 2.3.2 Rudiments, early 1990’s Selecting queries based on the distance to labeled instances, farthest-first, or on the posteriors generated by the current classifier, uncertainty sampling, are, together with Query By Committee, among the main groundwork approaches to AL. In the early 90’s, AL is explicitly assumed as a research area in the machine learning field. 3A perceptron is a simple type of neural network, developed in late 50’s and early 60’s mainly by Frank Rosenblatt, that deploys a linear binary classifier. 22 Active Learning Retrospective on a single base classifier, as is common, Baram et al. (Baram et al., 2004) propose an approach that relies on an ensemble of base classifiers. The AL process is governed by an algorithm that combines these base learners by evaluating their individual performance and dynamically switching to the best performer at each iteration. Batch mode revisited, batch diversity, 2003 Batch mode AL is a learning approach that is adequate when the training cost is high. Another motivation to add more than one query to the training set at each iteration is to avoid annoying the user with many consecutive iterations of a single query that might have a negligible improvement in the inferred classification model, not really observable by the user (Chen et al., 2010). In batch mode, instead of retraining at each single query – the traditional AL setting, retraining is done after having queried a batch of instances. This approach poses a new problem. The issue is that diversity within the batch of instances to query is required to avoid querying redundant instances. This desirable diversity is not assured by just selecting the top mmost informative instances as seen by the current learner (Schohn and Cohn, 2000; Warmuth et al., 2002). Specific care is needed to assure that all batch members add value on top of the rest. In 2003, Brinker (Brinker, 2003) proposes a new batch mode approach to AL that incorporates a diversity measure while selecting batch members. This approach selects the queries lying close to the decision boundary that have the largest angles to previously selected candidates. Brinker’s approach outperforms previous AL approaches using SVM base classifiers. Hoi et al. (Hoi et al., 2006) suggest a batch mode approach relying on the Fisher information matrix (Papathanasiou, 1993) to reduce redundancy among selected instances. Li et al. (Li and Sethi, 2006) compute diversity within selected instances from their conditional error. Hoi et al. (Hoi et al., 2009) propose semi-supervised SVM batch mode, a new batch mode approach with two objectives in mind: to increase the number of training instances and to assure their diversity to improve SVM performance. Semi-supervised SVM batch mode first learns a kernel function from labeled and unlabeled data. Then, this function is used to identify the most informative and diverse instances to query. Rare category detection, 2004 Pelleg (Dan Pelleg, 2004) describes a novel AL scenario that addresses a very similar problem to our own. Pelleg explores AL with the purpose of identifying 2.3 A retrospective view 23 rare categories – experiments are reported with rare categories having as few as 0.002% instances in the data pool – in a setting where no labeled instances from these classes are present in the initial training set. Our work is somehow more general than this one. We focus on gathering exemplary instances for all the classes to learn – irrespective of their frequency – in the absence of any pre-labeled instances, at low labeling cost. The authors propose an interleaving strategy based on a mixture model to fit the data and relying on the degree of ownership of each mixture components w.r.t. unlabeled instances. In each iteration, a batch of 50 instances is selected based on four selection criteria, one of which is the proposed interleaving strategy. No care to avoid redundancy in the batch composition is suggested. Hierarchical sampling, proposed by Dasgupta et al. (Dasgupta and Hsu, 2008) in 2008, was also applied to the detection of rare categories. The authors report significant gains in the number of queries that are required to discover at least one instance from each class. This latter work is also in line with our own efforts for devising a method capable to swiftly identify instances from unknown classes. Preliminary results have been published by us also in 2008 in a workshop paper (Escudeiro and Jorge, 2008). Class probability estimates, 2004 The most common use of AL is probably in classification problems, aiming at maximizing accuracy. In many situations, however – for instance, when in presence of unequal misclassification costs – computing class probability estimates is more useful than aiming at high accuracy. Class probability estimates are used to evaluate the expected utility of a set of alternatives, assuming particular relevance in decision making. A few works on the application of AL to class probability estimates show empirical evidence on the improvements assured by active selection of queries. BOOTSTRAP-LV (Saar-Tsechansky and Provost, 2004) requires less labeled instances to produce accurate class probability estimates when compared to the traditional uncertainty sampling strategy (Lewis and Gale, 1994). Melville et al. (Melville et al., 2005) improve over the previous work by using the Jensen-Shannon divergence as a measure of the utility of new queries. 24 Active Learning Retrospective 2.3.4 Exploring new directions, early 2000’s Application of AL in stream-based settings and the scalability of QBC are among the new directions addressed by AL research in the early 2000’s. Theoretical essays, trying to provide a sound theoretical ground for AL, were also a concern. Clustering approaches, 2004 Clustering has also been considered to provide an initial structure to data or to suggest valuable queries. In 2004, Basu et al. (Basu et al., 2004) used AL based on farthest-first to provide labeled data in a semi-supervised clustering setting (Basu et al., 2002). They actively acquire a set of mustlink and cannot-link constraints to improve the clustering process. Empirical results over UCI data (Frank and Asuncion, 2010) and text corpora, show that the proposed AL strategy improves over random pairwise queries. In 2004, Nguyen et al. (Nguyen and Smeulders, 2004) incorporate clustering into AL by learning a classification model from the set of the cluster representatives, and then propagate the classification decision to the other instances via a local noise model. The proposed model allows to select the most representative instances as well as to avoid repeatedly labeling instances in the same cluster. Adami et al. (Adami et al., 2005) merge clustering and oracle labeling to bootstrap a predefined hierarchy of classes. Although the original clusters provide some structure to the input, this approach still demands for a high validation effort, especially when these clusters are not aligned with class labels. Huang et al. (Huang et al., 2008) explore the Wikipedia5as a background knowledge base to create a concept-based representation of a text document enabling the automatic grouping of documents with similar themes. The semantic relatedness between Wikipedia concepts is used to find constraints for supervised clustering using AL. In 2008, Dasgupta et al. (Dasgupta and Hsu, 2008) propose hierarchical sampling, a clusterbased method that consistently improves label complexity over supervised learning by detecting and exploiting clusters that are loosely aligned with class labels. Their method starts with a hierarchical clustering of the unlabeled pool. Then, random samples from each node of a partition of 5http://en.wikipedia.org, accessed on October 2012 2.3 A retrospective view 25 the data, given by a pruning of the tree, are queried. Their labels are used to compute the purity of each node in the partition. Nodes with low levels of purity are replaced by their child nodes. This process can be halted whenever required, for instance when a given purity level is achieved at each node. At each iteration, the sampling strategy favors less pure nodes. Hu et al. (Hu et al., 2009), motivated by similar concerns, propose an AL schema, based on graph-theoretic clustering algorithms. Their approach aims to suppress the lack of ability of common AL approaches to query instances that belong to new classes, that have not yet appeared in the training set. This motivation is common to our own. The AL setting in general is considered to be an appropriate setting for learning from imbalanced data (Kapoor et al., 2010a). Xu et al. (Xu et al., 2003) proposed representative sampling in 2003. Representative sampling is an AL method that applies k-means clustering to the unlabeled instances lying within the SVM margin and select the cluster centroids for labeling. Their proposal significantly outperforms SVM AL - selecting the unlabeled instance that is closer to the separating hyperplane (Tong and Koller, 2002) – and random sampling at the initial stages of the learning process. However, after a number of iterations, in some cases, SVM AL outperforms representative sampling. According to the authors, this poor performance is probably due to the poor clustering structure of the unlabeled instances within the SVM margin when the margin is getting exhausted. Donmez et al. (Donmez et al., 2007) noticed that uncertainty based approaches tend to disagree with density based approaches when selecting queries for AL. Due to their nature, uncertainty based approaches perform well when in presence of a large labeled set and poorly when in presence of few labeled instances. The opposite behavior is observable in density based approaches. Donmez et al. (Donmez et al., 2007) propose a method, in 2007, that mixes density and uncertainty components to take advantage of their best performance at each particular situation. Their method dynamically updates the selection strategy parameters based on the estimated future residual error reduction. Scalable QBC, 2005 Gilad-Bachrach et al. (Gilad-bachrach et al., 2005) introduce Kernel Query By Committee, (KQBC), a novel QBC algorithm that is able to learn large scale problems by using 26 Active Learning Retrospective AL. KQBC projects the input feature space into a low dimensional space to reduce the cost of query selection. The authors reported improved performance over traditional QBC. Instance deletion, filtering out irrelevant instances, 2005 The former work of Lewis et al. on uncertainty sampling (Lewis and Gale, 1994) was extended by Becker et al. (Becker and Osborne, 2005) in 2005. In this later work, a two-stage method is proposed. In the first stage the instances that cannot be reliably selected using uncertainty sampling are filtered out. At the second stage, uncertainty sampling is applied to the remaining reliable instances to select queries. Empirical results support better performance of this method when compared to pure uncertainty sampling. A similar motivation – filtering out irrelevant instances that will most probably generate wasted queries – is present in Mazzoni et al. (Mazzoni et al., 2006). They propose relevance bias that combines the query selection criteria in use with the output of a relevance classifier, trained in parallel, to favor instances that are likely to be both relevant and informative. Queries are ranked by the product of the output of the active learner, normalized to [0,1], by the probability of relevance, the output of the relevance classifier. Three query selection criteria have been evaluated – simple margin (Tong and Koller, 2002), MaxMin margin (Tong and Koller, 2002) and a batch mode strategy assuring diversity among the selected instances (Brinker, 2003) – and compared to random query selection. The authors define probabilistic AL, a variant of the base query selection criteria that sorts unlabeled instances by the query selection criteria and then selects a random sample among the top 10% instead of selecting the top-ranked query. The rationale for this procedure is based on the heuristic nature of the query selection criteria in use that does not assure optimal query selection. Besides, the differences in the value of the selection criteria among the top-ranked queries might be non-significant. For these reasons, the top-ranked query might not be the optimal one and a random sample of the most probable candidates might be valuable. Despite the fact that there is no justification for the threshold that the authors use – 10% of the top-ranked instances – and that this threshold is independent of the data and, particularly, of the variance of the utility of those 10% top-ranked instances, improvements in performance are observed when compared to strict base criteria. Stream-based active learning, 2005 We must go back a few years to review one of the former approaches to stream-based AL. In 1997, Helmbold et al. (Helmbold and Panizza, 1997) discussed 2.3 A retrospective view 27 the trade-off between the cost of requesting a query and the cost of errors in a stream-based setting – referred by label efficient learning. Further approaches to stream-based, or online, AL include recent research efforts like the work from Bianchi et al. in 2005 and 2006 (Cesa-bianchi et al., 2005; Cesa-Bianchi et al., 2006) and more recent work from Dasgupta et al. in 2009 (Dasgupta et al., 2009) and Chu et al. in 2011 (Chu et al., 2011). The dynamic nature of data streams – increasing data volumes and evolving decision concepts – poses new challenges to stream-based AL. Between 2007 and 2010, Zhu et al. (Zhu et al., 2007, 2010c) introduce a minimum-variance principle to guide instance labeling from data streams based on an ensemble of classifiers. A weight updating rule is derived to ensure a proper adjustment to drifting concepts in the data stream. Theoretical essays, 2005 In 2005, Dasgupta (Dasgupta, 2005) defined theoretical bounds showing that AL has exponentially smaller label complexity than supervised learning under some particular and restrictive constraints. Kääriäinen extended this work by relaxing some of those constraints (Kääriäinen, 2006). An important conclusion of this later work is that the gains of AL are much more evident in the initial phase of the learning process, after which these gains degrade and the speed of learning drops to that of passive learning. In 2006, Balcan et al. propose Agnostic Active learning (Balcan et al., 2006), A2.A2achieves an exponential improvement over the usual label complexity of supervised learning in the presence of arbitrary forms of noise. This model is further studied by Hanneke (Hanneke, 2007), in 2007, who sets general bounds on label complexity. In 2007, Castro et al (Castro and Nowak, 2007) show theoretically that, in a classification task, AL outperforms passive learning achieving a faster rate of classification error decay irrespective of the behavior of the posterior probability in the vicinity of the decision boundary and of the complexity of the Bayes decision boundary. 2.3.5 Modern active learning, late 2000’s to early 2010’s Relaxing the base assumptions of AL sets the ground for proactive learning, a generalization of the former. AL can be particularly beneficial to applications depending on unstructured, highdimensional data, like text and video. The compromise between exploration and exploitation is 28 Active Learning Retrospective also being addressed. Variable labeling costs, 2005 Cullota et al. (Culotta and McCallum, 2005) introduce variable labeling costs applied to information extraction (IE) (Cowie and Lehnert, 1996). They propose a new AL paradigm which reduces not only the number of instances to label but also the difficulty in labeling each one of them. The proposed strategy provides a way to quantify the number of actions a user must perform to label each training example, distinguishing between boundary annotations – boundary or segmentation in IE is the task performed to define the limits of an entity in a sequence of text – and classification annotations – classifying in IE is the task performed to assign a class to an entity in a pre-segmented text. Boundary annotations are usually more demanding than classification annotations. SVM base classifiers, 2006 Most of the AL methods relying on SVM as base classifiers query for instances based on their distance to the current separating hyperplane. Mitra et al. (Mitra et al., 2004) extended this common approach by introducing to SVM an adaptive confidence factor estimated from local information using k-nearest-neighbor principles. Their method, motivated by the statistical query model of learning (Kearns, 1998), selects a batch of queries according to a distribution that is determined by the current separating hyperplane and by this adaptive confidence factor, enabling more robust and efficient learning capabilities. Cesa-Bianchi et al. (Cesa-Bianchi et al., 2006) introduced, in 2006, a label efficient method of selective sampling for linear classifiers that requests for the label of a given instance with a probability that is a function of its distance to the dividing hyperplane. This probability is higher when the distance to the hyperplane is lower. When this distance is 0, the current model has a confidence of 0 on the instance label, and the probability of asking a query is 1. Sculley (Sculley, 2007) proposes logistic margin sampling, a similar heuristic to the previous work from Cesa-Bianchi et al. (Cesa-Bianchi et al., 2006) but that models the sampling probability using a logistic regression of the distance to the dividing hyperplane. Both these heuristics are compared to the so-called fixed margin sampling, proposed by the authors, that simply requests a label for an instance when its distance to the dividing hyperplane is below a given preset threshold. 2.3 A retrospective view 29 Multi-label classification, 2006 AL is most frequently used in single-label classification tasks. Uncertainty sampling, for instance, focuses on measuring the confidence of the most probable class. Expected error reduction strategies are based on an error estimate for one single class. QBC select the instances where the current committee has the biggest disagreement w.r.t. the top class. There are some previous approaches of AL to multi-label classification (Brinker, 2006), frequently applied to image retrieval (Li et al., 2004; Qi et al., 2009). However these approaches are not adequate for text classification, as reported by Yang et al. (Yang et al., 2009) in 2009, either for exhibiting poor performance when applied to text corpora or for requiring reading and labeling the same document several times, which might be reasonable for images but very costly for text documents. Yang et al. (Yang et al., 2009) propose an AL approach to deal with multi-label text classification. The AL component selects queries based on the Maximum loss reduction with Maximal Confidence (MMC) criteria as defined by the authors. Esuli et al. (Esuli and Sebastiani, 2009) propose several AL strategies for multi-label classification tasks, evaluating them on text corpora, each one combining the outputs returned by individual binary classifiers as a result of classifying a given unlabeled document. Both of these approaches to multi-label text classification (Yang et al., 2009; Esuli and Sebastiani, 2009) are based on a set of binary classifiers, one for each class to learn. Exploration versus exploitation, 2006 Kai Yu et al. (Yu et al., 2006) propose transductive experimental design, an AL approach applied to regression (Hastie et al., 2003). Their work is focused on experimental design, and denotes concerns related to the exploratory aspects of AL (Thrun, 1998). Transductive experimental design searches for queries that are simultaneously hard to predict – addressing exploitation – and representative of the unexplored data – addressing exploration. In 2009 Cebron et al. (Cebron and Berthold, 2009), introduce Prototype Based Active Classification (PBAC), an AL algorithm for classification that evaluates the potential of each instance based on a combination of its representativeness and the uncertainty of the classifier. Their motivation – the datasets need to be explored first to generate a coarse model and then the model can be adapted to further fine-tune the classification accuracy – is aligned with our own and arises from the need to classify large datasets without any a-priori information on the target classes. PBAC 30 Active Learning Retrospective takes into account the density of the feature space and the uncertainty of the classifier combined to form one single criterion for the selection of queries. The transition between exploration and exploitation occurs as the learning process evolves. This transition is achieved at each iteration by decreasing the influence in the selection criterion of the exploration term whilst exploitation influence increases. This concern, an explicit sense of exploration versus exploitation, is also present in the work of Osugi et al. (Osugi et al., 2005) that apply a Kernel-Farthest-First algorithm for exploration in AL with SVM. The decision to go for an exploration step is made at each iteration based on the change that is induced by the newly added labeled instance on the hypothesis space. Our proposal dynamically shifts between exploration and exploitation modes without requiring any tuning thus, avoiding overhead costs. This automatic shifting is guided by both the geometric properties of the working set and the knowledge on the target concept embedded in the current hypothesis. Transfer learning, 2008 AL and transfer learning (Caruana, 1997; Dai et al., 2007) are distinct strategies to obtain labeled instances for learning. AL asks domain experts to label particularly informative queries while transfer learning intends to leverage the knowledge from a given domain to learn in a different one. Shi et al. (Shi et al., 2008) work on the application of AL to the transfer of knowledge across domains. The authors propose a framework to actively transfer knowledge from one domain in order to help labeling the instances in the target domain. They extend the standard procedure by including an uncertainty based AL component that queries an oracle when the out-of-domain example is classified with low confidence. Videos may come from many different sources or domains. For instance, we may find a video showing an airplane – let’s say, the semantic concept to learn – that comes from a movie or from a news channel. Each of these sources has its distinctive class distribution so, transfer of knowledge across different sources becomes relevant. AL can be used to reduce the labeling effort required to build a classifier for a new source by reusing a classifier previously trained for the same semantic concept but under a different source or domain. Li et al. (Li et al., 2010) proposed an hybrid approach to select queries in a cross-domain video semantic concept classification task. Their approach selects a batch of queries of fixed 2.3 A retrospective view 31 length. Queries are selected by an ensemble of a discriminative query strategy, SVM AL, and a generative query strategy that selects the sample that is most unlikely to have been generated by the source domain distribution. The percentage of queries in the batch that come from each of these strategies is defined by a parameter of the model. This parameter is initialized at 50% and is dynamically updated according to the number of positive instances that have been selected by the strategy in the previous iteration. The strategy that selects more positive instances will be assigned a bigger share in the batch of queries. Proactive learning, 2008 Recent work on AL is focused on relaxing some of the base assumptions underlying this learning paradigm, such as, the existence of a single omniscient oracle who is assumed to be infallible (never wrong), indefatigable (always answers), individual (only one oracle) and insensitive to costs (always free or always charges the same). Proactive learning (Donmez and Carbonell, 2008) is a generalization of AL designed to relax these unrealistic assumptions. Recent approaches and applications of active learning, 2008 Robson Motta et al. (Motta et al., 2009) propose a novel approach to support AL in classification tasks. They explore the use of complex network properties (Newman, 2003; Luciano et al., 2007) – mainly vertex centrality measures such as closeness and betweenness – to improve the performance of AL algorithms. The authors discussed and evaluated how these measures can be explored to guide query selection. Xiaofei He (He, 2010) showed improvements in optimal experimental design when applying AL. He proposed a novel AL algorithm based on the intrinsic geometry of the input space, grasped from the graph structure inferred from the data, to apply in image retrieval. Empirical results show improvements over SVM AL and Laplacian regularized least squares (Belkin et al., 2006). Despite the large volume of research on AL its methods are being slowly adopted in practical applications (Attenberg and Provost, 2011). Text classification and movie filtering are among the fields that may directly benefit from AL to a great extent. In general, any field characterized by unstructured abundant data will possess the features required to benefit from AL: high labeling cost and data availability. Meta-learning applied to predict the performance of learning algorithms is a field that may also benefit from AL. Labeling instances in this field may be expensive since it 38 Active Learning Approaches by a committee with an even number of members, 2m, each one assigning a label. Queries are selected by the principle of maximal disagreement among committee members. In a binary classifier, disagreement maximization is achieved when half of the committee classifies the input as positive while the other half classifies it as negative. In such circumstances, each query bisects the version space when m→∞, maximizing information gain (Shannon, 1948). Monte Carlo simulations using a two-member committee confirm the improved performance of Query By Committee (QBC) over random sampling as prescribed by the theoretical study. The information gain of a QBC query tends asymptotically to a finite non-zero value leading to an exponentially decreasing generalization error as the number of queries increases. When using random sampling this information gain tends to 0 and generalization error decreases as an inverse power law in the number of queries thus, performing poorer than QBC. The authors refer that, in a filtering approach, where queries are selected from the available dataset, the learner may have to evaluate many instances before finding one where the committee disagrees. This drawback does not stand in the queryconstruction setting where one can generate specific artificial instances to promote disagreement in the committee. QBC is normally used in stream-based learning where a query is made for each incoming instance generating committee disagreement. The results from this seminal paper on QBC (Seung et al., 1992) are generalized and further discussed by Freund et al. (Freund et al., 1997). Lu et al. (Lu et al., 2010) sustain that specific datasets demand for specific ensembles of base classifiers. The “one-size-fits-all” approach, underlying the original QBC approach, can be improved by dynamically adapting the ensemble of base classifiers to the dataset at hand. The authors propose adaptive informative sampling, extending the base QBC technique to accommodate their claim. Adaptive informative sampling is initialized with a balanced ensemble composed by an equal number of classifiers from two distinct types – their work relies on neural networks and decision trees. Then, at each iteration, the percentage of committee members from each type is updated based on the classifiers’ performance in the previous iteration in a way to favor best performers. The performance of a given classifier in the committee is evaluated by two distinct fitness functions depending on the number of classes to learn. In binary classification tasks, committee members, hi, are evaluated by the fitness function, f, in Equation 3.3, where t pkis the number of 3.3 Expected utility gain 39 true positives identified for class ckand nkis the total frequency of class kin the training set. f(hi) = t p0 n0×t p1 n1(3.3) For multi-class classification tasks the fitness function is defined as the number of misclassified instances in the training set. Experimental results show that adaptive informative sampling consistently outperforms homogeneous ensembles. 3.3 Expected utility gain The AL approaches that we have considered under this category select queries based on an estimate of the utility of unlabeled instances. The utility measure depends on the concrete task but expected error and error variance are usual. Cohn et al. (Cohn et al., 1996) describe an optimal solution for pool-based AL that selects the instance that, once labeled and added to the training set, produces the minimum expected error. The expected error of the learner is decomposed into three terms: noise in the class distribution (independent from the learner), the learner’s bias and the learner’s variance (reflecting the sensitivity of the learner to the training set). Direct estimation of both bias and variance, is not possible for inductive learning since it requires knowing the actual class distribution which is not available. However, variance estimation is computed without reference to the underlying probability distribution. Moreover, when in presence of low variance, accurate classification is achievable regardless of bias (Friedman, 1997). Cohn et al. assume approximately unbiased learners, i.e., learners whose average prediction for a given instance is equal to its true class. Under such circumstances error is reduced to the variance term thus, minimizing the learner’s variance is equivalent to minimizing error. This approach, however, requires high computational effort. Schohn et al. (Schohn and Cohn, 2000) worked on AL, with SVM base classifiers, defining a query selection heuristic that estimates the expected change in error when adding a given instance to the training set. Their results are, in some cases, better than if all available data is used to train. One optimal approach, in a binary classification task, estimates the expected error, Ej, after adding a new instance, xj, to the training set as the mean of the expected error when the new query being 40 Active Learning Approaches added belongs either to class 1, E(xj,1), or to class −1, E(xj,−1)(Equation 3.4). Ej=P(yj=1|xj)·E(xj,1)+P(yj=−1|xj)·E(xj,−1)(3.4) E(xj,ck)might be computed by Monte Carlo simulation (Cohn et al., 1996) or, as suggested by the authors, using a simpler non-probabilistic approach that defines E(xj,ck)as the volume spanned by the SVM margin and then computes Ej=maxE(xj,1),E(xj,−1). In such case, Ejsets a lower bound to the decrease in uncertainty that is achievable when adding xjto the training set. However, both these greedy approaches are unfeasible in practice since computing E(xj,ck) requires building a large number of classifiers for each iteration – twice the number of unlabeled instances for a binary classification task. The same drawback – high computational cost – is experienced by Roy et al. (Roy and McCallum, 2001) whose approach requires retraining the classifier several times at each iteration, one for each class to learn. To overcome this practical drawback, the authors claim that queries can be selected without the need to estimate the expected change in error, thus avoiding extensive retraining. Selecting the next query such that the expected generalization error is minimized can be accomplished by narrowing the existing margin as much as possible, that is, by querying the unlabeled instance that is closer to the dividing hyperplane. The computational cost of this heuristic is incomparably lower than the one required by the optimal algorithms described above. The results reported by the authors are also favorable to their proposal. High accuracy is achieved very quickly, in some cases requiring four times fewer labeled instances than competing methods. Chapelle (Chapelle, 2005) proposes an approach that directly computes an estimate of the expected generalization error, performing the optimal AL strategy described above (Equation 3.4) in a feasible way. This approach relies on a simple classifier, the Parzen window classifier (Devroye et al., 1996), that gives direct estimates of the posterior probabilities avoiding a costly retraining process at each iteration. Lindenbaum et al. (Lindenbaum et al., 2004) apply AL to instance based learning exploring nearest-neighbor classifiers1. They propose two accuracy based utility functions that are maxi1The nearest-neighbor classifier stores all previously labeled instances that are then used to classify unlabeled instances according to the label of its nearest labeled neighbor. Variations of this scheme include k-nearest-neighbor classifiers (Duda and Hart, 1973) that assign classes to unlabeled instances by majority vote of the k-nearest labeled neighbors (Cover and Hart, 1967). 3.4 Density based 41 mized after labeling and adding the new query to the training set: an absolute-accuracy utility function, that estimates the absolute expected accuracy of the future hypothesis regardless of the current one and a gain-based utility function that estimates the accuracy gain of the future hypothesis relative to the current one. Using random field models (Wong and Hajek, 1985), Wong and Hajek estimate the probability of the possible labels of an unlabeled instance, xj, and then compute its expected utility from those. Berardi et al. (Berardi et al., 2012) propose inspection gain, an approach to text classification that ranks automatically labeled documents by the expected improvement in the classification effectiveness that is achievable by retraining after reviewing the automatically labeled documents. The ranking function used to sort automatically labeled documents acts as a query selection criteria based on utility. 3.4 Density based Under this category we have considered AL approaches that are based either on the distance between instances or on the density of the data in input space or on clustering. Distance based approaches are common in AL. The frequent use of SVM as the base classifier may have contributed to this since uncertainty in SVM classifiers is related to distance to the dividing hyperplane. The simplest distance based approach, farthest-first (Hochbaum and Shmoys, 1985), selects the next query as the unlabeled instance that is farther apart from all labeled instances. This approach, favoring exploration over exploitation, relies exclusively on distance measures in the input space that are independent from the base learner. SVM AL (Tong and Koller, 2002) selects the instance lying within the SVM margin closest to the dividing hyperplane. This approach assumes a clear focus on exploitation. From the point of view of the exploration-exploitation trade-off these two opposing strategies, farthest-first and SVM AL, both based on distance, take extreme positions. Representative sampling (Xu et al., 2003), also a SVM based approach, goes a little further beyond SVM AL and tries to capture the structure underlying the unlabeled instances within the SVM margin. Representative sampling selects a batch of mqueries in each iteration following 42 Active Learning Approaches Algorithm 3.2 until some stopping criteria is satisfied. This batch is composed by the medoids2of the clusters formed by the unlabeled instances lying inside the SVM margin. Algorithm 3.2 Representative sampling (adapted from (Xu et al., 2003)) 1: while not stopping criteria do 2: Train a linear SVM based on the labeled instances 3: Cluster the unlabeled instances lying in the margin of the newly trained SVM into mgroups using k-means clustering and inner product as a similarity measure 4: Identify the mmedoids of the mclusters 5: Ask the oracle for the labels of these minstances 6: end while 7: Return the current SVM classifier The clustering step (step 3 in Algorithm 3.2) is expected to preserve the density distribution by allowing to query the most important uncertain instances. Batch diversity is achieved by selecting the medoid of each cluster as the batch members. Wang et al. (Wang et al., 2009) select a preliminary batch of instances that lie in the SVM margin and then enforce diversity by selecting those instances from this preliminary batch that explicitly maximize the distance between each other in the original input feature space. To assure diversity, Chen et al. (Chen et al., 2010) use distance diversity and set density in the SVM feature space to evaluate the heterogeneity of the selected batch. Clustering has also been explored to provide an initial structure to data or to suggest valuable queries (McCallum and Nigam, 1998; Nguyen and Smeulders, 2004; Hu et al., 2009; Zhu et al., 2010a). Adami et al. (Adami et al., 2005) merge clustering and oracle labeling to bootstrap a predefined hierarchy of classes. Although the original clusters provide some structure to the input, this approach still demands for a high validation effort, especially when these clusters are not aligned with class labels. This concern on misalignment is also present in (Dasgupta and Hsu, 2008). Dasgupta et al. propose a cluster-based method that consistently improves label complexity – the number of queries that is sufficient to learn a concept – over supervised learning. Their method detects and exploits clusters that are loosely aligned with class labels. 2A medoid is a representative object of a given set. It is the instance whose average dissimilarity to all the instances in the set is minimal. Medoids are similar in concept to centroids, but they are always real instances of the dataset. The medoid is the dataset instance that is closest to the centroid. 3.5 Hybrid approaches 43 Jiang et al. (Jiang and Ip, 2007) propose a novel dynamic distance-based approach to AL with SVM, named dynamic distance-based active learning. The authors claim that their approach outperforms the standard SVM AL approach (Tong and Koller, 2002). The dynamic distancebased strategy is implemented in two steps. In the first step, the nearest instance to the current decision boundary is queried – the standard SVM AL approach. Then, its neighbors are sorted by increasing distance to the current decision boundary. The second step involves the oracle that must label the instances in this ranked list, in sequence, from top to bottom – the closest instances to the decision boundary are queried first – until reaching an instance whose label is opposite to the previous. The last positive instance is added to the training set. 3.5 Hybrid approaches Hybrid approaches combine several distinct strategies in an attempt to take advantage of the benefits from each one. Pure strategies tend to favor either exploration or exploitation competences. While exploitation concerns seem to have been dominating AL research, exploration seems to have been gaining relevance. The issue is that exploration and exploitation are correlated. Acting on one has influence on the other, usually requiring a compromise solution. Focusing on instances near the decision boundary, favoring exploitation, prevents exploring regions in the feature space that might contain instances being misclassified by the current hypothesis (Baram et al., 2004). On the other hand, focusing on exploration, i.e., selecting queries from regions in the feature space away from the decision boundary, reduces the chances to sharpen current decision boundaries. Several hybrid approaches, like Prototype Based Active Classification (PBAC) (Cebron and Berthold, 2009), try to combine exploration and exploitation capabilities in a unique strategy in search for a good compromise solution. PBAC, motivated by the need to classify large datasets without any a-priori information, selects queries based on the uncertainty distribution, a novel criterion proposed by the authors. Uncertainty distribution estimates the utility of an instance from an aggregation of its representativeness potential, which is evaluated from density estimates on the unlabeled data, and classifier uncertainty, based on labeled data. PBAC (Algorithm 3.3) starts by exploring a dataset to generate a coarse model; then, this preliminary model is exploited to tune classification accuracy. The 44 Active Learning Approaches transition from exploration to exploitation occurs as the learning process evolves by decreasing at each iteration the influence of the exploration term while increasing the influence of the exploitation term. Algorithm 3.3 Prototype Based Active Classification (adapted from (Cebron and Berthold, 2009)) 1: Set threshold T 2: GlobalPotential =0 3: for all xj∈Udo 4: Compute the potential P(xj) 5: GlobalPotential =GlobalPotential +P(xj) 6: end for 7: while GlobalPotential >Tdo 8: for all xj∈Udo 9: Compute the classifier uncertainty C(xj) 10: Compute the uncertainty distribution D(xj)according to Equation 3.5 11: end for 12: Select qithe instance xjwith the highest potential 13: Obtain a class label yifor qi 14: Create a new prototype with values qiand class label yi 15: Classify the datasets with the current set of prototypes 16: Reduce the potentials 17: end while The uncertainty distribution, D, of an unlabeled instance, xj, combines its potential, P(xj), computed on the unlabeled data, and the classification uncertainty, C(xj), computed on the labeled data (Equation 3.5). In Equation 3.5, ε∈[0,1]controls the influence of the exploitation term. D(xj) = (1−ε)P(xj)+εC(xj)(3.5) The potential of xj,P(xj), is computed from the distance between xjand its closest neighbors. Instances that have more neighbors in their close vicinity have a higher potential. Having the potentials computed, the instance with higher potential, x∗ j, is selected and the potentials of x∗ jand their close neighbors are reduced to avoid having these instances selected in the next iteration. This potentials’ reduction step also reduces the overall influence of exploration as the learning process iterates. The reduction of potentials is also used to define a stopping criterion. The learning process stops when the total sum of all potentials drops under a predefined threshold, T. The classifier uncertainty for a given instance xj,P(xj), is computed as the entropy of its membership probabilities for all classes. These class probabilities are computed from a weighted 3.5 Hybrid approaches 45 k-nearest-neighbor classifier based only on the labeled instances, called prototypes. The class label for a given unlabeled instance, xj, is assumed to be the class label of the prototype with the largest prototype weight, i.e., the closest prototype to xj. An explicit concern of exploration versus exploitation, is also discussed by Osugi et al. (Osugi et al., 2005). They propose an AL strategy that decides at each iteration whether to explore or exploit. This decision is based on a binary random variable, a “coin flip” as the authors put it, assigning a probability pto explore (and 1−pto exploit). If the decision is to explore, the Kernel Farthest First (Baram et al., 2004) algorithm is applied to select the next query – select the unlabeled instance that is further away from all labeled instances in the feature space induced by the kernel function used by the classifier. Otherwise the next query is selected with Simple (Tong and Koller, 2002) – select the unlabeled instance that is closest to the current decision boundary. This new query is labeled and added to the training set. To determine how successful an exploration step was, the authors compute d(hi−1,hi)∈[−1,+1], the change induced from the previous hypothesis, hi−1, to the current, hi. If d(hi−1,hi)is positive, implying significant change from hi−1to hi, the previous exploration step is assumed to be successful and the probability pis kept high encouraging further exploration. If d(hi−1,hi)is negative, pis reduced. The exploration probability pis updated from iteration i−1 to iteration iusing Equation 3.6. pi=max(min(pλed(hi−1,hi),1−ε),ε)(3.6) where εis a parameter that bounds the value of p(so there is always a chance of exploring and exploiting) and λis the learning rate for updating p. The function d(hi−1,hi), used to measure the change induced by the query just added to the training set, is a linear transformation (Equation 3.7) of the cosine, s(h,h0), between the vectors of the real-valued labels, hand h0, predicted by both hypothesis hiand hi−1for the working set (including the predictions for labeled and unlabeled instances). d(hi−1,hi) = 3−4s(h,h0)(3.7) 46 Active Learning Approaches 3.6 Initialization and stopping criteria AL classification is an iterative approach that evolves a base classifier until a certain performance level which is assumed to be adequate given the task at hand. During the learning process the same strategy is executed in every step of a loop. This loop is preceded by an initialization step – providing an initial labeled set required to learn the first instance of the classifier – and halted when a given stopping criterion is met. A simple way to perform the initialization step is by random sampling while a simple stopping rule is the exhaustion of the unlabeled set. Some research has been done to improve these naive approaches. We are particularly concerned with the stopping criteria enabling us to halt the learning process when in presence of a good “enough” classifier, thus avoiding to ask for labels that add little or no value. 3.6.1 Initialization Initializing the labeled set in some proper way might reduce the number of wasted queries – queries that produce useless labels – and improve the performance of the classifiers learned at the initial stage of the learning process. Selecting a proper labeled set aims at early grasping the distribution of the data to classify, thus creating conditions to select valuable queries in the following iterations. This, however, is a task to be performed in the absence of any prior evidence on the concept to learn. Several approaches, based on chance alone or exploiting somehow the available working set, are available in the literature. Some straight approaches to the initialization of the labeled set are common, such as using a set of instances previously labeled by some mean (Sun and Hardoon, 2010) or random sampling. Initializing the labeled set by randomly selecting training instances from every class to learn is probably the most common approach (Tong and Koller, 2002; Zhang and Chen, 2002; Warmuth et al., 2003; Xu et al., 2004; Schütze et al., 2006). However, random sampling might be very demanding mainly when in presence of a severely imbalanced dataset. This is one of the main concerns in (Dima and Hebert, 2005) who define an initialization algorithm, based on the density of the input space, that discards redundant instances – those lying in regions of the feature space that are densely populated – while keeping instances 3.6 Initialization and stopping criteria 47 from sparse regions available for querying. Their assumption is that instances from densely populated regions are representatives of the same class with high probability and repeated queries on these regions will miss under-represented classes while increasing the number of wasted queries. This assumption leads to a behavior which ranks exploration higher than exploitation. An opposite reasoning – assuming that rare or borderline cases that do not occur very often are not interesting for classification and, therefore, discarding them from the initial labeled set – motivates the work described in (Cebron et al., 2007), where the seed queries are selected on the basis of the so called potential of each unlabeled instance. This potential, as defined by the authors, is a measure of the density of the input space in a given predefined neighborhood of the instance being evaluated. Any instance that lies within this neighborhood has a large influence on the potential of the instance at hand. Seed queries are the instances with the highest potential score, that is, those that lie in densely populated regions. This reasoning boosts exploitation over exploration. Clustering is also a common approach to the initialization phase that tries to explore the intrinsic structure of the working set. K-means clustering is used to select initial training instances in (Kang et al., 2004). The authors propose a method that divides the unlabeled instances into clusters and then selects the clusters’s medoids which are assumed to be the most representative instances from each cluster. The centroid itself may be difficult to label because it will be most likely a synthetic instance mainly when working with high dimensional input spaces as is the case with text corpora. Nevertheless, the cluster synthetic centroids themselves may also be used as training instances at no extra labeling cost since they will be assigned the same label that the oracle has assigned to the representative instance. In such a case, the centroids are named model examples. Experiments performed on various text datasets have shown that the active learner starting from the initial training set selected by this method reaches higher accuracy faster than when initialized by random sampling. The inclusion of the model examples in the training set further improves learning performance. Nguyen et at. (Nguyen and Smeulders, 2004) use a simplified version of the K-medoid algorithm (Kaufman and Rousseeuw, 1990) that finds Krepresentatives of the dataset to initialize the labeled set. These representative instances are those minimizing the sum of the distances from the data samples to the nearest representative. To overcome the high computational cost of the 54 Active Learning Approaches tions on queries is already larger than a predefined accuracy threshold (no benchmark is provided). Max-confidence and min-error are suggested, respectively, as the upper bound and the lower bound for stopping conditions. These criteria are based on the premises that if a classifier induced from the current training data has strong classification confidence on an unlabeled instance, then we can consider it as redundant. It should be noticed that min-error is adequate for batch mode AL. In a different setting, where only one query is selected per iteration, the accuracy performance is either 1, if the classifier predicts the correct label, or 0, otherwise. In such settings, max-confidence and min-error might be used ensemble. Once both conditions are met, the current classifier is assumed to have enough confidence on the labels of all the remaining unlabeled data and the learning process terminates. This former work by Zhu et al. is extended to introduce the minimum expected error strategy that involves estimating the classification error on future unlabeled instances. Overall-uncertainty is similar to max-confidence, but, instead of taking only the most informative instances into consideration, it is computed over all unlabeled instances. Classification-change assumes that the most informative instance is the one which causes the classifier to change its predicted label. Thus, the learning process is terminated once no predicted label changes during two consecutive iterations. Recently, in 2010, Zhu et al. (Zhu et al., 2010b) propose the selected accuracy method along with combinations of all the above strategies to estimate the required thresholds. The selected accuracy method is designed to apply in batch mode AL. In such a setting the learning algorithm has access, in each iteration, to the true labels of all the batch members. The unlabeled instances composing the batch are supposed to be the most informative given the current hypothesis and the unlabeled data pool. The learning process is terminated when the accuracy of the current classifier on these batch instances is above a given threshold. Missed clusters Schutze et al. (Schütze et al., 2006) claim that there is no obvious procedure to decide conveniently when to stop querying due to the so called missed clusters – unexplored regions in the input space containing positive instances. Missing clusters can only be found by chance, demanding for random sampling. As a consequence of this reasoning the authors claim that instead of trying to set stopping criteria depending on the available data another alternative is 3.6 Initialization and stopping criteria 55 to define a level of acceptable performance and stop the learning process when this level has been reached – they suggest using F1=80%. 56 Active Learning Approaches Chapter 4 Text Classification Classification tasks, in general, aim at assigning one or more classes, from a predefined set, to a given instance from the target domain. Text classification, also known as text categorization, refers to the classification task performed over text corpora. In text classification, classes, a.k.a. labels, are assigned to text documents. Early text classification approaches, in use between the 60’s and late 80’s, were performed by domain experts deploying a set of rules to assign classes to documents in a specific domain. This expert system’s approach has two major drawbacks: it is restricted to a specific target domain and requires a significant effort and time from the domain experts. These approaches are not scalable to the variety and volume of textual information that became available since the last decade of the 20th century with the widespread use of the Web and other Internet services. This mismatch between the chances offered by the amount of textual data widely available and the cost of text classification motivated the search for automatic text classification solutions. Research efforts focused on text classification in the area of machine learning arose naturally in the early 90’s. Nowadays, many of the text classification systems rely, to some extent, on automatic classifiers coming from the machine learning field. State-of-the-art text classification systems exhibit acceptable performance at a lower cost than that required by non-automatic systems relying exclusively on the knowledge of domain experts. Nevertheless, text classification has certain characteristics that make it a difficult task for machine learning. Text corpora, collections of text documents, are characterized by high-dimensional input spaces – frequently ranging over 104dimensions – having many irrelevant features and containing high levels of noise. As a consequence, a large 57 58 Text Classification number of labeled instances is usually required to train. However, building classification rules by hand is certainly more demanding – concerning human effort and the required skills – than assigning labels to a set of text documents to be used to train a classifier (Hayes, 1992). Text classification involves a set of tasks, including: (a) the proper preparation of text documents, which are by nature unstructured data objects, in order to extract the relevant features that are required by the classification process; (b) the proper representation of text documents in a format that is adequate for the classification process; (c) learning the target classes; (d) applying the learned model to classify new documents and (e) evaluate the performance of the classification process. The pre-processing tasks, referred above as tasks (a) and (b), are discussed in Section 4.1, while tasks (c) to (e) are discussed in Sections 4.2, 4.3, 4.4 and 4.5. 4.1 Pre-processing We consider a pre-processing stage comprising the tasks that are required to obtain a suitable document representation, valid for the subsequent automatic learning phase. This stage includes text preparation and text representation. 4.1.1 Text preparation The text preparation phase takes a text document as input and returns a set of features describing it. This phase includes several steps that attempt to eliminate non-informative features and might involve some or all of the following (based on (Baeza-Yates and Ribeiro-Neto, 1999) and (Weiss et al., 2004)): •tokenization – breaking the text document into tokens, commonly words; includes all sorts of lexical analysis steps, such as: eliminating punctuation, numbers, accents and extra spacing, converting to lower or upper case; •stop-word removal – removing irrelevant terms; requires a list of stop-words (words to eliminate); •stemming or lemmatization – reducing words to their semantic root; the Porter algorithm (Porter, 1980) is probably the most well known stemming algorithm; specific algorithms, such as the 4.1 Pre-processing 59 one proposed by Orengo et al. (Orengo and Huyck, 2001) for the Portuguese language, are required for each language; •feature selection – defining index terms, the features that will be used for document modeling. The full process of selecting features and computing their weights is known as indexing. The application of these pre-processing tasks must be carefully done because the predictive power of words is highly dependent on the topic of interest (Chakrabarti et al., 1998a). Another essential aspect to consider is the language in which the document is written, which determines, at least, the list of stop-words and the stemming algorithm to use. Stop-words removal is controversial. Removing words from a text, even those that in a linguistic sense have low semantic value, always reduces the information contained in the text document. Stop-word removal reduces the dimensionality of the feature space at a cost of loosing some information. A compromise solution must be set so that this information loss does not get counterproductive. What is left out from “to be or not to be” after stop-word removal? Recall that this phrase is completely made up of words that are frequently recognized as stop-words. To avoid this loss, some systems, like CiteSeer (Lawrence et al., 1999), for instance, do not remove any words from the documents to be indexed. Web documents, formatted in HTML or other markup language, still require splitting markup tags from content which is performed early in the tokenization step, before lexical analysis. The words that appear in documents often have many morphological variants. Thus, pairs of terms such as “student” and “students”, will not be recognized as equivalent without some form of processing. Reducing morphological variants of words with the same semantics to a common root, or stem, is called stemming. A stem, by definition, is the portion of the word that is left after the removal of its affixes (prefixes and suffixes). Most frequently, several morphological variants of words have the same semantics and so they can be interpreted as the same for text categorization purposes. This way, not only the number of features gets reduced but also the topics described in the text get more noticeable to the learning algorithms since semantically similar words are conflated to a single representative form. For automatic processing purposes, it does not usually matter whether the stems generated are genuine words or not (for example: "computation" might be stemmed to "comput" instead of "compute") provided that different words with the same base meaning are conflated to the same stem and that words with distinct meanings are kept 60 Text Classification separate. Inflectional stemming, in linguistic terminology called morphological analysis, may be seen as a light stemming process limited to regularize grammatical variants such as singular/plural, genre and past/present. There are a number of stemming algorithms (known by stemmers or lemmatizers) available and widely used, such as, the Porter algorithm (Porter, 1980), the Krovetz algorithm (Krovetz, 1993) and the Lovins algorithm (Lovins) – the first stemmer with widespread dissemination, published in 1968. In text classification the number of features is typically much larger than the number of training instances and, if care is not taken, undesirable overfitting may arise. Feature selection is desirable not only to avoid overfitting but also to reduce feature space dimension and, consequently, storage and processing cost. Feature selection (Yang and Pedersen, 1997) or feature reduction techniques may be heuristic – governed by linguistic principles or specific rules from the universe of discourse – or statistical. The procedure for feature selection usually comprises the following steps (Chakrabarti, 2003): 1. compute, for each feature, a measure that allows to discriminate target classes; 2. list features in decreasing order of that measure and 3. keep the subset of the features with the highest discriminative power. The high feature space dimensionality, common in text corpora, can be reduced with techniques that might be categorized either as feature selection or re-parameterization techniques (Aas and Eikvil, 1999). Feature selection attempts to remove non-informative words from documents in order to improve categorization effectiveness and reduce computational complexity while reparameterization is the process of constructing new features, as combinations or transformations of the original ones. Feature selection approaches are usually further classified as wrapper or filter techniques depending on whether they explore the learning algorithm to select the most appropriate features or not. Among common feature selection techniques we may include (Yang and Pedersen, 1997): •document frequency threshold (Xu et al., 2008) relies on the inverse document frequency, i.e. the number of documents where the feature is present, and eliminates features whose inverse document frequency falls off some pre-defined threshold; the application of this 4.1 Pre-processing 61 technique is simple, inexpensive and has been providing good results, although it requires some care in the specification of the threshold value; •information gain (Zheng et al., 2004) sorts features by decreasing order of their information gain; the most informative features are retained while the least informative are removed from the feature set; •mutual information (Dumais et al., 1998; Novoviˇ cová et al., 2004; Peng et al., 2005) measures the association between features and classes based on a two way contingency table; features with the highest mutual information are selected; •chi-square (Galavotti et al., 2000; Zheng et al., 2004) uses the same contingency table as mutual information but performs a chi-square statistical test to infer independence between features and target classes; the major advantage of this method, compared to mutual information, is that, since the test statistic is normalized, it allows for comparisons among features for the same class; •term strength (Wilbur and Sirotkin, 1992; Liu et al., 2003) is significantly different from the above; this method computes each term strength independently from the document class. It assumes that documents sharing many common words are similar and, further, that the common words are informative. This method estimates term importance based on the conditional probability of a term appearing in a certain document given that it appears in another similar document; •The Markov blanket criterion (Koller and Sahami, 1996; Aliferis et al., 2010) reduces the feature set by incrementally excluding the least relevant features until the reduced subset is satisfactory; •Latent semantic indexing (Deerwester et al., 1990), LSI, is a re-parameterization technique, which uses the singular value decomposition of the document×term matrix to reduce the dimension of feature space; 62 Text Classification •Part-Of-Speech (POS) tagging assigns grammatical categories – such as verbs, nouns and adjectives – to terms in a text depending on their definition and context. Using POS tagging information for feature selection in text is a relevant approach to identify the most meaningful terms (Masuyama and Nakagawa, 2004; Gonçalves et al., 2006); •Named Entities (NE) may also provide very relevant indexing terms for text in specific domains. NE are recognized as one of the most important indexing elements in biomedical text (Saha et al., 2009). NE Recognition (NER) aims to locate and classify terms into semantic categories, such as protein or gene, in the biomedical domain, or company or place in the business domain.; •Synonyms replacing is another technique available to reduce the dimension of the features space in text (Bolshakov and Gelbukh, 2004). Synonyms may be replaced by a unique term. Synonyms may be obtained from lexical databases, like WordNet1, or simpler synonyms dictionaries. A different approach aimed at reducing the time and computational effort required to train a classifier is sub-sampling which uses only a reduced sample of the available data to train. Text bundling (Shih et al., 2003) is a sub-sampling technique that reduces the number of training instances by averaging together small groups of instances, such that important statistical information is retained. Text bundling organizes texts belonging to the same class into homogeneous groups. Each of these groups is averaged to generate a single bundled text that will replace all the group in the training set. This approach requires a pre-labeled set that might be used to organize the corpus in homogeneous groups corresponding to the target classes. 4.1.2 Text representation Once the text preparation stage described above is concluded, each document is reduced to its representative features. Then, at the next step, text representation, this set of features is encoded into a specific format representing the document in an adequate manner for automatic processing. 1http://wordnet.princeton.edu/ 4.1 Pre-processing 63 Classic text models, view a document as a bag-of-words, describing text documents by the terms – words or phrases – appearing in it. In these models, each term in a document – known by index term – has a weight associated to it. The vector space model (Salton et al., 1997), probably the most commonly used model for text representation, assigns real non-negative weights to index terms. In this model, documents are represented by vectors in a multi-dimensional Euclidean space. Each dimension in this space corresponds to an index term, a relevant term that is contained in the document collection and also part of the vocabulary in use. In the vector model, index term weights are usually obtained as a function of two factors: •the term frequency factor, T F, a measure of intra-cluster similarity; computed as the number of times that the term occurs in the document, normalized in a way as to make it independent of document length and •the inverse document frequency factor, IDF, a measure of inter-cluster dissimilarity; weights each term according to its discriminative power in the entire collection. The degree of similarity of documents is evaluated as the correlation between the vectors representing the documents. This is usually quantified by the cosine of the angle between the two vectors. Some proposals, distinct from the traditional vector space model, try to explore sequences of characters or words, known as n-grams (Cavnar and Trenkle, 1994; Lodhi et al., 2002; Zhang and Zhu, 2007; Rahmoun and Elberrichi, 2007). Structured models (Baeza-Yates and Navarro, 1996), combining information on text content with information on the document structure, are also available although not as popular as bag-ofwords models. At the end of the 80’s and throughout the 90’s, various structured text retrieval models have been proposed (Chakrabarti, 2003), such as non-overlapping list model, proximal nodes model (Navarro and Baeza-Yates, 1995), simple concordance list models (Dao et al., 1997), path prefixing and PAT expressions (Salminen and Tompa, 1994). These models, that explore the structural characteristics of the documents, are more directed for information retrieval (BaezaYates and Ribeiro-Neto, 1999), where the goal is to rank documents by their relevance to a given 70 Text Classification 2004; Zhang and Zhou, 2005). In hierarchical classification it is also common to break down the original problem into a set of flat problems for simplicity reasons. These approaches, however, do not take into account the information contained in the hierarchical structure of the concept to learn (Koller and Sahami, 1997; Kiritchenko et al., 2006). Top-down, or level-based, approaches, take into account the hierarchical nature of the target concept at a local level (Sun and Lim, 2001). These approaches build flat classifiers to learn classification models that can predict the classes at each level of the hierarchy. These flat classifiers are then applied sequentially at all levels in the hierarchy that are deemed relevant for a given instance by the previous level classifier. The process stops when a certain level classifier does not find any relevant class for the instance at hand at its own level or when the process reaches a leaf node. Global approaches for hierarchical classification, known by big-bang (Sun and Lim, 2001; Kiritchenko et al., 2006), build a single classifier able of discriminating all the classes in the hierarchy taking into consideration the existing hierarchical relationships. 4.3 Learning settings The application of machine learning techniques to classification problems generally requires two distinct stages: (1) the learning stage – when the classifier is learned, that is the algorithm builds a model of the concept to be learned based on training and test data – and (2) the production stage – when the previously learned model is applied to unseen instances in order to classify them. The learning stage demands for a sample of the target population that is to be partitioned in a training set and a test set. The need to label instances in this sample, according to the specific target concept, is probably one of the most expensive tasks experienced during all the classification process. Therefore, it becomes a core aspect to take into consideration. Irrespectively of the learning setting in use, some target classes may not be learnable for several reasons (Schütze et al., 2006), such as, having few instances available in the corpus or using a text model that is not expressive enough for the purpose of the classification task – the bag-of-words model, for instance, does not take into consideration the relative order of words which might be of crucial importance. 4.3 Learning settings 71 When both training and test sets are fully labeled, we are in presence of a supervised learning setting. On the other extreme, if none of the training instances is labeled, we are in presence of unsupervised learning. When the training data is partially labeled, we are in presence of a semi-supervised learning setting. Bennet et al. (Bennett and Demiriz, 1998) further classify semisupervised learning problems as either semi-supervised clustering, when the number of labeled instances is small when compared to the dimension of the training set, or transduction problems, when the number of labeled instances is large when compared to the training set dimension. The transduction problem refers to the estimation of the value of a classification function at a given instance, which opposes to the standard inductive learning problem of estimating the classification function for all possible instances and then using the fixed function to deduce its value at a given instance. The supervised setting requires the full dataset, from where the training and test samples are obtained, to be labeled or, at least, that there is a large number of labeled instances from each class. This is one major drawback in this setting, concerning text classification, because of the high cost of labeling text documents. The process of manually assigning labels to text documents is both time consuming, inaccurate and subject to incontrollable factors arising from human nature (Macskassy et al., 1998) – two users with the same skills may classify the same page differently or the same user may classify the same page differently at different moments of time. In opposition to this passive learning process, active learning (Chapters 2 and 3) gives the learner the ability to select which instances should be included in the training set. Active learning (AL) reduces the amount of labeling that needs to be done through selective sampling of unlabeled data. In AL the learner examines a collection of unlabeled instances and selects the most informative ones, requiring an annotator to label the selected instances, and iteratively re-trains on the augmented set of labeled training examples. In the unsupervised setting there is no prior knowledge on labels, neither on the labels of each document nor even on the labels themselves. Clustering algorithms organize documents in homogeneous groups, based on their similarity, forming partitions of the dataset that minimize intra-group variance and maximize inter-group variance. Semi-supervised learning techniques are particularly interesting when the process of labeling training data is expensive and time consuming, as is the case of labeling text documents. In this 72 Text Classification setting, classifiers are wrapped by some method in order to take advantage of unlabeled documents. Several approaches have been proposed to solve the semi-supervised learning problem: •Bootstrapping (Jones et al., 1999) is a simple iterative method. At each iteration, labeled instances are used to learn a classifier. This classifier is applied to label unlabeled instances; those where there is enough evidence in favor of a certain label against the others are added to the labeled set. The algorithm proceeds iteratively until convergence. •Usage of Expectation-Maximization (Nigam et al., 2000) (EM) to estimate maximum a posterior parameters for a generative text classification model. •Co-training (Blum and Mitchell, 1998) is a supervised learning method, particularly useful when it is required to combine sources of evidence originated form very distinct spaces – particularly if they have rather different dimensions and scales, which may bias the aggregation of measures from these distinct sources. With co-training distinct classifiers keep disjunctive, independent feature sets and their estimates are never directly consolidated; instead this method uses the estimates of one classifier to train others. The application of co-training requires the existence of distinct and independent sets of features. Blum et al (Blum and Mitchell, 1998) apply co-training to Web document classification, a field where the features are naturally separable into disjoint sets, such as text in the page itself and words appearing in the in-links to the page, and two classifiers, one for each feature set, can be built. •Error Correcting Output Code (Dietterich and Bakiri, 1995) (ECOC) is a method that converts a K-multi-class problem in a set of L binary problems (Witten and Frank, 2000). Any binary classifier can then be used to learn these L problems. ECOC assigns to each class a unique binary string, the code word, where each bit is predicted by one of the binary classifiers. The predicted class is the one whose code word is closest to the code word produced by the set of the L binary classifiers. The distance between code words is computed by the Hamming distance, which is calculated as the number of different bits in both code words. Ghani (Ghani, 2001) describes a method for semi-supervised learning that uses the ECOC method bundled with co-training techniques in order to learn the binary classifiers. 4.4 Text classifiers 73 •Transduction (Gammerman et al., 1998) is naturally related to instance based learning. In transduction we are interested in the classification of a particular instance rather than in a general rule for classifying any future instance. •Coaching (Tibshirani and Hinton, 1998) is a technique that applies when we are in the presence of two distinct sets of predictive variables but only one of these will be available on the future examples to classify. Coaching techniques use one of the sets of predictive variables to coach the other set how to improve prediction in the absence of the former. 4.4 Text classifiers Many classification problems are binary in nature: a given example either belongs to some specified concept or it does not. In text categorization we are usually interested in sets of classes with more than just two distinct classes: the classification problem is frequently a multi-class problem. One common approach to multi-class problems, valid for some classifiers, is to use a set of binary classifiers, each one responsible for determining the relevance of the document as to one specific class. The relevance scores of each one of the individual binary classifiers are then combined in order to provide the final answer. Several types of classifiers used in machine learning in tabular, structured data, are also applied to unstructured high-dimensional problems like text classification. 4.4.1 Rochio Rochio’s algorithm (Joachims, 1997) is a classic method for document categorization in Information Retrieval2(Manning et al., 2008). In this method the training examples are used to build a prototype vector for each class. The prototype vector for each class is computed as the average vector over all the training document vectors that belong to the class. A new document is classified according to the distance measured between the document vector and the class prototype vectors. 2The purpose of Information Retrieval is not to assign classes to documents but to rank documents according to their similarity to a given query document – usually a user query specified through a set of keywords. 74 Text Classification 4.4.2 K-Nearest-Neighbors K-Nearest-Neighbors (KNN) is an instance based classifier which has been demonstrating good performance in pattern recognition and text categorization problems (Yang and Chute, 1994; Yang and Pedersen, 1997). This method classifies a document based on the characteristics of its closest kneighbor documents in the input space. In applications to text categorization, documents are usually represented in the traditional vector space model and the cosine between document vectors is also frequently used as the similarity measure. Classes might be assigned by some voting scheme – the majority class in the kneighbors is assigned, for instance – or, the classes that have a relevance score above a given threshold are assigned to the document (Yang et al., 2002). KNN is a local method based on instances that does not require any training stage. However, it demands for a fully pre-labeled set of instances. 4.4.3 Naive Bayes Naive Bayes methods (Kibriya et al., 2005; Kim et al., 2006; Jiang et al., 2011) use the joint probability of terms, ti, and categories, cj, to estimate category probabilities given a document, P(cj|t1,t2,...,tn). Dependencies between terms are ignored, i.e., Naive Bayes assumes that the conditional probability of a term given a category is independent of the conditional probability of any other terms given the category – the naive assumption. When assuming term independence, the conditional probability of document d, given class cj can be obtained by Equation 4.9: P(d|cj) = ∏ i P(ti|cj)(4.9) Given a document, the algorithm computes the posterior probabilities of each one of the classes and assigns to the document the most probable one, cNB (Equation 4.10). Marginal, a priori, class probabilities, P(cj), may be estimated from the class distribution in the training set. cNB =argmax cj∈C P(cj)∏ i P(ti|cj)(4.10) 4.4 Text classifiers 75 Computing class posteriors requires to estimate the conditional probabilities P(ti|cj), which may be obtained by Equation 4.11: P(ti|cj) = ni+1 n+|vocabulary|(4.11) In Equation 4.11, nis the total number of terms in all training documents belonging to category cj,niis the frequency of termtiand |vocabulary|is the total number of distinct terms in the training corpus – the lexicon cardinality (Fang et al., 2001). The constant 1, added to the numerator, and |vocabulary|, added to the denominator, are both necessary to avoid the 0/0 indeterminate that would arise for the terms, ti, not appearing in the training documents belonging to class cj, thus forcing P(d|cj) = 0 in such cases. Special care is required when applying Naive Bayes to high-dimensional data, as is the case of text corpora. In fact, when dealing with very large sets of attributes, problems relating to the limits of precision in computers may arise. By nature of probability, P(x|y)<=1. It is also true that lim n→∞∏iP(ti|cj) = 0. In practice, it may happen that ngrows large enough for the value of ∏iP(ti|cj)to exceed below the limits of double precision floating point numbers in modern computers. Computing the logarithm of the conditional probabilities as follows, addresses this problem (Equation 4.12). argmax cj∈C"−log(P(cj)∏ i P(ti|cj)#=argmax cj∈C"−log(P(cj))−∑ i log(P(ti|cj))#(4.12) 4.4.4 Decision trees Decision trees are decision structures built over a root node containing all the training instances (Witten and Frank, 2000; Lewis and Ringuette, 1994). The set of instances in any specific node is partitioned into its descendant nodes. This split is made with the objective of minimizing the diversity of categories present at each node and it is carried out until no further reasonable improvement is possible. At a given node, the split is made as to assure that the sum of the diversities at the child nodes is (much) less than the diversity at the present node without splitting. The goal is to maximize diversity(node)−∑diversity(childnodes). Care must be taken to avoid overfitting which is usually done by pruning the decision tree. 76 Text Classification There are two common pruning approaches: post or backward pruning and pre or forward pruning (Witten and Frank, 2000). In the pos-pruning approach the tree is expanded as much as possible at an initial stage and then it is pruned back by removing those nodes that do not significantly improve the homogeneity, hence the predictive power, of the tree. Pre-pruning approaches evaluate when to stop developing sub-trees during the tree construction process. The nodes at the bottom of the tree are called the leaf nodes. Any training example belongs to a certain leaf node. Each leaf node is then assigned to a class and the error rate of the leaf is the probability of examples in that leaf node being misclassified. The global tree error rate is a weighted sum of all the leaf nodes error rates. A key issue in decision trees is to decide which features allow for the best split at each node, the one that generates the most homogeneous partition, and the definition of the diversity measure to use. One of the most common diversity measures is entropy. The entropy of a given node, L, is given by Equation 4.13. − K ∑ j=1 P(cj|L)log(P(cj|L)) (4.13) Where P(cj|L)is the probability of a training example belonging to class cjgiven that it is located in node L, which can be estimated by the relative frequency of class cjin node L (Equation 4.14): P(cj|L) = Nj(L) N(L)(4.14) Nj(L)is the number of instances of class cjin node Land N(L)is the total number of instances in node L. Several algorithms are available to grow decision trees – CART, ID3, CHAID and C4.5 are common approaches (Aas and Eikvil, 1999). The CART algorithm (Breiman et al., 1984) builds a binary decision tree by splitting the training examples at a given node. The splitting rule is a linear combination of features. The main task is to decide, at each node, which combination of features performs the best partition and what is the split value. ID3 (Quinlan, 1986) splits nodes based on the unused attribute exhibiting minimum entropy – i.e., maximum information gain. The C4.5 (Quinlan, 1993) algorithm builds decision trees that have two children per node, when splitting on numeric features, but might have more then two children per node when the splitting rule is based on a categorical attribute. In such cases, it is not limited to binary trees (two children per node) as is CART. CHAID (Kass, 1980) is also a popular algorithm but it is limited 4.4 Text classifiers 77 to categorical features; thus, if the domain under study has numeric attributes then they must be previously discretized. 4.4.5 Support Vector Machines Support Vector Machines (SVM) (Joachims, 1998) are based on the intuition that a hyperplane that is close to several training examples will have a bigger chance of making erroneous decisions than one which is as far as possible from all training examples. The SVM algorithm is a binary classifier that defines a maximum margin hyperplane between the convex hulls formed by the training examples of each class. The maximum margin hyperplane is the one that is as far away as possible from both convex hulls – it is orthogonal to the shortest line connecting the hulls, intersecting it half way. This hyperplane may be defined as a function of the training examples that are closest to it, the support vectors. SVMs, like all discriminative classifiers, are non-parametric. They do not assume any underlying data distribution besides the trivial assumption that training and testing instances all come from the same population, thus assuming identical distributions. SVM implementations require some parameter tuning depending on the type of kernels in use. Linear kernels require no parameters. Radial Basis Function (RBF) kernels require setting γ, the width of the RBF kernel, and the cost parameter, C, that affects the trade-off between model complexity and training error, that is, the acceptable proportion of nonseparable instances. If C is too large, favoring model complexity, we have a high penalty for nonseparable instances which may lead to store many support vectors and overfit – C=1 is a small value for C while C=1000 is high. 4.4.6 Exploring other features besides content text Hypertext (Web) documents might have some additional attributes besides content text. When compared to plain text this type of documents allows for a richer representation that might be explored in (hyper)text classification. Yang et al (Yang et al., 2002) define five types of regularities that might be present in hypertext collections: •no regularity – the only place that has relevant information about the class of the document is the document itself, 78 Text Classification •encyclopaedia regularity – documents with a given class only link to documents with the same class, •co-referencing regularity – some, or all, of the neighboring documents belong to the same class but this class is distinct from the document class, •pre-classified regularity – the regularity is present at the structural level where a single page (hub) points to several pages which belong to the same class and •metadata regularity – metadata is available from external sources and can be explored as additional sources of evidence generating new features. The authors then define the types of features that should be used in order to improve the classification task of documents belonging to each of these regularities. However, there is no suggestion as to how to previously determine the type of regularity that is present in a given document collection. According to their experiments different classifier designs should be considered, depending on which of the above regularities holds. With no regularity we would not expect any benefit from using hyperlinks and the suggestion is to use flat text classifiers, exclusively based on the text of the document itself. Encyclopaedia regularity suggests augmenting the text of each document with the text of its neighbors, thus increasing the number of words related to the topic that are present in the document representation. In the case of co referential regularity, the text of the document should also be augmented with the text from its neighbors but these imported words should be treated as if they came from a different vocabulary, for instance prefixing them with a specific tag. If the collection has a pre-classified regularity then there is no need to look at the document text, it suffices to look at the pages that link to it and determine their class. When external sources of information are available that can be used as metadata, metadata regularity, we can collect them – possibly relying on information extraction techniques. Chakrabarti et al (Chakrabarti et al., 1998b) also test several feature sets, similar to the ones suggested by (Yang et al., 2002): local text, local text concatenated with all neighbors text, local text plus neighbors text prefixed with discriminative tags. They conclude that naive use of terms in the link neighborhood of a document can even degrade performance. Yang et al (Yang et al., 2002) have reached the same conclusion, which seems consensual. Although the use of extended sets of features available in hypertext collections – including text from hyperlink anchors, the full 4.5 Performance measures 79 text from neighbor documents, HTML tags, category distribution over a linked neighborhood, metadata available from external sources – might provide rich information for the classification task, it is not guaranteed that the use of such features will improve performance, which in general is dependent of the specific document collection. A folksonomy3, a.k.a. social classification or collaborative tagging is a distributed unsupervised classification system created and maintained by a group of individual users. Folksonomies may suffer from common problems related to tag ambiguity, synonymous tags or multilingualism (Robu et al., 2009; Wetzker et al., 2010; Trattner et al., 2011). Nevertheless, an empirical analysis of the complex dynamics of tagging systems (Halpin et al., 2007) shows that coherent categorization schemes can emerge from unsupervised tagging by groups of users. 4.5 Performance measures Performance evaluation is one of the most important issues in machine learning, in general. In classification tasks, this evaluation can be based on several measures. Common measures in text classification are recall, precision, F-measure – which aggregates recall and precision in a single measure – and accuracy or error – two complementary measures of the efficiency of the learner. Recall is defined as the ratio between the number of documents correctly classified and the total number of documents in the category. Precision is defined as the ratio between the number of documents correctly classified and the total number of documents classified in the category. Usually a classifier exhibits a trade-off between precision and recall. These measures are negatively correlated: improvement in recall is made at the cost of precision and vice-versa. It is frequent to have text classifiers operating at the break-even point – the operating point where recall and precision have the same value. The F-measure combines recall and precision in a unique indicator (Equation 4.15): Fβ=β2+1×precision ×recall β2×precision +recall (4.15) where βis a parameter allowing different weighting of precision and recall – precision and recall are equally weighted when β=1. At the break-even point, recall, precision and F1all have the 3http://vanderwal.net/folksonomy.html 86 Problem Statement throughout the learning process. None of the classes to learn are previously specified with the exception of what can be inferred from W. We are assuming an iterative learning process with queries being asked at each iteration. When a query is asked we assume that the true label yjof one unlabeled instance xjis always provided. At each iteration, i, during the learning process, Liand Uiform a set partition of W.Liis the subset of instances in Wwhose true label is known at iteration i,Li= <xj,yj>:xj∈W∧yj=E(xj)∈C.Uiis the subset of instances inWwhose label is not known at iteration i. A domain expert, E, knowing the target concept and being aware of each of the classes in C, is always available. At each iteration, i, this expert may be queried for the label of a single unlabeled instance xj∈Ui– batch mode AL was not considered – at a certain cost, A. When queried for a label, the expert always provides its true label, ∀j,E(xj) = yj,yj∈C– the expert Eis always available and always certain. We assume the availability of a base classification algorithm that generates hypotheses – a.k.a. classifiers, h, from a set of labeled instances. The classifier, hi, generated at each iteration, i, from Li, predicts labels, ˆyj, for the instances xj∈Ui. The utility of an instance at iteration i,B, is the value of the improvement in the performance of hthat a query may induce if included in Li+1. 5.4.2 Learning process In general, AL is an iterative process. Each iteration has three phases: learn, predict and query. This learning process is initialized from a set of pre-labeled instances, L1. This set must contain at least two labeled instances from Whaving distinct labels. This imposition stems from the fact that we need at least a positive and a negative example to boot up a classifier. Besides this imposition, there are no other constrains to the building process of L1. A core concern, however, must be taken into consideration. Since we are focusing on cost reduction and the cost of L1is N1A, assuming N1is the number of pre-labeled instances in L1, then N1should be small, ideally N1=2 as we use. The instances in L1are randomly selected from W. Their labels are requested to the domain expert, E. 5.4 Formal problem setting 87 Once this initialization set, L1, is built we enter the iterative learning process. At each iteration, i, the labeled set Liis used to build a classifier, hi, that predicts labels to all instances in Ui. Then, the AL criteria in applied to select a query, qifrom Ui. We are assuming that one single query is selected at each iteration. Batch mode AL was not considered. The label of the selected query is requested to the expert, E. The query is then added to the labeled set, Liand removed from the unlabeled set, Ui. The labeled set for the next iteration, Li+1, is the union of the previous labeled set and the query selected at the current iteration Li+1= Li∪{<qi,E(qi)>}. The unlabeled set for the next iteration, Ui+1is the set difference between the previous unlabeled set and the query selected at the current iteration Ui+1=Ui\{qi}.Liand Uialways form a partition of W. This process iterates until a given stopping criterion is met. The verification of the hypotheses under investigation depends on: 1. the early identification of instances whose labels fully cover C, i.e., there should be a small isuch that ∀ck∈C,∃xj∈Li:E(xj) = ck: 2. simultaneously, a low error rate should be observed at the predictions made by the learned hypothesis, i.e., the ratio of the number of correct predictions made by hion Uiby the cardinality of Uishould be low when compared to current approaches; 3. the identification of effective stopping criteria preventing costly useless queries. 5.4.3 Evaluation of solutions The evaluation of the solutions for our problem should be based on error, an essential performance dimension in classification, and on the number of target classes that are known, i.e., that have representative instances in L. Having representatives from all classes in Cis a core concern in the research problem being investigated. At each iteration, i, the error rate is evaluated on the set of unlabeled instances, Ui– generalization error. The number of known classes is evaluated on the set of labeled instances, Li. Besides the number of known classes in itself, it is also important to record the first time that a given class is identified, i.e., the first iteration outputting a query being labeled with a given class, ck. We will refer to this indicator as first-hit. From a broader perspective it is also important to evaluate the minimum number of queries that are required to identify representative instances of all the target 88 Problem Statement classes. we define label disclosure complexity for this purpose. All these performenca indicators are defines in Section 6.3.1. Chapter 6 D-Confidence Given a target concept with an arbitrary number of classes together with a sample of unlabeled instances from the target space – the working set, W– our purpose is to build an accurate classifier covering all target classes while posing as few queries as possible. A query consists of requesting the oracle, E, to provide the true label, yj, to a specific instance, xj∈U.Uis the set of instances in Wwhose label is not known. Querying Efor a label has a cost, A– the querying cost – assumed to be constant throughout the learning process. The working set is assumed to be representative of the class space – the representativeness assumption (Liu and Motoda, 2001). Active learners commonly search for queries in the neighborhood of the decision boundary (Figure 6.1a), where class uncertainty is higher. However, the uncertainty region, as perceived given current evidence, might be unaligned with the real target concept. The (perceived) uncertainty region is defined (Cohn et al., 1994) as the area that is not determined by available information, that is, the set of instances in the working set such that there are two hypotheses that are consistent with all training instances yet disagree on the classification of those. Limiting instance selection to the perceived uncertainty region seems adequate when the training set is a representative sample of the target concept in which case the perceived uncertainty region is probably consistent with the target concept. Class representativeness in the training set is assumed by the majority of active learning (AL) approaches. In such a scenario, selecting queries from the uncertainty region is effective in reducing version space. But, what if the real uncertainty region is not correctly or fully perceived by the current hypothesis? Under such an assumption, favoring exploitation rather than exploration withholds the 89 90 D-Confidence chances to achieve an early complete coverage of the target concept. (a) Perceived uncertainty region (b) Real uncertainty region Figure 6.1: Uncertainty region (shaded). nrepresents labeled instances from class cnand xrepresents unlabeled instances. We assume that the concept to learn has three distinct classes, one of which has not yet been identified 6.1 The intuition The initial stage of the learning process, when still searching for exemplary instances covering all target classes, is critical regarding the labeling cost. While still missing labeled instances of some target classes, the uncertainty region perceived by the active learner (Figure 6.1a) might be reduced to a portion of the real uncertainty region (Figure 6.1b) or might be severely biased. Being limited to this partial erratic view of the concept, the learner may be misled and is more likely to waste queries, thus increasing labeling cost at no benefit. The amount of the uncertainty region that the learner misses is related to the number of target classes that have not yet been identified. Our intuition (Figure 6.2) is that query selection should be based not only on classifier confidence but also on distance to previously labeled instances. In the presence of two instances with equally low confidence – say, Xaand Xbin Figure 6.2 – we prefer to select the one that is farther apart from what we already know, i.e., from previously labeled instances – referring to Figure 6.2 we would prefer to query Xathan Xb. 6.2 The d-Confidence criterion 91 Figure 6.2: For equally confident instances prefer those that are far from previously explored regions in instance space We expect that an AL approach that exhibits a high exploratory potential at the initial phase of the learning process – while still searching for exemplary instances for some of the target classes – and then smoothly shifts to a higher exploitation potential might reduce the amount of wasted queries, thus reducing the labeling cost. We search for a query selection criterion that favors exploration – tends to selects queries from unexplored regions in instance space – at an initial phase and then, as the input space is becoming explored, turns to favor exploitation. 6.2 The d-Confidence criterion Many AL approaches rely on classifier confidence to select queries (Angluin, 1988) and assume that the pre-labeled set covers all the labels to learn. The performance of these approaches is focused on accuracy, favoring exploitation over exploration. Our scenario is somehow different: we do not assume that we have pre-labeled instances from all classes and, besides accuracy, we are mainly concerned with the fast identification of representative instances from all classes. To achieve our goals we propose a new selection criterion, d-Confidence (Escudeiro and Jorge, 2012), which deals well with under-represented classes. Instead of relying exclusively on classifier confidence we propose to select queries based on the ratio between classifier confidence and the distance to known classes. D-Confidence, weighs the confidence of the classifier with the inverse of the distance between the instance at hand and previously known classes. 92 D-Confidence D-Confidence is expected to favor a faster coverage of instance space, exhibiting a tendency to explore unknown regions. As a consequence, it provides better exploratory behavior than confidence alone. This drift towards unexplored regions and unknown classes is achieved by selecting the instance with the lowest d-Confidence as the next query. Low d-Confidence combines low confidence – probably indicating instances from unknown classes – with high distance to known classes – pointing to unseen regions in instance space. This effect produces significant differences in the behavior of the learning process. Active learners focused on the uncertainty region, ask queries that are expected to narrow it down. The issue is that the portion of the uncertainty region that is perceived at a given moment is determined by the labels known at that moment. Focusing our search for queries exclusively in this region, while we are still looking for exemplary instances of some target classes that are not yet known, is not effective given our goals. Unknown classes hardly come by unless they are represented in the current uncertainty region. Algorithm 6.1 presents d-Confidence, our AL proposal specially tailored to achieve a fast class representative coverage. Algorithm 6.1 D-Confidence algorithm 1: given W 2: compute distance between instances in W 3: i=1 4: initialize L1 5: while not stopping criteria do 6: Ui=W−Li 7: Ci=distinct class labels in Li 8: learn hifrom Li 9: apply hito Uigenerating con fi(xj,ck),∀xj∈Ui,Ck∈Ci 10: for (xj∈Ui)do 11: for (ck∈Ci)do 12: dk j=ClassDist(xj,ck) 13: dcon fi(xj,ck) = con fi(xj,ck) dk j 14: end for 15: dCon fi(xj) = maxck(dcon fi(xj,ck)) 16: end for 17: qi=argmin xj (dCon fi(xj)) 18: Li+1=Li∪<qi,E(qi)> 19: i++ 20: end while Wis the working set, a representative sample of instances from the problem space. Liis a 6.2 The d-Confidence criterion 93 subset of W. Members of Liare the instances in Wwhose labels are known at iteration i.Ciis the set of the class labels that have representative instances in Li.U, a subset of W, is the set of the unlabeled instances present in the working set. At iteration i,Uiis the (set) difference between Wand Li;hirepresents the classifier learned at iteration i;qiis the query selected at iteration i; con fi(uj,ck)is the posterior confidence on class ckgiven instance uj, at iteration i. The core of our proposal is the computation of the d-Confidence value of unlabeled instances. That is accomplished at the outer for cycle in Algorithm 6.1, at steps 10 to 16, as explained next. 6.2.1 Computing d-Confidence D-Confidence is obtained as the ratio between confidence and distance between unlabeled instances and known classes (Equation 6.1). We may view d-Confidence as the confidence per unit distance. dCon f (xj) = max k con f (xj,ck) dk j!(6.1) For a given unlabeled instance, xj∈Ui, the classifier generates the posterior confidence w.r.t. known classes (step 9 in Algorithm 6.1). The distance between one unlabeled instance xjand all labeled instances belonging to class ck∈Ci,dk j, is computed by ClassDist() at step 12. At our current implementation this distance indicator, dk j, is the median of the distances between instance xjand all labeled instances in Libelonging to class ck. We expect the median to soften the effect of outliers. The Euclidean metric was previously used, at step 2, to compute the distance between all pairs of instances in W. We compute dcon fi(xj,ck), the marginal d-Confidence for each known class ck∈Cigiven xj, by dividing class confidence by the aggregated distance to that class (step 13). The maximum d-Confidence on individual classes ck∈Cifor a given instance xj∈Uiis finally computed (step 15) as the d-Confidence of the instance at iteration i,dCon fi(xj). If we now look at the iterative learning process as a whole, we see that at the initial phase there are few labeled instances – the instance space is barely explored – and the median of the distances to know classes is high for many unlabeled instances and low for others. This high variability will have a big influence in d-Confidence and will led it to select queries that lie far apart from known classes, thus exhibiting a high exploratory potential. When the instance space gets more and more 94 D-Confidence explored, the median of the distances to known classes is expected to become more homogeneous among unlabeled instances and the confidence factor of d-Confidence exerts its influence rising the exploitation potential of d-Confidence. D-Confidence is expected to dynamically shift between exploration and exploitation as the learning process iterates. This dynamic shifting is guided by the bond between the variance of the posteriors generated by hiand the variance of the distance between members of Uiand Li. Being based on the distance between what is known and what has not been explored yet, d-Confidence is also a robust approach that applies independently of the specific geometric properties of the instance space. D-Confidence automatically adapts to the input space structure – having both Uand Linto consideration – without requiring any preliminary tuning effort. This characteristic of d-Confidence is expected to reduce any severe bias from the original data distribution that may occur in AL approaches that are exclusively based on confidence (Wang and Hua, 2011) and do not take into consideration the structural properties of the input space. Also, this approach does not incur in the overhead cost that is imposed by the few AL approaches that are concerned with the exploration versus exploitation compromise. For instance, (Osugi et al., 2005; Cebron and Berthold, 2009) are two of these approaches, both requiring to tune two parameters guiding the transition between exploration and exploitation. SVM classifiers – by default, we use SVM as the base classifier – can be unstable with a small training set (Dagli, 2005). This is probably due to the fact that SVM confidence is very high for any instances lying far from the decision margin. The decision hyperplane might change significantly from one iteration to the next when the training set is small and even more when we do not have an initial pre-labeled set covering all classes. As a consequence the set of instances where the classifier is highly confident may also change from iteration to iteration rather easily. D-Confidence merges two complementary aspects of the working dataset: distance, which is measured in the input features space, and confidence, which is computed in the base classifier features space. Adding the contribution of the distance measured in the input space is expected to improve the robustness of d-Confidence and contribute to improve the stability of the learning process when using SVM base classifiers. 6.2 The d-Confidence criterion 95 6.2.2 Baseline criteria D-Confidence aggregates two baseline AL criteria, confidence and distance (based on farthestfirst). The confidence generated at each iteration by the current version of the base classifier, con fi(xj,ck), is the posterior probability of class ckgiven xj. The aggregated distance to known classes, dk j, is computed by ClassDist(xj,ck)based on the individual distances between each pair of instances (Equation 6.2). Individual pair distances might be computed by any distance function – at the current implementation we are using the Euclidean distance. ClassDist(xj,ck)is any aggregation function computed on the individual pair distances between one unlabeled instance xj∈Uiand every labeled instance from class ck∈Ci– at the current implementation we are using the median. ClassDisti(xj,ck) = dk j=mediandist xj,Lk i (6.2) Lk iis the set of labeled instances known at iteration ithat belong to class ck, that is, Lk i= <xj,yj>∈Li:yj=ck. 6.2.3 Effect of d-Confidence on SVM The output of SVM classifiers is the signed distance to the decision boundary measured in terms of half margin width – an instance located on the decision boundary outputs 0 while an instance which is collinear with support vectors for class +1 generates an output 1 and an instance which is collinear with support vectors for class −1 generates an output −1. An instance with a distance to the decision boundary that is ntimes the distance between the boundary and a support vector outputs n. This distance, d, is transformed into p∈[0,1], a measure of the posterior confidence of the learner on class +1. If, as is commonly the case, this transformation is based on logistic regression (Equation 6.3), the SVM classifier will be very confident on any instance located far from the decision boundary (Figure 6.3a), reducing the chances to select queries that are far from the current uncertainty region. p=f(d) = 1 1+e−d(6.3) 102 D-Confidence (a) ds0000 (b) ds0001 (c) ds0010 (d) ds0011 (e) ds0100 (f) ds0101 (g) ds0110 (h) ds0111 (i) ds1000 (j) ds1001 (k) ds1010 (l) ds1011 (m) ds1100 (n) ds1101 (o) ds1110 (p) ds1111 Figure 6.4: Artificial datasets 6.3 Experimental setup 103 Table 6.1: Artificial datasets and their properties Dataset properties Dataset Alignment Distribution Topology Separability non-collinear balanced polymorphic separable ds0000 overlapping ds0001 isomorphic separable ds0010 overlapping ds0011 imbalanced polymorphic separable ds0100 overlapping ds0101 isomorphic separable ds0110 overlapping ds0111 collinear balanced polymorphic separable ds1000 overlapping ds1001 isomorphic separable ds1010 overlapping ds1011 imbalanced polymorphic separable ds1100 overlapping ds1101 isomorphic separable ds1110 overlapping ds1111 •Cleveland heart disease (imbalanced class distribution), •a random sample from Vowels (higher number of distinct classes than the others), •a sample from Satlog (higher number of attributes than the others) and •a sample from Poker (highly imbalanced class distribution). These datasets were selected for their properties, mainly due to their distinct class distributions (Table 6.2). Table 6.2: Class distribution in tabular datasets Dataset #instances #features 1 2 3 4 5 6 7 8 9 10 11 Iris 150 4 50 50 50 Cleveland 298 13 161 53 36 35 13 Vowels 330 10 30 30 30 30 30 30 30 30 30 30 30 Satlog 500 36 125 118 96 67 48 46 Poker 500 10 270 170 34 12 4 3 3 2 1 1 The Poker dataset with a highly imbalanced class distribution causes some exceptions. The two classes with frequency 1 from the Poker dataset are never selected as initial classes. Two out of the 10 folds used for cross validation do not include all the 10 classes in the Poker dataset. 104 D-Confidence For this reason, the maximum number of classes found when using this dataset is below the total number of classes in the dataset, since this figure is estimated as a mean over all validation folds. At this second evaluation phase we have investigated the performance of d-Confidence when using, besides SVM, neural networks (NNET) and decision trees (RPART) as base classifiers. Datasets used in the third phase For the third phase we have selected two high-dimensional unstructured datasets. Two samples from traditional text corpora were used: •a stratified sample from the 20 Newsgroups corpus (NG), containing 500 documents described by 10333 terms and •a stratified sample from the R52 set of the Reuters-21578 collection (R52), containing 1000 documents described by 6019 terms. The NG dataset has documents from 20 distinct classes while the R52 dataset has documents from 52 distinct classes. Text documents are modeled with TF×IDF weighting. These datasets have been selected for their distinct class distributions. The class distribution in NG is fairly balanced (Figure 6.5a) with a maximum frequency of 35 and a minimum frequency of 20 while the R52 dataset presents an highly imbalanced class distribution (Figure 6.5b). The most frequent class in R52 has a frequency of 435 while the least frequent has only two instances in the dataset. This dataset has 42 classes, out of 52, with a frequency below 10 from which 31 have a frequency below five. (a) NG corpus (b) R52 corpus Figure 6.5: Class distributions in text corpora We are relying on SVM as our base classifier by default. Although the performance of text classifiers depends heavily on the document collection at hand (Yang and Pedersen, 1997), some 6.4 Evaluation 105 classifiers, particularly SVM and K-Nearest-Neighbors seem to outperform others in the majority of the domains (Joachims, 1998). A few properties of text documents – high dimensional feature spaces, many irrelevant features, document vectors’ sparsity and the fact that most text categorization problems are linearly separable – justify the dominance of SVM in text categorization tasks (Joachims, 1998). 6.4 Evaluation The evaluation of d-Confidence described in this chapter investigates its ability as a query selection criterion in comparison to its baseline and other state-of-the-art criteria. In particular, we investigate the ability of d-Confidence to reduce the labeling effort needed to cover all target classes without compromising accuracy. The results obtained in the three phases of our evaluation plan are discussed in Sections 6.4.1 to 6.4.3. The results from the work of our colleagues Motta et al. (Motta et al., 2012) are discussed in Section 6.4.4. 6.4.1 Instance space coverage This phase aims to assess the ability of d-Confidence to achieve a fast coverage of input space and fast retrieval of representative instances from all target classes. Fast, in this sense, means with few queries which is equivalent to low cost. We also want to evaluate the accuracy of the classification models generated by d-Confidence. Are we trading accuracy for coverage? Another aim of these experiments is to investigate how the geometric structure of the dataset impacts the performance of d-Confidence. In this phase we have used SVM with RBF kernels as the base classifier. We have recorded, at every iteration, the newly added query, the number of distinct labels known to the classifier and generalization error for all selection criteria under evaluation – farthest-first, confidence and d-Confidence. From these, we have computed, on each dataset, mean coverage, mean number of queries required to identify the hidden class – which in this case is equivalent to LDC since #C=3 and #C1=2 – and mean generalization error in each iteration over all cross validation folds (Table 6.3). 106 D-Confidence Table 6.3: Coverage (Cov), mean number of queries to identify one instance from the unknown class (LDC) and error (Err) with an SVM classifier on artificial data. Mean coverage and error are computed over all iterations in all cross validation folds for every artificial dataset. ff stands for farthest-first, cstands for confidence and dc stands for d-Confidence Dataset Cov (ff) Cov (c) Cov (dc) LDC (ff) LDC (c) LDC (dc) Err (ff) Err (c) Err (dc) ds0000 0.745 0.967 0.979 46 20 60.209 0.038 0.023 ds0001 0.756 0.922 0.937 42 19 22 0.281 0.192 0.174 ds0010 0.716 0.920 0.908 71 19 20.104 0.032 0.014 ds0011 0.684 0.893 0.886 24 27 30.198 0.137 0.104 ds0100 0.838 0.897 0.945 180 9 10 0.185 0.032 0.046 ds0101 0.721 0.914 0.933 66 35 13 0.221 0.112 0.106 ds0110 0.725 0.877 0.894 147 28 20.149 0.052 0.019 ds0111 0.675 0.875 0.870 149 34 11 0.219 0.111 0.086 ds1000 0.767 0.908 0.974 89 29 30.352 0.077 0.088 ds1001 0.743 0.953 0.976 74 11 70.411 0.240 0.255 ds1010 0.771 0.893 0.958 180 24 20.238 0.039 0.016 ds1011 0.704 0.911 0.933 92 25 60.282 0.174 0.144 ds1100 0.769 0.883 0.819 104 55 13 0.222 0.183 0.198 ds1101 0.767 0.852 0.835 89 22 11 0.276 0.188 0.178 ds1110 0.766 0.862 0.877 18 29 20.153 0.052 0.028 ds1111 0.667 0.803 0.827 7 32 30.220 0.128 0.120 Iris 0.720 0.918 0.949 84 18 30.304 0.134 0.082 Instance space coverage is the percentage of instances in Wthat lie on a given neighborhood of any labeled instance. We assume that, at any iteration i, those instances yielding a distance to any labeled instance in Lilower than 1 10 of the maximum distance between instances in Ware covered. The progress of instance space coverage is depicted in Figure 6.6 where we can see the percentage of covered instances after querying four, 16 and 64 instances. Figure 6.6: Progression of instance space coverage as new queries are added. cstands for confidence; dc stands for d-Confidence On every dataset we have computed mean coverage and mean error over all iterations and over the 10 folds for farthest-first, confidence and for d-Confidence. This process generated three 6.4 Evaluation 107 paired samples with the observed instance space coverage plus three paired samples with observed error. With these samples we have tested the significance of the differences of the means using paired t-tests. The number of queries required to identify one instance from the unseen class is estimated as the average over the 10 folds for farthest-first, confidence and d-Confidence. These means have also been tested for equal means with paired t-tests. Statistically different means, at a significance level of 5%, are bold faced in Table 6.3. D-Confidence consistently improves instance space coverage over both confidence and farthest-first. This behavior is observed irrespectively of dataset properties. There is a clear dominance of both d-Confidence and confidence when compared to farthest-first. D-Confidence outperforms confidence on six out of eight collinear datasets – collinear datasets have the first numerical digit on their name set to 1,ds1??? (see Section 6.3.2). This same figure is observed on balanced datasets (ds?0??), on polymorphic (ds??0?) and also on separable (ds???0) datasets. On all the other groups of datasets – non-collinear (ds0???), imbalanced (ds?1??), isomorphic (ds??1?) and overlapping (ds???1) – d-Confidence outperforms confidence on five out of eight datasets. The results on polymorphic datasets are particularly interesting since these contain classes having distinct clusters in different regions of instance space. Although the coverage efficiency of d-Confidence is not as clear as in isomorphic datasets, d-Confidence still outperforms both confidence and farthest-first. From Figure 6.6 we observe that confidence generally achieves a better coverage than d-Confidence after the initial four queries – which happens in 10 out of 16 datasets. After these few initial queries this trend reverses and d-Confidence improves over confidence. After 16 queries d-Confidence outperforms confidence in 14 out of 16 datasets. Label disclosure complexity When analyzing LDC – which, in this case is equivalent to the number of queries required to first hit an instance of the third class – we observe a clear dominance of d-Confidence against confidence and farthest-first. D-Confidence outperforms confidence and farthest-first in 14 out of 16 datasets. Confidence present a lower LDC at ds0001 and ds0100. The overall mean LDC on these artificial datasets is 7 for d-Confidence, 26 for confidence and 86 for 108 D-Confidence farthest-first – a clear advantage of d-Confidence. This is a core result addressing our purposes. The low LDC observed in these artificial datasets is a very promising indicator of the competence of d-Confidence to achieve low-cost disclosure of all target classes. Error Somehow surprisingly, we observe that d-Confidence also improves on error. D-Confidence outperforms both confidence and farthest-first in 11 out of 16 datasets while confidence achieves the better performance in four out of 16. In other words, improved class coverage is not done at the cost of increasing error. Cluster morphism seems to have impact on error. From all the isomorphic datasets, d-Confidence has a significant lower mean error than that of confidence and farthest-first on seven out of eight datasets. However, on polymorphic datasets, d-Confidence has similar results to those of confidence – d-Confidence outperforms confidence on three out of eight datasets, while the inverse occurs on four datasets. Performance evaluation on Iris Such results on simulated data have been checked on a real dataset (Figure 6.7). We have applied this same experimental plan to the Iris dataset (Frank and Asuncion, 2010). The results we have achieved on Iris confirm the results on artificial data. Instance space coverage is more efficient when using d-Confidence and this is not achieved at the cost of increasing error which, in fact, also improves. Figure 6.7: Instance space coverage on the Iris dataset as new queries are added 6.4 Evaluation 109 On the Iris dataset we have also recorded the number of queries required to get a full coverage of instance space. Instance space is assumed to be fully covered when all instances in the working set lie closer than a certain predefined distance from at least one labeled instance. This predefined distance has been set to 1 10 – the initial setting – and then to 1 8,1 6and 1 4of the maximum distance between instances. It is expected that the number of queries required to achieve a full coverage decreases as the radius of the assumed covered neighborhood increases. This should be more evident when newly added queries belong to remote regions in instance space thus having reduced neighborhood intersections with previously covered instances. Our purpose is to evaluate whether d-Confidence is in fact exploring unseen regions in instance space more efficiently than confidence – its direct competitor. We have observed that the number of queries required to get a 100% coverage of instance space with confidence decreases from 84 to 35 – a reduction of 58% in the labeling effort – when the neighborhood radius goes from 1 10 to 1 4. On this same scenario, d-Confidence labeling effort to get a full coverage is reduced from 51 to 8 queries – a reduction of 84%. These results confirm that d-Confidence selects queries from remote regions in instance space more efficiently than confidence. The performance of d-Confidence on Iris supports the foreseen improvements over its baseline criteria. The Iris LDC for farthest-first is 84, for confidence it is 18 and for d-Confidence, three. The mean error is 30.4% for farthest-first, 13.4% when using confidence and 8.2% when using d-Confidence. Impact of input space geometry The difference between farthest-first’s performance and the other criteria is very significant. We have questioned whether farthest-first under-performance is related to some bias introduced by our artificial datasets and/or the indicator we are using to assess instance space coverage. Our hypothesis is that it is related to both the topology of the dataset – mainly with the relation between dense and sparse regions in instance space – and the indicator in use to measure coverage. Being guided by distance only, farthest-first might be directed to distant regions that are sparse. This behavior does not contribute to instance space coverage the way we have defined it – number of instances lying in some neighborhood of all labeled instances in Li. 110 D-Confidence Table 6.4: Artificial datasets sorted by decreasing order of farthest-first coverage Dataset Cov (ff) ds0100 0.838 ds1010 0.771 ds1100 0.769 ds1000 0.767 ds1101 0.767 ds1110 0.766 ds0001 0.756 ds0000 0.745 ds1001 0.743 ds0110 0.725 ds0101 0.721 ds0010 0.716 ds1011 0.704 ds0011 0.684 ds0111 0.675 ds1111 0.667 Sorting the artificial datasets by decreasing order of farthest-first mean coverage (see Table 6.4) provides some evidence on this question. We may observe that in the top eight datasets there are six separable datasets. Our separable datasets have dense clusters distant from each other (see Figure 6.4). This is an adequate topology for farthest-first that guides the learning process to select queries from distant regions that are simultaneously dense thus, contributing to improved coverage in our sense. In non-separable datasets there is no clear distance between clusters and the distribution of instances in input space is more homogeneous. When being directed to select queries in borderline regions, that are also less dense, farthest-first misses the chance to improve coverage as much as the other criteria. Impact of cluster variance Analyzing cluster variance (Table 6.5) provides further evidence on this hypothesis. Inter-cluster and intra-cluster variance were computed for the number of clusters artificially generated in each dataset. The correlation between the percentage of total variance that is explained by inter-cluster variance and instance space coverage for farthest-first (Table 6.6) is more than 10% higher than that of confidence and d-Confidence. There is also a high correlation between d-Confidence and confidence coverage rates. 6.4 Evaluation 111 Table 6.5: Percentage of inter-cluster to total variance Dataset Number of clusters Inter-cluster/Total variance ds0000 6 0.886 ds0001 5 0.785 ds0010 3 0.875 ds0011 3 0.670 ds0100 5 0.974 ds0101 5 0.874 ds0110 3 0.837 ds0111 3 0.664 ds1000 6 0.958 ds1001 6 0.947 ds1010 3 0.924 ds1011 3 0.765 ds1100 5 0.897 ds1101 5 0.827 ds1110 3 0.666 ds1111 3 0.651 Apparently confidence introduces a bias that leads the learning process to select queries from more dense areas in instance space – favoring exploitation. Farthest-first directs the learning process to query instances in unexplored regions irrespectively of how dense they are – favoring exploration. Despite the high correlation between the coverage rates of d-Confidence and confidence, d-Confidence outperforms confidence probably for its ability to take advantage of the merits of both its baseline criteria. Main outcomes The results from these experiments provide evidence that d-Confidence outperforms the traditional confidence approach as well as farthest-first regarding instance space coverage, identification of unknown classes and error. D-Confidence improves instance space coverage and reduces the number of queries required to identify instances from unknown classes without Table 6.6: Correlation between inter-cluster/total variance and coverage Correlation Inter/Total Cover ff Cover c Cover ff 0.689 1 Cover c 0.562 0.231 1 Cover dc 0.580 0.316 0.806 118 D-Confidence a relative frequency of 0.2% and six other classes have a relative frequency below 1% – allows evaluating the early identification of under-represented classes. The average first-hit computed from Table 6.8 over under-represented classes – classes 5 to 10 – shows a weak performance of confidence in finding rare classes (Table 6.10). Table 6.10: Average first-hit over under-represented classes at the Poker dataset Classifier ff c dc SVM 80 182 76 NNET 80 141 72 RPART 80 162 89 D-Confidence outperforms both its baseline criteria w.r.t. the early identification of instances from under-represented classes when using SVM and NNET as base classifiers. Farthest-first however, improves over the other when using RPART. LDC provides further evidence supporting the improved performance of d-Confidence over its baseline criteria. In fact, d-Confidence has the lowest LDC on all combinations of dataset and classifier that were evaluated on tabular data except on the Vowels dataset when using RPART as a base classifier (Table 6.9). The average gain on d-Confidence LDC for all pairs dataset/classifier when compared to confidence on tabular data is of 542%, meaning that confidence requires over six times more queries than d-Confidence to identify all target classes. This figure, however, is highly biased by the outlier observed on Iris/NNET. Nevertheless, if we remove this outlier from our data we still have a gain of 101% in LDC, meaning that, on average, confidence requires twice as many queries as d-Confidence to achieve a full coverage of the classes to learn on all tabular datasets. Performance under different levels of class imbalance With the purpose of further investigating the ability of d-Confidence when in presence of imbalanced data, we have evaluated the AL strategies being studied under different levels of class imbalance. We have performed this evaluation on the datasets with uniform class distribution – Iris and Vowels – using SVM as the base classifier. The original training datasets were manipulated to assure imbalanced class distributions. From each of those datasets we have extracted four samples with biased class distributions. At Iris, the number of instances from one of the classes – which will become the minority class – was 6.4 Evaluation 119 reduced in those samples to 1, 3, 5 and 9, corresponding to a percentage of 2%, 6%, 11% and 19% relative to the frequency of each of the two remaining classes which kept their original frequency. At Vowels, the number of instances from four of its 11 classes – which will become the minority classes – was reduced in those samples to 1, 2, 3 and 6, corresponding to a percentage of 3%, 7%, 10% and 21% relative to the frequency of each of the remaining classes whose frequency was kept unchanged. Then we have repeated the same experiments as before but now on these biased training sets. The empirical results are presented in Table 6.11. The LDC computed from these experiments (Table 6.11) confirms the ability of d-Confidence to retrieve rare instances in comparison to its baseline criteria. Table 6.11: LDC under different imbalance levels. SVM as base classifier. Imbalance is the ratio of the frequency of the minority classes to the rest Dataset Imbalance ff.ldc c.ldc dc.ldc Best Iris 19% 84 61 3 dc Iris 11% 87 61 3 dc Iris 6% 87 61 4 dc Iris 2% 88 88 5 dc Vowels 21% 99 26 23 dc Vowels 10% 84 39 35 dc Vowels 7% 98 69 55 dc Vowels 3% 102 58 74 c On average, d-Confidence presents lower LDC than its baseline criteria on all settings except at Vowels with 3% imbalance. We may observe a similar scenario, with a significant dominance by d-Confidence, when analyzing the number of known classes and error (Table 6.12). D-Confidence outperforms its baseline criteria with statistical significance at all settings except at the Vowels dataset with 21% imbalance. Common queries selection Comparing the instances that are selected by each AL strategy adds relevant information to our discussion. Are all strategies selecting the same instances at the same stages of the learning cycle? We have investigated this question by measuring the percentage of common queries being selected by each criteria as the learning process iterates at Iris (Figure 6.9a) and Vowels (Figure 6.9b). Each curve in these charts represents the average, computed over all cross validation folds at each iteration, of the percentage of common instances observed in the labeled sets used to train the classifier under the referred strategies – d-Confidence (dc), confidence 120 D-Confidence Table 6.12: Micro-averaged number of known classes and error. Means have been computed over all iterations from all cross validation folds for each combination of dataset, imbalance level and query selection criteria. Bold faced values are statistically significant at 5% Dataset Imbalance ff.kc c.kc dc.kc ff.e c.e dc.e Iris 2% 2.56 2.48 2.96 0.72 0.79 0.67 Iris 6% 2.60 2.58 2.98 0.63 0.59 0.40 Iris 11% 2.61 2.59 2.98 0.58 0.49 0.26 Iris 19% 2.64 2.62 2.98 0.52 0.41 0.15 Vowels 3% 8.11 8.87 8.98 0.94 0.92 0.92 Vowels 7% 8.40 9.36 9.55 0.92 0.92 0.91 Vowels 10% 8.65 9.77 10.12 0.91 0.89 0.89 Vowels 21% 8.83 10.27 10.28 0.81 0.77 0.76 (c) or farthest-first (ff). Instances in L1– which, given a dataset, are the same for all AL criteria – were not considered when computing these intersections. Only the instances that were in fact selected by each criteria from the first iteration on were accounted for. (a) Iris (imbalance 19%) (b) Vowels (imbalance 21%) Figure 6.9: Evolution of the percentage of common selected queries throughout the learning cycle. Each line represents the percentage of common instances for a given pair of strategies (dc-c, dc-ff, c-ff) It is clear from Figure 6.9a that d-Confidence and confidence query many common instances during the initial stage of the learning process at the Iris dataset. In fact, after the first 29 queries, the labeled sets of both these strategies, L29, have nearly 60% intersection. This level of overlapping then stabilizes to start increasing later as a consequence of the exhaustion of the unlabeled set which necessarily increases the interception between the labeled sets of all strategies. 6.4 Evaluation 121 The opposite behavior is observed when comparing farthest-first with either confidence or dConfidence. Despite the fact that d-Confidence and farthest-first share many common instances at the very first iterations (60%), this overlap drops fast getting close to 20% after 11 queries. At the Vowels dataset, the overlap between the labeled sets being built by all AL strategies increases at a constant rate throughout the majority of the learning process. Only at the very beginning, during the initial 35 iterations, a distinct behavior is observed with d-Confidence and farthest-first querying more common instances than the other. As observed also at the Iris dataset, confidence and farthest-first are the strategies sharing fewer queries. This behavior is expected since d-Confidence is a combination of both confidence and farthest-first while these are independent from each other. With the exception of the initial stage of the learning process for Iris w.r.t. dc-c, the percentage of common queries shared by d-Confidence and its baseline criteria is small. This is an indication that d-Confidence is promoting a new learning path. 6.4.3 Text The evolution of the error rate and the number of known classes over text corpora is shown in Figures 6.10a and 6.10b with curves for each selection strategy under evaluation. (a) NG corpus (b) R52 corpus Figure 6.10: Known classes and generalization error Similarly to what we have done at phase two, the evolution of error and mean number of known classes throughout all the learning cycle has been also summed up to summarize overall 122 D-Confidence performance on text corpora (Table 6.13). Table 6.13: Micro-averaged number of known classes and error. Means have been computed over all iterations from all cross validation folds for each combination of dataset, classifier and query selection criteria Dataset Classifier ff.kc c.kc dc.kc ff.e c.e dc.e NG SVM 19.2 18.6 19.1 0.631 0.629 0.612 R52 SVM 34.4 35.5 39.7 0.531 0.383 0.447 Besides the total number of queries required to retrieve labels from all classes and generalization error, we have also observed first-hit (Tables 6.14 and 6.15). When computing first-hit for a given class we have excluded the experiments where the initial labeled set, L1, contains instances from that class. Table 6.14: First-hit for the NG dataset Class Freq ff-fh c-fh dc-fh 1 29 29.8 36.9 35.7 2 22 45.4 46.6 45.7 3 21 87.9 63.7 85.4 4 34 7.5 29.4 7.4 5 35 22.2 23.6 25.2 6 24 17.6 41.2 17.1 7 21 11.4 59.6 12.6 8 24 12.6 32.9 13.1 9 25 12.5 45.4 11.4 10 22 45.5 41.1 48.9 11 22 3.8 47.2 3.9 12 24 3.7 31.8 4.8 13 28 30.0 31.3 34.0 14 28 6.1 25.8 5.4 15 22 5.4 27.4 6.2 16 28 2.4 14.9 2.6 17 23 25.3 23.8 31.0 18 26 8.6 38.3 8.6 19 22 22.7 23.6 24.7 20 20 8.6 29.7 7.7 average 20.45 35.71 21.57 The learning process for the R52 dataset was halted after 600 iterations, before exploring the full unlabeled pool – the working set had 1000 instances, 900 of which were used for training in each fold. All the class labels to learn were identified after 600 iterations for all the selection 6.4 Evaluation 123 Table 6.15: First-hit for the R52 dataset Class Freq ff-fh c-fh dc-fh 1 239 1.0 24.0 1.0 2 5 78.5 115.6 64.7 3 3 230.3 118.6 178.7 4 2 98.7 167.4 107.8 5 6 239.0 173.7 110.6 6 11 7.5 80.0 10.0 7 4 15.9 123.6 19.1 8 3 130.0 173.3 102.9 9 7 240.2 128.8 136.0 10 2 153.2 118.0 99.5 11 40 14.6 12.4 20.0 12 2 209.9 158.5 166.4 13 435 2.5 25.2 4.0 14 2 219.0 152.2 150.4 15 3 192.8 214.1 123.9 16 7 113.7 91.9 107.8 17 9 33.1 92.7 46.3 18 5 24.9 96.7 16.8 19 2 93.1 140.0 104.7 20 3 411.8 206.7 184.9 21 2 273.2 143.6 154.5 22 2 588.6 188.9 202.8 23 30 76.0 28.9 63.4 24 4 341.9 171.7 171.1 25 4 253.9 196.2 224.0 26 2 459.6 313.1 256.4 27 5 282.8 130.0 150.7 28 2 294.7 216.3 144.5 29 2 422.5 175.5 198.7 30 3 68.5 213.3 85.2 31 2 111.7 206.0 126.7 32 2 248.3 233.7 167.0 33 30 53.0 39.7 49.7 34 15 67.6 44.6 99.0 35 4 187.8 271.6 219.6 36 2 58.2 153.2 84.1 37 3 45.7 137.6 44.8 38 3 66.6 159.3 52.1 39 2 101.2 226.0 106.9 40 2 90.4 144.3 75.5 41 5 67.6 68.7 62.9 42 3 206.6 159.1 144.8 43 4 43.4 153.4 36.7 44 14 72.7 103.8 76.6 45 3 86.5 179.7 123.9 46 12 3.2 68.6 6.6 47 2 45.9 148.5 51.1 48 3 101.9 160.8 76.1 49 35 39.4 36.4 72.9 50 3 219.0 175.6 108.7 51 3 482.2 146.1 183.5 52 2 302.7 258.8 196.5 average 159.10 143.58 107.16 124 D-Confidence criteria, except for farthest-first. The mean number of known classes after 600 iterations equals 52 for confidence and d-Confidence, meaning these criteria have achieved full coverage of the class labels to learn in all the cross validation folds. For farthest-first the average number of known classes, 50.3, is below 52 which means that farthest-first was not able to identify all class labels in all cross validation folds after 600 iterations. Farthest-first missed, in several folds, six classes with frequency of two, two classes with frequency of three and one class with a frequency of four. In such cases we have assigned the most favorable first-hit value for the unidentified classes – a value from 601 on. For instance, in a given fold where farthest-first misses two classes their first-hit values are assumed to be 601 and 602 – the very first queries after halting the learning process at 600 iterations. First-hit means were computed on this assumption – the most favorable assumption for farthest-first. Finding under-represented classes There is no clear dominance, neither from d-Confidence nor from farthest-first, when finding unknown classes in the NG dataset (Figure 6.10a). However, both these criteria outperform confidence at this dataset. The difference between mean first-hit of d-Confidence and farthest-first in Table 6.14 – 20.45 for farthest-first and 21.57 for d-Confidence – is not statistically significant (α=5%). In R52, farthest-first starts by identifying unknown classes a little faster than d-Confidence (Figure 6.10a). However, after the initial learning stage, d-Confidence outperforms and dominates farthest-first. This behavior had already been observed, with tabular datasets, in the previous experimental phase. When identifying unknown classes, farthest-first leads, up to the 45th query, on average, taking a maximum advantage of two classes after 37 queries. After 45 queries, with 13.2 classes identified on average, d-Confidence clearly dominates farthest-first. It is interesting to notice that farthest-first beats d-Confidence on the majority classes (Table 6.15) but, once all majority classes have been found and only minority classes are left unexposed, d-Confidence reveals its ability to find rare instances. The mean frequency of the classes that are first found in R52 by d-Confidence is 3.2, while it is 12.5 for confidence and 33.8 for farthest-first. This aspect might be further investigated from a coarser point of view by analyzing how fast each AL criterion retrieves exemplary instances from a batch of classes instead of analyzing single 6.4 Evaluation 125 classes one at a time. To analyze this particular aspect we provide a benchmark based on random query selection – averaged over 10 random samples. We have recorded the number of queries required to identify bunches of distinct classes in multiples of 10 for R52 and multiples of 4 in NG. These bunches are constituted by classes sorted by increasing order of their first-hit. Figures 6.11 and 6.12 give an overview of the number of queries that are required in each setting to first hit a given number of distinct classes. Figure 6.11: Queries required to identify bunches of distinct classes in NG dataset Figure 6.12: Queries required to identify bunches of distinct classes in R52 dataset In the case of the R52 dataset, d-Confidence always finds new classes faster, that is with fewer queries, than confidence. The first bunch of 10 distinct classes – the first classes being identified 126 D-Confidence are generally majority classes – is found as fast with random sampling and farthest-first as with d-Confidence but, from there on, when rare classes come by, d-Confidence takes the lead. The outcome is quite different in the NG dataset. In this dataset d-Confidence still outperforms confidence but it is beaten by random selection of instances after identifying 13.3 classes on average – after 22 queries on average. The ability to retrieve exemplary instances from unknown classes of d-Confidence is comparable to that of farthest-first on NG. When in presence of balanced datasets, as NG, d-Confidence identifies new classes faster than random selection at the initial phase of the learning process but selecting instances by chance is better to identify instances in the latest stage of the learning process when few classes remain undetected. Figures 6.13 provide additional evidence on the ability of d-Confidence to find rare instances. (a) D-Confidence vs farthest-first (b) D-Confidence vs confidence Figure 6.13: Average gain of d-Confidence over its baseline criteria to first hit classes on R52. Classes are sorted by increasing frequency These charts represent the difference in d-Confidence first-hit compared to their baseline criteria. Negative differences mean that d-Confidence performed better, i.e., found representative instances of the class with fewer queries than its baseline criteria. In these charts, classes are sorted by increasing frequency, in first place, and then by decreasing gain. This sorting scheme is responsible for the patterns that are observed in both charts of Figure 6.13. For instance, all the minority classes that are represented in the horizontal axis of Figures 6.13a and 6.13b by the coordinates 1 to 17 have a frequency of two. For this group, the gain is sorted by increasing order thus generating the pattern that we may observe in both charts for each group of classes with the same frequency. The dashed trend lines, represented in both charts (Figures 6.13), with a positive slope clearly 6.4 Evaluation 127 show that the gain in d-Confidence first-hit, when compared to its baseline criteria, decreases when the class frequency increases. D-Confidence assures a significant reduction in the mean number of queries that are required to first hit classes in R52. This reduction is more important in minority classes, i.e., in the first classes appearing in the horizontal axis. Another perspective of these results may clarify our point of view. Figure 6.14a presents the number of classes that were first found by each criteria for each different class frequency in the horizontal axis. Figure 6.14b represents the accumulated number of first found classes. As detailed below, both these charts show evidence on the improved ability of d-Confidence to find exemplary instances of under-represented classes. (a) First found classes (b) Accumulated first found Figure 6.14: Number of classes of a given frequency first found by each criteria on R52 When comparing d-Confidence against farthest-first we can observe that from the 17 classes in R52 that have a frequency of two, d-Confidence finds 11 before farthest-first. From the 12 classes with a frequency of three, d-Confidence finds 10 before farthest-first. From the 13 classes with frequency between four and nine, d-Confidence finds 10 with fewer queries than farthest-first. From the remaining 10 classes, with a frequency between 11 and 435, d-Confidence finds only two before farthest-first. A similar comparison against confidence shows similar results. From the 17 classes in R52 that have a frequency of two, d-Confidence finds 13 before confidence. From the 12 classes with a frequency of three, d-Confidence finds 10 before confidence. From the 13 classes with frequency between four and nine, d-Confidence finds 10 with fewer queries than confidence. From the remaining 10 classes, with a frequency between 11 and 435, d-Confidence finds five before confidence.