COLEP: Certifiably Robust Learning-Reasoning Conformal Prediction via Probabilistic Circuits

Q1: Consideration of finite-sample error induced by Monte-Carlo sampling in randomized smoothing. How does COLEP perform when accounting for finite-sample errors when estimating randomized smoothing expectations?

We thank you for bringing up this interesting point! We added the following discussions as well as theoretical and empirical results considering the finite-sample errors of randomized smoothing in the revised manuscript.

RSCP+ [1] points out the neglect of finite-sample errors of Monte-Carlo sampling by randomized smoothing in RSCP [2]. A naive solution is to apply union bound over all calibration samples, but it leads to a loose prediction set as shown in RSCP+. Therefore, RSCP+ proposes a subtle solution by viewing the empirical mean $\hat{S}\_{\text{RS}}$ as the non-conformity scores and thus only need to bound the finite-sample error of the empirical mean $\hat{S}\_{\text{RS}}$ on the test sample $(x\_{n+1},y\_{n+1})$ (Corollary 2 in [1]). Specifically, they apply Hoeffding’s inequality and Empirical Bernstein’s inequality to bound the finite-sample error of empirical mean $\hat{S}\_{\text{RS}}$ compared to the true mean $S\_{\text{RS}}$ of the test sample $(x\_{n+1},y\_{n+1})$ (Theorem C.6 in [1]). In this way, RSCP+ does not need to apply union over calibration samples and one concentration bound over the test sample is sufficient.

Since COLEP applies randomized smoothing to the model output in the learning component instead of the end-to-end non-conformity scores, we need to deal with the finite-sample error in a slightly different way, but the general spirit aligns with RSCP+. COLEP applies randomized smoothing to get the bound of output probabilities of the main model and knowledge models, and then propagates the bound to the probability bound after the reasoning component (Theorem 1) and the bound of non-conformity scores (Theorem 2). Therefore, to consider the finite-sample errors, we need to define a $\beta$-confidence worst-case non-conformity score based on Equation (12) in Theorem 2. Concretely, in Equation (12), we replace the original probability upper bound $\mathbb{U}\_{\delta}[\cdot]$ with a $\beta$-confidence version $\mathbb{U}\_{\beta,\delta}[\cdot]$, denoting the upper bound of non-conformity scores with confidence $1-\beta$, and similarly for the lower bound. In this way, during the proof of Theorem 2, we need to apply the union bound in the derivation from Equation (53) to Equation (54) by considering the event probability $\mathbb{P}[\hat{\pi}\_j^{\text{COLEP}}(\tilde{X}\_{n+1}) \le \mathbb{U}\_{\beta,\delta}[\hat{\pi}\_j^{\text{COLEP}}(X\_{n+1})] ] \ge 1 - 2\beta$. Similarly, we consider the event related to the lower bound in the derivation from Equation (57) to Equation (58). Finally, to counter the effect of finite-sample error and maintain a $1-\alpha$ coverage, we need to compute the $1-\alpha+2\beta$ quantile in Equation (11) in Theorem 2. We provided the rigorous theorem statement and proofs in Theorem 6 in Appendix F.3. We separated the theoretical result with finite-sample errors since Theorem 2 also allows for deterministic certification methods such as bound propagation methods which do not lead to finite-sample errors. We added related discussions and references in the remarks of Theorem 2.

We also empirically considered the finite-sample errors induced by randomized smoothing expectation approximation and provided the updated results in Figure 2 and Figure 3 in the revised manuscript. We consider the finite-sample errors of RSCP following RSCP+ (Corollary 2 in [1]) and the finite-sample errors of COLEP following Theorem 6 in Appendix F.3. We performed 100k Monte-Carlo sampling for a smaller error in practice and provided all the details in the experiment section of the revised manuscript. We generally observe an error of $[0.002,0.005]$ induced by finite samples of randomized smoothing. One can further reduce the finite-sample errors by increasing the Monte-Carlo sample sizes or applying better concentration bounds. From the updated results in Figure 2 and Figure 3, we can still conclude that COLEP with the reasoning component demonstrates better robustness and prediction efficiency than SOTA baseline RSCP.

