ROC Analysis of Classifiers in Machine Learning: A Survey
---
paper_title: Receiver Operating Characteristic Curves and Their Use in Radiology

paper_content:

Sensitivity and specificity are the basic measures of accuracy of a diagnostic test; however, they depend on the cut point used to define “positive” and “negative” test results. As the cut point shifts, sensitivity and specificity shift. The receiver operating characteristic (ROC) curve is a plot of the sensitivity of a test versus its false-positive rate for all possible cut points. The advantages of the ROC curve as a means of defining the accuracy of a test, construction of the ROC, and identification of the optimal cut point on the ROC curve are discussed. Several summary measures of the accuracy of a test, including the commonly used percentage of correct diagnoses and area under the ROC curve, are described and compared. Two examples of ROC curve application in radiologic research are presented. © RSNA, 2003
---
paper_title: Epidemiologic methods. Studying the occurrence of illness

paper_content:

Edited by Thomas D Koepsell, Noel S Weiss. Oxford: Oxford University Press, 2003, £39.95, pp 513. ISBN 0-19-515078-3 ::: ::: Several books introducing epidemiology are available. They usually follow the traditional layout: from initial definitions to the description and control of biases and measurement errors and it becomes challenging to offer something “different”. ::: ::: Epidemiological Methods , by Koepsell and Weiss succeeds in presenting epidemiology in a …
---
paper_title: Signal detection theory and psychophysics

paper_content:

418,865. Time-pieces. HARWOOD, J., 120, Pinner Road, Harrow, Middlesex. Oct. 23, 1933, No. 29295. [Class 139.] Winding-apparatus.-In a time-piece, which is self-wound by an oscillating weight, the weight oscillates in or parallel to a vertical plane through the axis of the indicating hands and is combined with a toothless winding mechanism. Rigid with the winding arbor A of the mainspring A is a disc B, the edge of which coacts with two studs G, G and a lever I on a trefoil plate E. Lever I is connected by link O to an arm 0 rigid with the weight W which oscillates about pivot R against spring X. When the link O is raised, the nose of lever I binds on the edge of disc B and the latter is moved counter-clockwise, Fig. 2, with plate E to wind the mainspring. A similar trefoil plate D with pins F, F and lever H prevents retrograde movement of disc B in a clockwise direction. V, V are buffer springs. To prevent overwinding the link O may be made in two relatively sliding parts which are joined together by an S-spring slightly weaker than the fully wound mainspring. A mark on the weight may be visible through a hole in the dial to indicate whether the weight is oscillating freely. The movement of the timepiece, or the timepiece as a whole, may be mounted for oscillation so as to function as the winding weight.
---
paper_title: Signal detection theory: valuable tools for evaluating inductive learning

paper_content:

This paper describes the use of signal detection theory as a tool for evaluating and comparing concept descriptions learned by inductive inference. We outline the use of ROC curves and describe the experience we have had in using these concepts for inductive learning using connectionist models, genetic search, and symbolic concept acquisition.
---
paper_title: Measuring the accuracy of diagnostic systems

paper_content:

Diagnostic systems of several kinds are used to distinguish between two classes of events, essentially "signals" and "noise". For them, analysis in terms of the "relative operating characteristic" of signal detection theory provides a precise and valid measure of diagnostic accuracy. It is the only measure available that is uninfluenced by decision biases and prior probabilities, and it places the performances of diverse systems on a common, easily interpreted scale. Representative values of this measure are reported here for systems in medical imaging, materials testing, weather forecasting, information retrieval, polygraph lie detection, and aptitude testing. Though the measure itself is sound, the values obtained from tests of diagnostic systems often require qualification because the test data on which they are based are of unsure quality. A common set of problems in testing is faced in all fields. How well these problems are handled, or can be handled in a given field, determines the degree of confidence that can be placed in a measured value of accuracy. Some fields fare much better than others.
---
paper_title: Receiver operating characteristic (ROC) literature research

paper_content:

There is disclosed a technique for use in a recorder-reproducer system to provide synchronization between video information playback of the system and a local video information source. In the arrangement provided, a synchronizing signal which is produced from a first control track signal of the system, is phase compared with a reference signal from the local source. The first control track signal is one which can have one of many phase relationships with respect to the reference signal, only one of which is the desired one. A second signal from the control track and a signal extracted from the video signal are recovered from the record medium. Both of these signals can provide information as to the desired phase relation between the synchronizing signal and the reference signal. Means are provided for examining the recovered signals, for selecting the one that best defines at that time the desired phase relationship and for utilizing that signal to control the production of the synchronizing signal.
---
paper_title: Repairing Concavities in ROC Curves

paper_content:

