Abstract
Conformal prediction has recently emerged as a promising strategy forquantifying the uncertainty of a predictive model; these algorithms modify themodel to output sets of labels that are guaranteed to contain the true labelwith high probability. However, existing conformal prediction algorithms havelargely targeted classification and regression settings, where the structure ofthe prediction set has a simple form as a level set of the scoring function.However, for complex structured outputs such as text generation, theseprediction sets might include a large number of labels and therefore be hardfor users to interpret. In this paper, we propose a general framework forconformal prediction in the structured prediction setting, that modifiesexisting conformal prediction algorithms to output structured prediction setsthat implicitly represent sets of labels. In addition, we demonstrate how ourapproach can be applied in domains where the prediction sets can be representedas a set of nodes in a directed acyclic graph; for instance, for hierarchicallabels such as image classification, a prediction set might be a small subsetof coarse labels implicitly representing the prediction set of all their morefine-descendants. We demonstrate how our algorithm can be used to constructprediction sets that satisfy a desired coverage guarantee in several domains.