Constructing New and Better Evaluation Measures for Machine Learning

1 Introduction

Evaluation measures are widely used in machine learning and data mining to compare different learning algorithms. They are also often used as objective functions to construct learning models. For example, accuracy is a common evaluation measure in machine learning. It has been widely used to compare predictive performance of many learning algorithms including decision trees, neural networks, and naive Bayes (e.g., [Kononenko, 1990]), and it is also the goal of optimization in constructing decision trees [Quinlan, 1993]. In recent years, the ROC (Receiver Operating Characteristics) originated in signal detection [Green and Swets, 1966] has been introduced into machine learning [Provost and Fawcett, 1997; Provost et al., 1998]. The area under the ROC curve, or simply AUC, has been proposed in comparing learning algorithms [Provost and Domingos, 2003] and constructing or optimizing learning models [Ferri et al., 2002; Rakotomamonjy, 2004].

[Bradley, 1997] experimentally compares popular machine learning algorithms using both accuracy and AUC, and finds that AUC exhibits several desirable properties compared to accuracy. For example, AUC has increased sensitivity in Department of Computer Science The University of Western Ontario London, Ontario, Canada N6A 5B7 cling@csd.uwo.ca Analysis of Variance (ANOVA) tests, is independent of the decision threshold, and is invariant to a priori class probability distributions. Recently, [Caruana and Niculescu-Mizil, 2004] empirically compare nine commonly used machine learning measures in terms of the correlation relations. They find that RMS (Root Mean Square error) is most correlated with the other measures on average, and thus it is a robust measure in uncertain situations. They also construct a new measure called SAR by averaging the measures of accuracy, AUC, and RMS, and claim that this new measure works better than RMS.

In [Ling et al., 2003] two formal criteria are established to compare evaluation measures. They are called (statistical) consistency, and (statistical) discriminancy. They formally prove that AUC is consistent with, and more discriminant (or finer) than accuracy, for the binary balanced datasets (which have the same number of positive and negative examples).

In this paper we propose a general method to construct new measures based on existing ones, and prove that they are consistent with and finer than the existing ones. 1 Further, we will show experimentally that the newly constructed measure is more correlated to RMS than the existing ones. With a consistent and finer measure, a greedy hill-climbing learning algorithm (such as neural networks) would search better (i.e., not likely to get stuck in a flat plateau) and find better optimal solutions. We conduct experiments to show that neural networks optimized by the new measure predict better than the ones optimized by the existing ones. This illustrates the usefulness of designing new and finer measures for machine learning, as it provides a general method to improve learning algorithms using greedy search.

2 Review of Formal Criteria for Comparing Measures

In [Ling et al., 2003] the degree of consistency and degree of discriminancy of two measures are proposed and defined. The degree of consistency between two measures f and g, denoted as Cf,g, is simply the fraction (probability) that two measures are consistent over some distribution of the instance space. Two measures are consistent when comparing two objects a and b, if f stipulates that a is better than b, g also stipulates that a is better than b.

1 We normalize all measures in our discussion to be in [0, 1], with 0 to be the worst, and 1 to be the best. For this reason, the accuracy is used instead of the error rate. Also RMS (Root Mean Square error) in this paper is actually (1-RMS).

Using the example of AUC (as f ) and accuracy (as g) on two ranked lists (as a and b), most of the time AUC and accuracy do agree on each other (i.e., they are consistent). However, there are exceptions when AUC and accuracy contradict. Table 1 lists two ranked lists of 10 testing examples, 2 presumably as the result of the prediction by two learning algorithms. The AUC of the ranked list a is 21 25 , 3 and the AUC of the ranked list b is 16 25 . Thus the ranked list a is better than the ranked list b according to AUC. But assuming that both learning algorithms classify half (the right most 5) of the 10 examples as positive, and the other 5 as negative. The accuracy of a is 60%, and the accuracy of b is 80%. Therefore, b is better than a according to accuracy. Clearly, AUC and accuracy are inconsistent here. Again the probability that two measures f and g are consistent is defined as degree of consistency Cf,g. [Ling et al., 2003] define that two measures f and g are consistent iff the degree of consistency Cf,g > 0.5. That is, f and g are consistent if they agree with each other on over half of the cases.