In this paper we investigate methods to detect and repair concavities in ROC curves by manipulating model predictions. The basic idea is that, if a point or a set of points lies below the line spanned by two other points in ROC space, we can use this information to repair the concavity. This effectively builds a hybrid model combining the two better models with an inversion of the poorer models; in the case of ranking classifiers, it means that certain intervals of the scores are identified as unreliable and candidates for inversion. We report very encouraging results on 23 UCI data sets, particularly for naive Bayes where the use of two validation folds yielded significant improvements on more than half of them, with only one loss.
---
paper_title: Comparing classifiers when the misallocation costs are uncertain

paper_content:

Receiver Operating Characteristic (ROC) curves are popular ways of summarising the performance of two class classification rules. In fact, however, they are extremely inconvenient. If the relative severity of the two different kinds of misclassification is known, then an awkward projection operation is required to deduce the overall loss. At the other extreme, when the relative severity is unknown, the area under an ROC curve is often used as an index of performance. However, this essentially assumes that nothing whatsoever is known about the relative severity – a situation which is very rare in real problems. We present an alternative plot which is more revealing than an ROC plot and we describe a comparative index which allows one to take advantage of anything that may be known about the relative severity of the two kinds of misclassification.
---
paper_title: The meaning and use of the area under a receiver operating characteristic (ROC) curve.

paper_content:

A representation and interpretation of the area under a receiver operating characteristic (ROC) curve obtained by the "rating" method, or by mathematical predictions based on patient characteristics, is presented. It is shown that in such a setting the area represents the probability that a randomly chosen diseased subject is (correctly) rated or ranked with greater suspicion than a randomly chosen non-diseased subject. Moreover, this probability of a correct ranking is the same quantity that is estimated by the already well-studied nonparametric Wilcoxon statistic. These two relationships are exploited to (a) provide rapid closed-form expressions for the approximate magnitude of the sampling variability, i.e., standard error that one uses to accompany the area under a smoothed ROC curve, (b) guide in determining the size of the sample required to provide a sufficiently reliable estimate of this area, and (c) determine how large sample sizes should be to ensure that one can statistically detect difference...
---
paper_title: Generating ROC curves for artificial neural networks

paper_content:

Receiver operating characteristic (ROC) analysis is an established method of measuring diagnostic performance in medical imaging studies. An ROC curve characterizes the inherent tradeoff between true positive and false positive detection rates in a classification system. Traditionally, artificial neural networks (ANNs) have been applied as a classifier to find one "best" partition of feature space, and therefore a single detection rate. This work proposes and evaluates a new technique for generating an ROC curve for a 2-class ANN classifier. We show that the new technique generates significantly better ROC curves than the method currently used to generate ROCs for ANNs. >
---
paper_title: A ROC-based reject rule for support vector machines

paper_content:

This paper presents a novel reject rule for SVM classifiers, based on the Receiver Operating Characteristic curve. The rule minimizes the expected classification cost, defined on the basis of classification and error costs peculiar for the application at hand. Experiments performed with different kernels on several data sets publicly available confirmed the effectiveness of the proposed reject rule.
---
paper_title: An improved measure for comparing diagnostic tests

paper_content:

We present a loss based method for comparing the predictive performance of diagnostic tests. Unlike standard assessment mechanisms, like the area under the receiver-operating characteristic curve and the misclassification rate, our method takes specific advantage of any information that can be obtained about misclassification costs. We argue that not taking costs into account can lead to incorrect conclusions, and illustrate with two examples.
---
paper_title: The Geometry of ROC Space: Understanding Machine Learning Metrics through ROC Isometrics

paper_content:

Many different metrics are used in machine learning and data mining to build and evaluate models. However, there is no general theory of machine learning metrics, that could answer questions such as: When we simultaneously want to optimise two criteria, how can or should they be traded off? Some metrics are inherently independent of class and misclassification cost distributions, while other are not -- can this be made more precise? This paper provides a derivation of ROC space from first principles through 3D ROC space and the skew ratio, and redefines metrics in these dimensions. The paper demonstrates that the graphical depiction of machine learning metrics by means of ROC isometrics gives many useful insights into the characteristics of these metrics, and provides a foundation on which a theory of machine learning metrics can be built.
---
paper_title: A Response to Webb and Ting’s On the Application of ROC Analysis to Predict Classification Performance Under Varying Class Distributions

paper_content:

In an article in this issue, Webb and Ting criticize ROC analysis for its inability to handle certain changes in class distributions. They imply that the ability of ROC graphs to depict performance in the face of changing class distributions has been overstated. In this editorial response, we describe two general types of domains and argue that Webb and Ting's concerns apply primarily to only one of them. Furthermore, we show that there are interesting real-world domains of the second type, in which ROC analysis may be expected to hold in the face of changing class distributions.
---
paper_title: On the Application of ROC Analysis to Predict Classification Performance Under Varying Class Distributions

