nips nips2003 nips2003-3 knowledge-graph by maker-knowledge-mining

3 nips-2003-AUC Optimization vs. Error Rate Minimization

Source: pdf

Author: Corinna Cortes, Mehryar Mohri

Abstract: The area under an ROC curve (AUC) is a criterion used in many applications to measure the quality of a classiﬁcation algorithm. However, the objective function optimized in most of these algorithms is the error rate and not the AUC value. We give a detailed statistical analysis of the relationship between the AUC and the error rate, including the ﬁrst exact expression of the expected value and the variance of the AUC for a ﬁxed error rate. Our results show that the average AUC is monotonically increasing as a function of the classiﬁcation accuracy, but that the standard deviation for uneven distributions and higher error rates is noticeable. Thus, algorithms designed to minimize the error rate may not lead to the best possible AUC values. We show that, under certain conditions, the global function optimized by the RankBoost algorithm is exactly the AUC. We report the results of our experiments with RankBoost in several datasets demonstrating the beneﬁts of an algorithm speciﬁcally designed to globally optimize the AUC over other existing algorithms optimizing an approximation of the AUC or only locally optimizing the AUC. 1 Motivation In many applications, the overall classiﬁcation error rate is not the most pertinent performance measure, criteria such as ordering or ranking seem more appropriate. Consider for example the list of relevant documents returned by a search engine for a speciﬁc query. That list may contain several thousand documents, but, in practice, only the top ﬁfty or so are examined by the user. Thus, a search engine’s ranking of the documents is more critical than the accuracy of its classiﬁcation of all documents as relevant or not. More generally, for a binary classiﬁer assigning a real-valued score to each object, a better correlation between output scores and the probability of correct classiﬁcation is highly desirable. A natural criterion or summary statistic often used to measure the ranking quality of a classiﬁer is the area under an ROC curve (AUC) [8].1 However, the objective function optimized by most classiﬁcation algorithms is the error rate and not the AUC. Recently, several algorithms have been proposed for maximizing the AUC value locally [4] or maximizing some approximations of the global AUC value [9, 15], but, in general, these algorithms do not obtain AUC values signiﬁcantly better than those obtained by an algorithm designed to minimize the error rates. Thus, it is important to determine the relationship between the AUC values and the error rate. ∗ This author’s new address is: Google Labs, 1440 Broadway, New York, NY 10018, corinna@google.com. 1 The AUC value is equivalent to the Wilcoxon-Mann-Whitney statistic [8] and closely related to the Gini index [1]. It has been re-invented under the name of L-measure by [11], as already pointed out by [2], and slightly modiﬁed under the name of Linear Ranking by [13, 14]. True positive rate ROC Curve. AUC=0.718 (1,1) True positive rate = (0,0) False positive rate = False positive rate correctly classiﬁed positive total positive incorrectly classiﬁed negative total negative Figure 1: An example of ROC curve. The line connecting (0, 0) and (1, 1), corresponding to random classiﬁcation, is drawn for reference. The true positive (negative) rate is sometimes referred to as the sensitivity (resp. speciﬁcity) in this context. In the following sections, we give a detailed statistical analysis of the relationship between the AUC and the error rate, including the ﬁrst exact expression of the expected value and the variance of the AUC for a ﬁxed error rate.2 We show that, under certain conditions, the global function optimized by the RankBoost algorithm is exactly the AUC. We report the results of our experiments with RankBoost in several datasets and demonstrate the beneﬁts of an algorithm speciﬁcally designed to globally optimize the AUC over other existing algorithms optimizing an approximation of the AUC or only locally optimizing the AUC. 2 Deﬁnition and properties of the AUC The Receiver Operating Characteristics (ROC) curves were originally developed in signal detection theory [3] in connection with radio signals, and have been used since then in many other applications, in particular for medical decision-making. Over the last few years, they have found increased interest in the machine learning and data mining communities for model evaluation and selection [12, 10, 4, 9, 15, 2]. The ROC curve for a binary classiﬁcation problem plots the true positive rate as a function of the false positive rate. The points of the curve are obtained by sweeping the classiﬁcation threshold from the most positive classiﬁcation value to the most negative. For a fully random classiﬁcation, the ROC curve is a straight line connecting the origin to (1, 1). Any improvement over random classiﬁcation results in an ROC curve at least partially above this straight line. Fig. (1) shows an example of ROC curve. The AUC is deﬁned as the area under the ROC curve and is closely related to the ranking quality of the classiﬁcation as shown more formally by Lemma 1 below. Consider a binary classiﬁcation task with m positive examples and n negative examples. We will assume that a classiﬁer outputs a strictly ordered list for these examples and will denote by 1X the indicator function of a set X. Lemma 1 ([8]) Let c be a ﬁxed classiﬁer. Let x1 , . . . , xm be the output of c on the positive examples and y1 , . . . , yn its output on the negative examples. Then, the AUC, A, associated to c is given by: m n i=1 j=1 1xi >yj (1) A= mn that is the value of the Wilcoxon-Mann-Whitney statistic [8]. Proof. The proof is based on the observation that the AUC value is exactly the probability P (X > Y ) where X is the random variable corresponding to the distribution of the outputs for the positive examples and Y the one corresponding to the negative examples [7]. The Wilcoxon-Mann-Whitney statistic is clearly the expression of that probability in the discrete case, which proves the lemma [8]. Thus, the AUC can be viewed as a measure based on pairwise comparisons between classiﬁcations of the two classes. With a perfect ranking, all positive examples are ranked higher than the negative ones and A = 1. Any deviation from this ranking decreases the AUC. 2 An attempt in that direction was made by [15], but, unfortunately, the authors’ analysis and the result are both wrong. Threshold θ k − x Positive examples x Negative examples n − x Negative examples m − (k − x) Positive examples Figure 2: For a ﬁxed number of errors k, there may be x, 0 ≤ x ≤ k, false negative examples. 3 The Expected Value of the AUC In this section, we compute exactly the expected value of the AUC over all classiﬁcations with a ﬁxed number of errors and compare that to the error rate. Different classiﬁers may have the same error rate but different AUC values. Indeed, for a given classiﬁcation threshold θ, an arbitrary reordering of the examples with outputs more than θ clearly does not affect the error rate but leads to different AUC values. Similarly, one may reorder the examples with output less than θ without changing the error rate. Assume that the number of errors k is ﬁxed. We wish to compute the average value of the AUC over all classiﬁcations with k errors. Our model is based on the simple assumption that all classiﬁcations or rankings with k errors are equiprobable. One could perhaps argue that errors are not necessarily evenly distributed, e.g., examples with very high or very low ranks are less likely to be errors, but we cannot justify such biases in general. For a given classiﬁcation, there may be x, 0 ≤ x ≤ k, false positive examples. Since the number of errors is ﬁxed, there are k − x false negative examples. Figure 3 shows the corresponding conﬁguration. The two regions of examples with classiﬁcation outputs above and below the threshold are separated by a vertical line. For a given x, the computation of the AUC, A, as given by Eq. (1) can be divided into the following three parts: A1 + A2 + A3 A= , with (2) mn A1 = the sum over all pairs (xi , yj ) with xi and yj in distinct regions; A2 = the sum over all pairs (xi , yj ) with xi and yj in the region above the threshold; A3 = the sum over all pairs (xi , yj ) with xi and yj in the region below the threshold. The ﬁrst term, A1 , is easy to compute. Since there are (m − (k − x)) positive examples above the threshold and n − x negative examples below the threshold, A1 is given by: A1 = (m − (k − x))(n − x) (3) To compute A2 , we can assign to each negative example above the threshold a position based on its classiﬁcation rank. Let position one be the ﬁrst position above the threshold and let α1 < . . . < αx denote the positions in increasing order of the x negative examples in the region above the threshold. The total number of examples classiﬁed as positive is N = m − (k − x) + x. Thus, by deﬁnition of A2 , x A2 = (N − αi ) − (x − i) (4) i=1 where the ﬁrst term N − αi represents the number of examples ranked higher than the ith example and the second term x − i discounts the number of negative examples incorrectly ranked higher than the ith example. Similarly, let α1 < . . . < αk−x denote the positions of the k − x positive examples below the threshold, counting positions in reverse by starting from the threshold. Then, A3 is given by: x A3 = (N − αj ) − (x − j) (5) j=1 with N = n − x + (k − x) and x = k − x. Combining the expressions of A1 , A2 , and A3 leads to: A= A1 + A2 + A3 (k − 2x)2 + k ( =1+ − mn 2mn x i=1 αi + mn x j=1 αj ) (6) Lemma 2 For a ﬁxed x, the average value of the AUC A is given by: < A >x = 1 − x n + k−x m 2 (7) x Proof. The proof is based on the computation of the average values of i=1 αi and x j=1 αj for a given x. We start by computing the average value < αi >x for a given i, 1 ≤ i ≤ x. Consider all the possible positions for α1 . . . αi−1 and αi+1 . . . αx , when the value of αi is ﬁxed at say αi = l. We have i ≤ l ≤ N − (x − i) since there need to be at least i − 1 positions before αi and N − (x − i) above. There are l − 1 possible positions for α1 . . . αi−1 and N − l possible positions for αi+1 . . . αx . Since the total number of ways of choosing the x positions for α1 . . . αx out of N is N , the average value < αi >x is: x N −(x−i) l=i < αi >x = l l−1 i−1 N −l x−i (8) N x Thus, x < αi >x = x i=1 i=1 Using the classical identity: x < αi >x = N −(x−i) l−1 l i−1 l=i N x u p1 +p2 =p p1 N l=1 l N −1 x−1 N x i=1 N −l x−i v p2 = = N l=1 = u+v p N (N + 1) 2 x l−1 i=1 i−1 N x l N −l x−i (9) , we can write: N −1 x−1 N x = x(N + 1) 2 (10) Similarly, we have: x < αj >x = j=1 x Replacing < i=1 αi >x and < Eq. (10) and Eq. (11) leads to: x j=1 x (N + 1) 2 (11) αj >x in Eq. (6) by the expressions given by (k − 2x)2 + k − x(N + 1) − x (N + 1) =1− 2mn which ends the proof of the lemma. < A >x = 1 + x n + k−x m 2 (12) Note that Eq. (7) shows that the average AUC value for a given x is simply one minus the average of the accuracy rates for the positive and negative classes. Proposition 1 Assume that a binary classiﬁcation task with m positive examples and n negative examples is given. Then, the expected value of the AUC A over all classiﬁcations with k errors is given by: < A >= 1 − k (n − m)2 (m + n + 1) − m+n 4mn k−1 m+n x=0 x k m+n+1 x=0 x k − m+n (13) Proof. Lemma 2 gives the average value of the AUC for a ﬁxed value of x. To compute the average over all possible values of x, we need to weight the expression of Eq. (7) with the total number of possible classiﬁcations for a given x. There are N possible ways of x choosing the positions of the x misclassiﬁed negative examples, and similarly N possible x ways of choosing the positions of the x = k − x misclassiﬁed positive examples. Thus, in view of Lemma 2, the average AUC is given by: < A >= k N x=0 x N x (1 − k N x=0 x N x k−x x n+ m 2 ) (14) r=0.05 r=0.01 r=0.1 r=0.25 0.0 0.1 0.2 r=0.5 0.3 Error rate 0.4 0.5 .00 .05 .10 .15 .20 .25 0.5 0.6 0.7 0.8 0.9 1.0 Mean value of the AUC Relative standard deviation r=0.01 r=0.05 r=0.1 0.0 0.1 r=0.25 0.2 0.3 Error rate r=0.5 0.4 0.5 Figure 3: Mean (left) and relative standard deviation (right) of the AUC as a function of the error rate. Each curve corresponds to a ﬁxed ratio of r = n/(n + m). The average AUC value monotonically increases with the accuracy. For n = m, as for the top curve in the left plot, the average AUC coincides with the accuracy. The standard deviation decreases with the accuracy, and the lowest curve corresponds to n = m. This expression can be simpliﬁed into Eq. (13)3 using the following novel identities: k X N x x=0 k X N x x x=0 ! N x ! ! N x ! = = ! k X n+m+1 x x=0 (15) ! k X (k − x)(m − n) + k n + m + 1 2 x x=0 (16) that we obtained by using Zeilberger’s algorithm4 and numerous combinatorial ’tricks’. From the expression of Eq. (13), it is clear that the average AUC value is identical to the accuracy of the classiﬁer only for even distributions (n = m). For n = m, the expected value of the AUC is a monotonic function of the accuracy, see Fig. (3)(left). For a ﬁxed ratio of n/(n + m), the curves are obtained by increasing the accuracy from n/(n + m) to 1. The average AUC varies monotonically in the range of accuracy between 0.5 and 1.0. In other words, on average, there seems nothing to be gained in designing speciﬁc learning algorithms for maximizing the AUC: a classiﬁcation algorithm minimizing the error rate also optimizes the AUC. However, this only holds for the average AUC. Indeed, we will show in the next section that the variance of the AUC value is not null for any ratio n/(n + m) when k = 0. 4 The Variance of the AUC 2 Let D = mn + (k−2x) +k , a = i=1 αi , a = j=1 αj , and α = a + a . Then, by 2 Eq. (6), mnA = D − α. Thus, the variance of the AUC, σ 2 (A), is given by: (mn)2 σ 2 (A) x x = < (D − α)2 − (< D > − < α >)2 > = < D2 > − < D >2 + < α2 > − < α >2 −2(< αD > − < α >< D >) (17) As before, to compute the average of a term X over all classiﬁcations, we can ﬁrst determine its average < X >x for a ﬁxed x, and then use the function F deﬁned by: F (Y ) = k N N x=0 x x k N N x=0 x x Y (18) and < X >= F (< X >x ). A crucial step in computing the exact value of the variance of x the AUC is to determine the value of the terms of the type < a2 >x =< ( i=1 αi )2 >x . 3 An essential difference between Eq. (14) and the expression given by [15] is the weighting by the number of conﬁgurations. The authors’ analysis leads them to the conclusion that the average AUC is identical to the accuracy for all ratios n/(n + m), which is false. 4 We thank Neil Sloane for having pointed us to Zeilberger’s algorithm and Maple package. x Lemma 3 For a ﬁxed x, the average of ( i=1 αi )2 is given by: x(N + 1) < a2 > x = (3N x + 2x + N ) 12 (19) Proof. By deﬁnition of a, < a2 >x = b + 2c with: x x α2 >x i b =< c =< αi αj >x (20) 1≤i

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 com Abstract The area under an ROC curve (AUC) is a criterion used in many applications to measure the quality of a classiﬁcation algorithm. [sent-4, score-0.094]

