CoChat
Sign Up
PreprintCited by 4Machine Learning and AlgorithmsMachine Learning and Data ClassificationExplainable Artificial Intelligence (XAI)

Who Should Predict? Exact Algorithms For Learning to Defer to Humans

Open access
Mozannar, Hussein, Lang, Hunter, Wei, Dennis, Sattigeri, Prasanna, Das, Subhro, Sontag, David·2023·arXiv
DOI 10.48550/arxiv.2301.06197arXiv 2301.06197
Open this paper in CoChat — free accountOpen PDF

Abstract

Automated AI classifiers should be able to defer the prediction to a human decision maker to ensure more accurate predictions. In this work, we jointly train a classifier with a rejector, which decides on each data point whether the classifier or the human should predict. We show that prior approaches can fail to find a human-AI system with low misclassification error even when there exists a linear classifier and rejector that have zero error (the realizable setting). We prove that obtaining a linear pair with low error is NP-hard even when the problem is realizable. To complement this negative result, we give a mixed-integer-linear-programming (MILP) formulation that can optimally solve the problem in the linear setting. However, the MILP only scales to moderately-sized problems. Therefore, we provide a novel surrogate loss function that is realizable-consistent and performs well empirically. We test our approaches on a comprehensive set of datasets and compare to a wide range of baselines.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2301.06197

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • The state-of-the-art approach to managing assignments in human-AI collaboration is learning to defer.

    “The state-of-the-art approach to managing assignments in HAIC is learning to defer (L2D)4–13, in which algorithms choose whether to assign a task to a human expert or an ML model, leveraging their complementary strengths.”

    From A benchmarking framework and dataset for learning to defer in human-AI decision-making (2025) · cites this paper as [9]

    The Introduction and Section 3 describe learning to defer as using a rejector to choose whether the classifier or a human predicts, with the aim of complementary team performance. The paper compares deferral algorithms with prior baselines, but does not establish that learning to defer is the state-of-the-art approach to task assignment across human–AI collaboration generally. (LLM, conf=0.78)

    Experimental — accuracy not yet measured

  • Learning to Defer algorithms improve human-AI collaboration by deferring decisions to human experts when they are likely to be more accurate than the AI model.

    “Learning to Defer (L2D) algorithms improve human-AI collaboration by deferring decisions to human experts when they are likely to be more accurate than the AI model.”

    From A benchmarking framework and dataset for learning to defer in human-AI decision-making (2025) · cites this paper as [9]

  • The paper chose to create a total of 50 experts because this far surpasses the numbers previously considered in learning-to-defer research.

    “We chose to create a total of 50 experts as this far surpasses the numbers previously considered in L2D research4–13.”

    From A benchmarking framework and dataset for learning to defer in human-AI decision-making (2025) · cites this paper as [9]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 49

  1. D. A. E. Acar, A. Gangrade, and V. Saligrama. Budget learning via bracketing. In International Conference on Artificial Intelligence and Statistics, pages 4109-4119. PMLR, 2020.
  2. P. L. Bartlett and M. H. Wegkamp. Classification with a reject option using a hinge loss. Journal of Machine Learning Research, 9(Aug):1823-1840, 2008.
  3. P. L. Bartlett, M. I. Jordan, and J. D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138-156, 2006.
  4. R. M. Battleday, J. C. Peterson, and T. L. Griffiths. Capturing human categorization of natural images by combining deep networks and cognitive models. Nature communications, 11(1):1-14, 2020.
  5. E. Beede, E. Baylor, F. Hersch, A. Iurchenko, L. Wilcox, P. Ruamviboonsuk, and L. M. Vardoulakis. A human-centered evaluation of a deep learning system deployed in clinics for the detection of diabetic retinopathy. In Proceedings of the 2020 CHI Conference on Human Factors in Computing Systems, pages 1-12, 2020.
  6. Y. Bengio, A. Courville, and P. Vincent. Representation learning: A review and new perspectives. IEEE transactions on pattern analysis and machine intelligence, 35(8):1798-1828, 2013.
  7. A. Blum and R. Rivest. Training a 3-node neural network is np-complete. Advances in neural information processing systems, 1, 1988.
  8. S. Boyd and L. Vandenberghe. Convex optimization. Cambridge university press, 2004.
  9. N. Charoenphakdee, Z. Cui, Y. Zhang, and M. Sugiyama. Classification with rejection based on cost-sensitive classification. In International Conference on Machine Learning, pages 1507-1517.
  10. PMLR, 2021.
  11. M.-A. Charusaie, H. Mozannar, D. Sontag, and S. Samadi. Sample efficient learning of predictors that complement humans. In International Conference on Machine Learning, pages 2972-3005.
  12. PMLR, 2022.
  13. C. Chow. On optimum recognition error and reject tradeoff. IEEE Transactions on information theory, 16(1):41-46, 1970.
  14. C. Cortes, G. DeSalvo, and M. Mohri. Learning with rejection. In International Conference on Algorithmic Learning Theory, pages 67-82. Springer, 2016.
  15. T. Davidson, D. Warmsley, M. Macy, and I. Weber. Automated hate speech detection and the problem of offensive language. In Eleventh international aaai conference on web and social media, 2017.
  16. A. De, P. Koley, N. Ganguly, and M. Gomez-Rodriguez. Regression under human assistance. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 2611-2620, 2020.
  17. R. El-Yaniv and Y. Wiener. On the foundations of noise-free selective classification. Journal of Machine Learning Research, 11(May):1605-1641, 2010.
  18. A. Gangrade, A. Kag, and V. Saligrama. Selective classification via one-sided prediction. In International Conference on Artificial Intelligence and Statistics, pages 2179-2187. PMLR, 2021.
  19. Y. Geifman and R. El-Yaniv. Selective classification for deep neural networks. In Advances in neural information processing systems, pages 4878-4887, 2017.
  20. Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2022. URL https://www.gurobi. com. V. Guruswami and P. Raghavendra. Hardness of learning halfspaces with noise. SIAM Journal on Computing, 39(2):742-765, 2009.
  21. G. Huang, Z. Liu, L. Van Der Maaten, and K. Q. Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4700-4708, 2017.
  22. M. Jacobs, M. F. Pradier, T. H. McCoy, R. H. Perlis, F. Doshi-Velez, and K. Z. Gajos. How machine- learning recommendations influence clinician treatment selections: the example of antidepressant selection. Translational psychiatry, 11(1):1-9, 2021.
  23. G. Kerrigan, P. Smyth, and M. Steyvers. Combining human predictions with model probabilities via confusion matrices and calibration. Advances in Neural Information Processing Systems, 34, 2021.
  24. V. Keswani, M. Lease, and K. Kenthapadi. Towards unbiased and accurate deferral to multiple experts. arXiv preprint arXiv:2102.13004, 2021. · arXiv
  25. S. Khot and R. Saket. On the hardness of learning intersections of two halfspaces. Journal of Computer and System Sciences, 77(1):129-141, 2011.
  26. D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014. · arXiv
  27. A. Kumar, A. Raghunathan, R. M. Jones, T. Ma, and P. Liang. Fine-tuning can distort pre- trained features and underperform out-of-distribution. In International Conference on Learning Representations, 2022.
  28. Y. Lin. Support vector machines and the bayes rule in classification. Data Mining and Knowledge Discovery, 6(3):259-275, 2002.
  29. H. Liu, V. Lai, and C. Tan. Understanding the effect of out-of-distribution examples and interac- tive explanations on human-ai decision making. Proceedings of the ACM on Human-Computer Interaction, 5(CSCW2):1-45, 2021a.
  30. J. Liu, B. Gallego, and S. Barbieri. Incorporating uncertainty in learning to defer algorithms for safe computer-aided diagnosis. arXiv preprint arXiv:2108.07392, 2021b. · arXiv
  31. P. Long and R. Servedio. Consistency versus realizable h-consistency for multiclass classification. In International Conference on Machine Learning, pages 801-809. PMLR, 2013.
  32. I. Loshchilov and F. Hutter. Decoupled weight decay regularization. arXiv preprint arXiv:1711.05101, 2017. · arXiv
  33. D. Madras, T. Pitassi, and R. Zemel. Predict responsibly: Improving fairness and accuracy by learning to defer. In Advances in Neural Information Processing Systems, pages 6150-6160, 2018.
  34. A. Majkowska, S. Mittal, D. F. Steiner, J. J. Reicher, S. M. McKinney, G. E. Duggan, K. Eswaran, P.- H. Cameron Chen, Y. Liu, S. R. Kalidindi, et al. Chest radiograph interpretation with deep learning models: assessment with radiologist-adjudicated reference standards and population-adjusted evaluation. Radiology, 294(2):421-431, 2020.
  35. H. Mozannar and D. Sontag. Consistent estimators for learning to defer to an expert. In International Conference on Machine Learning, pages 7076-7087. PMLR, 2020.
  36. H. Mozannar, A. Satyanarayan, and D. Sontag. Teaching humans when to defer to a classifier via exemplars. In Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI), 2022.
  37. T. Nguyen and S. Sanner. Algorithms for direct 0-1 loss optimization in binary classification. In International Conference on Machine Learning, pages 1085-1093. PMLR, 2013.
  38. N. Okati, A. De, and M. Gomez-Rodriguez. Differentiable learning under triage. arXiv preprint arXiv:2103.08902, 2021. · arXiv
  39. M. F. Pradier, J. Zazo, S. Parbhoo, R. H. Perlis, M. Zazzi, and F. Doshi-Velez. Preferential mixture- of-experts: Interpretable models that rely on human expertise as much as possible. arXiv preprint arXiv:2101.05360, 2021. · arXiv
  40. M. Raghu, K. Blumer, G. Corrado, J. Kleinberg, Z. Obermeyer, and S. Mullainathan. The algorithmic automation problem: Prediction, triage, and human effort. arXiv preprint arXiv:1903.12220, 2019. · arXiv
  41. N. Raman and M. Yee. Improving learning-to-defer algorithms through fine-tuning. arXiv preprint arXiv:2112.10768, 2021. · arXiv
  42. N. Razavian, S. Blecker, A. M. Schmidt, A. Smith-McLallen, S. Nigam, and D. Sontag. Population- level prediction of type 2 diabetes from claims data and analysis of risk factors. Big Data, 3(4): 277-287, 2015.
  43. N. Reimers and I. Gurevych. Sentence-bert: Sentence embeddings using siamese bert-networks. arXiv preprint arXiv:1908.10084, 2019. · arXiv
  44. B. Ustun and C. Rudin. Supersparse linear integer models for optimized medical scoring systems. Machine Learning, 102(3):349-391, 2016.
  45. R. Verma and E. Nalisnick. Calibrated learning to defer with one-vs-all classifiers. arXiv preprint arXiv:2202.03673, 2022. · arXiv
  46. X. Wang, Y. Peng, L. Lu, Z. Lu, M. Bagheri, and R. Summers. Hospital-scale chest x-ray database and benchmarks on weakly-supervised classification and localization of common thorax diseases. In IEEE CVPR, volume 7, 2017.
  47. B. Wilder, E. Horvitz, and E. Kamar. Learning to complement humans. arXiv preprint arXiv:2005.00582, 2020. · arXiv
  48. S. Zagoruyko and N. Komodakis. Wide residual networks. arXiv preprint arXiv:1605.07146, 2016. · arXiv
  49. M. Zhang and S. Agarwal. Bayes consistency vs. h-consistency: The interplay between surrogate loss functions and the scoring function class. Advances in neural information processing systems, 33:16927-16936, 2020.

Cited by

Sorted by citations

Authors
Mozannar, H., Lang, H., Wei, D., Sattigeri, P., Das, S., & Sontag, D.
Affiliations
IBM (United States) (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2023
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2301.06197
arXiv
2301.06197
OpenAlex
W4320703314
Cited by
4
References
0
Citations by year
2025: 3 · 2024: 1
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
  • Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Data Classification
  • Physical Sciences › Computer Science › Artificial Intelligence › Explainable Artificial Intelligence (XAI)
Keywords
human-AI collaboration, NP-hardness, mixed-integer linear programming, surrogate loss, linear classifiers, automated decision-making

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review