[1] Provably Robust Conformal Prediction with Improved Efficiency, ICLR 2024 submission (https://openreview.net/forum?id=BWAhEjXjeG)

[2] Gendler, Asaf, et al. "Adversarially robust conformal prediction." ICLR 2021.

Q2: Clarification of adaptive PGD attack against the learning-reasoning pipeline.

We thank you for the valuable comment. We added a clear clarification that we consider an adaptive PGD attack against the complete learning-reasoning pipeline in Section 7. Formally, the attack process can be formulated as the optimization problem: $\max\_{\|\eta\|\_2 \le \delta} \ell\_\text{CE}(\hat{\pi}^{\text{COLEP}}(x),y)$, where $\ell\_\text{CE}$ is the cross-entropy loss and $\hat{\pi}^{\text{COLEP}}(x)$ is the class probabilities given sample $x$ computed by Equation (6) which takes the reasoning component into consideration.

Q3: Are the i.i.d. assumptions necessary for the learning-reasoning component, or can this be relaxed to just exchangeability as with vanilla CP?

We thank you for the valuable questions. In Section 3 of the revised manuscript, we made it clear that we only need the exchangeability assumptions as vanilla CP. Specifically, we only assume the clean test sample is drawn exchangeably to the calibration samples and the adversarial sample is within bounded perturbations from the clean test sample.

Thank you for the comment! We evaluate the marginal coverage and average set size under PGD attack with perturbation bound $\delta=0.25$ (same setting as Figure 3). We added the specification in the caption of Table 5 in the updated version.

Thank you for the comprehensive reply!

I have one follow question. If I understood correctly Figure 3 in the updated version considers the finite-sample errors for COLEP similar to RSCP+. However, for the second bar do you show RSCP (without error correction) or do you show RSCP+ (with error correction)? I'm asking since [1] reported very high set size for RSCP+.

It might be also interesting to show COLEP and COLEP+ (or however the corrected version is called) side by side.

Thank you for the engaging discussion and the detailed reply.

I agree with your comment. One minor point is that since $\frac{\epsilon}{\delta}$ is fixed it can be interepreted either as the first line or the second line of certification.

While the first line might be indeed more reasonable. I think that the second line also make sense. The reason is that if the perturbation ball is symmetric, then a ball around the perturbed $x'$ must contain the clean $x$ (of course the ball around the clean $x$ is different, but the two balls overlap).

Now when certifying classification, if everything inside the ball has the same prediction then the prediction for $x'$ coincides with the prediction for $x$. We can conclude this without knowing the clean $x$. The same applies for the conformal set if we use the worst-case score, since the worst-case score in a ball around x' is by definition larger than the score of the clean x.

Thank you for the quite valuable response!

Providing general certification for the second line based on the symmetry between $x$ and $x'$ is indeed an interesting point! Specifically, given perturbed $x'$ during test time, we can compute the bounds of output logits in the $\delta$-ball, which will also cover the clean $x$. Since the logit bounds also hold for clean $x$, we can compute the worst-case scores based on the bounds and finally construct the prediction set with the clean quantile value.

We agree that the two lines of certification are sound and essentially parallel. It is fundamentally due to the exchangeability of clean samples, which leads to consideration of worst-case bounds either during calibration or inference. One practical advantage of the first line of certification might be that the computation of worst-case bounds requires more runtime, and thus, computing it during the offline calibration process might be more desirable than during the online inference process. In terms of the tightness of the certification, we currently do not have a straightforward intuition of which one is dominantly better. Since we mainly focus on demonstrating the effectiveness of logical reasoning in this paper, we would like to leave the interesting exploration to future work.

We added discussions of alternative certification methods in the revised version in Appendix A. Thank you again for the valuable comments and points!

Q2: The notations are complex for readers.

We thank you for your valuable comments and suggestions. We make the following updates to enhance the reading of the paper.

1. We include more comprehensive and structured notation review tables in Appendix K for a better understanding of the analysis of COLEP. Specifically, we provide an overview of notations related to model definitions in Table 5, notations related to conformal prediction in Table 6, notations related to certification of Section 5 in Table 7, and notations related to analysis of Section 6 in Table 8. All the used notations in COLEP are currently provided in the notation tables in a structured manner, which is emphasized at the beginning of Section 4. In this way, readers can look up the meanings of notations easily and quickly via the tables.

2. We also improved the overall certification flow in Figure 4 in Appendix E. We restructured the flow and included more illustrations to improve the readability. We also added a brief overview description of the certification flow for a better understanding. The certification setting is that the inference time adversaries can add bounded perturbations to the test sample and violate the data exchangeability assumption, compromising the guaranteed coverage. The certification generally achieves the following three goals. (1) We can preserve the guaranteed coverage using a prediction set that takes the perturbation bound into account (in Theorem 2), achieved by computing the probability bound of models before the reasoning component (by randomized smoothing) and the bound after the reasoning component (by Theorem 1). (2) We prove the worst-case coverage (a lower bound) if we use the standard prediction set as before (in Theorem 3). (3) We theoretically show that COLEP can achieve better prediction coverage (in Theorem 4) and prediction accuracy (in Theorem 5) than a data-driven model without the reasoning component.

3. We follow the suggestion to separate important definitions from the paragraphs for ease of backtracking the original definitions. Concretely, we separate the definitions of $\hat{\pi}_j(x)$ and $\hat{\pi}^{(l)}(x)$ in Section 4.1 and the definition of $F(\mu)$ in Section 4.2.

We believe that these enhancements will make it simpler for readers to understand the provided analysis.

Q3: More details of reasoning component construction in the experiment part in the main text.

We thank you for the valuable suggestion, In summary, we have 3 PCs and 28 knowledge rules in GTSRB, 3 PCs and 30 knowledge rules in CIFAR-10, and 4 PCs and 187 knowledge rules in AwA2. Based on the domain knowledge in each dataset, we encode a set of implication rules into PCs. In each PC, we encode a type of implication knowledge with disjoint attributes. In GTSRB, we have a PC of shape knowledge (e.g., “octagon'', “square''), a PC of boundary color knowledge (e.g., “red boundary'', “black boundary''), and a PC of content knowledge (e.g., “digit 50'', “Turn Left''). In CIFAR-10, we have a PC of category knowledge (e.g., “animal'', “transportation''), a PC of space knowledge (e.g., “in the sky'', “in the water'', “on the ground''), and a PC of feature knowledge (e.g., “has legs'', “has wheels''). In AwA2, we have a PC of superclass knowledge (e.g., “procyonid'', “big cat''), a PC of predation knowledge (e.g., “fish'', “meat'', “plant''), a PC of appearance (e.g., “big ears'', “small eyes''), and a PC of fur color knowledge (e.g., “green'', “gray'', “white'').

For example, in the PC of shape knowledge in GTSRB, we can encode the implication rules related to the shape knowledge such as $\text{IsStopSign} \implies \text{IsOctagon}$ (stop signs are octagon) with weight $w_1$, $\text{IsSpeedLimit} \implies \text{IsSquare}$ (speed limit signs are square) with weight $w_2$, and $\text{IsTurnLeft} \implies \text{IsRound}$ (turn left signs are round) with weight $w_3$. To implement the COLEP learning-reasoning framework, we follow the steps to encode the rules into PCs.

• (1) We learn the main model and knowledge models implemented with DNNs to estimate a preliminary probability for $N_c$ class labels and $L$ concept labels (e.g., $p(\\text{IsSpeedLimit}=1)=\\hat{\\pi}\_{sp}$, p\(\text{IsSquare}=1)=\\hat{\\pi}\_{sq}).

• (2) We compute the factor value $F(\mu)$ for any possible assignment $\mu \in \\{0,1\\}^{N_c+L}$ as $F(\mu) = \exp \{\sum\_{h=1}^H w\_h \mathbb{I}\_{[\mu \sim K_h]}\}$ (e.g.,$F([1,1,1,1,1,1])=e^{w_1+w_2+w_3}$ since the assignment satisfy all three knowledge rules above).

• (3) We construct a three-layer PC as shown in Figure 1: (a) the bottom layer consists of leaf nodes representing Bernoulli distributions of all class and concept labels parameterized by the preliminary class probabilities, and the constant factor values of assignments (e.g., $B(\hat{\pi}\_{sp}),B(1-\hat{\pi}\_{sp}),B(\hat{\pi}\_{sq}),B(1-\hat{\pi}\_{sq}),...,F([1,1,1,1,1,0]),F([1,1,1,1,1,1]),...$), (b) the second layer consists of product nodes computing the likelihood of each assignment by multiplying the likelihood of the instantiations of Bernoulli variables and the correction factor values (e.g., $\hat{\pi}\_{sp} \times \hat{\pi}\_{sq} \times … \times F([1,1,1,1,1,1])$), and (c) the top layer is a sum node computing the summation of the products.

• (4) We linearly combine multiple PCs that encode different types of knowledge rules (e.g., 3 PCs in GTSRB: PCs of shape/color/content knowledge).

We included the statistics of knowledge rules and details of PC implementation in Section 7 and Appendix J.1 in the revised manuscript.

Q4: Visualization of the functionality of the reasoning component.

We thank you for the suggestion of adding visualization of the contribution of different knowledge rules. Specifically in GTSRB, we consider the contribution of the shape knowledge rules, color knowledge rules, and content knowledge rules. In CIFAR-10, we consider the contribution of the category knowledge rules, space knowledge rules, and feature knowledge rules. More details of the meanings and examples of knowledge rules are provided in response to Q3 and Appendix J.1. We provided the visualization of contributions of different types of knowledge rules in Figure 5 in Appendix J.2. The results show that the rules related to the color knowledge in GTSRB and space knowledge in CIFAR-10 benefits the certified coverage more, but collectively applying all the well-designed knowledge rules lead to even better coverage. The effectiveness of these types of knowledge is attributed to a higher utility of the knowledge models (i.e., the accuracy of concept detection). Concretely, the feature of these more effective concepts is relatively easy to learn and can be more accurately detected (e.g., color concepts are more easily learned than shape concepts). The correlation between the knowledge model utility and effectiveness of COLEP is also theoretically analyzed and observed in Section 6.

Q1: Limited empirical evaluations.

We thank you for your valuable comments and suggestions on the evaluation part. We made the following updates to clarify and strengthen the evaluation of COLEP.

1. We avoided the confusion induced by improper namings in Section 7. APS score is indeed not the SOTA method, and thus, we called it a baseline of conformal prediction and only called RSCP [1] as the SOTA approach in adversarially robust conformal prediction in the revised version.

2. We followed the suggestion to compare with more baselines of various conformal prediction scores to show the robustness of COLEP. Specifically, we further evaluate the RAPS score [2], which improves the APS score by adding a regularization term regarding the ranking of the ground truth label. We also evaluate the recent clustered conformal prediction (CCP) [3], which computes the quantile and performs calibration at the cluster level. We compare COLEP with these baselines on AwA2 under PGD attack. The results in the following Table 1 show that (1) conformal prediction with vanilla conformity scores APS, RAPS, and CCP leads to a broken coverage in the adversary setting, while adversarially robust conformal prediction method RSCP and COLEP still maintains the valid coverage, and (2) compared to RSCP, COLEP demonstrates a better tradeoff between the coverage and prediction efficiency.

3. We added the following clarifications and more evaluations to demonstrate the scalability of COLEP. Besides the relatively small-scale but standard benchmark CIFAR-10 and GTSRB, we also conducted evaluations on AwA2 [4] in different settings in Figure 2 and Figure 3 in Section 7. AwA2 dataset contains 37,322 images of 50 different animal classes, which are extracted from the ImageNet dataset and with a high resolution of $256 \times 256$. The dataset also has 85 attribute labels (concept labels) for each animal class and is suitable for evaluations of knowledge-intensive tasks. In total, we construct 187 implication rules in total with 4 types of knowledge encoded in 4 PCs separately. Evaluations on AwA2 are already the largest scale in the related literature on learning-reasoning [5] and neuro-symbolic [6]. The scalability of COLEP comes from the usage of probabilistic circuits with linear inference time with respect to the graph size instead of the intractable Markov logic network with NP-complete time complexity used by prior works [5,6]. To consolidate the scalability to AwA2, we further added more evaluations with multiple perturbation bounds in the following Table 1. The results together with results in Figure 2 and Figure 3 on AwA2 demonstrate the scalability and robustness of COLEP to achieve an impressive prediction coverage and efficiency in the adversary setting.

We also admit that it is challenging for evaluations on the full ImageNet with 1000 classes due to the expensive costs of training thousands of concept models and the lack of knowledge rules at the current stage, which is also discussed as one limitation in Appendix A. However, we deem that the principles and analysis in COLEP shed light on the effectiveness of the reasoning component to achieve a more robust conformal prediction. It is also interesting for future work to leverage the CLIP model for concept detection and the large language models for the design of knowledge rules, which can fully unleash the power of COLEP on more large-scale evaluations.

Table 1. Marginal coverage / average set size of multiple conformal prediction baselines, SOTA method RSCP, and COLEP under PGD Attack and AutoAttack with $\ell_2$ bounded perturbations $0.25$ and $0.50$ on AwA2. The nominal level of coverage is $0.9$.

[1] Gendler, Asaf, et al. "Adversarially robust conformal prediction." ICLR 2021.

[2] Angelopoulos, Anastasios, et al. "Uncertainty sets for image classifiers using conformal prediction." ICLR 2021.

[3] Ding, Tiffany, et al. "Class-Conditional Conformal Prediction With Many Classes." NeurIPS 2023.

[4] Xian, Yongqin, et al. "Zero-shot learning—a comprehensive evaluation of the good, the bad and the ugly." TPAMI 2018.

[5] Yang, Zhuolin. Improving certified robustness via statistical learning with logical reasoning. NeurIPS 2022.

[6] Wu, Tailin, et al. "Zeroc: A neuro-symbolic model for zero-shot concept recognition and acquisition at inference time." NeurIPS 2022.

We thank the reviewer for the valuable suggestions and positive feedback!! We will definitely follow the reviewer’s suggestion to further improve our paper further and add additional results and related analysis based on our discussion. Please let us know if you have other suggestions, and we hope our paper will lead to an interesting new direction to integrate data-driven learning with knowledge-enabled logical reasoning for the community.

Q1: Density notations and difficulty of reading.

Upon your feedback, we made the following improvements to the readability of the notations and analysis.

1. We include more comprehensive and structured notation review tables in Appendix K for a better understanding of the analysis of COLEP. Specifically, we provide an overview of notations related to model definitions in Table 5, notations related to conformal prediction in Table 6, notations related to certification of Section 5 in Table 7, and notations related to analysis of Section 6 in Table 8. All the used notations in COLEP are currently provided in the notation tables in a structured manner, which is emphasized at the beginning of Section 4. In this way, readers can look up the meanings of notations easily and quickly via the tables.

2. We also improved the overall certification flow in Figure 4 in Appendix E. We restructured the flow and included more illustrations to improve the readability. We also added a brief overview description of the certification flow for a better understanding. The certification setting is that the inference time adversaries can add bounded perturbations to the test sample and violate the data exchangeability assumption, compromising the guaranteed coverage. The certification generally achieves the following three goals. (1) We can preserve the guaranteed coverage using a prediction set that takes the perturbation bound into account (in Theorem 2), achieved by computing the probability bound of models before the reasoning component (by randomized smoothing) and the bound after the reasoning component (by Theorem 1). (2) We prove the worst-case coverage (a lower bound) if we use the standard prediction set as before (in Theorem 3). (3) We theoretically show that COLEP can achieve better prediction coverage (in Theorem 4) and prediction accuracy (in Theorem 5) than a data-driven model without the reasoning component.

3. We follow the suggestion to separate important definitions from the paragraphs for ease of backtracking the original definitions. Concretely, we separate the definitions of $\hat{\pi}_j(x)$ and $\hat{\pi}^{(l)}(x)$ in Section 4.1 and the definition of $F(\mu)$ in Section 4.2.

We believe that with the improvements, the readers can follow the presented analysis more easily.

Q2: Citation issues.

We thank you for the valuable comments. We added the citations of seminal articles in the related work section.

Q3: Limitations section.

We included the discussions on limitations in Appendix A and added references to it in Section 8. To summarize, a possible limitation of COLEP may lie in the computational costs induced by pretraining knowledge models. However, the problem can be partially relieved by training knowledge models with parallelism. Moreover, we only need to pretrain them once and then can encode different types of knowledge rules based on domain knowledge. The training cost is valuable since we theoretically and empirically show that more knowledge models benefit the robustness of COLEP a lot for conformal prediction. Another possible limitation may lie in the access to knowledge rules. For the datasets that release hierarchical information (e.g., ImageNet, CIFAR-100, Visual Genome), we can easily adapt the information to implication rules used in COLEP. We can also seek knowledge graphs with related label semantics for rule design. These approaches may be effective in assisting practitioners in designing knowledge rules, but the process is not fully automatic, and human efforts are still needed. Overall, for any knowledge system, one naturally needs domain experts to design the knowledge rules specific to that application. There is probably no universal strategy on how to aggregate knowledge for any arbitrary application, and rather application-specific constructions are needed. This is where the power as well as limitation of our framework comes from.

Q4: Notation fix in the preliminaries.

We thank you for pointing it out. We fixed the notation in Section 3 in the revised manuscript.

Q5: Why is COLEP better suited to conformal prediction than already existing methods?

To the best of our knowledge, RSCP [1] is the most relevant existing method proposed for the problem of adversarially robust conformal prediction. RSCP provides the robustness certification of conformal prediction for a single model where they treat the mapping from input to the non-conformity score as a black-box function and apply randomized smoothing to achieve the certification. COLEP differs from RSCP [1] in all these aspects. Namely,

At the model level: RSCP considers a standard single model, while COLEP follows a two-stage learning-reasoning pipeline where the learning component employs several models, and then integrates a separate reasoning component with PCs to it. We study this complex pipeline and theoretically prove that its robustness is better than a robust single model (RSCP) in terms of prediction coverage and prediction accuracy.

At the certification level: the direct application of randomized smoothing as in RSCP does not yield a tight end-to-end robustness certification for COLEP. As such, we

a) use robustness certification approaches to derive bounds of the learning component,