2 However, the objective function optimized in most of these algorithms is the error rate and not the AUC value. [sent-5, score-0.129]

3 We give a detailed statistical analysis of the relationship between the AUC and the error rate, including the ﬁrst exact expression of the expected value and the variance of the AUC for a ﬁxed error rate. [sent-6, score-0.189]

4 Our results show that the average AUC is monotonically increasing as a function of the classiﬁcation accuracy, but that the standard deviation for uneven distributions and higher error rates is noticeable. [sent-7, score-0.178]

5 Thus, algorithms designed to minimize the error rate may not lead to the best possible AUC values. [sent-8, score-0.112]

6 We show that, under certain conditions, the global function optimized by the RankBoost algorithm is exactly the AUC. [sent-9, score-0.051]

7 We report the results of our experiments with RankBoost in several datasets demonstrating the beneﬁts of an algorithm speciﬁcally designed to globally optimize the AUC over other existing algorithms optimizing an approximation of the AUC or only locally optimizing the AUC. [sent-10, score-0.138]

8 1 Motivation In many applications, the overall classiﬁcation error rate is not the most pertinent performance measure, criteria such as ordering or ranking seem more appropriate. [sent-11, score-0.189]

9 Consider for example the list of relevant documents returned by a search engine for a speciﬁc query. [sent-12, score-0.092]