paper_content:

We counsel caution in the application of ROC analysis for prediction of classifier performance under varying class distributions. We argue that it is not reasonable to expect ROC analysis to provide accurate prediction of model performance under varying distributions if the classes contain causally relevant subclasses whose frequencies may vary at different rates or if there are attributes upon which the classes are causally dependent.
---
paper_title: Comparing classifiers when the misallocation costs are uncertain

paper_content:

Receiver Operating Characteristic (ROC) curves are popular ways of summarising the performance of two class classification rules. In fact, however, they are extremely inconvenient. If the relative severity of the two different kinds of misclassification is known, then an awkward projection operation is required to deduce the overall loss. At the other extreme, when the relative severity is unknown, the area under an ROC curve is often used as an index of performance. However, this essentially assumes that nothing whatsoever is known about the relative severity – a situation which is very rare in real problems. We present an alternative plot which is more revealing than an ROC plot and we describe a comparative index which allows one to take advantage of anything that may be known about the relative severity of the two kinds of misclassification.
---
paper_title: Efficient AUC Learning Curve Calculation

paper_content:

A learning curve of a performance measure provides a graphical method with many benefits for judging classifier properties. The area under the ROC curve (AUC) is a useful and increasingly popular performance measure. In this paper, we consider the computational aspects of calculating AUC learning curves. A new method is provided for incrementally updating exact AUC curves and for calculating approximate AUC curves for datasets with millions of instances. Both theoretical and empirical justifications are given for the approximation. Variants for incremental exact and approximate AUC curves are provided as well.
---
paper_title: Extracting Context-Sensitive Models in Inductive Logic Programming

paper_content:

Given domain-specific background knowledge and data in the form of examples, an Inductive Logic Programming (ILP) system extracts models in the data-analytic sense. We view the model-selection step facing an ILP system as a decision problem, the solution of which requires knowledge of the context in which the model is to be deployed. In this paper, "context" will be defined by the current specification of the prior class distribution and the client's preferences concerning errors of classification. Within this restricted setting, we consider the use of an ILP system in situations where: (a) contexts can change regularly. This can arise for example, from changes to class distributions or misclassification costs; and (b) the data are from observational studies. That is, they may not have been collected with any particular context in mind. Some repercussions of these are: (a) any one model may not be the optimal choice forall contexts; and (b) not all the background information provided may be relevant for all contexts. Using results from the analysis of Receiver Operating Characteristic curves, we investigate a technique that can equip an ILP system to reject those models that cannot possibly be optimal in any context. We present empirical results from using the technique to analyse two datasets concerned with the toxicity of chemicals (in particular, their mutagenic and carcinogenic properties). Clients can, and typically do, approach such datasets with quite different requirements. For example, a synthetic chemist would require models with a low rate of commission errors which could be used to direct efficiently the synthesis of new compounds. A toxicologist on the other hand, would prefer models with a low rate of omission errors. This would enable a more complete identification of toxic chemicals at a calculated cost of misidentification of non-toxic cases as toxic. The approach adopted here attempts to obtain a solution that contains models that are optimal for each such user according to the cost function that he or she wishes to apply. In doing so, it also provides one solution to the problem of how the relevance of background predicates is to be assessed in ILP.
---
paper_title: Learning Decision Trees Using the Area Under the ROC Curve

paper_content:

ROC analysis is increasingly being recognised as an important tool for evaluation and comparison of classifiers when the operating characteristics (i.e. class distribution and cost parameters) are not known at training time. Usually, each classifier is characterised by its estimated true and false positive rates and is represented by a single point in the ROC diagram. In this paper, we show how a single decision tree can represent a set of classifiers by choosing different labellings of its leaves, or equivalently, an ordering on the leaves. In this setting, rather than estimating the accuracy of a single tree, it makes more sense to use the area under the ROC curve (AUC) as a quality metric. We also propose a novel splitting criterion which chooses the split with the highest local AUC. To the best of our knowledge, this is the first probabilistic splitting criterion that is not based on weighted average impurity. We present experiments suggesting that the AUC splitting criterion leads to trees with equal or better AUC value, without sacrificing accuracy if a single labelling is chosen.
---
paper_title: Improving Accuracy and Cost of Two-class and Multi-class Probabilistic Classifiers Using ROC Curves

paper_content:

