Repairing Concavities in ROC Curves

1 Introduction

There is an increasing amount of work on model selection and model combination in the machine learning and data mining literature: for instance, model selection based on ROC space [Provost and Fawcett, 2001], model combination by means of bagging [Breiman, 1996], boosting [Freund and Schapire, 1996], arcing [Breiman, 1998], the mixture of experts method [Jacobs et al., 1991], to name just a few. A review on ensembles of learning machines can be found in [Valentini and Masulli, 2002].

Typically, these methods assume a set of given models with fixed performance, and the issue is how best to combine these models to obtain a better ensemble model. There is no attempt to analyse the performance of the given models to determine a region where performance is sub-standard. This paper investigates methods to improve given models using ROC analysis.

ROC (Receiver Operating Characteristic) analysis is usually associated with classifier selection when both class and misclassification cost distribution are unknown at training time. However, ROC analysis has a much broader scope that is not limited to cost-sensitive classification. A categorical classifier is mapped to a point in ROC space by means of its false positive rate on the X-axis and its true positive rate on the Y-axis. A probabilistic classifier results in a ROC

Shaomin Wu

School of Construction Management and Engineering, University of Reading Reading, United Kingdom

Shaomin.Wu@reading.ac.uk

curve, which aggregates its behaviour for all possible decision thresholds. The quality of a probabilistic classifier can be measured by the Area Under the ROC Curve (AUC), which measures how well the classifier separates the two classes without reference to a decision threshold. A good classifier should have a large AUC, and AUC=1 means that there is a decision threshold such that the corresponding categorical classifier has 100% accuracy.

We use the term model repair to denote approaches that modify given models in order to obtain better models. In contrast, ensemble methods produce hybrid models that leave the original models intact. An approach to model construction using ROC space is given in [Blockeel and Struyf, 2002], where the authors identify and assemble parts of a decision tree that perform well in different areas of ROC space. Our approach in this paper is to identify 'bad' areas, or concavities, in a ROC curve and repair them by manipulating the corresponding low-quality predictions. The approach is experimentally validated using both naive Bayes and decision tree, but the approach has much wider scope as it can be applied to any classifier that computes class scores.

To illustrate the approach, we describe in Section 2 the RepairPoint algorithm that combines three models based on different thresholds of the same probabilistic classifier, and creates a new model which theoretically should improve upon the worst of the three models. In Section 3 we introduce the main algorithm RepairSection, that mirrors an entire concave region (a region of the curve that is below its convex hull). In Section 4 we present experimental results on 23 data sets from the UCI repository. Section 5 reviews some related work on model ensembles, gives the main conclusion and suggests further work.

2 Basics of repairing classifiers in ROC space

Assume that the confusion matrix of a classifier evaluated on a test set is as in Table 1. Then the true positive rate of the classifier is a/(a+b) and the false positive rate of the classifier is c/(c+d). The point (c/(c+d),a/(a+b)) in the XY plane (i.e., ROC space) will be used to represent the performance of this classifier.

If a model is under the ascending diagonal in ROC space, this means that it performs worse than random. Models A and B in Figure 1 are such worse-than-random models.

However, there is a very useful trick to obtain better-thanrandom models: simply invert all predictions of the original model. This corresponds to exchanging the columns in the contingency table, leading to a new true positive rate of b/(a+b) = 1-a/(a+b), i.e. one minus the original true positive rate; similarly we obtain a new false positive rate of d/(c+d) = 1-c/(c+d). Geometrically, this corresponds to mirroring the original ROC point through the midpoint on the ascending diagonal.

Notice that the ascending diagonal really connects two classifiers: the classifier which always predicts negative in (0,0), and the classifier which always predicts positive in (1,1). This suggests that the above repair procedure can be generalised to line segments connecting arbitrary classifiers. For instance, consider Figure 2. Denote the sets of true and false positives of Model i by TPi and FPi, then we can construct Model 4 under the condition that TP1 ⊆ TP3 ⊆ TP2 and FP1 ⊆ FP3 ⊆ FP2. In particular, these inclusion constraints are satisfied if Models 1, 2 and 3 are obtained by setting thresholds on the same probabilistic model, which is what we assume throughout the paper.