10 That list may contain several thousand documents, but, in practice, only the top ﬁfty or so are examined by the user. [sent-13, score-0.038]

11 Thus, a search engine’s ranking of the documents is more critical than the accuracy of its classiﬁcation of all documents as relevant or not. [sent-14, score-0.202]

12 More generally, for a binary classiﬁer assigning a real-valued score to each object, a better correlation between output scores and the probability of correct classiﬁcation is highly desirable. [sent-15, score-0.016]

13 A natural criterion or summary statistic often used to measure the ranking quality of a classiﬁer is the area under an ROC curve (AUC) [8]. [sent-16, score-0.225]

14 1 However, the objective function optimized by most classiﬁcation algorithms is the error rate and not the AUC. [sent-17, score-0.129]

15 Thus, it is important to determine the relationship between the AUC values and the error rate. [sent-19, score-0.066]

16 1 The AUC value is equivalent to the Wilcoxon-Mann-Whitney statistic [8] and closely related to the Gini index [1]. [sent-22, score-0.075]

17 It has been re-invented under the name of L-measure by [11], as already pointed out by [2], and slightly modiﬁed under the name of Linear Ranking by [13, 14]. [sent-23, score-0.058]

18 718 (1,1) True positive rate = (0,0) False positive rate = False positive rate correctly classiﬁed positive total positive incorrectly classiﬁed negative total negative Figure 1: An example of ROC curve. [sent-26, score-0.621]