The degree of discriminancy of f over g, denoted as Df/g, is defined as the ratio of cases where f can tell the difference but g cannot, over the cases where g can tell the difference but f cannot. Using AUC (as f ) and accuracy (as g) as example again. There are many cases in which AUC can tell the difference between two ranked lists but accuracy cannot. This is partially due to the fact that AUC has many more values than accuracy. But counter examples also exist in which accuracy can tell the difference but AUC cannot. Table 2 shows such a counter example. We can obtain that both ranked lists have the same AUC ( 3 5 ) but different accuracies (60% and 40% respectively). [Ling et al., 2003] define that ameasure f ismore discriminant (or finer) than g iff Df /g > 1. That is, f is finer than g if there are more cases where f can tell the difference but g cannot, than g can tell the difference but f cannot.

In the next section we will propose a general approach to construct new measures that are provably consistent with and finer than the existing ones.

2 The domain of AUC and accuracy is the ranked lists of labeled examples, ordered according to the increasing probability of being positive. Almost all classification learning algorithms, such as decision trees, naive Bayes, support vector machines, and neural networks produce probability estimations on the classification which can be used to rank testing examples.

3 The AUC can be calculated by the formula [Hand and Till, 2001] AUC = ∑n0 i=1 (ri-i) n0n1 , where n0 and n1 are the number of positive and negative examples (both 5 here) respectively, and ri is the position of the ith positive example.

3 Constructing New and Better Measures

First of all, we show formally that the finer relation is transitive (while the consistent relation is not; a counter example can be easily given). We use f ≻ g to denote that f is finer than g. The following theorem proves that the finer relation is transitive.

Theorem 1 For measures f , g, and h, if f ≻ g and g ≻ h, then f ≻h.

Proof: Let Ψ be the set of the objects to be evaluated, Γ =Ψ×Ψ, A,B,X1,X2,Y1,Y2 ⊂ Γ. In the following definitions we use " f =" to represent " f (a) = f (b)", "g ̸=" to represent "g(a) ̸=g(b)" etc. We define A={(a,b)|a,b,∈Ψ, f ̸= ,g =}, B = {(a,b)| f =,g ̸=}, X1 = {(a,b)| f ̸=,g ̸=,h =}, X2 = {(a,b)| f =,g ̸=,h =}, Y1 = {(a,b)| f ̸=,g =,h ̸=}, Y2 = {(a,b)| f =,g =,h ̸=}. Then clearly Df /g = |A| |B| > 1, Dg/h = |X1|+|X2| |Y1|+|Y2| > 1, and Df /h = |A|-|Y1|+|X1| |B|-|X2|+|Y2| . Since we have |A| > |B|, and |X1|+|X2| > |Y1|+|Y2|, thus |A|-|Y1|+|X1| > |B| - |X2| + |Y2|, D f /h > 1. □

We propose a general approach to construct a "two-level measure", denoted as f :g, based on two existing measures f and g. Intuitively, f :g is a new measure where f is used first as a "dominant" measure in comparison. If f ties in the comparison, then g would be used as a tie breaker. We can formally define the two-level measure f :g as follows.

Definition 1 A two-level measure φ formed by f and g, denoted by f :g, is defined as:

• φ(a) >φ(b) iff f (a) > f (b), or f (a) = f (b) and g(a)> g(b);
• φ(a) =φ(b) iff f (a) = f (b) and g(a) =g(b).

When using AUC and accuracy as two existing measures, if AUC values of the two ranked lists are different, then the new two-level measure AUC:acc agrees with AUC, no matter what the value of accuracy is. But if AUC values are the same, then the two-level measure agrees with accuracy. Our new measure AUC:acc is different from the new measure SAR proposed in [Caruana and Niculescu-Mizil, 2004] as ours is not a simple linear combination of existing measures, and is still a measure for ranked lists with class labels.

The following theorem proves that the two-level measure defined is consistent with and finer than the existing measures.

Theorem 2 Let φ = f :g be the two-level measure formed by f and g, f ≻g, andDf /g ̸=∞. Then Cφ, f =1, and Dφ/ f =∞. In addition, Cφ,g ≥Cf ,g, and Dφ/g =∞. That is, φ is a finer measure than both f and g; i.e., φ≻ f ≻g.