b) consider the structural properties of PCs and provide efficient robustness certification of the PC component and

c) translate the bound of output probabilities of COLEP to the bound of non-conformity scores to achieve the end-to-end certification.

[1] Gendler, Asaf, et al. "Adversarially robust conformal prediction." International Conference on Learning Representations. 2021.

Q6: What does "certified conformal prediction" mean? Is this different from saying that we have a marginal coverage guarantee?

Certified conformal prediction presents the worst-case coverage guarantee under bounded input perturbations. Marginal coverage guarantee presents the lower bound of prediction coverage with the assumption of exchangeability, indicating that the test samples are clean and drawn from the same distribution as the calibration samples. In contrast, certified conformal prediction presents the lower bound of prediction coverage with bounded input perturbations on the clean test sample. The additional input perturbations can violate the exchangeability assumption and break the original marginal coverage guarantee. Based on the problem, COLEP presents a certification of the worst-case coverage guarantees considering the adversarial perturbations during the inference time and improves the robustness with the power of logical reasoning. We made it more clear in the revised manuscript.

Q7: Explanations of why the certified coverage of COLEP is below $0.9$ in Figure 2.

We evaluate the certified coverage (i.e., the lower bound of prediction coverage under bounded perturbations) in Figure 2. Since $0.9$ is the nominal coverage level without perturbations during the test time, the certified coverage considering perturbations should be lower than the nominal coverage level $0.9$ and can be rigorously computed by our certification, as shown in Figure 2. In Figure 2, the comparison of the certified coverage to the baseline (RSCP) demonstrates the robustness of COLEP with logical reasoning and the tightness of our certification in Theorem 3.