19 The line connecting (0, 0) and (1, 1), corresponding to random classiﬁcation, is drawn for reference. [sent-27, score-0.018]

20 The true positive (negative) rate is sometimes referred to as the sensitivity (resp. [sent-28, score-0.106]

21 In the following sections, we give a detailed statistical analysis of the relationship between the AUC and the error rate, including the ﬁrst exact expression of the expected value and the variance of the AUC for a ﬁxed error rate. [sent-30, score-0.189]

22 2 We show that, under certain conditions, the global function optimized by the RankBoost algorithm is exactly the AUC. [sent-31, score-0.051]

23 We report the results of our experiments with RankBoost in several datasets and demonstrate the beneﬁts of an algorithm speciﬁcally designed to globally optimize the AUC over other existing algorithms optimizing an approximation of the AUC or only locally optimizing the AUC. [sent-32, score-0.138]

24 2 Deﬁnition and properties of the AUC The Receiver Operating Characteristics (ROC) curves were originally developed in signal detection theory [3] in connection with radio signals, and have been used since then in many other applications, in particular for medical decision-making. [sent-33, score-0.015]

25 Over the last few years, they have found increased interest in the machine learning and data mining communities for model evaluation and selection [12, 10, 4, 9, 15, 2]. [sent-34, score-0.014]

26 The ROC curve for a binary classiﬁcation problem plots the true positive rate as a function of the false positive rate. [sent-35, score-0.264]

27 The points of the curve are obtained by sweeping the classiﬁcation threshold from the most positive classiﬁcation value to the most negative. [sent-36, score-0.179]

28 For a fully random classiﬁcation, the ROC curve is a straight line connecting the origin to (1, 1). [sent-37, score-0.083]

29 Any improvement over random classiﬁcation results in an ROC curve at least partially above this straight line. [sent-38, score-0.065]

30 The AUC is deﬁned as the area under the ROC curve and is closely related to the ranking quality of the classiﬁcation as shown more formally by Lemma 1 below. [sent-41, score-0.162]

31 Consider a binary classiﬁcation task with m positive examples and n negative examples. [sent-42, score-0.21]

32 We will assume that a classiﬁer outputs a strictly ordered list for these examples and will denote by 1X the indicator function of a set X. [sent-43, score-0.122]

33 , xm be the output of c on the positive examples and y1 , . [sent-48, score-0.121]

34 Then, the AUC, A, associated to c is given by: m n i=1 j=1 1xi >yj (1) A= mn that is the value of the Wilcoxon-Mann-Whitney statistic [8]. [sent-52, score-0.147]

35 The proof is based on the observation that the AUC value is exactly the probability P (X > Y ) where X is the random variable corresponding to the distribution of the outputs for the positive examples and Y the one corresponding to the negative examples [7]. [sent-54, score-0.345]

36 The Wilcoxon-Mann-Whitney statistic is clearly the expression of that probability in the discrete case, which proves the lemma [8]. [sent-55, score-0.142]

37 With a perfect ranking, all positive examples are ranked higher than the negative ones and A = 1. [sent-57, score-0.241]

38 Threshold θ k − x Positive examples x Negative examples n − x Negative examples m − (k − x) Positive examples Figure 2: For a ﬁxed number of errors k, there may be x, 0 ≤ x ≤ k, false negative examples. [sent-60, score-0.433]

39 3 The Expected Value of the AUC In this section, we compute exactly the expected value of the AUC over all classiﬁcations with a ﬁxed number of errors and compare that to the error rate. [sent-61, score-0.125]

40 Different classiﬁers may have the same error rate but different AUC values. [sent-62, score-0.093]

41 Indeed, for a given classiﬁcation threshold θ, an arbitrary reordering of the examples with outputs more than θ clearly does not affect the error rate but leads to different AUC values. [sent-63, score-0.263]

42 Similarly, one may reorder the examples with output less than θ without changing the error rate. [sent-64, score-0.122]

43 We wish to compute the average value of the AUC over all classiﬁcations with k errors. [sent-66, score-0.062]

44 Our model is based on the simple assumption that all classiﬁcations or rankings with k errors are equiprobable. [sent-67, score-0.049]

45 One could perhaps argue that errors are not necessarily evenly distributed, e. [sent-68, score-0.032]

46 , examples with very high or very low ranks are less likely to be errors, but we cannot justify such biases in general. [sent-70, score-0.097]

47 For a given classiﬁcation, there may be x, 0 ≤ x ≤ k, false positive examples. [sent-71, score-0.094]

48 Since the number of errors is ﬁxed, there are k − x false negative examples. [sent-72, score-0.149]

49 The two regions of examples with classiﬁcation outputs above and below the threshold are separated by a vertical line. [sent-74, score-0.14]

50 Since there are (m − (k − x)) positive examples above the threshold and n − x negative examples below the threshold, A1 is given by: A1 = (m − (k − x))(n − x) (3) To compute A2 , we can assign to each negative example above the threshold a position based on its classiﬁcation rank. [sent-78, score-0.438]

51 Let position one be the ﬁrst position above the threshold and let α1 < . [sent-79, score-0.071]

52 < αx denote the positions in increasing order of the x negative examples in the region above the threshold. [sent-82, score-0.236]

53 The total number of examples classiﬁed as positive is N = m − (k − x) + x. [sent-83, score-0.137]

54 Thus, by deﬁnition of A2 , x A2 = (N − αi ) − (x − i) (4) i=1 where the ﬁrst term N − αi represents the number of examples ranked higher than the ith example and the second term x − i discounts the number of negative examples incorrectly ranked higher than the ith example. [sent-84, score-0.334]

55 < αk−x denote the positions of the k − x positive examples below the threshold, counting positions in reverse by starting from the threshold. [sent-88, score-0.261]

56 Combining the expressions of A1 , A2 , and A3 leads to: A= A1 + A2 + A3 (k − 2x)2 + k ( =1+ − mn 2mn x i=1 αi + mn x j=1 αj ) (6) Lemma 2 For a ﬁxed x, the average value of the AUC A is given by: < A >x = 1 − x n + k−x m 2 (7) x Proof. [sent-90, score-0.239]

57 The proof is based on the computation of the average values of i=1 αi and x j=1 αj for a given x. [sent-91, score-0.051]

58 We start by computing the average value < αi >x for a given i, 1 ≤ i ≤ x. [sent-92, score-0.062]

59 We have i ≤ l ≤ N − (x − i) since there need to be at least i − 1 positions before αi and N − (x − i) above. [sent-100, score-0.064]

60 Since the total number of ways of choosing the x positions for α1 . [sent-108, score-0.107]

61 (11) leads to: x j=1 x (N + 1) 2 (11) αj >x in Eq. [sent-113, score-0.013]

62 (6) by the expressions given by (k − 2x)2 + k − x(N + 1) − x (N + 1) =1− 2mn which ends the proof of the lemma. [sent-114, score-0.034]

63 (7) shows that the average AUC value for a given x is simply one minus the average of the accuracy rates for the positive and negative classes. [sent-116, score-0.259]

64 Proposition 1 Assume that a binary classiﬁcation task with m positive examples and n negative examples is given. [sent-117, score-0.281]

65 Then, the expected value of the AUC A over all classiﬁcations with k errors is given by: < A >= 1 − k (n − m)2 (m + n + 1) − m+n 4mn k−1 m+n x=0 x k m+n+1 x=0 x k − m+n (13) Proof. [sent-118, score-0.073]

66 Lemma 2 gives the average value of the AUC for a ﬁxed value of x. [sent-119, score-0.087]

67 To compute the average over all possible values of x, we need to weight the expression of Eq. [sent-120, score-0.072]

68 (7) with the total number of possible classiﬁcations for a given x. [sent-121, score-0.016]

69 There are N possible ways of x choosing the positions of the x misclassiﬁed negative examples, and similarly N possible x ways of choosing the positions of the x = k − x misclassiﬁed positive examples. [sent-122, score-0.32]

70 Thus, in view of Lemma 2, the average AUC is given by: < A >= k N x=0 x N x (1 − k N x=0 x N x k−x x n+ m 2 ) (14) r=0. [sent-123, score-0.037]

71 0 Mean value of the AUC Relative standard deviation r=0. [sent-146, score-0.055]

72 5 Figure 3: Mean (left) and relative standard deviation (right) of the AUC as a function of the error rate. [sent-157, score-0.067]

73 Each curve corresponds to a ﬁxed ratio of r = n/(n + m). [sent-158, score-0.063]

74 The average AUC value monotonically increases with the accuracy. [sent-159, score-0.092]

75 For n = m, as for the top curve in the left plot, the average AUC coincides with the accuracy. [sent-160, score-0.097]

76 The standard deviation decreases with the accuracy, and the lowest curve corresponds to n = m. [sent-161, score-0.093]

77 (13), it is clear that the average AUC value is identical to the accuracy of the classiﬁer only for even distributions (n = m). [sent-171, score-0.099]

78 For n = m, the expected value of the AUC is a monotonic function of the accuracy, see Fig. [sent-172, score-0.041]

79 For a ﬁxed ratio of n/(n + m), the curves are obtained by increasing the accuracy from n/(n + m) to 1. [sent-174, score-0.065]

80 The average AUC varies monotonically in the range of accuracy between 0. [sent-175, score-0.104]

81 In other words, on average, there seems nothing to be gained in designing speciﬁc learning algorithms for maximizing the AUC: a classiﬁcation algorithm minimizing the error rate also optimizes the AUC. [sent-178, score-0.109]

82 Indeed, we will show in the next section that the variance of the AUC value is not null for any ratio n/(n + m) when k = 0. [sent-180, score-0.063]

83 4 The Variance of the AUC 2 Let D = mn + (k−2x) +k , a = i=1 αi , a = j=1 αj , and α = a + a . [sent-181, score-0.072]

84 A crucial step in computing the exact value of the variance of x the AUC is to determine the value of the terms of the type < a2 >x =< ( i=1 αi )2 >x . [sent-185, score-0.086]

85 (14) and the expression given by [15] is the weighting by the number of conﬁgurations. [sent-187, score-0.035]

86 The authors’ analysis leads them to the conclusion that the average AUC is identical to the accuracy for all ratios n/(n + m), which is false. [sent-188, score-0.087]

87 4 We thank Neil Sloane for having pointed us to Zeilberger’s algorithm and Maple package. [sent-189, score-0.02]

88 x Lemma 3 For a ﬁxed x, the average of ( i=1 αi )2 is given by: x(N + 1) < a2 > x = (3N x + 2x + N ) 12 (19) Proof. [sent-190, score-0.037]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('auc', 0.935), ('classi', 0.101), ('roc', 0.095), ('ranking', 0.081), ('rankboost', 0.076), ('negative', 0.073), ('mn', 0.072), ('examples', 0.071), ('positions', 0.064), ('cations', 0.059), ('yj', 0.058), ('rate', 0.056), ('statistic', 0.05), ('corinna', 0.05), ('positive', 0.05), ('curve', 0.048), ('lemma', 0.045), ('false', 0.044), ('threshold', 0.043), ('documents', 0.042), ('cation', 0.039), ('mohri', 0.038), ('zeilberger', 0.038), ('average', 0.037), ('accuracy', 0.037), ('error', 0.037), ('optimized', 0.036), ('expression', 0.035), ('ranked', 0.033), ('errors', 0.032), ('monotonically', 0.03), ('deviation', 0.03), ('optimizing', 0.028), ('outputs', 0.026), ('xed', 0.025), ('engine', 0.025), ('incorrectly', 0.025), ('value', 0.025), ('list', 0.025), ('labs', 0.024), ('variance', 0.023), ('park', 0.021), ('expressions', 0.02), ('pointed', 0.02), ('name', 0.019), ('locally', 0.019), ('designed', 0.019), ('connecting', 0.018), ('misclassi', 0.018), ('er', 0.018), ('straight', 0.017), ('globally', 0.017), ('area', 0.017), ('xi', 0.017), ('fty', 0.017), ('mna', 0.017), ('rankings', 0.017), ('reordering', 0.017), ('uneven', 0.017), ('maximizing', 0.016), ('relationship', 0.016), ('binary', 0.016), ('expected', 0.016), ('total', 0.016), ('quality', 0.016), ('ratio', 0.015), ('similarly', 0.015), ('ways', 0.015), ('google', 0.015), ('pertinent', 0.015), ('radio', 0.015), ('exactly', 0.015), ('decreases', 0.015), ('region', 0.015), ('pairs', 0.015), ('reorder', 0.014), ('communities', 0.014), ('neil', 0.014), ('position', 0.014), ('proof', 0.014), ('optimize', 0.014), ('higher', 0.014), ('thousand', 0.013), ('justify', 0.013), ('ranks', 0.013), ('determine', 0.013), ('increasing', 0.013), ('criterion', 0.013), ('ts', 0.013), ('leads', 0.013), ('datasets', 0.013), ('nition', 0.013), ('sweeping', 0.013), ('avenue', 0.013), ('tricks', 0.013), ('choosing', 0.012), ('coincides', 0.012), ('proves', 0.012), ('cortes', 0.012), ('counting', 0.012)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999934 3 nips-2003-AUC Optimization vs. Error Rate Minimization

Author: Corinna Cortes, Mehryar Mohri

2 0.088969596 164 nips-2003-Ranking on Data Manifolds

Author: Dengyong Zhou, Jason Weston, Arthur Gretton, Olivier Bousquet, Bernhard Schölkopf

Abstract: The Google search engine has enjoyed huge success with its web page ranking algorithm, which exploits global, rather than local, hyperlink structure of the web using random walks. Here we propose a simple universal ranking algorithm for data lying in the Euclidean space, such as text or image data. The core idea of our method is to rank the data with respect to the intrinsic manifold structure collectively revealed by a great amount of data. Encouraging experimental results from synthetic, image, and text data illustrate the validity of our method. 1

3 0.061040241 121 nips-2003-Log-Linear Models for Label Ranking

Author: Ofer Dekel, Yoram Singer, Christopher D. Manning

Abstract: Label ranking is the task of inferring a total order over a predeﬁned set of labels for each given instance. We present a general framework for batch learning of label ranking functions from supervised data. We assume that each instance in the training data is associated with a list of preferences over the label-set, however we do not assume that this list is either complete or consistent. This enables us to accommodate a variety of ranking problems. In contrast to the general form of the supervision, our goal is to learn a ranking function that induces a total order over the entire set of labels. Special cases of our setting are multilabel categorization and hierarchical classiﬁcation. We present a general boosting-based learning algorithm for the label ranking problem and prove a lower bound on the progress of each boosting iteration. The applicability of our approach is demonstrated with a set of experiments on a large-scale text corpus. 1

4 0.055247858 109 nips-2003-Learning a Rare Event Detection Cascade by Direct Feature Selection

Author: Jianxin Wu, James M. Rehg, Matthew D. Mullin

Abstract: Face detection is a canonical example of a rare event detection problem, in which target patterns occur with much lower frequency than nontargets. Out of millions of face-sized windows in an input image, for example, only a few will typically contain a face. Viola and Jones recently proposed a cascade architecture for face detection which successfully addresses the rare event nature of the task. A central part of their method is a feature selection algorithm based on AdaBoost. We present a novel cascade learning algorithm based on forward feature selection which is two orders of magnitude faster than the Viola-Jones approach and yields classiﬁers of equivalent quality. This faster method could be used for more demanding classiﬁcation tasks, such as on-line learning. 1

5 0.046050344 124 nips-2003-Max-Margin Markov Networks

Author: Ben Taskar, Carlos Guestrin, Daphne Koller

Abstract: In typical classiﬁcation tasks, we seek a function which assigns a label to a single object. Kernel-based approaches, such as support vector machines (SVMs), which maximize the margin of conﬁdence of the classiﬁer, are the method of choice for many such tasks. Their popularity stems both from the ability to use high-dimensional feature spaces, and from their strong theoretical guarantees. However, many real-world tasks involve sequential, spatial, or structured data, where multiple labels must be assigned. Existing kernel-based methods ignore structure in the problem, assigning labels independently to each object, losing much useful information. Conversely, probabilistic graphical models, such as Markov networks, can represent correlations between labels, by exploiting problem structure, but cannot handle high-dimensional feature spaces, and lack strong theoretical generalization guarantees. In this paper, we present a new framework that combines the advantages of both approaches: Maximum margin Markov (M3 ) networks incorporate both kernels, which efﬁciently deal with high-dimensional features, and the ability to capture correlations in structured data. We present an efﬁcient algorithm for learning M3 networks based on a compact quadratic program formulation. We provide a new theoretical bound for generalization in structured domains. Experiments on the task of handwritten character recognition and collective hypertext classiﬁcation demonstrate very signiﬁcant gains over previous approaches. 1

6 0.035844211 95 nips-2003-Insights from Machine Learning Applied to Human Visual Classification

7 0.034901157 181 nips-2003-Statistical Debugging of Sampled Programs

8 0.033973932 101 nips-2003-Large Margin Classifiers: Convex Loss, Low Noise, and Convergence Rates

9 0.032800104 47 nips-2003-Computing Gaussian Mixture Models with EM Using Equivalence Constraints

10 0.029096004 104 nips-2003-Learning Curves for Stochastic Gradient Descent in Linear Feedforward Networks

11 0.028786499 113 nips-2003-Learning with Local and Global Consistency

12 0.028768249 134 nips-2003-Near-Minimax Optimal Classification with Dyadic Classification Trees

13 0.028364515 173 nips-2003-Semi-supervised Protein Classification Using Cluster Kernels

14 0.028244644 192 nips-2003-Using the Forest to See the Trees: A Graphical Model Relating Features, Objects, and Scenes

15 0.027858263 9 nips-2003-A Kullback-Leibler Divergence Based Kernel for SVM Classification in Multimedia Applications

16 0.027823385 188 nips-2003-Training fMRI Classifiers to Detect Cognitive States across Multiple Human Subjects

17 0.027713154 51 nips-2003-Design of Experiments via Information Theory

18 0.02759717 186 nips-2003-Towards Social Robots: Automatic Evaluation of Human-Robot Interaction by Facial Expression Classification

19 0.026873969 136 nips-2003-New Algorithms for Efficient High Dimensional Non-parametric Classification

20 0.02590522 23 nips-2003-An Infinity-sample Theory for Multi-category Large Margin Classification

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.089), (1, -0.043), (2, -0.004), (3, -0.064), (4, -0.003), (5, -0.034), (6, -0.054), (7, -0.025), (8, -0.014), (9, 0.019), (10, 0.07), (11, 0.034), (12, 0.037), (13, -0.008), (14, 0.064), (15, -0.036), (16, -0.101), (17, -0.078), (18, 0.027), (19, -0.018), (20, -0.022), (21, 0.019), (22, 0.02), (23, -0.05), (24, 0.033), (25, 0.059), (26, 0.009), (27, 0.0), (28, -0.019), (29, -0.032), (30, -0.073), (31, -0.034), (32, -0.044), (33, 0.02), (34, -0.02), (35, 0.021), (36, 0.025), (37, -0.048), (38, 0.077), (39, 0.024), (40, -0.046), (41, 0.011), (42, 0.0), (43, 0.034), (44, 0.079), (45, 0.018), (46, -0.093), (47, -0.06), (48, -0.109), (49, -0.055)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.86649561 3 nips-2003-AUC Optimization vs. Error Rate Minimization