Proof: Let A = {(a,b)| f :g(a) > f :g(b), f (a) < f (b)}. By Definition 1, A = Φ. Therefore Cφ, f = 1. Let B = {(a,b)| f (a) = f (b),g(a) > g(b)}, C = {(a,b)| f (a) > f (b), g(a) > g(b)}, D = {(a, b)| f (a) > f (b), g(a) < g(b)}, Then Cφ,g = |B|+|C| |B|+|C|+|D| , Cf ,g = |C| |C|+|D| . Thus Cφ,g ≥ Cf ,g. For discriminancy there does not exist a,b ∈ Ψ such that " f :g(a) = f :g(b) and f (a) > f (b)". Since Df /g > 1, Df /g ̸= ∞, there exists a,b ∈ Ψ such that " f (a) = f (b) and g(a) > g(b)" which is equivalent to " f :g(a) ̸= f :g(b) and f (a) = f (b)". Therefore Dφ/ f = ∞, similarly we have Dφ/g = ∞. □

To confirm Theorem 2 when it applies to the two-level measure AUC:acc, we conduct experiment to compute the degree of consistency and discriminancy between the AUC:acc and AUC (and acc). This also gives us an intuition for the degrees of the consistency and discriminancy between AUC:acc, AUC and acc.

To conduct the experiment, we exhaustively enumerate all possible pairs of ranked lists with 6, 8, 10, 12, 14, and 16 examples of artificial datasets with an equal number of positive and negative examples. 4 The two criteria are computed, and the results are shown in Tables 3. Clearly, we can see from the table that Cφ,AUC = 1, and Dφ/AUC =∞. Similarly, we can see that Cφ,acc > CAUC,acc, and Dφ/acc = ∞. These confirm Theorem 2.

One might think that we could construct a more discriminant "three-level" measure (such as ( f :g): f ) from the newly formed two-level measure f :g and an original measure f or g, and this process could repeat to get finer and finer measures. However, this will not work. Recall that in Theorem 2 one of the conditions to construct a finer two-level measure φ = f :g is that Df /g ̸=∞. However, Theorem 2 proves that Dφ/ f =Dφ/g = ∞, making it impossible for φ to be combined with f or g for further constructing new measures. Therefore, we can only use this method of constructing a two-level measure once from two existing measures.

This general method of constructing new, consistent, and finer measures is useful in evaluating learning algorithms. For example, when comparing two learning algorithms, if AUC is the same on a testing set, then we compare the accuracy to see which one is better. This gives rise to a finer evaluation measure in comparing learning algorithms than using AUC or accuracy alone. Another advantage of discovering a finer measure is that many learning algorithms build a model by optimizing some measure using hill climbing greedy search. A consistent and finer measure will guide greedy search better as it is less likely to stop prematurely in a flat plateau. We will discuss this later in the paper.

4 Artificial datasets are used for the uniform distribution of the instance space.

In the next section, we will experimentally compare the new measure AUC:acc with RMS, and show that it is more correlated with RMS than AUC and accuracy.

4 Comparing the NewMeasure to RMS

As indicated by [Caruana and Niculescu-Mizil, 2004], given true probabilities of examples, RMS (Root Mean Square error) [Kenney and Keeping, 1962] is shown to be the most reliable measure when the best measure is unknown. In this section, we use artificial data generated with known true probabilities to show empirically that the newly constructed measure AUC:acc is slightly more correlated with RMS than AUC, and significantly more correlated with RMS than accuracy.

We first randomly generate pairs of "true" ranked lists and perturbed ranked lists. The "true" ranked list always consists of n binary examples, with the i-th example having the probability of pi = i n of belonging to the positive class. We then generate a perturbed ranked list by randomly fluctuating the probability of each example within a range bounded by ε. That is, if the true probability is p, the perturbed probability is randomly distributed in [max(0, pi -ε),min(1, pi +ε)]. Table 4 shows an example of the "true" and perturbed ranked lists with 10 examples. Examples with probabilities greater than 0.5 are regarded as positive, otherwise as negative. From this table the values of RMS, AUC, acc, and AUC:acc compared to the "true" ranked list can be easily computed as 0.293, 0.68, 0.6, 0.686 and 0.657 respectively.