Furthermore, we can also take the test-time perturbations into consideration during the calibration process to ensure the certified coverage remains at the specified level $0.9$. We evaluate the results in this scenario in Figure 3. The results show that the coverage of COLEP is always above the nominal coverage $0.9$ and achieves better efficiency than RSCP.

Q1: More clarifications about assignment $\mu$, factor function value $F(\mu)$, and the computation of $\pi^{\text{COLEP}}_j(x)$ accordingly.

We included the following clarification of definitions in Section 4.2. $F(\mu)$ is indeed a fixed factor function once $H$ knowledge rules and weights are determined. Note that $\mu$ is an index variable of the summation process in Equation (6) (instead of observation), and thus we do not need to observe the values of $\mu$. For a particular index vector $\mu$ in the summation process, $F(\mu)$ computes the summation of the weights of satisfied knowledge rules, denoting how well the index vector $\mu$ aligns with the specified knowledge rules.

Let’s consider the illustrative example of stop sign classification model with an auxiliary knowledge model of octagon shape classification in Section 4.2. The index variable $\mu \in \\{0,1\\}^2$ denotes a possible assignment of Bernoulli random variables $\text{IsStopSign}$ and $\text{IsOctagon}$. Therefore, we have that $F(\mu=[0,0])=F(\mu=[0,1])=F(\mu=[1,1])=e^w$ and $F(\mu=[1,0])=e^0$ since only the assignment $\mu=[1,0]$ (i.e., $\text{IsStopSign}=1, \text{IsOctagon}=0$) violates the knowledge rule $\text{IsStopSign} \rightarrow \text{IsOctagon}$ with weight $w$. Then according to Equation (6), we can compute $\pi_j^{\text{COLEP}}(x)$ (i.e., $p(\text{IsStopSign}=1)$) by marginalizing the Bernoulli variable $\text{IsOctagon}$ as follows: $\pi_j^{\text{COLEP}}(x) = \dfrac{p(\text{IsStopSign}=1)p(\text{IsOctagon}=0)F(\mu=[1,0]) + p(\text{IsStopSign}=1)p(\text{IsOctagon}=1)F(\mu=[1,1])}{p(\text{IsStopSign}=1)p(\text{IsOctagon}=0)F(\mu=[1,0]) + p(\text{IsStopSign}=1)p(\text{IsOctagon}=1)F(\mu=[1,1]) + p(\text{IsStopSign}=0)p(\text{IsOctagon}=0)F(\mu=[0,0]) + p(\text{IsStopSign}=0)p(\text{IsOctagon}=1)F(\mu=[0,1])}$, where $p(\cdot)$ is the likelihood estimate of the main model and knowledge models without the reasoning component.