Author: Corinna Cortes, Mehryar Mohri

2 0.66757107 164 nips-2003-Ranking on Data Manifolds

Author: Dengyong Zhou, Jason Weston, Arthur Gretton, Olivier Bousquet, Bernhard Schölkopf

3 0.57568014 121 nips-2003-Log-Linear Models for Label Ranking

Author: Ofer Dekel, Yoram Singer, Christopher D. Manning

4 0.44158053 113 nips-2003-Learning with Local and Global Consistency

Author: Dengyong Zhou, Olivier Bousquet, Thomas N. Lal, Jason Weston, Bernhard Schölkopf

Abstract: We consider the general problem of learning from labeled and unlabeled data, which is often called semi-supervised learning or transductive inference. A principled approach to semi-supervised learning is to design a classifying function which is sufﬁciently smooth with respect to the intrinsic structure collectively revealed by known labeled and unlabeled points. We present a simple algorithm to obtain such a smooth solution. Our method yields encouraging experimental results on a number of classiﬁcation problems and demonstrates effective use of unlabeled data. 1

5 0.43911237 109 nips-2003-Learning a Rare Event Detection Cascade by Direct Feature Selection

Author: Jianxin Wu, James M. Rehg, Matthew D. Mullin

6 0.43325683 181 nips-2003-Statistical Debugging of Sampled Programs

