Active Learning with Ensembles for Image Classification
- 格式：pdf
- 大小：160.04 KB
- 文档页数：6
Active Learning with Ensembles for Image Classification Content Areas:Machine Learning,Data MiningAbstractIn many real-world tasks of image classification,limited amounts of labeled data are available totrain automatic classifiers.Consequently,extensivehuman expert involvement is required for verifica-tion.A novel solution is presented that makes useof active learning combined with an ensemble ofclassifiers for each class.The result is a significantreduction in required expert involvement for uncer-tain image region classification.1IntroductionMultimedia content is rapidly becoming a major target for data mining research.This paper is concerned with im-age mining,discovering patterns and knowledge from im-ages for the purpose of classifying images or for similarity matching between images.The specific problem we address is image region classification.Egeria Densa is an exotic submerged aquatic weed causing navigation and reservoir-pumping problems in the Sacramento-San Joaquin Delta of Northern California.As a part of a control program to man-age Egeria,classification of regions in aerial images is re-quired.This problem can be abstracted to one of classifying massive data without class labels.Relying on human experts for class labeling is not only time-consuming and costly,but also unreliable if the experts are overburdened with minute and routine tasks.Massive manual classification becomes im-practical when images are complex with many different ob-jects(e.g.,water,land,Egeria)under varying picture-taking conditions(e.g.,deep water,sun glint).The main objective of the project is to relieve experts from going through all the images and pointing out locations where Egeria exists in the image.We aim to automate the process via active learning to limit expert involvement to decisions about which the auto-matic classifier is uncertain.The following desiderata for an image classification system present a unique challenge to AI research for novel solutions.1.Reduced expert involvement.Classification algorithms that require less expert involvement are essential in real-world ap-plications,as human interaction forms the most serious bot-tleneck for efficient processing.2.Fewer labeled training beled data are necessary to train automatic classi-fiers in a supervised fashion.The only source for such data is manual,tedious,and expensive labeling by experts.This process becomes a bottleneck for massive processing.Conse-quently,it is sensible to ask for only a small number of labeled images for training.3.Classification performance.An im-age classification system can produce certain and uncertain classifications.Being able to reduce the number of uncertain classifications translates directly to the reduction of required expert involvement.In addition,classifications deemed cer-tain should be correct.Standard performance measures for detection problems such as accuracy,precision,and recall should be used in evaluation.4.Generalization.To gen-eralize,a classifier must perform well with unseen images. This is a central issue in pattern recognition and learning the-ory.A typical approach to avoid overfitting in training is to regularize the structure of the classifier[?].Another[?; ?]is to combine the outputs of an ensemble of several,per-haps weak classifiers.The contributions of this paper are a novel concept of class-specific ensembles,and learning algorithms for search of op-timal ensembles and for iterative active learning.We notice that different types of classifiers are better suited to detect-ing different objects such as Egeria,land,water.Since it is impractical to train one classifier for each object(as experts need to provide training instances for all objects),we propose a novel approach to class-specific ensembles and explain why it should outperform the single ensemble approach.We also present a novel method of combining individual classifiers to form an optimal ensemble.We show that this approach sig-nificantly reduces the number of uncertain image regions and is better than a single ensemble for the task of object detec-tion.Iterative active learning is proposed to further reduce expert involvement in classification of new images.With limited interaction with experts,our active learning scheme adapts the ensembles to new images.Because of the scarcity of training images,it is likely that training data only partially represent testing data(new images).Iterative active learning allows the ensembles to efficiently work on new image data with limited expert involvement.Section2presents related work.Our approach is moti-vated and described in detail in section3.Section4docu-ments the algorithms for each step.Section5provides empir-ical evaluation details.We conclude in section6.2Related WorkAlthough regularization and structural risk minimization canbe effective in ensuring the generalization capability of a sin-gle classifier,recent research suggests that generalization can be guaranteed by using ensemble methods in a particular way [?].The key point is to have individual classifiers that are uncorrelated with each other.Bagging trains classifiers of the ensemble using different subsets of the training data [?].Boosting gives different weights to different samples of the training data for each clas-sifier of the ensemble [?].Random forests use a randomly chosen subset of original features at each decision node of a classifier [?].It is also possible,although less effective,to restrict each classifier to a particular feature set [Duin and Tax,2000].Researchers also focus on optimal combination strategies to obtain the final result from an -mon combination strategies are maximum posterior probabil-ity,majority,normalized product of the posteriors (maximum belief),consensus,median,and means of the outputs.In active learning,Freund et al.[Freund et al.,1997]sug-gested the Query-by-Committee algorithm (QBC)that uses a committee of perceptrons to sample from a training data set to reduce prediction error.Most current research [Iyen-gar et al.,2000;Hakkani-Tur et al.,2002;Saar-Tsechensky and Provost,2001;2002]concentrates on algorithms to pro-cess data automatically and algorithms that involve much less human expert involvement.A variant of an Active Learn-ing algorithm has been suggested [Iyengar et al.,2000]that learns from specific unlabelled instances via uncertainty sam-pling.The goal is to reduce the number of queries to human experts.Hakkani-Tur et al.[Hakkani-Tur et al.,2002]sug-gested a similar approach in the domain of automatic speech recognition (ASR).The difference between their approaches is in their sampling methods that select the most informative examples for learning.Other researchers [Saar-Tsechensky and Provost,2001;2002]mentioned that most of the previ-ous work on Active Learning focused on improving accuracy rather than reducing expert involvement.Instead they con-centrated on using class probability estimates to get the class probability rankings,which enabled effective sampling from unlabelled instances.The authors proved that their sampling technique is better (in terms of training data set size)than un-certainty sampling or bootstrapping.3Class-Specific EnsemblesWe first discuss the need for class-specific ensembles,in par-ticular dual ensembles for a 2-class problem,and then elabo-rate on how to learn the dual ensembles.3.1Single vs.Dual EnsemblesThe example in Figure 1illustrates the need for dual ensem-bles in our domain and their difference from a single en-semble.A single ensemble can produce three outputs:True,False,Uncertain ,as shown in the left of Figure 1.The mid-dle part is uncertain as the ensemble cannot reach consensus;its posterior probability is close neither to 1nor to 0.The True and False parts do not overlap because in such an en-Single Ensemble Dual EnsemblesFigure 1:An illustrative example for two types of ensembles semble learning,the focus is on one class and the other class is determined by default.In a more general setting where the class distributions for True and False are not exactly reversed,being certain about True does not necessarily mean being certain about False .Then it would be necessary to learn two different ensembles for the two classes,as shown in the right of Figure 1.The regions between the lines A and B are don’t know s or un-certain regions.Each ensemble focuses either on instances of one class or on its ing multiple ensembles helps provide a better classification and also a better separa-tion between the certain and uncertain classifications.The subsequent problem is to identify relevant classifiers to form dual ensembles.3.2In Search of Optimal Dual EnsemblesWe may tend to use as many classifiers in an ensemble as possible because of the following.•Each classification algorithm may have a different view of the training image and capture varied aspects of the image,as different classification algorithms have differ-ent biases and assumptions.•No single classifier can cover all.In other words,some algorithms may succeed in capturing some latent infor-mation about the domain,while others may fail.However,problems can result from using too many classifi-cation algorithms,as follows.•Using more classification algorithms can result in longer overall training time,especially so if some of the algo-rithms are time-consuming to train.•Some algorithms may be prone to over-learning in the image domain.If these algorithms are included in the ensemble,there may be a high risk of allowing the en-semble to overfit the training image(s).The above analysis suggests the necessity of searching for a relevant set of classifiers to form an ensemble.Exhaus-tive search for the best combination is impractical because the search space is exponential in the total number of classifica-tion algorithms for consideration.Thus we need an efficient methodology to find the optimal combination of classifiers for the dual ensembles.We first discuss suitable performancemeasures for defining an optimal ensemble,then determine a proper learning algorithm that can optimize the measures.Precision,Recall,and Accuracy are the common criteria used for performance comparison.These measures are de-fined in terms of the instances that are relevant and the in-stances that are correctly classified (or retrieved).The true positives (TP)and true negatives (TN)are the correctly clas-sified instances.A false positive (FP)is when the outcome is incorrectly predicted as YES when it is in fact NO.A false negative (FN)is when the outcome is incorrectly classified as NO when in fact it is YES.Precision,recall,and accuracy are defined in terms of TP,TN,FN,and FP.•P recision =T P/(T P +F P ):the fraction of the classi-fied information which is relevant.•Recall =T P/(T P +F N ):the fraction of the classified relevant information versus all relevant information.•Accuracy =(T P +T N )/(T P +F P +T N +F N ):the overall success rate of the classifier.Accuracy takes into account the true negatives (TN)in its numerator.If a particular image has a large number of class “negative”that are classified correctly,then the resultant ac-curacy may be misleadingly high,overshadowing the others (TP,FN,FP).Particularly,in our application,we are mainly concerned with detecting Egeria (true positives).It has been noted [Provost et al.,1998]that accuracy may not provide a good measure for classification.Since both precision and recall have only TP in their numerator,they are suitable for performance measuring.In addition,we consider reduction in uncertain regions (UC)as a third measure.High precision or high recall alone is not a good perfor-mance measure as each describes only one aspect of classifi-cation.Together they provide a good measure:for example,the product of precision and recall (PR).If both values are 1,their product is 1,which means all and only positivein-stances are classified as positive.Hence,PR is a measure for both generality and accuracy.Among many learning algorithms for classification,clus-tering,and association rules,we observe that association rule algorithms [?]can search the attribute space to find the best combination of attributes associated with a class.An asso-ciation rule A ⇒B satisfies the minimum support and mini-mum confidence.The support for a rule is the joint probabil-ity P (A,B )and the confidence is the conditional probabil-ity P (B |A ),where A and B are itemsets of attribute values (e.g.,a 1=v 1,a 2=v 2,b 1=c 1,b 2=c 2).In our case,B is a class value (b =c ),and A is a combination of attribute values.Thus the confidence of a rule gives us the measure of accuracy of the rule,while the support gives us the mea-sure of generality of the rule.Association rules with very high support are those both general and accurate.There are efficient algorithms to learn association rules from data [?;?].Since precision and recall are parallel to confidence and support,we employ association rule algorithms to search for the optimal dual ensembles.In order to search for optimal ensembles,we need a data set that links classifiers to the label of each image region.This new data set can be obtained by applying all the classifica-tion algorithms to the training image so that each classifieris a feature (i.e.,column)and its value is the prediction of the classifier.For each image region (one instance in the new data set),there are predictions of all the classfiers and also the class label Egeria or not given by experts.We are concerned only with those rules that have the class label Egeria or non-Egeria as the consequent.We will restrict our search to such rules and obtain rules with the maximum number of features (classifiers)in the precedent without a significant loss in sup-port or confidence.The best rule for each class label indicates the best combination of classifiers for the ensemble.Detailed algorithms are given below.4Active Learning with Dual EnsemblesActive learning with ensembles consists of two parts:1.Searching for the optimal dual ensembles;2.Adapting the ensemble active learning to new images.We discuss the details below.4.1Searching for Optimal Dual EnsemblesThe algorithm is presented in Figure 3and illustrated in Fig-ure 2.It takes as input the entire set of classification algo-rithms E and training data T r with class labels l T r ,and pro-duces as output the optimal ensembles for class label yes and class label no .The major steps are (i)creating a new data set D (steps 1-3),(ii)learning association rules from D for dual classes (steps 4-6),and (iii)finding the best association rules for each class (steps 7-14).Rules with support-confidence product >90%of the maximum support-confidence for T r are considered for selection.Each rule set is ranked accord-ing to length -the total number of classification algorithms in the precedent.This is because such rules have the maximum number of tightly bound classifiers in predicting the class la-bel.The longest rule from each set is selected to obtain the optimal ensemble for each class label.Figure 2:Illustrative example for Algorithm in Figure 3input:T r,E:Set of n classification algorithms output:E l=yes,E l=no01Train E with T r to obtain n classifiers,cl1to cl n;02Obtain class labels,l1T r to l nT rfor T r using cl1to cl n;03Form a data set,D←{l1T r ,l2T r,.....,l nT r,l T r};04Learn association rules,Assoc from D;05Assoc1←Filter(Assoc/consequent is l T r=yes);06Assoc0←Filter(Assoc/consequent is l T r=no);07m l=yes←Max(Assoc1,supp∗conf);08m l=no←Max(Assoc0,supp∗conf);09Assoc1←Filter(Assoc1/supp∗conf≥0.9∗m l=yes); 10Assoc0←Filter(Assoc0/supp∗conf≥0.9∗m l=no); 11Assoc1←Sort(Assoc1,length(precedent));12Assoc0←Sort(Assoc0,length(precedent));13E l=yes←Precedent(First(Assoc1));14E l=no←Precedent(First(Assoc0));Figure3:Algorithm for selecting optimal classifiersThe next task is to use the dual ensembles(E l=yes andE l=no)to determine certain and uncertain instances.We needto decide the maximum number of classifiers in an ensemble that should agree on a prediction to reach a decision of“cer-tain”or“uncertain”for each ensemble.An ensemble withall classifiers being required to agree on a prediction would lead to high precision,but low recall;an ensemble with few classifiers being required to agree would lead to high recall and low precision.Thus,we need tofind the maximum num-ber of classifiers with which the ensemble gives the best esti-mated precision and recall.The training image is used againfor this task.E l=yes is certain only if all n l=yes classifiers agree on YES.The precision-recall product(PR0)is recorded.If(n l=yes−1)classifiers agree,the PR1is checked.This process is repeated tofind PR k for(n l=yes−k)classifiersby incrementing k until1classifier remains.The agreement threshold for E l=yes is then the maximum number of class-fiers with highest PR.The same procedure is repeated for en-semble E l=no.The dual ensembles E l=yes and E l=no work together to decide if an instance’s prediction is certain or not following the rule of majority.In predicting an instance,if both E l=yes and E l=no are certain with their predictions,follow the one with more agreeing classifiers;if one is certain and the otheris uncertain,follow the certain one;if both are uncertain,the instance is uncertain.4.2Adapting via Iterative Active LearningClearly,the ensembles obtained from one training image have their limitations:when applied to some of the unseen images, they might result in a large number of uncertain instances. Instead of asking experts to resolve all these uncertain in-stances,we propose an iterative active learning approach that only requires experts to resolve a small number of instances, say25,and uses this additional information to adapt the orig-inal ensemble to a new image.The algorithm is presented in Figure4which takes as input T r,a new image T s,the number of uncertain instances m for experts to resolve,and the dual ensembles.The value of m should be reasonably small so an expert will not be overwhelmed.The algorithm returns the adapted dual ensembles for T s.The essence of the algorithm is to use a small amount of the expert’s input to iteratively adapt the ensembles to a new image so expert involvement can be further reduced while increasing P and R.The oracle is the human expert.The improvement stops when PRgain or UCgain is insignificant(<5%or<10%respectively)or UC new is smaller than m.input:T r,T s,m=25,E l=yes,E l=no,output:E l=yes,E l=no:adapted ensemble pair;01P old←0,R old←0,UC old←0;02Classify T s with E l=yes and E l=no;03Obtain T s cer and T s uncer,UC new=#T s uncer;04if UC new≥m05Calculate P new,R new;06do07T s uncer←RandomSamples(T s uncer,m);08T s cer←RandomSamples(T s cer,m);09T r←T r+T s cer;T s←T s−T s cer−T s uncer;10foreach x i∈T s uncer do11l←class label(x i)from an oracle;12T r←T r+{x i,l};13Retrain E l=yes and E l=no with T r;apply to T s;14Obtain T s cer and T s uncer;15P old=P new;R old=R new;UC old=UC new;16Recalculate P new and R new;17PRgain=P new∗R new−P old∗R oldP old∗R old;18UCgain=UC new−UC oldUC new;19while PRgain>5%∨UCgain>10%∨UC new>m;20Return E l=yes and E l=no;Figure4:Iterative Active Learning Algorithm5Experiments and EvaluationsWe perform experiments with a set of real-world image data. Each image is300×300pixels in TIF format(RGB).The extracted features are of color,texture,and edge.There are 13features in total.The template for feature extraction is 8×8pixels.With50%overlap between neighboring regions, there are a total of73×73or5328regions(instances)per image.We designed4experiments to evaluate the following:1.How dual ensembles fare against single ensembles;2.Whether we need to learn the dual ensembles;3.How the dual ensembles fare against classification rulesdetermined by experts;4.If the dual ensembles are applicable to new images. With the principal goal of reducing the burden on experts,we use only one image for training and apply the learned results to another16testing images of different areas for detection.Optimal Dual Ensembles(A)Optimal Single Ensemble(B)Random Dual Ensembles(C)Domain Expert’s Rules(D) #P*R*UC*P*R*UC*P*R*UC*P*R*UC* 10.71410.802500.714100.802500.50.720750.7950523.60.77400.944835 20.94850.669700.948500.6697000.949760.64762523.20.97000.6865582 30.77660.575270.776650.57545230.782120.58760305.30.81510.677850 40.58980.892280.589950.8922022.50.584410.88936161.50.68330.904418 50.84910.454490.849050.45460140.871910.45609290.60.93450.621786 60.81420.7323200.808650.70675720.813060.68375230.20.81650.738595 70.98410.698250.984100.6972518.50.982620.68771224.30.98400.6711121 80.79600.31761590.798700.30510209.50.793480.38006349.90.92670.6058253 90.93780.3473290.937250.3522013.50.941490.35171252.30.93040.304333 100.58030.4316440.572800.4316553.50.577260.511761520.64780.3599134 110.37740.5285660.366700.490551070.344910.51220241.10.48660.6718129 120.96100.526980.961050.527459.50.961400.5114785.50.96320.523163 130.92690.4438160.926800.44450220.924930.43987121.90.92610.425958 140.83670.5637240.836800.5616541.50.872060.578273960.94700.566799 150.47150.7703140.472000.7750030.520610.72030268.40.56450.7105245 160.95860.6899120.958500.68805220.961330.6907685.40.97330.698441 170.88280.574070.882300.5714521.50.874660.61960340.30.91790.5672134 Average UC*Insts25.18Average UC*Insts38.44Average UC*Insts238.32Average UC*Insts128Average UC*Incr52.7%Average UC*Incr846.6%Average UC*Incr408.4% Comparative ResultsAverage PR Gain-1.04%Average PR Gain-2.01%Average PR Gain14.6%Table1:Experimental ResultsAmong the classification algorithms available in themachine-learning package WEKA[Witten and Frank,2000],we select all that can be applied to the image domain toensure a variety of classification algorithms.There aresix categories:(a)Decision Tree based algorithms suchas C4.5,Decision Stump,Id3,Alternating Decision Tree;(b)Rule/Discretization based algorithms like Decision Tree(PART),One Rule,PRISM,Hyper Pipes,V oting FeatureIntervals;(c)Neural Networks based algorithms such asV oted Perceptrons,Kernel Density Estimators,Logistic;(d)Support Vector Machine based algorithms like SequentialMinimal Optimization for SVMs;(e)Probability Estima-tors such as Naive Bayesian Classifier,Naive BayesianClassifier-simple;(f)Instance Based algorithms such as In-stance Based1,Decision Table.We apply the algorithm in Figure3with the complete setof classification algorithms as input.The output optimal en-semble pair found by association rules are:Decision Trees C4.5,Alternating Decision Trees,DecisionTrees(PART),PRISM,Hyper Pipes,Kernel Density,Logis-tic,Decision Tables⇒Class=yes.Id3,Alternating Decision Trees,Decision Trees(PART),PRISM,Kernel Density,Instance Based1,Decision Tables⇒Class=no.Let precision,recall,and number of uncertain instances forthe k th testing image from ensemble i be P ik ,R ik,and UC ik,and let the corresponding values from ensemble j be P jk,R jk,and UC jk.We calculate precision-recall gain and uncertain instance increase averaged over n testing images as follows:AverageUCIncrease=nk=1UC jk−nk=1UC iknk=1UC ik(1)AverageP RGain=nk=1P jk∗R jk−P ik∗R ikP jk∗R jkn(2)Table1summarizes experimental results in four columns(A,B,C,D).Image#1is the training image.The last tworows show the average PRgain and average UCincrease w.r.t.results in Column A.Experiment1.We compare the use of dual optimal en-sembles(E l=yes and E l=no)with that of single optimal en-sembles(either E l=yes or E l=no).The results are shown inColumn B.The average UCincrease is almost53%and theaverage PRgain is-1.04%.It is evident that in general,dualensembles are not only more accurate,but also separate cer-tain and uncertain instances better than single ensembles,ex-cept for2cases(images#9and#15).Experiment2.We compare the optimal dual ensembles to10randomly selected dual ensembles.We wish to check ifthe optimal dual ensembles could be found by chance.Eachclassifier is randomly chosen from one of the categories men-tioned earlier and learns from the training image.AlthoughBefore Iterative AL After Iterative AL#P R UC P R UCPRgain UCincr#runs 80.79600.31761590.79790.45094742.32%-70.44%3 90.93780.3473290.93780.3473290.0%0.0%1 100.58030.4316440.57090.50951116.13%-75.0%2 110.37740.5285660.44010.74991865.41%-72.73%3 Average UC Insts74.5Average UC Insts26.2530.97%-64.77% 2.25Table2:Experiment4resultsthe average PRgain is only decreased by2.01%,the UCin-crease increases significantly by846.6%as shown in Column C of Table1.We conclude that it is necessary to search for op-timal dual ensembles,as random dual ensembles work poorly in reducing UC.Experiment3.We compare the optimal dual ensembles to results obtained by the classification rules of domain experts. The experts’rules outperform the optimal dual ensembles in terms of PRgain by14.6%,but the number of uncertain in-stances(UC)increases by408.4%(in Column D of Table1). The high PRgain and high UC for the expert classification rules is due to the fact that an expert can only directly work on the former(designing highly general and accurate rules), but not on the latter(finding low UC rules).Our system is particularly designed to compensate in this shortcoming. Experiment4.We explore if the optimal dual ensembles can be further improved via iterative active learning.This function would be very useful in dealing with new images. The algorithm in Figure4iteratively selects a small number of certain and uncertain instances and adds them into the orig-inal training data after experts resolve the uncertain instances. The results are shown in Table2.After a few more iterations of learning,three out of four images with UC>25achieve PRgain(30.97%)and negative UCincrease(-64.77%).This experiment suggests that it is practical to adapt the learned dual ensembles to new images to achieve high performance in terms of PRgain and reduced uncertain instances.6ConclusionWe present a novel approach to active learning with ensem-bles of classifiers.One ensemble is trained for each class. The search of optimal ensembles is transformed to discover-ing association rules between classifiers and a class label.The learned ensembles are then adapted to new images via itera-tive active learning.Extensive experiments were conducted in the real-world domain of detecting seaweed in aerial images. Results show that both components of the solution(class spe-cific ensembles and active learning)can significantly reduce expert involvement without compromising performance. References[Duin and Tax,2000]R.Duin and D.Tax.Experiments with classifier combining rules.In Multiple Classifier Systems, First International Workshop,MCS2000,volume1857, pages16–29.Springer,2000.[Freund et al.,1997]Y.Freund,H.Seung,E.Shamir,and N.Tishby.Selective sampling using the query by commit-tee algorithm.Machine Learning,28(2-3):133–168,1997. [Hakkani-Tur et al.,2002]D.Hakkani-Tur,G.Riccardi,andA.Gorin.Active learning for automatic speech recogni-tion.In International Conference on Acoustics Speech and Signal Processing2002,2002.[Iyengar et al.,2000]V.Iyengar,C.Apte,and T.Zhang.Ac-tive learning using adaptive resampling.In KDD,pages 92–98,2000.[Provost et al.,1998]F.Provost,T.Fawcett,and R.Kohavi.The case against accuracy estimation for comparing induc-tion algorithms.In Proceedings of the15th International Conference on Machine Learning,pages445–453,1998. [Saar-Tsechensky and Provost,2001]M.Saar-Tsechensky and F.Provost.Active learning for class probability esti-mation.In Proceedings of International Joint Conference on AI,pages911–920,2001.[Saar-Tsechensky and Provost,2002]M.Saar-Tsechensky and F.Provost.Active sampling for class probability estimation.In Proceedings of Machine Learning,2002. [Witten and Frank,2000]I.Witten and E.Frank.Data Min-ing:Practical Machine Learning tools and techniques with java implementations.Morgan Kauffmann,2000.。