Model 4 operates as indicated in Table 2. The inclusion constraints guarantee that the geometric configuration of Figure 2 holds. This is formally stated in the following theorem.

Theorem 1 Assuming that TP1 ⊆ TP3 ⊆ TP2 and FP1 ⊆ FP3 ⊆ FP2, the model produced by Algorithm RepairPoint has true and false positive rates TPr4 = TPr1 +TPr2 -TPr3 and FPr4 =FPr1+FPr2-FPr3, where TPri and FPri denote true and false positive rates of Model i.

Proof. Under the inclusion constraints expressed in the theorem, there are four disjoint groups of examples: those classified positive by Models 1, 3 and 2 (TP1 ∪FP1); those clas- Given three models Model 1, Model 2 and Model 3, output Model 4 that operates as follows:

1. If both Model 1 and Model 2 predict negative, then predict negative;
2. If both Model 1 and Model 2 predict positive, then predict positive;
3. If Model 1 predicts negative and Model 2 predicts positive, then predict the opposite of what Model 3 predicts;
4. Otherwise, predict what Model 3 predicts.

Table 2: Algorithm RepairPoint. The last clause does not apply under the inclusion constraints and is only added for completeness.

sified negative by Model 1 and positive by Models 3 and 2 ((TP3 -TP1) ∪ (FP3 -FP1)); those classified negative by Models 1 and 3 and positive by Model 2 ((TP2 -TP3) ∪ (FP2 -FP3)); and those classified negative by all three models ((POS-TP2)∪(NEG-FP2), where POS and NEG are the sets of all positive and all negative examples, respectively). By construction, Model 4 classifies the first group as positive, the second group as negative, the third group as positive, and the fourth group as negative. The true positives of Model 4 are thus TP1 ∪(TP2-TP3); because of the inclusion constraints the result follows (analogous for false positives).

An equivalent construction is the following. Remove from the test set all instances classified positive by Model 1, and all instances classified negative by Model 2. We can imagine this as a smaller nested ROC space in which Model 1 represents (0,0) and Model 2 represents (1,1); because of the inclusion constraints the position of Model 3 remains unchanged. Note that Model 3 performs worse than a random model in this nested ROC space. We then construct Model 4 as in Figure 1, by inverting the predictions of Model 3 on the remaining test examples.

We end this section by noting that the true and false positive rates derived for Model 4 only hold for the same test set on which Models 1, 2 and 3 were evaluated. On a second, independent test set the ROC locations of the 4 classifiers may be different - in particular, Model 3 may not be below the line connecting Models 1 and 2, in which case Model 4 will be evaluated worse than Model 3. In our experiments, we therefore use validation sets to decide whether concavities are stable across different samples. This will be further discussed in Section 4.

3 Identifying and repairing concavities in a ROC curve

The previous section outlined the main ideas underlying repairing concavities in ROC curves. However, preliminary experiments indicated that the three-point approach is too crude to work well in practice. In this section we introduce our main algorithm, which manipulates a whole section of a ROC curve. A ROC curve is obtained by evaluating a probabilistic classifier on a test set and varying the decision threshold, resulting in a step curve [Hand and Till, 2001]. An efficient way of constructing this curve is by ranking the instances corresponding to their predicted probability of being positive [Fawcett, 2003]. Figure 3 shows both the ROC curve for a probabilistic model evaluated on a small test set 1 and its convex hull [Provost and Fawcett, 2001].