7 0.41981849 136 nips-2003-New Algorithms for Efficient High Dimensional Non-parametric Classification

8 0.38023597 28 nips-2003-Application of SVMs for Colour Classification and Collision Detection with AIBO Robots

9 0.3701629 187 nips-2003-Training a Quantum Neural Network

10 0.34324118 90 nips-2003-Increase Information Transfer Rates in BCI by CSP Extension to Multi-class

11 0.32570198 186 nips-2003-Towards Social Robots: Automatic Evaluation of Human-Robot Interaction by Facial Expression Classification

12 0.32283944 98 nips-2003-Kernel Dimensionality Reduction for Supervised Learning

13 0.31800964 188 nips-2003-Training fMRI Classifiers to Detect Cognitive States across Multiple Human Subjects

14 0.31375858 47 nips-2003-Computing Gaussian Mixture Models with EM Using Equivalence Constraints

15 0.30688301 51 nips-2003-Design of Experiments via Information Theory

16 0.30481806 137 nips-2003-No Unbiased Estimator of the Variance of K-Fold Cross-Validation

17 0.30429688 54 nips-2003-Discriminative Fields for Modeling Spatial Dependencies in Natural Images

18 0.3028017 172 nips-2003-Semi-Supervised Learning with Trees

19 0.30122837 147 nips-2003-Online Learning via Global Feedback for Phrase Recognition

