Efficient Confidence Set Enumeration for Multi-label Conformal Classification

Conformal prediction is a distribution-free and model agnostic framework that can provide statistical guarantees to machine learning algorithms: a point-wise predictor is transformed into a conformal predictor that outputs sets of predictions which include the ground truth with a user defined confidence rate. In multi-label conformal classification however, the exponential growth of the output space makes confidence sets prohibitively complex to compute in the general case. In this paper, we analyze this challenge under the prism of enumeration complexity. We detail a general approach for confidence set enumeration based on the flashlight method, prove a sufficient condition for efficient enumeration and apply this method on three types of problems. First, we give an enumeration algorithm with linear delay for modular non-conformity losses. Then, we discuss informed conformal classification where a boolean circuit specifies a set of valid label combinations and prove a sufficient condition for efficient enumeration based on standard properties of the circuit. Moreover, we leverage our results on informed conformal classification to tackle label interactions in the loss. Finally, we illustrate the benefits of our approach with a few experiments.