Four points of the ROC curve (point a, b, c and d) are located on the convex hull. Each of these points corresponds to a probability threshold, and thus each segment of the convex hull corresponds to a probability interval. For instance, the convex hull in Figure 3 has three segments corresponding to three disjoint probability intervals. Three out of these five segments delineate concave regions of the ROC curve, indicated as A, B and C. For example, area A is delineated by line ab and the ROC curve between point a and point b. In general, a concave area means that the ranking obtained from the probabilistic model in this probability interval is worse than random. For instance, consider area C which is the largest concavity. One way to repair this concavity is by ignoring the score calculated by the probabilistic model in this interval, and output a constant score (e.g., the mid-point of the interval). Assuming that ties are broken by assigning a random rank, this would replace the concave region of the ROC curve with the line segment cd. It is interesting to note that if this procedure is followed for all concavities, this corresponds to constructing the convex hull by discretising the probability scores.

1 For illustration purposes, the test set contains only a few examples and the resolution of the ROC curve is low. In practical circumstances a step curve with much higher resolution is obtained.

However, in theory we should be able to do better than that: we can invert the ranking of the instances in the probability interval, which can be seen as applying Algorithm RepairPoint to all thresholds in this interval. For instance, by applying this algorithm to the model corresponding to threshold c2, this point would be point-mirrored through the midpoint on line segment cd to the other side of the convex hull. The same can be done for the other thresholds. The resulting ROC curve is shown in Figure 4. We can note that the area C under the curve has been replaced by an equally large area C′ above the curve. The AUC of the repaired curve is therefore larger than both the AUC of the original curve and the AUC of its convex hull.

The algorithm to produce the model with the repaired ROC curve is given in Table 3. The procedure works for any model that calculates a score; a probabilistic model is a special case.

Given a scoring model M and two thresholds T1 > T2, construct a scoring model M′ predicting scores as follows. Let S be the score predicted by M:

1. If S >T1, then predict S;
2. If S <T2, then predict S;
3. Otherwise, predict T1+T2-S.

Table 3: Algorithm RepairSection. The algorithm effectively inverts the ranking of all instances whose score as predicted by M falls in the interval T1 < S < T2.

4 Experimental evaluation

We describe a number of experiments to evaluate our approach. We used 23 two-class data sets from the UCI repository [Blake and Merz, 1998]. Table 4 shows their numbers of attributes, numbers of examples, and relative size of the majority class.

The experimental procedure for the first experiment was as follows. We split a data set into ten folds and use eight of them for training, one for validation and one for testing. We trained a naive Bayes model and a decision tree model 2 on the training data, and chose two thresholds that delineate a concavity. We then produced a new model by repairing the probabilities between the thresholds; we only use the new model if it improves AUC on the validation set. The detailed procedure is given in Table 5.

We ran Experiment RepairSection ten times and obtained m pairs of AUC values. Since we use a validation set, we are able to decide whether or not repair resulted in a better model - if not, we discard it and use the original, unrepaired model. For this reason, we only report results on the non-discarded models, so m may be smaller than 100. The average AUCs of the unrepaired curve and the repaired curve for each data set are given in Tables 6 and 7. We also performed a paired t-test with m-1 degrees of freedom and level of confidence 0.1 to test the significance of the average difference in AUC. The results are favourable: the significance tests yield 10 wins and 3 losses for repaired naive Bayes models and 11 wins and 5 losses for repaired decision tree models.

Experiments without using a validation set yielded worse results, so the use of a validation set appears crucial. We

2 Notice that decision trees can be viewed as scoring classifiers [Ferri et al., 2002; Provost and Domingos, 2003].

1. Train a naive Bayes or decision treemodel M on the training data; construct a ROC curve C and its convex hull H on the training data.
2. Find adjacent points on H such that in this interval the area between C and H is largest. Let T1 and T2 be the corresponding score thresholds.
3. Produce a new probabilistic model M′ by calling RepairSection(T1, T2).
4. Evaluate M and M′ on the validation set, construct their ROC curves and calculate their AUCs. If AUC(M′ ) ≤ AUC(M) then go to 6.
5. Evaluate M and M′ on the test set, construct their ROC curves and calculate their AUCs.
6. Go to 1. until each fold has been used as a test set.

Table 6: Results of Experiment RepairSection with naive Bayes. *For the Bridges data set we used 5-fold crossvalidation.