The probability estimates of a naive Bayes classifier are inaccurate if some of its underlying independence assumptions are violated. The decision criterion for using these estimates for classification therefore has to be learned from the data. This paper proposes the use of ROC curves for this purpose. For two classes, the algorithm is a simple adaptation of the algorithm for tracing a ROC curve by sorting the instances according to their predicted probability of being positive. As there is no obvious way to upgrade this algorithm to the multi-class case, we propose a hillclimbing approach which adjusts the weights for each class in a pre-defined order. Experiments on a wide range of datasets show the proposed method leads to significant improvements over the naive Bayes classifier's accuracy. Finally, we discuss an method to find the global optimum, and show how its computational complexity would make it untractable.
---
paper_title: Repairing Concavities in ROC Curves

paper_content:

In this paper we investigate methods to detect and repair concavities in ROC curves by manipulating model predictions. The basic idea is that, if a point or a set of points lies below the line spanned by two other points in ROC space, we can use this information to repair the concavity. This effectively builds a hybrid model combining the two better models with an inversion of the poorer models; in the case of ranking classifiers, it means that certain intervals of the scores are identified as unreliable and candidates for inversion. We report very encouraging results on 23 UCI data sets, particularly for naive Bayes where the use of two validation folds yielded significant improvements on more than half of them, with only one loss.
---
paper_title: The relationship between Precision-Recall and ROC curves

paper_content:

Receiver Operator Characteristic (ROC) curves are commonly used to present results for binary decision problems in machine learning. However, when dealing with highly skewed datasets, Precision-Recall (PR) curves give a more informative picture of an algorithm's performance. We show that a deep connection exists between ROC space and PR space, such that a curve dominates in ROC space if and only if it dominates in PR space. A corollary is the notion of an achievable PR curve, which has properties much like the convex hull in ROC space; we show an efficient algorithm for computing this curve. Finally, we also note differences in the two types of curves are significant for algorithm design. For example, in PR space it is incorrect to linearly interpolate between points. Furthermore, algorithms that optimize the area under the ROC curve are not guaranteed to optimize the area under the PR curve.
---
paper_title: Explicitly representing expected cost: an alternative to ROC representation

paper_content:

ABSTRACT This paper proposes an alternative to ROC representation, in which the expected cost of a classi er is represented explicitly. This expected cost representation maintains many of the advantages of ROC representation, but is easier to understand. It allows the experimenter to immediately see the range of costs and class frequencies where a particular classi er is the best and quantitatively how much better it is than other classi ers. This paper demonstrates there is a point/line duality between the two representations. A point in ROC space representing a classi er becomes a line segment spanning the full range of costs and class frequencies. This duality produces equivalent operations in the two spaces, allowing most techniques used in ROC analysis to be readily reproduced in the cost space.
---
paper_title: Analysis and Visualization of Classifier Performance: Comparison under Imprecise Class and Cost Distributions

paper_content:

Applications of inductive learning algorithms to real-world data mining problems have shown repeatedly that using accuracy to compare classifiers is not adequate because the underlying assumptions rarely hold. We present a method for the comparison of classifier performance that is robust to imprecise class distributions and misclassification costs. The ROC convex hull method combines techniques from ROC analysis, decision analysis and computational geometry, and adapts them to the particulars of analyzing learned classifiers. The method is efficient and incremental, minimizes the management of classifier performance data, and allows for clear visual comparisons and sensitivity analyses.
---
paper_title: ROC Graphs : Notes and Practical Considerations for Data Mining Researchers

paper_content:

Receiver Operating Characteristics (ROC) graphs are a useful technique for organizing classifiers and visualizing their performance. ROC graphs are commonly used in medical decision making, and in recent years have been increasingly adopted in the machine learning and data mining research communities. Although ROC graphs are apparently simple, there are some common misconceptions and pitfalls when using them in practice. This article serves both as a tutorial introduction to ROC graphs and as a practical guide for using them in research.
---
paper_title: Improving Accuracy and Cost of Two-class and Multi-class Probabilistic Classifiers Using ROC Curves

paper_content:

The probability estimates of a naive Bayes classifier are inaccurate if some of its underlying independence assumptions are violated. The decision criterion for using these estimates for classification therefore has to be learned from the data. This paper proposes the use of ROC curves for this purpose. For two classes, the algorithm is a simple adaptation of the algorithm for tracing a ROC curve by sorting the instances according to their predicted probability of being positive. As there is no obvious way to upgrade this algorithm to the multi-class case, we propose a hillclimbing approach which adjusts the weights for each class in a pre-defined order. Experiments on a wide range of datasets show the proposed method leads to significant improvements over the naive Bayes classifier's accuracy. Finally, we discuss an method to find the global optimum, and show how its computational complexity would make it untractable.
---
paper_title: Training multiclass classifiers by maximizing the volume under the ROC surface

paper_content:

Receiver operating characteristic (ROC) curves are a plot of a ranking classifier's true-positive rate versus its false-positive rate, as one varies the threshold between positive and negative classifications across the continuum. The area under the ROC curve offer a measure of the discriminatory power of machine learning algorithms that is independent of class distribution, via its equivalence to Mann-Whitney U-statistics. This measure has recently been extended to cover problems of discriminating three and more classes. In this case, the area under the curve generalizes to the volume under the ROC surface. ::: ::: In this paper, we show how a multi-class classifier can be trained by directly maximizing the volume under the ROC surface. This is accomplished by first approximating the discrete U-statistic that is equivalent to the volume under the surface in a continuous manner, and then maximizing this approximation by gradient ascent.
---
paper_title: The quickhull algorithm for convex hulls

paper_content:

The convex hull of a set of points is the smallest convex set that contains the points. This article presents a practical convex hull algorithm that combines the two-dimensional Quickhull algorithm with the general-dimension Beneath-Beyond Algorithm. It is similar to the randomized, incremental algorithms for convex hull and delaunay triangulation. We provide empirical evidence that the algorithm runs faster when the input contains nonextreme points and that it used less memory. computational geometry algorithms have traditionally assumed that input sets are well behaved. When an algorithm is implemented with floating-point arithmetic, this assumption can lead to serous errors. We briefly describe a solution to this problem when computing the convex hull in two, three, or four dimensions. The output is a set of “thick” facets that contain all possible exact convex hulls of the input. A variation is effective in five or more dimensions.
---
paper_title: Volume under the ROC surface for multi-class problems

paper_content:

Operating Characteristic (ROC) analysis has been successfully applied to classifier problems with two classes. The Area Under the ROC Curve (AUC) has been elected as a better way to evaluate classifiers than predictive accuracy or error and has also recently used for evaluating probability estimators. However, the extension of the Area Under the ROC Curve for more than two classes has not been addressed to date, because of the complexity and elusiveness of its precise definition. Some approximations to the real AUC are used without an exact appraisal of their quality. In this paper, we present the real extension to the Area Under the ROC Curve in the form of the Volume Under the ROC Surface (VUS), showing how to compute the polytope that corresponds to the absence of classifiers (given only by the trivial classifiers), to the best classifier and to whatever set of classifiers. We compare the real VUS with "approximations" or "extensions" of the AUC for more than two classes.
---
paper_title: Multi-class ROC analysis from a multi-objective optimisation perspective

paper_content:

The receiver operating characteristic (ROC) has become a standard tool for the analysis and comparison of classifiers when the costs of misclassification are unknown. There has been relatively little work, however, examining ROC for more than two classes. Here we discuss and present an extension to the standard two-class ROC for multi-class problems. We define the ROC surface for the Q-class problem in terms of a multi-objective optimisation problem in which the goal is to simultaneously minimise the Q(Q-1) misclassification rates, when the misclassification costs and parameters governing the classifier's behaviour are unknown. We present an evolutionary algorithm to locate the Pareto front-the optimal trade-off surface between misclassifications of different types. The use of the Pareto optimal surface to compare classifiers is discussed and we present a straightforward multi-class analogue of the Gini coefficient. The performance of the evolutionary algorithm is illustrated on a synthetic three class problem, for both k-nearest neighbour and multi-layer perceptron classifiers.
---
paper_title: A Simple Generalisation of the Area Under the ROC Curve for Multiple Class Classification Problems

paper_content:

The area under the ROC curve, or the equivalent Gini index, is a widely used measure of performance of supervised classification rules. It has the attractive property that it side-steps the need to specify the costs of the different kinds of misclassification. However, the simple form is only applicable to the case of two classes. We extend the definition to the case of more than two classes by averaging pairwise comparisons. This measure reduces to the standard form in the two class case. We compare its properties with the standard measure of proportion correct and an alternative definition of proportion correct based on pairwise comparison of classes for a simple artificial case and illustrate its application on eight data sets. On the data sets we examined, the measures produced similar, but not identical results, reflecting the different aspects of performance that they were measuring. Like the area under the ROC curve, the measure we propose is useful in those many situations where it is impossible to give costs for the different kinds of misclassification.
---
paper_title: C.: An improved model selection heuristic for AUC

paper_content:

The area under the ROC curve (AUC) has been widely used to measure ranking performance for binary classification tasks. AUC only employs the classifier's scores to rank the test instances; thus, it ignores other valuable information conveyed by the scores, such as sensitivity to small differences in the score values However, as such differences are inevitable across samples, ignoring them may lead to overfitting the validation set when selecting models with high AUC. This problem is tackled in this paper. On the basis of ranks as well as scores, we introduce a new metric called scored AUC(sAUC), which is the area under the sROC curve. The latter measures how quickly AUC deteriorates if positive scores are decreased. We study the interpretation and statistical properties of sAUC. Experimental results on UCI data sets convincingly demonstrate the effectiveness of the new metric for classifier evaluation and selection in the case of limited validation data.
---
paper_title: Efficient AUC Optimization for Classification