20 0.3002148 135 nips-2003-Necessary Intransitive Likelihood-Ratio Classifiers

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.059), (11, 0.037), (16, 0.017), (29, 0.016), (33, 0.206), (35, 0.036), (48, 0.01), (53, 0.118), (71, 0.088), (76, 0.046), (85, 0.116), (91, 0.077)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.90128791 176 nips-2003-Sequential Bayesian Kernel Regression

Author: Jaco Vermaak, Simon J. Godsill, Arnaud Doucet

Abstract: We propose a method for sequential Bayesian kernel regression. As is the case for the popular Relevance Vector Machine (RVM) [10, 11], the method automatically identiﬁes the number and locations of the kernels. Our algorithm overcomes some of the computational difﬁculties related to batch methods for kernel regression. It is non-iterative, and requires only a single pass over the data. It is thus applicable to truly sequential data sets and batch data sets alike. The algorithm is based on a generalisation of Importance Sampling, which allows the design of intuitively simple and efﬁcient proposal distributions for the model parameters. Comparative results on two standard data sets show our algorithm to compare favourably with existing batch estimation strategies.

2 0.88864458 172 nips-2003-Semi-Supervised Learning with Trees

Author: Charles Kemp, Thomas L. Griffiths, Sean Stromsten, Joshua B. Tenenbaum

