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

Understand

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.