paper_content:

In this paper we show an efficient method for inducing classifiers that directly optimize the area under the ROC curve. Recently, AUC gained importance in the classification community as a mean to compare the performance of classifiers. Because most classification methods do not optimize this measure directly, several classification learning methods are emerging that directly optimize the AUC. These methods, however, require many costly computations of the AUC, and hence, do not scale well to large datasets. In this paper, we develop a method to increase the efficiency of computing AUC based on a polynomial approximation of the AUC. As a proof of concept, the approximation is plugged into the construction of a scalable linear classifier that directly optimizes AUC using a gradient descent method. Experiments on real-life datasets show a high accuracy and efficiency of the polynomial approximation.
---
paper_title: Partial ensemble classifiers selection for better ranking

paper_content:

Ranking is an important task in data mining and knowledge discovery. We propose a novel approach called PECS algorithm to improve the overall ranking performance of a given ensemble. We formally analyse the sufficient and necessary condition under which PECS algorithm can effectively improve ensemble ranking performance. The experiments with real-world data sets show that this new approach achieves significant improvements in ranking over the original bagging and Adaboost ensembles.
---
paper_title: A critical analysis of variants of the AUC

paper_content:

The area under the ROC curve, or AUC, has been widely used to assess the ranking performance of binary scoring classifiers. Given a sample, the metric considers the ordering of positive and negative instances, i.e., the sign of the corresponding score differences. From a model evaluation and selection point of view, it may appear unreasonable to ignore the absolute value of these differences. For this reason, several variants of the AUC metric that take score differences into account have recently been proposed. In this paper, we present a unified framework for these metrics and provide a formal analysis. We conjecture that, despite their intuitive appeal, actually none of the variants is effective, at least with regard to model evaluation and selection. An extensive empirical analysis corroborates this conjecture. Our findings also shed light on recent research dealing with the construction of AUC-optimizing classifiers.
---
paper_title: Modifying ROC curves to incorporate predicted probabilities

paper_content:

The area under the ROC curve (AUC) is becoming a popular measure for the evaluation of classifiers, even more than other more classical measures, such as error/accuracy, logloss/entropy or precision. The AUC measure is specifically adequate to evaluate in two-class problems how well a model ranks a set of examples according to the probability assigned to the positive class. One shortcoming of AUC is that it ignores the probability values, and it only takes the order into account. On the other hand, logloss or MSE are alternative measures, but they only consider how well the probabilities are calibrated, and not its order. In this paper we introduce a new probabilistic version of AUC, called pAUC. This measure evaluates ranking performance, but also takes the magnitude of the probabilities into account. Secondly, we present a method for visualising a pROC curve such that the area under this curve corresponds to pAUC.
---
paper_title: A critical analysis of variants of the AUC

paper_content:

The area under the ROC curve, or AUC, has been widely used to assess the ranking performance of binary scoring classifiers. Given a sample, the metric considers the ordering of positive and negative instances, i.e., the sign of the corresponding score differences. From a model evaluation and selection point of view, it may appear unreasonable to ignore the absolute value of these differences. For this reason, several variants of the AUC metric that take score differences into account have recently been proposed. In this paper, we present a unified framework for these metrics and provide a formal analysis. We conjecture that, despite their intuitive appeal, actually none of the variants is effective, at least with regard to model evaluation and selection. An extensive empirical analysis corroborates this conjecture. Our findings also shed light on recent research dealing with the construction of AUC-optimizing classifiers.
---
paper_title: ROC Graphs with Instance-Varying Costs

paper_content:

Receiver operating characteristics (ROC) graphs are useful for organizing classifiers and visualizing their performance. ROC graphs have been used in cost-sensitive learning because of the ease with which class skew and error cost information can be applied to them to yield cost-sensitive decisions. However, they have been criticized because of their inability to handle instance-varying costs; that is, domains in which error costs vary from one instance to another. This paper presents and investigates a technique for adapting ROC graphs for use with domains in which misclassification costs vary within the instance population. pulation.
---
paper_title: Efficient AUC Optimization for Classification

paper_content:

In this paper we show an efficient method for inducing classifiers that directly optimize the area under the ROC curve. Recently, AUC gained importance in the classification community as a mean to compare the performance of classifiers. Because most classification methods do not optimize this measure directly, several classification learning methods are emerging that directly optimize the AUC. These methods, however, require many costly computations of the AUC, and hence, do not scale well to large datasets. In this paper, we develop a method to increase the efficiency of computing AUC based on a polynomial approximation of the AUC. As a proof of concept, the approximation is plugged into the construction of a scalable linear classifier that directly optimizes AUC using a gradient descent method. Experiments on real-life datasets show a high accuracy and efficiency of the polynomial approximation.
---
paper_title: The DET curve in assessment of detection task performance