Q2: Discussion of the robustness of COLEP with contaminated knowledge graph.

We thank you for the interesting question! It is interesting to consider cases where the knowledge graph is contaminated by adversarial attackers or contains noises and misinformation by the neglect of designers. According to the response to Q1, $\mu$ is an index variable instead of observations, and thus, the robustness of COLEP mainly originates from the knowledge rules via factor function $F(\cdot)$ denoting how well each assignment conforms to the specified knowledge rules. Since the knowledge rules and weights are specified by practitioners and fixed during inferences, the PCs encoding the knowledge rules together with the main model and knowledge models (learning + reasoning component in Figure 1) can be viewed as a complete model. According to the adversarial attack settings in the literature[1,2], the model weights can be well protected and not manipulated by attackers in practical cases, and thus, the PC graph (i.e., source of side information) which is a part of the complete model can not be easily manipulated by adversarial attackers.

On the other hand, it is an interesting question to discuss the case when the knowledge rules may be contaminated and contain misinformation due to the neglect of designers. We can view the problem of checking knowledge rules and correcting misinformation as a pre-processing step before the employment of COLEP. The parallel module of knowledge checking and correction is explored by a line of research [3,4,5], which basically detects and corrects false logical relations via semantic embeddings and consistency-checking techniques. It is also interesting to leverage more advanced large language models to check and correct human-designed knowledge rules. We deem that the process of knowledge-checking is independent and parallel to COLEP, which may take additional efforts before the deployment of COLEP but significantly benefits in achieving a much more robust system based on our analysis and evaluations. We added the related discussions in Appendix A.