After we generate 200 tuples of RMS, AUC, acc, and AUC:acc, we calculate the Pearson correlation coefficients [Edwards, 1976] of AUC, acc, and AUC:acc compared to RMS 5 . We also vary the value of ε, and repeat this process five times. The averaged correlation coefficients are listed in Table 5. We perform a two-tailed paired t-test with 95% confidence interval to see whether the differences in these correlation coefficients are statistically significant. The values in bold means that they are significantly indifferent with the largest values in each row, but they are significantly larger than the values not in bold.

Several interesting conclusions can be drawn from the table. First of all, the correlation coefficients of AUC and AUC:acc are all significantly greater than that of acc with all ε values. It indicates that these measures are more correlated with RMS than accuracy. Secondly, we can see that when ε

5 Again, AUC, acc, and AUC:acc are all compared to (1-RMS) as all measures are normalized to be in [0, 1], with 0 as the worst and 1 as the best predictive performance.

is small (0.3 and 0.5), there is no significant difference in correlation coefficients of AUC and AUC:acc. But with the increasing value of ε, our newly constructed measure AUC:acc becomes significantly more correlated with RMS than AUC. Thirdly, when ε is small (0.3), the values of all correlation coefficients are relatively small (0.2454), but when ε is large (0.9), the values are larger (0.7188). This can be expected as when the perturbation (ε) is small, there can often be no change in ranking (AUC = 1) and accuracy (acc = 1), while RMS is not 0. Thus the values of AUC and acc do not correlate well with RMS. When the perturbation (ε) is large, the rank list (AUC) and accuracy are both affected.

In sum, from the experiments conducted in this section, we can conclude that AUC:acc is slightly more correlated with RMS than AUC, which is significantly more correlated than accuracy.

5 Building Better Models with Finer Measures

In Section 3, we showed that the two-level measure AUC:acc is finer than AUC (which is in turn finer than accuracy). That is, AUC:acc ≻ AUC ≻ acc. As we have discussed earlier, a significant advantage of discovering consistent and finer measures is that they can be used in building learning models (such as classifiers) by optimizing the finer measures directly with greedy hill-climbing search. Intuitively, greedy search will less likely to stop prematurely with a long flat plateau if a finer measure is used for optimization. In this section, we will show that by maximizing AUC:acc or AUC, we will get better prediction than by maximizing the accuracy. We will conduct our experiments using artificial neural networks (ANNs). This is because ANNs are a typical hill-climbing greedy search, and are much more sensitive to small changes in the optimization process by producing different weights. On the other hand, decision trees, for example, may not be sensitive enough to changes in the attribute selection criterion.

Essentially we want to train three ANNs with the same training data optimized using AUC:acc, AUC, and acc respectively. For simplicity, we call the three ANN models ANNAUC:acc, ANNAUC, and ANNacc respectively. Then we test these three ANN models on the testing sets. The predictive performance of the three different learning models on the test sets are measured by AUC:acc, AUC, and acc. We do this many times (using a 5-fold cross-validation) to obtain the average on testing AUC:acc, testing AUC, and testing accuracy. What we expect to see is that the model optimized by AUC:acc predicts better than the model optimized by AUC, measured by all of the three measures (AUC:acc, AUC, and acc). Similarly, the model optimized by AUC would be better than the model optimized by accuracy.

To optimize ANN with a measure f ( f is either AUC:acc, AUC, or acc here), we implement the following simple optimization process: We still use the standard back-propagation algorithm that minimizes the sum of the squared differences (same as the RMS error) as it is the most robust and "strict" measure, but we monitor the change in f instead to decide when to stop training. 6 More specifically, we save the current weights in the neural network, and look ahead and train the network for N more epochs, and obtain the new f value. If the difference between the two f values is larger than a pre-selected threshold ε, it indicates that the neural network is still improving according to f , so we save the new weights (after training N epochs) as the current best weights, and the process repeats. If the difference between the two f values is less than ε, it indicates that the neural network is not improving according to f (a long flat plateau), so the training stops, and the saved weights are used as the final weights for the neural network optimized by f .