paper_content:

Abstract : We introduce the DET Curve as a means of representing performance on detection tasks that involve a tradeoff of error types. We discuss why we prefer it to the traditional ROC Curve and offer several examples of its use in speaker recognition and language recognition. We explain why it is likely to produce approximately linear curves. We also note special points that may be included on these curves, how they are used with multiple targets, and possible further applications.
---
paper_title: Efficient AUC Learning Curve Calculation

paper_content:

A learning curve of a performance measure provides a graphical method with many benefits for judging classifier properties. The area under the ROC curve (AUC) is a useful and increasingly popular performance measure. In this paper, we consider the computational aspects of calculating AUC learning curves. A new method is provided for incrementally updating exact AUC curves and for calculating approximate AUC curves for datasets with millions of instances. Both theoretical and empirical justifications are given for the approximation. Variants for incremental exact and approximate AUC curves are provided as well.
---
paper_title: Properties and Benefits of Calibrated Classifiers

paper_content:

A calibrated classifier provides reliable estimates of the true probability that each test sample is a member of the class of interest. This is crucial in decision making tasks. Procedures for calibration have already been studied in weather forecasting, game theory, and more recently in machine learning, with the latter showing empirically that calibration of classifiers helps not only in decision making, but also improves classification accuracy. In this paper we extend the theoretical foundation of these empirical observations. We prove that (1) a well calibrated classifier provides bounds on the Bayes error (2) calibrating a classifier is guaranteed not to decrease classification accuracy, and (3) the procedure of calibration provides the threshold or thresholds on the decision rule that minimize the classification error. We also draw the parallels and differences between methods that use receiver operating characteristic (ROC) curves and calibration based procedures that are aimed at findig a threshold of minimum error. In particular, calibration leads to improved performance when multiple thresholds exist.
---
paper_title: Learning Curves for the Analysis of Multiple Instance Classifiers

paper_content:

In Multiple Instance Learning (MIL) problems, objects are represented by a set of feature vectors, in contrast to the standard pattern recognition problems, where objects are represented by a single feature vector. Numerous classifiers have been proposed to solve this type of MIL classification problem. Unfortunately only two datasets are standard in this field (MUSK-1 and MUSK-2), and all classifiers are evaluated on these datasets using the standard classification error. In practice it is very informative to investigate their learning curves, i.e. the performance on train and test set for varying number of training objects. This paper offers an evaluation of several classifiers on the standard datasets MUSK-1 and MUSK-2 as a function of the training size. This suggests that for smaller datasets a Parzen density estimator may be preferrer over the other 'optimal' classifiers given in the literature.
---
paper_title: Active Learning to Maximize Area Under the ROC Curve

paper_content:

In active learning, a machine learning algorithm is given an unlabeled set of examples U, and is allowed to request labels for a relatively small subset of U to use for training. The goal is then to judiciously choose which examples in U to have labeled in order to optimize some performance criterion, e.g. classification accuracy. We study how active learning affects AUC. We examine two existing algorithms from the literature and present our own active learning algorithms designed to maximize the AUC of the hypothesis. One of our algorithms was consistently the top performer, and Closest Sampling from the literature often came in second behind it. When good posterior probability estimates were available, our heuristics were by far the best.
---
paper_title: An Analysis of Rule Evaluation Metrics

paper_content:

In this paper we analyze the most popular evaluation metrics for separate-and-conquer rule learning algorithms. Our results show that all commonly used heuristics, including accuracy, weighted relative accuracy, entropy, Gini index and information gain, are equivalent to one of two fundamental prototypes: precision, which tries to optimize the area under the ROC curve for unknown costs, and a cost-weighted difference between covered positive and negative examples, which tries to find the optimal point under known or assumed costs. We also show that a straightforward generalization of the m-estimate trades off these two prototypes.
---
paper_title: The relationship between Precision-Recall and ROC curves

paper_content:

Receiver Operator Characteristic (ROC) curves are commonly used to present results for binary decision problems in machine learning. However, when dealing with highly skewed datasets, Precision-Recall (PR) curves give a more informative picture of an algorithm's performance. We show that a deep connection exists between ROC space and PR space, such that a curve dominates in ROC space if and only if it dominates in PR space. A corollary is the notion of an achievable PR curve, which has properties much like the convex hull in ROC space; we show an efficient algorithm for computing this curve. Finally, we also note differences in the two types of curves are significant for algorithm design. For example, in PR space it is incorrect to linearly interpolate between points. Furthermore, algorithms that optimize the area under the ROC curve are not guaranteed to optimize the area under the PR curve.
---
paper_title: An Analysis of Rule Learning Heuristics