Abstract: We describe a nonparametric Bayesian approach to generalizing from few labeled examples, guided by a larger set of unlabeled objects and the assumption of a latent tree-structure to the domain. The tree (or a distribution over trees) may be inferred using the unlabeled data. A prior over concepts generated by a mutation process on the inferred tree(s) allows efﬁcient computation of the optimal Bayesian classiﬁcation function from the labeled examples. We test our approach on eight real-world datasets. 1

3 0.87756592 132 nips-2003-Multiple Instance Learning via Disjunctive Programming Boosting

Author: Stuart Andrews, Thomas Hofmann

Abstract: Learning from ambiguous training data is highly relevant in many applications. We present a new learning algorithm for classiﬁcation problems where labels are associated with sets of pattern instead of individual patterns. This encompasses multiple instance learning as a special case. Our approach is based on a generalization of linear programming boosting and uses results from disjunctive programming to generate successively stronger linear relaxations of a discrete non-convex problem. 1

same-paper 4 0.82880163 3 nips-2003-AUC Optimization vs. Error Rate Minimization

Author: Corinna Cortes, Mehryar Mohri

5 0.70567197 192 nips-2003-Using the Forest to See the Trees: A Graphical Model Relating Features, Objects, and Scenes

Author: Kevin P. Murphy, Antonio Torralba, William T. Freeman

Abstract: Standard approaches to object detection focus on local patches of the image, and try to classify them as background or not. We propose to use the scene context (image as a whole) as an extra source of (global) information, to help resolve local ambiguities. We present a conditional random ﬁeld for jointly solving the tasks of object detection and scene classiﬁcation. 1

6 0.69702226 124 nips-2003-Max-Margin Markov Networks

7 0.6959033 109 nips-2003-Learning a Rare Event Detection Cascade by Direct Feature Selection

8 0.69562072 54 nips-2003-Discriminative Fields for Modeling Spatial Dependencies in Natural Images

9 0.693501 147 nips-2003-Online Learning via Global Feedback for Phrase Recognition

10 0.69222939 47 nips-2003-Computing Gaussian Mixture Models with EM Using Equivalence Constraints

11 0.69132406 41 nips-2003-Boosting versus Covering

12 0.68869501 126 nips-2003-Measure Based Regularization

13 0.68803567 113 nips-2003-Learning with Local and Global Consistency

14 0.68752283 138 nips-2003-Non-linear CCA and PCA by Alignment of Local Models

15 0.68517572 135 nips-2003-Necessary Intransitive Likelihood-Ratio Classifiers

16 0.68322331 9 nips-2003-A Kullback-Leibler Divergence Based Kernel for SVM Classification in Multimedia Applications

17 0.68235886 28 nips-2003-Application of SVMs for Colour Classification and Collision Detection with AIBO Robots

18 0.68192983 145 nips-2003-Online Classification on a Budget

19 0.6817739 93 nips-2003-Information Dynamics and Emergent Computation in Recurrent Circuits of Spiking Neurons

20 0.68159139 23 nips-2003-An Infinity-sample Theory for Multi-category Large Margin Classification