[1] Goodfellow, Ian J., Jonathon Shlens, and Christian Szegedy. "Explaining and harnessing adversarial examples." arXiv preprint arXiv:1412.6572 (2014).

[2] Gendler, Asaf, et al. "Adversarially robust conformal prediction." International Conference on Learning Representations. 2021.

[3] Melo, André, and Heiko Paulheim. "An approach to correction of erroneous links in knowledge graphs." CEUR Workshop Proceedings. Vol. 2065. RWTH Aachen, 2017.

[4] Caminhas, Daniel D. "Detecting and correcting typing errors in open-domain knowledge graphs using semantic representation of entities." (2019).

[5] Chen, Jiaoyan, et al. "Correcting knowledge base assertions." Proceedings of the Web Conference 2020.

Q3: Computation of the bound of class probabilities for more general functions.

As illustrated in Section 5.1, the computation of the bound of class probabilities consists of two steps:

• (1) bound computation of class probabilities after the learning component (i.e., $\min\_{\| \eta \|_2 \le \delta} \pi\_j(x+\eta)$ and $\max\_{\| \eta \|_2 \le \delta} \pi\_j(x+\eta)$)
• (2) bound computation of class probabilities after the reasoning component (i.e., $\min\_{\|\eta\|\_2 \le \delta} \pi\_j^{\text{COLEP}}(x+\eta)$ and $\max\_{\|\eta\|\_2 \le \delta} \pi\_j^{\text{COLEP}}(x+\eta)$).

We can compute the bound in step (1) for any general functions $\pi_j$ with randomized smoothing. We can compute the bound in step (2) based on the results of step (1) according to Theorem 1, which holds for general probabilistic circuits that can encode arbitrary logic rules. Therefore, COLEP allows for bound computation for general deep neural networks in the learning component and general probabilistic circuits in the reasoning component.

Q4: Selection of weight $w$ in $F(\mu)$.

We thank you for the interesting question. The weight $w$ of logical rules is specified based on the utility of the corresponding knowledge rule. In Section 6, we theoretically show that the robustness of COLEP correlates with the utility of knowledge rules regarding the uniqueness of the rule, defined in Equation (17). Specifically, a universal knowledge rule which generally holds for almost all class labels is of low quality and does not benefit the robustness and should be assigned with a low weight $w$. For example, if all the traffic signs in the dataset are of octagon shape, then the implication rule $\text{IsStopSign} \implies \text{IsOctagon}$ should be useless and assigned with a low weight $w$, which also aligns with the intuition.

In the empirical evaluations, since we already designed knowledge rules of high quality (i.e., good uniqueness) as shown in Section 7, we do not need to spend great efforts selecting weights for each knowledge rule individually. We assume that all the knowledge rules have the same weight $w$ and select a proper weight $w$ for all the knowledge rules via grid search. The results in the following Table 1 inspire us to fix $w$ as $1.5$, and the evaluations demonstrate that it is sufficient to achieve good robustness in different settings. One can also model the weight selection problem as a combinatorial optimization, which is non-trivial but can better unleash the power of COLEP. We leave a more intelligent and automatic approach of knowledge weight selection for future work. We included the discussions in Section 7 and Appendix J.

Table 1. Certified coverage of COLEP on GTSRB with different weights $w$ of knowledge rules under perturbation bound $\delta=0.25$.

We thank you again for the valuable suggestions and comments! Since it is close to the end of the discussion period, we wonder whether our responses address your concerns. We are happy to take any further questions or concerns.

We thank you for the valuable feedback!

Q2 & Q4: More discussions about partially true knowledge rules and the guidelines of selections of rule weights.

We thank you for the interesting and valuable question! If a knowledge rule is true with a lower probability, then the associated weight rule should be smaller, and vice versa. In the example, the probability is with respect to the data distribution, which means that $70\\%$ of data satisfies the rule “IsStopSign->IsOctogan”. Besides, other distribution-dependent factors such as the portions of class labels also affect the importance of corresponding rules. If one class label is pretty rare in the data distribution, then the knowledge rules associated with it clearly should be assigned a small weight, and vice versa. In summary, the importance of knowledge rules depends on the data distribution, no matter whether we select it via grid search or optimize it in a more subtle way. Therefore, we deem that a general guideline for an effective and efficient selection of rule weights is to perform a grid search on a held-out validation set, which is also essential for standard model training. However, we do not think the effectiveness of COLEP is quite sensitive to the selection of weights. From the theoretical analysis and evaluations, we can expect benefits from the knowledge rules as long as we have a positive weight $w$ for the rules. We included related discussions in Appendix A in the revision.