paper_content:

In this paper we analyze the most popular search heuristics for separate-andconquer rule learning algorithms. Our results show that all commonly used heuristics, including accuracy, weighted relative accuracy, entropy, Gini index and information gain, are equivalent to one of two fundamental prototypes: precision, which tries to optimize the area under the ROC curve for unknown costs, and a cost-eighted difference between covered positive and negative examples, which tries to find the optimal point under known or assumed costs. We also show that a straight-forward generalization of the m-heuristic is a means for trading off between these two prototypes.
---
paper_title: Explicitly representing expected cost: an alternative to ROC representation

paper_content:

ABSTRACT This paper proposes an alternative to ROC representation, in which the expected cost of a classi er is represented explicitly. This expected cost representation maintains many of the advantages of ROC representation, but is easier to understand. It allows the experimenter to immediately see the range of costs and class frequencies where a particular classi er is the best and quantitatively how much better it is than other classi ers. This paper demonstrates there is a point/line duality between the two representations. A point in ROC space representing a classi er becomes a line segment spanning the full range of costs and class frequencies. This duality produces equivalent operations in the two spaces, allowing most techniques used in ROC analysis to be readily reproduced in the cost space.
---
paper_title: Cost curves: An improved method for visualizing classifier performance

paper_content:

This paper introduces cost curves, a graphical technique for visualizing the performance (error rate or expected cost) of 2-class classifiers over the full range of possible class distributions and misclassification costs. Cost curves are shown to be superior to ROC curves for visualizing classifier performance for most purposes. This is because they visually support several crucial types of performance assessment that cannot be done easily with ROC curves, such as showing confidence intervals on a classifier's performance, and visualizing the statistical significance of the difference in performance of two classifiers. A software tool supporting all the cost curve analysis described in this paper is available from the authors.
---
paper_title: What ROC curves can’t do (and cost curves can

paper_content:

This paper shows that ROC curves, as a method of visualizing classifier performance, are inadequate for the needs of Artificial Intelligence researchers in several significant respects, and demonstrates that a different way of visualizing performance – the cost curves introduced by Drummond and Holte at KDD’2000 – overcomes these deficiencies.
---
paper_title: An improved measure for comparing diagnostic tests

paper_content:

We present a loss based method for comparing the predictive performance of diagnostic tests. Unlike standard assessment mechanisms, like the area under the receiver-operating characteristic curve and the misclassification rate, our method takes specific advantage of any information that can be obtained about misclassification costs. We argue that not taking costs into account can lead to incorrect conclusions, and illustrate with two examples.
---
paper_title: Comparing classifiers when the misallocation costs are uncertain

paper_content:

Receiver Operating Characteristic (ROC) curves are popular ways of summarising the performance of two class classification rules. In fact, however, they are extremely inconvenient. If the relative severity of the two different kinds of misclassification is known, then an awkward projection operation is required to deduce the overall loss. At the other extreme, when the relative severity is unknown, the area under an ROC curve is often used as an index of performance. However, this essentially assumes that nothing whatsoever is known about the relative severity – a situation which is very rare in real problems. We present an alternative plot which is more revealing than an ROC plot and we describe a comparative index which allows one to take advantage of anything that may be known about the relative severity of the two kinds of misclassification.
---

<format>
Title: ROC Analysis of Classifiers in Machine Learning: A Survey

Section 1: Introduction
Description 1: Write an introduction to ROC analysis, its history, and its relevance in machine learning.

Section 2: Definition of the ROC space
Description 2: Define ROC space, explain the concept of confusion matrix, TPR, FPR, and the basic characteristics of ROC graphs.

Section 3: Engaging classifiers into the ROC construction process
Description 3: Detail the process of generating ROC curves for various classifiers and discuss specifics for common classification models.

Section 4: Applications of ROC analysis
Description 4: Describe the diverse applications of ROC analysis in machine learning, such as model evaluation, comparison, selection, presentation, and construction.

Section 5: Improvements of the basic ROC technique
Description 5: Discuss the enhancements and extensions to the basic ROC method, including ROC convex hulls, confidence intervals, multi-class extensions, and AUC metric variants.

Section 6: Alternatives to the tools of ROC analysis
Description 6: Provide an overview of alternative techniques to ROC graphs for classifier performance comparison, such as DET curves, LC plots, cost curves, and PR curves.

Section 7: Conclusion
Description 7: Summarize the key points discussed in the survey and mention the ongoing and future work in ROC analysis in machine learning.

</format>