We choose ε = 0.01 and N = 100. We choose 20 real-world datasets from the UCI Machine Learning Repository [Blake and Merz, 1998]. The properties of these datasets are shown in Table 6. Each dataset is split into training and test sets using 5-fold cross-validation.

The predictive performance on the testing sets from the three models ANNAUC:acc, ANNAUC, and ANNacc is shown in Table 7.

6 There are few previous works, such as [Herschtal and Raskutti, 2004], that directly optimize AUC in learning.

Note that in Table 7 the predictive results of different models on each dataset can only be compared vertically because it is not meaningful to compare results horizontally as values of accuracy, AUC, and AUC:acc are not comparable.

We perform a paired t-test with the 95% confidence level on each of the 20 datasets comparing the models of ANNAUC:acc, ANNAUC and ANNacc, measured by AUC:acc, AUC and accuracy, respectively. We count in how many datasets that one model is statistically significantly better or worse than another model. The summary of these comparisons is listed in Table 8. The data in each cell indicates the win-draw-loss number of datasets that the model in the corresponding row over the model in the corresponding column. Several interesting conclusions can be drawn from the results in Table 7 and 8. Clearly, the result shows that the ANNAUC:acc model performs significantly better than ANNAUC and ANNacc, and ANNAUC performs significantly better than ANNacc in terms of the three different measures. When evaluated with AUC:acc (or AUC), ANNAUC:acc is significantly better than ANNAUC ( 8 wins, 11 draws, 1 loss), and ANNAUC is significantly better than ANNacc ( 10wins, 9 draws, 1 loss). When evaluated with accuracy, ANNAUC:acc is significantly better than ANNAUC ( 8 wins, 12 draws, 0 loss), and ANNAUC is significantly better than ANNacc ( 11wins, 8 draws, 1 loss). Therefore models optimized by AUC:acc are significantly better than models optimized by AUC and acc. This shows the advantage of using consistent and finer measures in model building by greedy search - optimizing consistent and finer measures lead to models with better predictions.

6 Discussions

The experimental results in the previous section show that the ANN model optimized by AUC:acc performs better than the ANN model optimized by accuracy even if they are both evaluated with accuracy. This is somewhat against a common intuition in machine learning that a model should be optimized by a measure that it will be measured on. However, some recent works have reported similar findings. For example, [Rosset, 2004] has compared the model selection performance of AUC and accuracy in highly uncertain situations. He shows that AUC is more likely to choose the correct model than accuracy, even if the model selection criterion is the model's future accuracy. We have conducted an extensive empirical study that verifies [Rosset, 2004]'s conclusions. Further, we compare the model selection performance of nine evaluation measures, and show that, in general, a finer measure f is more likely to select better models than g even if the model is evaluated by g (submitted manuscript). This prompts us to believe that a finer measure may have an intrinsic advantage in model selection and model optimization.

We believe that finer measures also have advantages in hill climbing search algorithms, leading towards a better training model. The basic idea of hill climbing is to always head towards a state which is better than the current one. A heuristic measure is used to choose the best state from several candidate future states. As future states can be viewed as different learning models, the heuristics measure which chooses the best future state can be viewed as choosing the best future model. Since a finer measure is shown to be more likely to choose the better model, it is more likely to choose the better future state. Therefore, we can conclude that a finer heuristics measure is more likely to lead to a better learning model in hill climbing algorithms. The experimental results in the previous section can be well explained by this conclusion.

7 Conclusions and Future Work

Evaluation metrics are essential in machine learning and other experimental science and engineering areas. In this paper, we first review the formal criteria established in [Ling et al., 2003] to compare the predictive performance of any two single-number measures. We then propose a general approach to construct new measures based on existing ones, and prove that the new measures are consistent with and finer than the existing ones. We compare experimentally the new measure AUC:acc with a best measure RMS, and show that it is more correlated with it than AUC and acc. Finally, we show that learning models optimized with hill-climbing by the new and finer measure predict better than models optimized by the existing ones.

In our future work, we plan to study how to construct new measures based on the popular evaluation measures in information retrieval and natural language processing. We will also re-design other popular learning algorithms by optimizing these new constructed measures.