Minor comments: Changing the example on page 3.

We changed the example on Page 3 for better alignment in the revised version.

Q3. More details about how to compute the probability bound (e.g., $\min\_{\\|\\eta\\|\_2 < \delta}\pi_j(x+\eta)$).

We directly apply randomized smoothing [1] to compute the bound of model output in the learning component (i.e., $\min\_{ \\|\\eta\\|_2 < \delta}\\pi\_j(x+\\eta)$, $\max\_{ \\|\\eta\\|_2 < \delta}\\pi\_j(x+\\eta)$) in experiments. Following the standard procedure in [1], we (a) randomly sample Gaussian noises $\eta$ from $\mathcal{N}(0,\sigma^2)$ for 100k times, (b) compute the empirical mean of the output of the smoothed model $\hat{\mathbb{E}}[\\pi\_j(x+\\eta)]$, (c) compute the lower bound and upper bound as $\min\_{ \\|\\eta\\|_2 < \delta}\\pi\_j(x+\\eta) = \Phi(\Phi^{-1}(\hat{\mathbb{E}}[\\pi\_j(x+\\eta)]) - \delta/\sigma)$, $\max\_{ \\|\\eta\\|_2 < \delta}\\pi\_j(x+\\eta)=\Phi(\Phi^{-1}(\hat{\mathbb{E}}[\\pi\_j(x+\\eta)]) + \delta/\sigma)$, where $\Phi(\cdot)$ is the standard Gaussian CDF and $\delta$ is the perturbation bound. We also provided related details in Appendix C.3 in our paper.

[1] Cohen, Jeremy, Elan Rosenfeld, and Zico Kolter. "Certified adversarial robustness via randomized smoothing." ICML 2019.

Q3: Add more discussions about the theorems in the main paper.

We thank you for the valuable suggestion. We added more details in the remarks of theorems in the revised manuscript. Concretely, we made the following additions:

• updated details of how we can get the probability bounds of the learning component and how we leverage them for computations of the bounds after the reasoning component in remarks of Theorem 1

• details of the meanings of different terms such as certified prediction set and worst-case non-conformity score and the corresponding references to the equations in the remark of Theorem 2

• illustrations of the technical difference between Theorem 3 and Theorem 2 in the remark of Theorem 3 for a better understanding

• discussions of the physical meanings of the quantities affecting the bounds such as the utility of models $T_{j,\mathcal{D}}^{(r)},Z_{j,\mathcal{D}}^{(r)}$ and the utility of knowledge rules $U_j^{(r)}$ in the remark of Theorem 4 and the practical insights implied by the results

• discussions of the influence of the utility of models $T_{j,\mathcal{D}}^{(r)},Z_{j,\mathcal{D}}^{(r)}$ and the utility of knowledge rules $U_j^{(r)}$ on the prediction accuracy of COLEP and the practical implications in the remark of Theorem 5

Q4: Add more empirical evaluations of COLEP. Specifically, evaluate the performance of COLEP against other forms of adversarial attacks.

We thank you for the valuable suggestions. To evaluate the robustness of COLEP under various types of attacks, we further consider AutoAttack [1], which uses an ensemble of four diverse attacks to reliably evaluate the robustness: (1) APGD-CE attack, (2) APGD-DLR attack, (3) FAB attack, and (4) square attack. APGD-CE and APGD-DLR attacks are step-size-free versions of PGD attacks with cross-entropy loss and DLR loss, respectively. FAB attack optimizes the adversarial sample by minimizing the norm of the adversarial perturbations. Square attack is a query-efficient black-box attack. We evaluate the prediction coverage and averaged set size of COLEP and SOTA method RSCP with $\ell_2$ bounded perturbation of $0.25$ on GTSRB, CIFAR-10, and AwA2. The desired coverage is $1-\alpha=0.9$ in the evaluation. The results in the following Table 1 show that under diverse and stronger adversarial attacks, COLEP still achieves higher marginal coverage than the nominal level $0.9$ and also demonstrates a better prediction efficiency (i.e., smaller size of prediction sets) than RSCP. We incorporated the results in Appendix J.2 and referred to it in Section 7 in the main text.

Table 1. Marginal coverage / average set size of RSCP and COLEP under AutoAttack [1] with $\ell_2$ bounded perturbation of $0.25$ on GTSRB, CIFAR-10, and AwA2.

[1] Croce, Francesco, and Matthias Hein. "Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks." International conference on machine learning. PMLR, 2020.

Q1: Provide more details about how the PCs can help reduce the error of the main classifier. Specifically, add clarifications of how the prespecified factor weights and estimated likelihood (classes and concepts) and user-defined knowledge rules are combined together to make robust decisions.

We thank you for the valuable comment. We included the following details about the PC structure and its benefits to the robustness in Section 4.2 in the revised manuscript.

PC defines a joint distribution over a set of random variables (e.g., $\text{IsStopSign}$, $\text{IsOctagon}$) and computes the joint probability of them in the graph efficiently by performing forwarding passes. We can encode the knowledge rules with a 3-layer PC as shown in Figure 1: (1) the bottom layer consists of leaf nodes representing Bernoulli variables; (2) the second layer consists of product nodes computing the joint probability of an assignment by multiplying the likelihood of individual Bernoulli variables and the factor values (e.g., $\hat{\pi}_{s} \times \hat{\pi}^{o} \times F([1,1])$); and (c) the top layer is a sum node computing the summation of the products. With the PC structure, one can efficiently compute the marginal probabilities in Equation (6) with two forwarding passes. The details and proofs are shown in Appendix C.1.

