Conformal Structured Prediction

Thank you for taking the time and effort to read and provide comments on our work. We provide answers to all the remarks and questions below.

How does the proposed method for conformal structured prediction fundamentally differ from or improve upon prior hierarchical prediction approaches?

Thank you for sharing this related work. We note that our goals are significantly different from the goals in [1]. In particular, the goal in [1] is to find the prediction set with the highest probability mass (as indicated by Eq. (3) in [1]), whereas our goal is to find the smallest possible prediction sets under a constraint that the coverage rate meets some desired level. As indicated by Table 2 of [1], their approach would obtain much lower coverage (e.g., <50%), whereas our results demonstrate that our approach achieves the desired coverage rate.

[1] T Mortier, et al. Set-Valued Prediction in Hierarchical Classification with Constrained Representation Complexity, 2022.

Conduct tests in more complex environments. (e.g. multi-label classification, multi-class classification in healthcare, or real-world document settings).

Thank you for this suggestion. We have added a new experiment to demonstrate the application of our framework to predict the emotion labels in a given piece of text. In particular, we use the GoEmotion dataset [2], which consists of 27 emotion categories annotated on 58,000 English Reddit comments. They also provide a hierarchical structure on these categories (Figure 2 in [2]). We show coverage rates and average prediction set sizes here (https://ibb.co/pvttLc9) using the same format as the other results in our paper. We will add these results to an updated version of our paper.

[2] Demszky, D., Movshovitz-Attias, D., Ko, J., Cowen, A., Nemade, G., & Ravi, S. (2020). GoEmotions: A dataset of fine-grained emotions. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics (pp. 4040-4054).

The framework assumes that the label space is represented by a DAG. How does this assumption impact generalizability to label structures that are non-hierarchical, cyclical, or have overlapping dependencies?

We emphasize that our DAG structure is a structure on the space of prediction sets, and can differ from the structure of the label space. In applications where the label space has a tree or DAG structure, we can naturally consider structured prediction sets that conform to this structure, but this is not a requirement. For instance, if the label space has a graph structure, we could still construct prediction sets representing sets of labels, and impose a DAG structure on these prediction sets (e.g., based on set inclusion). Thus, our approach can be flexibly applied to more complex domains. If you have any suggestions about specific kinds of label structures that might be of interest, we are happy to discuss them in detail.

Could you elaborate on practical scenarios or domains where marginal coverage versus PAC coverage would be preferable? How should a practitioner decide between the two guarantees in real-world settings?

The main difference between the two is the margin of safety that is provided. Marginal guarantees are on average over both the training set and the new examples. Thus, for a given training set, the resulting classifier might fail to satisfy the guarantee. In contrast, PAC prediction sets hold with high probability over the training set. This difference is illustrated by comparing the coverage rate plots for the two different approaches in our paper. When using marginal guarantees, the average coverage across different random seeds is above the desired coverage level, but any individual random seed may fall above or below this level. In contrast, for PAC guarantees, the coverage is above the desired coverage level for almost all random seeds.

Given these properties, PAC coverage generally provides greater reliability than marginal coverage. Thus, in domains where it is critical for the deployed model to satisfy the coverage guarantee, PAC prediction sets should be used; otherwise, marginal guarantees may suffice.

Integer programming (IP) can be computationally intensive, particularly for large DAGs. Have you measured or benchmarked the runtime performance and scalability of the IP formulation, especially in tasks with larger label hierarchies?

The plot here (https://ibb.co/2y276tG) illustrates the average time required to solve each IP problem as we vary $m$ while fixing $\epsilon=0.1$, for each of our four domains.

(continued on next comment)

Thank you once again for taking the time to review our work. We have carefully addressed the concerns you raised to the best of our ability, and your feedback has been invaluable in improving the quality and clarity of our submission.

As the discussion period is nearing its end, we would greatly appreciate the opportunity to confirm if we have addressed your concerns satisfactorily. We hope to have the chance to discuss this further today before the discussion period closes. Have we addressed all your comments?

Thank you for taking the time and effort to read and provide comments on our work. We provide answers to all the remarks and questions below.

Discuss and compare to related works:

Conformal Risk Control

Uncertainty Sets for Image Classifiers using Conformal Prediction

We thank the reviewer for pointing out these two related works. We want to note the following differences between our proposed algorithm and these works.

In general, the goals in the “Conformal Risk Control” paper are qualitatively very different – their goal is to minimize more general risk functions (instead of prediction set size), whereas our goal is to extend conformal prediction to structured prediction. In Section 3.3, their purpose is to control an alternative risk function based on the hierarchical label structure, while still constructing traditional prediction sets. Indeed, we believe that our approach could be combined with theirs to further improve interpretability of the resulting prediction sets. For this specific task, their algorithm can be viewed as producing a structured prediction set; however, even in this context, their search is constrained to only parent nodes of the class with the highest estimated probability $\hat y$, whereas our search space is much more general (and can be much more flexibly specified by the user).

The goal of the “Uncertainty Sets for Image Classifiers using Conformal Prediction” paper is also very different from ours. The goal of their paper is to reduce the average prediction set size by adding a regularization term (Eq. (4) in their paper), whereas our goal is to compute structured prediction sets.

Compare with more baselines

We compare our method with a baseline strategy adapted from [1]. While the strategy proposed in [1] is specialized to the code domain, we generalize their framework to apply to arbitrary DAG structures. Our results (below) show that we significantly outperform this baseline, both in terms of prediction set size and computational cost. The main shortcoming of this approach is that it leverages existing PAC prediction set algorithms, which require that the monotonicity assumption holds. Thus, their algorithm restricts the structure of the prediction sets across different values of $\tau$ to enforce monotonicity. In contrast, our approach proves a novel conformal prediction bound (Theorem 3.2 in our paper) to avoid the need for monotonicity. We show results for the question-answering task here (prediction set sizes: https://ibb.co/rp2VWqs; computational cost: https://ibb.co/ss1B9wp). These plots show the prediction set sizes using the same annotations as Figure 4 of our paper. The baseline results are represented by dashed lines. For both prediction set size and computational cost, our approach outperforms the baseline for almost every parameter setting, and significantly so for $m=2$ and $m=4$. Results in other domains exhibit similar trends, and we will add them in an updated version of the paper (which we plan to submit by the end of the rebuttal period).

[1]: Adam Khakhar, Stephen Mell, and Osbert Bastani. Pac prediction sets for large language models of code. In International Conference on Machine Learning, In International Conference on Machine Learning, pp. 16237–16249. PMLR, 2023.

Include more qualitative examples (e.g. Figure 1) with details, such as the error level used for standard conformal prediction.

We first thank the reviewer for reminding us of the missing error level information. The error level for both the standard conformal prediction and conformal structured set is 0.05 (i.e., the desired coverage level is 0.95).

As suggested by the reviewer, we provided another qualitative example here https://ibb.co/VvRQFM2, comparing our method to the standard PAC prediction set algorithm. We set the error level to 0.05 and the confidence level to 0.99 ($\delta$=0.01), for both the standard PAC prediction set and our algorithm. As can be seen from the example, when constructing the prediction set using the standard PAC prediction set algorithm, the resulting prediction set is much larger than the one constructed by our algorithm. The large prediction set includes labels from very distant categories, making it much harder to interpret compared to having just two coarse-grained labels that summarize the labels. In our prediction set, the different dog breeds have been summarized as simply “dog”, and the different man-made artifacts have been summarized as “artifact”. The fact that the labels are quite coarse reflects the inherent uncertainty in the prediction for this image.

(continued on next comment)

Thank you for including discussion of relevant related work. I also appreciate the additional empirical analysis. The paper can certainly benefit from more examples and greater clarity in writing to better motivate the work (as I suggested earlier as well). However, given the responses to the raised concerns, I would like to update my score towards acceptance.

Thank you for taking the time and effort to read and provide comments on our work. We provide answers to the questions below.

As with the broader conformal prediction literature, our goal is not to achieve better AUC, but to provide statistical guarantees on the coverage of our algorithm. In fact, the conformal prediction setting is closely related to the P/R curve: “coverage” is equivalent to recall, and “prediction set size” is closely related to precision (in particular, if we ignore miscoverages, then precision set size = 1/precision; it is straightforward to modify this equation to account for miscoverages). The key distinction is the focus on obtaining provable finite-sample guarantees on the coverage (a.k.a., recall). Our main contribution is an algorithm for constructing a conformal predictor that satisfies this guarantee. While we propose an algorithm for solving this problem, we emphasize that it is much more generally applicable than just hierarchical label spaces; instead, we are targeting general structured prediction algorithms. Thus, we do not believe comparisons to existing approaches for hierarchical label prediction are useful comparisons for understanding the properties of our approach.

Nevertheless, we appreciate the reviewer’s suggestion to include a comparison with a baseline to highlight our method’s contribution. To this end, we have compared to a baseline from the conformal prediction literature.

We compare our method with a baseline strategy adapted from [1]. While the strategy proposed in [1] is specialized to the code domain, we generalize their framework to apply to arbitrary DAG structures. Our results (below) show that we significantly outperform this baseline, both in terms of prediction set size and computational cost. The main shortcoming of this approach is that it leverages existing PAC prediction set algorithms, which require that the monotonicity assumption holds. Thus, their algorithm restricts the structure of the prediction sets across different values of $\tau$ to enforce monotonicity. In contrast, our approach proves a novel conformal prediction bound (Theorem 3.2 in our paper) to avoid the need for monotonicity. We show results for the question-answering task here (prediction set sizes: https://ibb.co/rp2VWqs; computational cost: https://ibb.co/ss1B9wp). These plots show the prediction set sizes using the same annotations as Figure 4 of our paper. The baseline results are represented by dashed lines. For both prediction set size and computational cost, our approach outperforms the baseline for almost every parameter setting, and significantly so for $m=2$ and $m=4$. Results in other domains exhibit similar trends, and we will add them in an updated version of the paper (which we plan to submit by the end of the rebuttal period).

Finally, to understand the relationship to the P/R curve, consider the this scatter plot (https://ibb.co/ZBgcpqS), which shows the relationship between recall (i.e., coverage rate) and precision (i.e., average inverse prediction set size) for the question answering task, with $m=4$ for both methods. As can be seen, our approach significantly outperforms the baseline.

[1]: Adam Khakhar, Stephen Mell, and Osbert Bastani. Pac prediction sets for large language models of code. In International Conference on Machine Learning, In International Conference on Machine Learning, pp. 16237–16249. PMLR, 2023.

Thank you once again for taking the time to review our work. We have carefully addressed the concerns you raised to the best of our ability, and your feedback has been invaluable in improving the quality and clarity of our submission.

As the discussion period is nearing its end, we would greatly appreciate the opportunity to confirm if we have addressed your concerns satisfactorily. We hope to have the chance to discuss this further today before the discussion period closes. Have we addressed all your comments?