therefore conducted an experiment with two validation folds: we would only use the repaired model if its AUC was higher on both validation folds. The results for naive Bayes are shown in Table 8. We now obtain 12 significant wins and only 1 significant loss, and the average increase in accuracy is more than a percentage-point. Interestingly, two validation folds didn't work well for decision trees.

Finally, we conducted an experiment with naive Bayes whereby we selected all concavities, and repaired those that occurred on two validation sets. The results were similar to the results in the first experiment (11 significant wins and three losses), with some of the wins and losses occurring on different data sets. It appears that repairing only the largest concavity and using two validation sets is the best strategy (at least for naive Bayes).

5 Discussion and conclusions

The work reported in this paper bears some similarity with ensemble methods. Bagging and boosting are two well-known ensemble approaches. Both approaches are implemented by re-sampling methods. In bagging [Breiman, 1996], the ensemble is formed by making bootstrap replicates of the training data sets and then multiple generated hypotheses are used to get an aggregated predictor. Boosting algorithms [Freund and Schapire, 1996] assign different weights to training instances depending on whether they are correctly classified. The approaches presented in this paper do not make use of re-sampling techniques.

Another relevant ensemble method is majority voting [Kimura and Shridar, 1991; Lam and Sue, 1997], in which the class predicted by the ensemble is the most predicted class among the base classifiers. Algorithm RepairPoint in this paper uses a kind of voting: when both Model 1 and Model 2 (see Figure 2) agree on the classification of an instance, then we choose that class. Otherwise, we choose the class not predicted by Model 3. In majority voting, on the other hand, we would choose the class predicted by Model 3. The difference is that majority voting does not take the quality of the different models into account, whereas our repair scheme knows that Model 3 is sub-optimal and therefore corrects it predictions in the relevant region.

ROC curves contain a wealth of information about the performance of one or more classifiers, which can be utilised to construct better models. They have been used to find optimal labelling of decision trees [Ferri et al., 2002] and to find good decision thresholds for probabilistic classifiers [Lachiche and Flach, 2003]. In this paper we have proposed a novel approach to construct new models by repairing concavities in a ROC curve. The first method, RepairPoint, works on a probabilistic classifier with three probability thresholds, and tries to improve the poorest model with help of the other two. Preliminary experimental results (not reported) showed that this didn't work too well, but this may be due to the fact that the selection of the threshold for Model 3 is not easy. The threshold is a point chosen based on the ROC curve of the training data set; this point (see point c3 in Figure 3) has the farthest distance to the convex hull. If this threshold is not optimal on the test data (for instance, the position c3 in the ROC curve on the test data set unfortunately is located in the position c2), the AUC after repair becomes worse. Still, we believe that the idea of mirroring models around lines in ROC space will prove to be very useful. An interesting investigation for future work is whether a similar method can be made to work if the models are not obtained from a single scoring model (this would invalidate Theorem 1, i.e., the position of Model 4 may be different from the point obtained by pointmirroring).

The second method, RepairSection, locates and repairs an entire concave region of a ROC curve. Experimental results were very encouraging for both naive Bayes and decision trees. For naive Bayes we were able to improve results even further by using two validation folds, but this didn't work for decision trees. We are currently investigating why this is so. One possible explanation is that ROC curves obtained from decision trees have lower resolution (because all instances in a leaf receive the same predicted probability), which may mean that concavities are less stable across samples. Pruning may be another factor, as it has been shown that pruning is detrimental for probability prediction [Provost and Domingos, 2003; Ferri et al., 2003].

There are several other ways in which this work could be taken further. One is to investigate how much repair is possible, by concentrating on ROC curves with large concavities, possibly from artificial data sets. Another is to work with averaged ROC curves that are obtained by cross-validation (since each instance occurs in the test fold exactly once, an averaged ROC curve can be simply constructed by combining all instances with their predicted probabilities).

Acknowledgments

A preliminary version of this paper (without the experimental results with decision trees and two validation folds) appeared as [Flach and Wu, 2003]. We gratefully acknowledge the constructive comments made by the anonymous reviewers. We would also like to thank Rich Roberts for performing additional experiments.