The reasoning component can correct the output probability with encoded knowledge rules and improve the robustness of the prediction. Consider the following concrete example. Suppose that the adversarial example of a speed limit sign misleads the main classifier to detect it as a stop sign with a large probability (e.g., $\hat{\pi}_s=0.9$), but the octagon classifier is not misled and correctly predicts that the speed limit sign does not have an octagon shape (e.g., $\hat{\pi}_o=0.0$). Then according the computation as Equation (6), the corrected probability of detecting a stop sign given the attacked speed limit image is $\hat{\pi}^{\text{COLEP}}_s=0.9/(0.1e^w+0.9)$, which is down-weighted from the original wrong prediction $\hat{\pi}_s=0.9$ as we have a positive logical rule weight $w>0$. Therefore, the reasoning component can correct the wrong output probabilities with the knowledge rules and lead to a more robust prediction framework. Besides the intuition reflected by the simple example, we also theoretically show that the reasoning component benefits in achieving better prediction coverage and accuracy compared to a single DNN without the reasoning component.

Q2: Add clear specification of PC coefficient $\beta_r$ in the main manuscript.

Thank you for the suggestion! We incorporated more specifications for PC coefficients $\beta_r$ in the main manuscript in Section 4.2. Concretely, we can formulate the corrected conditional class probability $\pi_j^{\text{COLEP}}$ with multiple PCs as $\pi_j^{\text{COLEP}}(x) = \sum_{r \in [R]} \beta_{r} \pi_j^{(r)}(x)$, where $\pi_j^{(r)}$ is the output class probabilities of the $r$-th PC. The core of this formulation is the mixture model involving a latent variable $r_{\text{PC}}$ representing the PCs. In short, we can write $\pi_j^{(r)}(x)$ as $\pi_j^{(r)}(x)=\mathbb{P}[Y=y|X=x, r_{\text{PC}}=r]$, and $\pi_j(x)$ as the marginalized probability over the latent variable $r_{\text{PC}}$ as $\pi_j(x)=\sum_{r \in [R]} \mathbb{P}[r_{\text{PC}}=r] \cdot \pi_j^{(r)}(x)$. Hence, the coefficient $\beta_{r}$ for the $r$-th PC are determined by $\mathbb{P}[r_{\text{PC}}=r]$. Although we lack direct knowledge of this probability, we can estimate it using the data by examining how frequently each PC $r$ correctly predicts the outcome across the given examples, similarly as in the estimation of prior class probabilities for Naive Bayes classifiers.

Q5: Include more details about the number and complexity of PCs in the experiment part.

We thank you for the valuable question. In summary, we have 3 PCs and 28 knowledge rules in GTSRB, 3 PCs and 30 knowledge rules in CIFAR-10, and 4 PCs and 187 knowledge rules in AwA2. Based on the domain knowledge in each dataset, we encode a set of implication rules into PCs. In each PC, we encode a type of implication knowledge with disjoint attributes. In GTSRB, we have a PC of shape knowledge (e.g., “octagon'', “square''), a PC of boundary color knowledge (e.g., “red boundary'', “black boundary''), and a PC of content knowledge (e.g., “digit 50'', “Turn Left''). In CIFAR-10, we have a PC of category knowledge (e.g., “animal'', “transportation''), a PC of space knowledge (e.g., “in the sky'', “in the water'', “on the ground''), and a PC of feature knowledge (e.g., “has legs'', “has wheels''). In AwA2, we have a PC of superclass knowledge (e.g., “procyonid'', “big cat''), a PC of predation knowledge (e.g., “fish'', “meat'', “plant''), a PC of appearance (e.g., “big ears'', “small eyes''), and a PC of fur color knowledge (e.g., “green'', “gray'', “white''). For example, in the PC of shape knowledge in GTSRB, we can encode the implication rules related to the shape knowledge such as $\text{IsStopSign} \implies \text{IsOctagon}$ (stop signs are octagon), $\text{IsSpeedLimit} \implies \text{IsSquare}$ (speed limit signs are square), and $\text{IsTurnLeft} \implies \text{IsRound}$ (turn left signs are round). We included the statistics of PCs and knowledge rules in Section 7 and more details in Appendix J.1 in the revised manuscript.

Q6: Add evaluations with variations of parameters $\alpha$ and $\delta$.

We thank you for the valuable suggestions. We further evaluate COLEP with multiple nominal levels of coverage $1-\alpha$ and with various perturbation bounds $\delta$. We provide the results with multiple coverage levels $1-\alpha$ in the following Table 2, and the results with multiple perturbation bounds $\delta$ in Table 3. The results demonstrate that for different parameters of $\alpha$ and $\delta$, (1) COLEP always achieves a higher marginal coverage than the nominal level, indicating the validity of the certification in COLEP, and (2) COLEP shows a better trade-off between the prediction coverage and prediction efficiency (i.e., average set size) than the SOTA baseline RSCP. We incorporated the results in Appendix J.2 and referred to it in Section 7 in the main text.

Table 2. Marginal coverage / average set size of RSCP and COLEP under PGD Attack with multiple desired coverage levels $1-\alpha$ with $\ell_2$ bounded perturbation of $0.25$ on GTSRB.

Table 3. Marginal coverage / average set size of RSCP and COLEP under PGD Attack with multiple $\ell_2$ bounded perturbations on GTSRB. The nominal level of coverage is $0.9$.

We thank you again for the valuable suggestions and comments! Since it is close to the end of the discussion period, we wonder whether our responses address your concerns. We are happy to take any further questions or concerns.