  Conformal inference, cross-validation+, and the jackknife+ are hold-out
methods that can be combined with virtually any machine learning algorithm to
construct prediction sets with guaranteed marginal coverage. In this paper, we
develop specialized versions of these techniques for categorical and unordered
response labels that, in addition to providing marginal coverage, are also
fully adaptive to complex data distributions, in the sense that they perform
favorably in terms of approximate conditional coverage compared to alternative
methods. The heart of our contribution is a novel conformity score, which we
explicitly demonstrate to be powerful and intuitive for classification
problems, but whose underlying principle is potentially far more general.
Experiments on synthetic and real data demonstrate the practical value of our
theoretical guarantees, as well as the statistical advantages of the proposed
methods over the existing alternatives.
