The relationship between Precision-Recall and ROC curves

ABSTRACT

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.

REFERENCES

• 1: Bockhorst, J., & Craven, M. (2005). Markov networks for detecting overlapping elements in sequence data. Neural Information Processing Systems 17 (NIPS). MIT Press.
• 2: Bradley, A. (1997). The use of the area under the ROC curve in the evaluation of machine learning algorithms. Pattern Recognition, 30, 1145--1159.
• 3: Bunescu, R., Ge, R., Kate, R., Marcotte, E., Mooney, R., Ramani, A., & Wong, Y. (2004). Comparative Experiments on Learning Information Extractors for Proteins and their Interactions. Journal of Artificial Intelligence in Medicine, 139--155.
• 4: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 5: Cortes, C., & Mohri, M. (2003). AUC optimization vs. error rate minimization. Neural Information Processing Systems 15 (NIPS). MIT Press.
• 6: Davis, J., Burnside, E., Dutra, I., Page, D., Ramakrishnan, R., Costa, V. S., & Shavlik, J. (2005). View learning for statistical relational learning: With an application to mammography. Proceeding of the 19th International Joint Conference on Artificial Intelligence. Edinburgh, Scotland.
• 7: Chris Drummond , Robert C. Holte, Explicitly representing expected cost: an alternative to ROC representation, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.198-207, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347126]
• 8: Drummond, C., & Holte, R. C. (2004). What ROC curves can't do (and cost curves can). ROCAI (pp. 19--26).
• 9: César Ferri , Peter A. Flach , José Hernández-Orallo, Learning Decision Trees Using the Area Under the ROC Curve, Proceedings of the Nineteenth International Conference on Machine Learning, p.139-146, July 08-12, 2002
• 10: Yoav Freund , Raj D. Iyer , Robert E. Schapire , Yoram Singer, An Efficient Boosting Algorithm for Combining Preferences, Proceedings of the Fifteenth International Conference on Machine Learning, p.170-178, July 24-27, 1998
• 11: Goadrich, M., Oliphant, L., & Shavlik, J. (2004). Learning ensembles of first-order clauses for recall-precision curves: A case study in biomedical information extraction. Proceedings of the 14th International Conference on Inductive Logic Programming (ILP). Porto, Portugal.
• 12: Alan Herschtal , Bhavani Raskutti, Optimising area under the ROC curve using gradient descent, Proceedings of the twenty-first international conference on Machine learning, p.49, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015366]
• 13: Thorsten Joachims, A support vector method for multivariate performance measures, Proceedings of the 22nd international conference on Machine learning, p.377-384, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102399]
• 14: Stanley Kok , Pedro Domingos, Learning the structure of Markov logic networks, Proceedings of the 22nd international conference on Machine learning, p.441-448, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102407]
• 15: Macskassy, S., & Provost, F. (2005). Suspicion scoring based on guilt-by-association, collective inference, and focused data access. International Conference on Intelligence Analysis.
• 16: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 17: Prati, R., & Flach, P. (2005). ROCCER: an algorithm for rule learning based on ROC analysis. Proceeding of the 19th International Joint Conference on Artificial Intelligence. Edinburgh, Scotland.
• 18: Foster J. Provost , Tom Fawcett , Ron Kohavi, The Case against Accuracy Estimation for Comparing Induction Algorithms, Proceedings of the Fifteenth International Conference on Machine Learning, p.445-453, July 24-27, 1998
• 19: Vijay Raghavan , Peter Bollmann , Gwang S. Jung, A critical investigation of recall and precision as measures of retrieval system performance, ACM Transactions on Information Systems (TOIS), v.7 n.3, p.205-229, July 1989 [doi>10.1145/65943.65945]
• 20: Singla, P., & Domingos, P. (2005). Discriminative training of Markov Logic Networks. Proceedings of the 20th National Conference on Artificial Intelligene (AAAI) (pp. 868--873). AAAI Press.
• 21: Srinivasan, A. (2003). The Aleph Manual Version 4. http://web.comlab.ox.ac.uk/oucl/research/areas/machlearn/Aleph/.
• 22: Yan, L., Dodier, R., Mozer, M., & Wolniewicz, R. (2003). Optimizing classifier performance via the Wilcoxon-Mann-Whitney statistics. Proceedings of the 20th International Conference on Machine Learning.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Connectionism and neural nets
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Neural nets

General Terms:
Theory