Active Learning with Ensembles for Image Classification

1 Introduction

Multimedia contents are rapidly becoming a major target for data mining research. This work is concerned with image mining, discovering patterns and knowledge from images for the purpose of classifying 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 manage Egeria, classification of regions in aerial images is required. This problem can be abstracted to one of clas­ sifying massive data without class labels. Relying on hu­ man experts for class labeling is not only time-consuming and costly, but also unreliable if the experts are overburdened with numerous minute and routine tasks. Massive manual classification becomes impractical when images are complex with many different objects (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 go­ ing 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 automatic classifier is uncertain.

The contributions of this work are a novel concept of class­ specific ensembles, and learning class-specific ensembles. We notice that different types of classifiers are better suited to de­ tecting 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. We also discuss how to combine individual classifiers to learn class-specific ensembles. We show that this approach significantly reduces the number of uncertain image regions and is better than a single ensemble for the task of object detection.

2 Class-Specific Ensembles

We may tend to use as many classifiers in an ensemble as possible because (1) each classification algorithm may have a different view of the training image and capture varied as­ pects of the image, as different classification algorithms have different biases and assumptions; and (2) no single classifier can cover all aspects. In other words, some algorithms may succeed in capturing some latent information about the do­ main, while others may fail. However, problems can result from using too many classification algorithms: e.g., (1) us­ ing more classification algorithms can result in longer overall training time, especially so if some of the algorithms are time­ consuming to train; and (2) some algorithms may be prone to overfitting. If these algorithms are included in the ensemble, there may be a high risk of allowing the ensemble to over­ fit some training image(s). The above analysis suggests the necessity of searching for a relevant set of classifiers to form ensembles. Exhaustive search for the best combination is im­ practical because the search space is exponential in the total number of classification algorithms for consideration. Thus we need an efficient methodology to find the optimal combi­ nation of classifiers for the class-specific ensembles.

We adopt three performance criteria for this work: Preci­ sion, Recall, and number of uncertain regions (UC). The first two standard measures are defined in terms of the instances that are relevant and the instances that are classified (or re­ trieved). The third one is the number of instances (regions in an image) the class-specific ensembles cannot be certain about their class predictions. High precision or high recall alone is not a good performance measure as each describes only one aspect of classification. 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 positive instances are classified as posi­ tive. Hence, PR is a measure for both generality and accuracy. F measure can be used for the same purpose.

3 Learning Class-Specific Ensembles

In order to learn class-specific 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 classifier is a feature (i .e., a 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 'non-Egeria' given by experts. We are concerned only with those rules that have the class label Egeria or not as the consequent. We will restrict our search to such rules and obtain rules with the maximum number of fea­ tures (class ifiers) in the precedent without a significant loss in support or confidence. The best rule for each class label indicates the best combination of classifiers for the ensemble.

Among many learning algorithms for classification, clus­ tering, and association rules, we observe that association rule algorithms [Agrawal and Srikant, 1994] can search the at­ tribute space to find the best combination of attributes associ­ ated with a class. Our algorithm is presented in Figure 1. It takes as input the entire set of classification algorithms E and training data Tr with class labels lrr. and produces as output two ensembles for class label yes and class label no.

The next task is to use the dual ensembles (Et=yes and Et=no) to determine certain and uncertain instances. We need to 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 with all class ifiers being required to agree on a prediction would lead to high precision, but low recall; an ensemble with few classi­ fiers being required to agree would lead to high recall and low precision. We need to find a balanced number of classifiers with which the ensemble gives the best estimated precision and recall. The training image is used again for this task.

The dual ensembles E t=yes and E t=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 Et=yes and Et=no are certain with their predictions, follow the one with more agreeing classifiers; if one is certain and the other is uncertain, follow the certain one; if both are uncertain, the instance is uncertain.

4 Experiments and Evaluations

With the principal goal of reducing the burden on expe1ts, we use only one image for training and apply the learned results to another 16 testing images of different areas for detection. Among the classification algorithms available in the machine­ learning package WEKA [Witten and Frank, 2000], we select all that can be applied to the image domain to ensure a variety of classification algorithms. We apply the algorithm in Fig­ ure 1 with the complete set of classification algorithms as in­ put. The class-specific ensembles found by association rules are: Class = yes <¢= Decision Trees C4.5, Alternating De­ cision Trees, Decision Trees (PART), PRISM, Hyper Pipes, Kernel Density, Logistic, Decision Tables; and Class = no <¢= Id3, Alternating Decision Trees, Decision Trees (PART), PRISM, Kernel Density, Instance Based 1, Decision Tables.

We design 3 experiments and provide the summarized re­ sults here (the details will be provided upon request) .

Experiment 1. We compare the use of dual ensembles (Et=yes and Et=no) with that of single ensembles (either Et=yes or Et=no). The average UCincrease (increase in un­ certain regions) is almost 53% and the average PRgain is - 1.04%. It is observed that in general, dual ensembles are not only more accurate, but also separate certain and uncertain instances better than single ensembles.

Experiment 2. We compare the learned dual ensembles to 10 randomly selected dual ensembles. Each classifier is ran­ domly chosen and learns from the training image. Although the average PRgain is only decreased by 2.01 %, the UCin­ crease increases significantly by 846.6%. Hence, it is nec­ essary to search for relevant dual ensembles, as random dual ensembles work poorly in reducing UC.

Experiment 3. We compare the learned dual ensembles to results obtained by the classification rules of domain experts. The experts' rules outperform the learned dual ensembles in terms of PRgain by 14.6%, but the number of uncertain in­ stances (UC) increases by 408.4% 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.

5 Conclusion

We present a novel approach to active learning with ensem­ bles of classifiers. One ensemble is trained for each class. Extensive experiments were conducted in the real-world do­ main of detecting seaweed in aerial images.