COLEP: Certifiably Robust Learning-Reasoning Conformal Prediction via Probabilistic Circuits
Authors: Mintong Kang
Nezihe Merve Gürel
Linyi Li
Bo Li
Venue: ICLR 2024 poster (2024)
Keywords: conformal prediction
adversarial robustness
probabilistic circuits
Primary area: societal considerations including fairness, safety, privacy
TL;DR: We propose a certifiably robust learning-reasoning pipeline for conformal prediction.

Abstract: Conformal prediction has shown spurring performance in constructing statistically rigorous prediction sets for arbitrary black-box machine learning models, assuming the data is exchangeable. However, even small adversarial perturbations during the inference can violate the exchangeability assumption, challenge the coverage guarantees, and result in a subsequent decline in empirical coverage. In this work, we propose a certifiably robust learning-reasoning conformal prediction framework (COLEP) via probabilistic circuits, which comprise a data-driven learning component that trains statistical models to learn different semantic concepts, and a reasoning component that encodes knowledge and characterizes the relationships among the trained models for logic reasoning. To achieve exact and efficient reasoning, we employ probabilistic circuits (PCs) within the reasoning component. Theoretically, we provide end-to-end certification of prediction coverage for COLEP in the presence of $\ell_2$ bounded adversarial perturbations. We also provide certified coverage considering the finite size of the calibration set. Furthermore, we prove that COLEP achieves higher prediction coverage and accuracy over a single model as long as the utilities of knowledge models are non-trivial. Empirically, we show the validity and tightness of our certified coverage, demonstrating the robust conformal prediction of COLEP on various datasets, including GTSRB, CIFAR10, and AwA2. We show that COLEP achieves up to 12% improvement in certified coverage on GTSRB, 9% on CIFAR-10, and 14% on AwA2.

Published as a conference paper at ICLR 2024
COLEP: CERTIFIABLY ROBUST LEARNING-REASONING CONFORMAL PREDICTION VIA PROBABILISTIC CIRCUITS
Mintong Kang
Nezihe Merve Gürel
Linyi
UIUC mintong28illinoie edu
TU Delft n.m. www.euuuueeeeeeee @tudeeft.
UIUC
Linyi2eillinois edu
Bo
UChicago UIUC
solouchicago.edu
ABSTRACT
Conformal prediction has shown spurring performance in constructing statistically rigorous prediction sets for arbitrary black-box machine learning models, assuming the data is exchangeable. However, even small adversarial perturbations during the inference can violate the exchangeability assumption, challenge the coverage guar- antees, and result in a subsequent decline in prediction coverage. In this work, we propose the first certifiably robust learning-reasoning conformal prediction frame- work (COLEP) via probabilistic circuits, which comprises a data-driven learning component that trains statistical models learn different semantic concepts, and a reasoning component that encodes knowledge and characterizes the relationships among statistical knowledge models for logic reasoning. To achieve exact and efficient reasoning, we employ probabilistic circuits (PCs) to construct the reason- ing component. Theoretically, we provide end-to-end certification of prediction coverage for COLEP under la bounded adversarial perturbations. We also provide certified coverage considering the finite size the calibration set. Furthermore, we prove that COLEP achieves higher prediction coverage and accuracy model as long as the utilities knowledge models are non-trivial. Empirically, we show the validity and tightness of our certified coverage, demonstrating the robust conformal prediction of COLEP on various datasets.
single
INTRODUCTION
Deep neural networks (DNNs) have demonstrated impressive achievements in different domains (He jet af. 2016 Vaswani et al. 2017 Li et al.] [022b] Pan et al. 2019 Chen et al. 2018). However, as DNNs are increasingly employed in real-world applications, particularly those safety-critical ones such as autonomous driving (Xu et al. 2022a) and medical diagnosis (Kang et al. 2023a), concerns regarding their trustworthiness and reliability have emerged (Szegedy al.) 2014 Eykholt al. 2018: Cao et al.) [021]] Li et al., 2017] Wang et al. (023). To address these concerns, it is crucial to provide the worst-case certification for the model predictions (i.e., certified robustness) (Wong & Kolter 2018 Cohen et al.) 2019 Li et al.) 2023). and develop techniques that enable users to statistically evaluate the uncertainty linked to the model predictions (i.e., conformal prediction) (Lei
al.
2018 Solari & Djordjilović 2022).
In particular, considering potential adversarial manipulations during test time, where small perturba- tion could mislead the models to make incorrect predictions (Szegedy et al., 2014 Madry et al., 20188 Xiao et al. 2018 Cao et al.) 2021; Kang et al.) (222bb, different robustness certification approaches have been explored to provide the worst-case prediction guarantees for neural networks. On the other hand, conformal prediction has been studied as an effective tool for generating prediction sets that reflect the prediction uncertainty of a given black-box model, assuming that the data is exchangeable (Romano et al.) 2020 Vovk al. (005). Such prediction uncertainty has provided probabilistic guarantee in addition to the worsf-case certification. However, it is unclear how such uncertainty certification would perform in the worst-case adversarial environments.

---

Published as a conference paper at ICLR 2024
Although the worst-case certification for conformal prediction is promising, it is challenging for purely data-driven models to achieve high certified prediction coverage (i.e., worst-case coverage with bounded input perturbations). Recent studies on the Stuminn-rrasoning framework, which integrates extrinsic domain knowledge and reasoning capabilities into data-driven models, have demonstrated great success in improving the model worst-case certifications (Yang et al., [002] Zhang et al. 2023). In this paper, we aim to bridge the worst-case robustness certification and uncertainty certification, and explore whether such knowledge-enabled logical reasoning could help improve the certified prediction coverage for conformal prediction. We ask: How to efficiently integrate knowledge and reasoning capabilities into DNNs for conformal prediction? Can we prove that such knowledge and logical reasoning enabled framework would indeed uchieve higher certified prediction coverage and accuracy than that of a single DNN?
In this work, we first propose a certifiably robust leamningreaaoningg conformal prediction framework (COLEP) via probabilistic circuits (PCs). In particular, we train different data- DNNs in the "learning" component, whose logical relationships (e.g.. a stop sign should be of octagon shape) are encoded in the "reasoning" component, which is constructed with probabilistic circuits (Darwiche) 1999) 200T) for logical reasoning as shown in Fig T. Theoretically, we first derive the certified coverage for COLEP under &g bounded perturbations. We also provide certified coverage considering the finite size of the calibration set. We then prove that COLEP achieves higher certified coverage and accuracy than that of single model as long as the knowledge models have non-trivial utilities. To our best knowledge, this is the first knowledge-enabbee enabled learning framework for conformal prediction and with provably higher certified coverage in adversarial settings.
We have conducted extensive experiments on GTSRB, CIFAR-10, and AwA2 datasets to demonstrate the effectiveness and tightness of the certified coverage for COLEP. We show that the certified prediction coverage of COLEP is significantly higher compared with the SOTA baselines, and COLEP has weakened the tradcoff between prediction coverage and prediction set size. We perform a range of ablation studies to show the impacts of different types of knowledge.
Related work Conformal prediction is statistical tool to construct the prediction set with guar- anteed prediction coverage (Vovk et al.) 1999; [005 Shafer & Vovk 2008 Lei et al.] 2013 Yang & Kuchibhotia| |021 Solari & Djordjilović [2022] Jin et al.] 20023). assuming that the data is ex-
changeable. Several works have explored the scenarios where the exchangeability assumption is violated (Jin et al. 2023 Barber et al. 2022 Ghosh al. 2023 Kang al., 2023c 2024a). However,
it is unclear how to provide the worst-case certification for such prediction coverage considering adversarial setting. Recently, Gendler et al. (Gendler et al. (022) provided a certified method for conformal prediction by applying randomized smoothing to certify the non-conformity scores. How- ever, such certified coverage could be loose due to the generic nature of randomized smoothing. We propose COLEP with censing-reasoning framework to achieve much stronger certified coverage by leveraging the knowledge-enables logic reasoning capabilities. We provide a comprehensive literature review on certified robustness and logical reasoning in appendix B
2 PRELIMINARIES
Suppose that we have data samples {(X,, Yo with features X, Rd and labels Y, E ) := (I, NeJ. Assume that the data samples are drawn exchangcably from some unknown distribution Pxv. Given desired coverage - (0, 1), conformal prediction methods construct prediction set Cr.a C y for a new data sample (X.41,, Yx41) ~ Pxy with the guarantee of marginal prediction coverage: P[Y,+1 E Cn,o (Xn+1)] 2 a-a.
In this work, we focus on the split conformal prediction setting (Lei et al. 2018 Solari & Djordjilović 2022). where the data samples are randomly partitioned into two disjoint sets: a training set In and a calibration set Zem [n] JT,. In here and what follows, [n] == { ,n.. We fit a classifier
h(()) : R > Y' to the training set I, to estimate the conditional class probability (x) == P[Y = v| =] of Y given X. Using the estimated probabilities that we denote by (2), then compute a non-conformity score S+, (X,, Y.) for each sample in the calibration set Z.a to measure how much non-conformity each validation sample has with respect to its ground truth label. A commonly used non-conformity score for valid and adaptive coverage is introduced by (Romano et al., 2020) as: Sx, (z. y) = Ejey R (x)) + (z)u, where 14, is the indicator function and is uniformly sampled over the interval [0, 1). Given a desired coverage 1 - a, the prediction set of a new data point X,+1 formulated as:
Ca = (y E EY: Ss, (Xu+1,0) S Q1- (Xi, (i)
(1)
2

---

Published as a conference paper at ICLR 2024
where Q1-a( (Xi, (Ez,)) is the [L]=a)(++]]a)]] largest value of the set (X,, The prediction set Cr (X (Xn+1) includes all the labels with smaller non-conformity score than the (1 q)-quantile of scores in the calibration set. Since we assume the data samples are exchangeable, the marginal coverage of the prediction set (Xx+1) is no less than 1 a.
3 LEARNING-REASONIE
PIPELINE FOR CONFORMAL PREDICTION
To achieve high certified prediction coverage against adversarial perturbations, we introduce the certifiably robust learning-reasonigg conformal prediction framework (COLEP). For better readability. we provide structured tables for used notations through the analysis in Appendix K
3.1
OVERVIEW OF COLEP
The COLEP is comprised of a data-driven learning component and a logic-driven reasoning component. The learning component is equipped with a main model to perform the main task of classification and knowledge models, each learns different concepts from data. Following the learning component is the reasoning component, which consists of R subcom- ponents (e.g., PCs) responsible for encoding diverse domain knowledge and logical reasoning by charac- terizing the logical relationships among the learning models. The COLEP framework is depicted in Fig [
PE Map Enaekiior
Make
STOP
Bilad
lolgit
Madik
Shewlergg
learning
Honseing
Figure Overview of COLEP. Concretely, consider an input x Rd (c.g.. the stop sign image) and an untrusted main model (e.g., stop sign classification model) within the learning component that predicts the label of i along with estimates of conditional class probabilities
(2) where E > = Ne]. Note that the main model as a Ne-class classification model can be viewed as N. binary classification models, each with success probability [JE[N_] (-). In Fig we particularly illustrate COLEP using binary stop sign classifier (-) as the main model for simplicity. Each knowledge model (c.g.. octagon shape classification model (-)- learns a concept from æ (c.g.. octagon shape) and outputs its prediction denoted by g() 1) where I E [Z.] indexes particular knowledge model. There can be only two possible outcomes: whether the I-th knowledge model detects the concept gD) 1 or not g O. Consistently with the notation of the main model, we denote the conditional concept probability of the 1-th knowledge model by
(x) = Ip = =]| =z],
(x) : P( = 1 x
(3)
for 1 [4] Once the learning models output their predictions along with estimated probabilities, the reasoning component accepts these estimates as input and passes them through R distinct reasoning suhcomponents in parallel. It then combines the probabilities at the outputs of the reasoning subcomponents to calculate the corrected estimates of conditional class probabilities by COLEP, which we denote #5o (a:) for j [N.] (e.g., corrected probability of x having stop sign or not: acoLze (x) or 1-acotae (x)) and form the conformal prediction set with them.
3.2 REASONING VIA PROBABILISTIC CIRCUITS
We encode two types of knowledge in the reasoning component: (1) preventive knowledge of the form "A = 8" (e.g., "IsStopSign = IsOctagon"), and (2) permissive knowledge of the form "B = A" (e.g., "flasContentStor corresponding to the main model (e.g.. "IsStopSign"), B as one of the L knowledge models (e.g.. "IsOctagon").. and = denotes logical implication with conditional variable the left operand and a consequence variable the right. In this part, we consider one particular reasoning subcomponent (i.e., one PC) and encode preventive and permissive knowledge rules (K,) !! it. The h-th knowledge rule K₁, is assigned with weight wv. Rt.
= IsStopSign"", where A represents the main task
To enable exact and efficient reasoning, we need to seek for appropriate probabilistic models as the reasoning component. Recent work (Gürel et al. | Yang et al. (022) encode propositional logic rules with Markov Logic Networks (MLNs) (Richardson & Domingos (006). but the inference com- plexity is exponential regarding the number of knowledge models. Variational inference is efficient for reaonsing (Zhang et al.) 2023), but induces error during reasoning. Thus, we use probabilistic circuits (PCs) to achieve better trade-offs between the model expressiveness and reasoning efficiency.
3

---

Published as a conference paper at ICLR 2024
Encode preventive and permissive knowledge rules with PCs. PCs define joint distribution over a set of random variables. PCs take an assignment of the random variables as input and output the joint probability of the assignment. Specifically, the input of PCs can be represented by an No L sized vector of Bernoulli random variables (e.g.. [iSSoopSign, IsOctagon, IsRed, IsDigit)) with the corresponding vector of success probabilities (e.g., [#,, # #", 4a)) denoted as:
म == [ [ ]E(21]
(4)
Note that a concatenated vector of the estimated conditional class and concept probabilities of the main model and knowledge models, respectively (e.g., A [ #", *",#"", #", #*1 with N:- 1, T. 2). Since conformal prediction is our main focus, the conditional probabilities R in eq. 44) will be frequently referenced throughout the paper. To distinguish the index representing each class label E [No], we use jv E [N. + LJ to address entries of N₂ + L sized vectors.
The computation of PCs is based on an acyclic directed graph G. Each leaf node Ouat in G represents univariate distribution (e.g., (z)): Bernoulli distribution over Signo with success rate 4. (x)). The output of a PC is typically the root node Ovee representing the joint probability of an assignment (e.g., PilsStopSSin = 1, IyOctagon = 1/x)). The graph 9 contains internal sum nodes computing a convex combination of children nodes, and product nodes computing the product of them.
Formally, we let the leaf node O in the computational graph g be Bernoulli distribution with success probability (2). Let μ E M := {0, 1>No+² be the index variable (not an observation) of a possible assignment for No classes the interest of the main model and L concepts in the interest of L knowledge models. We also define the factor function F; {0, 1 13Ne+L + R which takes as input a possible assignment μ and outputs the factor value of the assignment:
F(R) = exp
WA TI po-
(5)
where [|p=Ka] = indicates that the assignment ie follows the given logic rule Kr, and otherwise [(unKal 0 (c.g.. in the shape PC in fig. [ ([I,,]) = = [[ = I, where K is the rule "IsStopSign = IsOctagon" with weight u²). F(u) essentially measures how well the assignment jr conforms to the specified knowledge rules. Following (Darwiche) 2002 2003). we let sum nodes compute the logical "or" operation, and product nodes compute the logical "and" operation. We associate each assignment μ M with the factor value F(μ) at the level of leaf nodes as fig. [ Given a feasible assignment of random variables, the output of PC O computes the likelihood of the assignment (e.g., P(IsStopSign = 1, IsOctogon = 1(r)). When considering the likelihood of the j-th class label, we can marginalize class labels other than j and formulate the class probability conditioned on input x as:
J #COLEP (x) EmEAe, 1,=1 My=1 Orear(1)) EpEN, M, n. exp EN T (z), pmx) F(u) EyEM O1oa(114)
(6)
ΣpEn exp
No+ T(# (z), }3:}} F(u)
where (aa = log(ab+ (1 a)(1-b))
( bb) for simplicity of notations and μj denotes the j-th element of vector μ. Note that the numerator and denominator of eq. (6) can be exactly and efficiently computed
with single forwarding pass of PCs (Hitzler & Sarker 2022 Choi & Darwiche 2017; Rooshenas
& Lowd. 2014). We can also improve the expressiveness of the reasoning component by linearly combining outputs of R. PCs +f")) with coefficients B, for the r-th PC as #5OLEP (x) = Eretry 8. (x) The core of this formulation is the mixture model involving a latent variable rre representing the PCs. In short, we can write *goLE (x)) as the marginalized probability over the latent variable rpc as
#3 acoteP (x: -re(m Pfrec = r] - (z). Hence, the coefficient S. for the r-th PC are determined by Plrre = 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.
Illustrative example. We open up the stop sign classification example in fig. further as follows. The main model predicts that the image x has a stop sign with probability i. (z)). In parallel to it, the knowledge model that detects octagon shape predicts that the image has an object with octagon shape with probability (ar). Then we can encode the logic rule "IsStopSign = IsOctagon" " with weight w as fig. [ 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 speed limit sign misleads the main classifier
4

---

Theorem 1 (Bounds for Conditional Class Probabilities #5OLEP (I) within the Reasoning Component). Given any input x and perturbation bound 5, we let (Fyy (a),, (a)) be bounds for the estimated conditional class and concept probabilities by all models with iv E [Ne + L] (for example, achieved via randomized smoothing). Let v be the set of index of conditional variables in the PC except for estimate of Published as a conference paper at ICLR 2024
to detect it as stop sign with large probability (e.g., n. 0.9), but the octagon classifier is not misled and correctly predicts that the speed limit sign has a square shape (c.g., R. = 0.0). Then according the computation as eq. 1 the corrected probability of detecting stop sign given the attacked speed limit image is f* 4COLEP 0.9/(0.1e" + 0.9), which is dewn-weighted from the original wrong prediction c. 0.9 as we have positive logical rule weight 0. Therefore, the reasoning component can correct the wrong output probabilities with the knowledge rules and lead to a more robust prediction framework.
3.3 CONFORMAL. PREDICTION WITH COLEP
After obtaining the corrected conditional class probabilities using COLEP in eq. (6) we move on to conformal prediction with COLEP. To begin with, we construct prediction sets for each class label within the learning component. Using eq. ( the prediction set for the j-th class, where j E [Na].
can be formulated as:
Gnaag (Xa+1)= (a2 E (0,1): Seguer (X++1. S Q1-a, (1S (x==))))))))) (7)
where 1 - aj is the user-defined coverage level, similar to in the standard conformal prediction. The fact that element is present in Chayy (Xn+1) signifies that the class label j is possible ground truth label for Xa+1 and can be included in the final prediction set. That is:
CRoLER (Xx+1)= (i E [Ne] : E CROLEP (Xn+1))
(8)
where a = maxze(Na](as). It is worth noting that if az is set to a fixed value for all j E [Nel a in the standard conformal prediction setting is recovered. In this work, adopt fixed for each ay for simplicity, but note that our framework allows sctting different miscoverage levels for each class j. which is advantageous in addressing imbalanced classes. We defer more discussions on the flexibility of defining class-wise coverage levels to Appendix D.
CERTIFIABLY ROBUST LEARNING- REASONIIG CONFORMAL PREDICTION
In this section, we provide robustness certification of COLEP for conformal prediction. We start by providing the certification of the reasoning component in Section 4.1 and then move to end-to-end certified coverage as well as finite-sample certified coverage in Section 4.2 We defer all the proofs to
Appendix. The overview of the certification framework is provided in fig. in Appendix E
4.1 CERTIFICATION FRAMEWORK AND CERTIFICATION OF THE REASONING COMPONENT
The inference time adversaries violate the data exchangeability assumption, compromising the guaranteed coverage. With COLEP, we aim to investigate (1) whether the guaranteed coverage can be preserved for COLEP using a prediction that takes the perturbation bound into account, and (2) whether we can provide a worst-case coverage (a lower bound) using the standard prediction set as before in eq. We provide certification for goal (1) and (2) in Thms. 2 and respectively.
The certification procedure can be decomposed into several subsequent stages. First, we certify learning robustness by deriving the bounds for within the learning component given the input perturbation bound 8. There are several existing approaches to certify the robustness of models within this component (Cohen et al. 2019 Zhang et al. 2018 Gowal et al. 2018). In this work, we use randomized smoothing (Cohen et al., 2019) (details in Appendix C.3 and get the bound of R under the perturbation. Next, we certify reasoning robustness by deriving the reasoning-correeted
bounds using the bounds of the learning component (Thm. I]. Finally, we certify the robustness of
conformal prediction considering the reasoning-core corrected bounds (Thm. 2 and Thm. B
As robustness of the learning component is performed using randomized smoothing, we directly focus on the robustness certification of reasoning component.
j E [N.] and Vi be that of consequence variables. Then the bound for the conditional class probability #5 goose is given by:
5

---

Published as a conference paper at ICLR 2024
(z)) exx 1==0
Σ (x) Σ T( (2))
F(u)
SvEV
jvEV?
U|ay coMe
(r)]
+1
(9)
(x) Σ exp 11=
ET (3v) + (Tt (s))
F(1)
jvEVa
where (aa, log(ab++ (1-a) b)). We similarly give the lower bound [ in Appendix F.
Remarks. Thm. T esstablishss a certification connection from the probability bound of the learning component to that of the reasoning component. Applying robustness certification methods to DNNs, we can get the probability bound of the learning component [it Å) within bounded input perturba- tions. Thm. [ shows that we can compute the probability bound after the reasoning component [L[#GOLEP]] L y COLEP] following eq. 99. Since Equation (9) presents an analytical formulation of the bound after the reasoning component as a function of the bounds before the reasoning component, we can directly and efficiently compute [[[[goue)]] [[a5oLee]] in evaluations.
4.2 CERTIFIABLY ROBUST CONFORMAL PREDICTION
In this section, we leverage the reasoning component bounds in Thm. too perform calibration with worst-case non-conformity score function for adversarial perturbations. This way, we perform certifiably robust conformal prediction in the adversary setting during the inference time. We formulate the procedure achieve this in Thm. 2]
Theorem 2 (Certifiably Robust Conformal Prediction of COLEP). Consider new test sample X drawn from Pxy. For any bounded perturbation ||||| S in the input space and the adversarial sample Xa41 == X + 6, we have the following guaranteed marginal coverage:
P\Yn+1 CCOLEPs (Xn+1) 2 1-a
(10)
if we construct the certified prediction set of COLEP where
((osse(Xn+t)) = {3= [No] Sugnee (x=-1. S Q Qi-a((1, ( swars (Xi, "I, [Iy; (Ezm
(11)
and S quarg (1.)) is a function of worst-case non-conformity score considering perturbation radius 6: o
8 cour, (X (pr [[a[=] (X:)] + u(1 - U,( (X+))),
Y: *
(12)
1 La [Tr coMeP (X:)] + uLD (+t COLRe (X.)).
Y, =
with Us(1 Us(#gorse (x) ma #f0100(x (xr + 7)) and Ls [+) coMes (x) = min 4foM
(a + n).
Remarks. Thm. shows that the coverage guarantee of COLEP in the adversary setting is still valid
(eq. (TO)) if we construct the prediction by considering the worst-case perturbation in eq. (II).
That is, the prediction set of COLEP in eq. (11) covers the ground truth of an adversarial sample with
nominal level a. To achieve that, we use worst-case conformotri score as in eq. [12) during
calibration to counter the influence of adversarial sample during inference. The bound of output probability (U, (*LC)))) Th.s [+ COLEP) in eq. 12) can be computed by Thm. achieve end-to-end robustness certification of COLEP, which generally holds for any DNN and probabilistic circuits. We also consider the finite-sample errors of using randomized smoothing for the learning component certification as Anonymous (2023) and provided the theoretical statement and proofs in thm. i
Appendix F3
Theorem 3 (Certified (Worst-Case) Coverage of COLEP), Consider the new sample Xn+1 drawn from Pxy and adversarial sample X,+1 == Xn+1 + e with any perturbation ||c]|2 S in the inpur space. We have:
P(Yn+1 CCoLaR (oxess(xx))))==)))) 2 COLSERr
min jE[Nel
{
COLSE.r)
(13)
where the certified (worst-case) coverage of the j-th class label T3 c0138. is formulated as: Qr((S corss, (X,, "x,,TTy::)) S QI-a (X,, Tlm=)))ee...)))
coLsP..r
max
(14)
coverage as eq. by considering the worst-case perturbation during calibration to counter the influence test-time adversaries. In contrast, Thm. targets the case when we still adopt standard calibration process without the consideration of test-time perturbations, which would lead to lower coverage than 1 11-1- a and Thm. B concretely shows the formulation of the worst-case coverage. Thm.33 presents the formulations of the lower bound of the coverage (7 (7 c01.8xx with the standard prediction set as eq. (8) in the adversary
Remarks. Thm. constructs certified prediction set with
setting. In addition the certified coverage, we consider finite calibration set size and certified coverage with finite sample errors in Appendix G

---

Published as a conference paper at ICLR 2024
5 THEORETICAL ANALYSIS OF COLEP
In Section 5.3 we theoretically show that COLEP achieves better coverage and prediction accuracy than a single main model long as the utility of knowledge models and rules (characterized in Section 5. is non-trivial. To achieve it, we provide a connection between those utilities and the effectiveness of PCs in Section 5.2] The certification overview provided in fig. in Appendix E
5.1 CHARACTERIZATION OF MODELS AND KNOWLEDGE RULES
We consider a mixture of benign distribution Dj and adversarial distribution D. denoted by Dm := pD, D. + PD. Da with po, + PD, an undirected graph G. = (V., Er). where V, = [Ne L] corresponds to Ne (binary) class labels and (binary) concept labels. There exists an edge between node ji E V, and node ja E V. iff they are connected by an implication rule ji = j2 or fa + j1.
We map a set of implication rules encoded in the r-th PC to
Let Ar (jv) be the set of nodes in the connected component of node jv in graph G,- Let Ar.(fv) C A-(iv) be the set of conditional variables and Ar. S Arv) be the set of consequence variables. For any sample x, let p(x) E [0, 1JNo+t be the Boolean vector of ground truth class and concepts such that v(x)= := [|4 Ne)) 14, [[] We denote v(x)) as when sample is clear in the context. For simplicity, we assume a fixed weight w E R for all knowledge rules in the analysis. In what follows, we characterize the prediction capability of each model (main or knowledge) and establish a relation between these characteristics and the prediction performance of COLEP.
For each class and concept probability estimated by learning models [ : R2 1 [0, 1] (recall eq. (4), we have the following definition:
Po (z) S 1 - f.y.D lps. 0] 2 2jv.D, PD (+t) 2 f.. |ny 1] Ejv.D
(15)
where Ly, Rjv.D are parameters quantifying quality of the main model and knowledge models in predicting correct class and concept, respectively. In particular, fy.D characterizes the threshold of confidence whereas 2 quantifies the probability matching this threshold over data distribution D. Specifically, models with a large Dj,.D, Zj..D imply that the model outputs a small class probability when the ground truth of input is and a large class probability when the ground truth of input is 1, indicating the model performs well on prediction. We define the combined utility of models within r-th PC by using individual model qualities. For j-th class, we have:
T = Al
2 = 3))
(16)
and the utility of associated knowledge rules within r-th PC for the j-th class as:
[P [esv 0, Jiv E (r. [ = 0], r Pa(j)
(17)
[ [psv 1, 3jv E (j) [D5 = 1], P.()
where Pa(i) and P.()) are PC index sets where j appears as conditional and consequence variables. 73") quantifies the utility of knowledge rules for class j. Consider the case where j corresponds to
conditional variable in the r-th PC. Small U767) indicates that P [pyy = 1, E Ar) IV, 0] is
high, hence implication rules for jv are universal and of low utility.
5.2 EFFECTIVENESS OF THE REASONING COMPONENT WITH PCs
Here we theoretically build the connection between the utility of knowledge models T ( 2/2 and the utility of implication rules (-(t)) with the effectiveness of reasoning components. We quantify the effectiveness of the reasoning component the relative confidence in ground truth class probabilities. Specifically, we expect E [ (X) न, (X) |Y = j] to be large for j E [Ne] as it enables COLEP to correct the prediction of the main model, especially in the adversary setting. Lemma 5.1 (Efffectiveness of the Reasoning Component). For any class probability within models j E [Nc] and data sample (X, (X,Y) drawn from the mixture distribution Din, we can prove that:
E
COLE? (X) + 5 (X) 5,00 IY # ú]
COLSP (x)
= 5]
E Bt (X)
5]
(18)
5,00 Σ pD DE(D,, Db)
BB (r))
4
Σ B,
# Rg + (1 - n, 1,
n, + (1 - 1/1
(EPA())
TEP,()
G = Σ PD De(
Σ Br (EPa())
3
+
B. 2(1)
f, + (1 - R $,)2,77 -3
Rty + (1 - /
3D
PEP
(19)
where 11r)
(1/T/:) - w 1) and we shorthand At (X) as ft..
7

---

Published as a conference paper at ICLR 2024
Remarks. Lemma 5.1 analyzes the relative confidence of the ground truth class probabilities after corrections with the reasoning component. Towards that, we consider different cases based on the utility of the models and knowledge rules described earlier and combine conditional upper bounds with probabilities. We can quantify the effectiveness of the reasoning component with 6,,0; F,11 since non-trivial cj,0, f,.1 can correct the confidence of ground truth class in the expected direction and benefit conformal prediction by inducing a smaller non-conformity score for an adversarial sample.
5.3 COMPARISON BETWEEN COLEP AND SINGLE MAIN MODEL
Here we reveal the superiority of COLEP over a single main model in terms of the certified prediction coverage and prediction accuracy. Let 6 = F) (6,,0 = OJ and 6j,IID =
= II. In Section 5.2 we show that the utility of models and knowledge rules is crucial in forming an understanding of COLEPand 6,,0 > C, > 0 holds. In similar spirit, 5,,0D > 0 and E,,,D > 0 for j E [No] and DE E (D., D in the subsequent analysis.
Theorem 4 (Comparison of Marginal Coverage of COLEP and Main Model), Consider the adversary setting that the calibration set Iua consists of RDD samples drawn from the benign distribution Du. while the new sample (X,-1, Yn41) is drawn n.D, times from the adversarial distribution Da. Assume that A(ā3, Da) < 0.5 < A(+,, Da) for E [No]. where A(²5, D) is the expectation of prediction
accuracy of n on D. Then we have:
P[Yn-1 E Onpae (Xn+1)) > P[ E Cn, (Xn+t))) w.p.
1- max (exp { 2n (0.5 - A(t,, D.)) & D. JE[Nc]
+ Hno. 2nd, ((A(ft) Da) - 0.5) > Epsee
")}
eE(0.1)
where pyo = Pr, [p] and 1f1 PD,, [T, [1]] are class probabilities on benign distribution.
(20)
Remarks. Thm. Thm.Asshos shows that COLEP can achieve better marginal coverage than a single model with a high probability exponentially approaching 1. The probability increases in particular with higher quality of models represented by E,.1.D., Ej,,,D, A(f,, Dz). E,,.D., quantifies the effectiveness of the correction of the reasoning component and is positively correlated with the utility of models T((r)
j.D: Z/ and the utility of knowledge rules (7(r)) as shown in Lemma 5.1 indicating that better knowledge models and rules benefits a higher prediction coverage with COLEP. The probability also increases with lower accuracy on the adversarial distribution A(t,, P.),, indicating COLEP improves marginal coverage more likely in a stronger adversary setting.
Theorem 5 (Comparison of Prediction Accuracy of COLEP and Main Model). Suppose that we evaluate the expected prediction accuracy of #50hx0 (-) and ft).)) on n samples drawn from D' and denote the prediction accuracy A(#50LáP()). (m)) and A(*x(-); Dm)) Then we huve:
A(#
()) 2 A(xx(), D..), w.p. Σ PD
Σ Poly s]exp ( 22((es,,,))) (21)
De( cE(U.1)
Remarks. Thm. 5 shows that COLEP achieves better prediction accuracy than the main model with a high probability exponentially approaching 1. The probability increases with more effectiveness of the reasoning component quantified by a large Ej.,,D, which positively correlates to the utility of models T 2/15) and the utility of knowledge rules (r()) as shown in Lemma 5.1 indicating that better knowledge models and rules benefits a higher prediction accuracy with COLEF. Appendix [] we further show that COLEP achieves higher prediction accuracy with more useful knowledge rules.
6 EXPERIMENTS
We evaluate COLEP on certified conformal prediction in the adversarial setting on various datasets, including GTSRB (Stalkkapp et al. 2012), CIFAR-10, and AwA2 (Xian et al. 2018). For fair comparisons, we the same model architecture and parameters in COLEP and baselines CP (Romano et al., 2020) and RSCP (Gendler et al.] 2022). The desired coverage is set 0.9 across evaluations. Note that we leverage randomized smoothing for learning component certification (100k Monte-Carlo sampling) and consider the finite-sample errors of RSCP following Anonyyous (023)
and that of COLEP following Thm. 6 We fix weights w as 1.5 and provide more details in Appendix]
Construction of the reasoning component. 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 encode
knowledge (e.g., "digit 50", "tur left"). Specifically, in the PC of shape knowledge, the implication rules such as IsStopSign = IsOctagon (stop signs are octagon), IsSpeedLimit = IsSquare (speed limit signs square). In summary, we have PCs and 28 knowledge rules in
8

---

Published as a conference paper at ICLR 2024
Certified Coverage
A:5
3 RSSP COLPP Upper and Fyme
0.55
81 RSSC CCOEE - Upper Brd. foor)
0.55
RSCC m COLEP Upper Brd, feer
0:85
0.85
0.85
0.8
088
0.8
0.75
0.75
D.5
0:65
0:55
8-12
5 0.25
0.50
6- 0.125
6- 0.25
0.50
0.25
(a) GTSRB
(b) CIFAR-10
(c) AwA2
Figure 2: Comparison of certified coverage between COLEP (r Cr and RSCP under bounded perturbations
8
0.125, 0.25, 0.50 on GTSRB, CIFAR- 10, and AwA2. The upper bound of certified coverage T(ces) is 0.9.
Marginal Coverage
Everagedaan See
Marginal Coverage
Averaged See
Marginal Coverage
Averaged Sot
2.5
0.55
0.90
0.90
88
1.5
0.85
09
0.86
0.86
0.91
0.5
0.75
CP RSCP COLEP
RSCP COLEP
RSCP COLEP
CP RECP COLEP
RSEP COLEP
CP RSCP COLEP
(a) GTSRB
(b) CIFAR-I0
(c) AwA2
Figure 3: Comparison the marginal coverage and averaged set size for CP, RSCP, and COLEP under PGD
attack (6 = 0.25) on GTSRB, CIFAR-IO, and AwA2. The nominal coverage level (green line) is 0.9.
GTSRB, 3 PCs and 30 knowledge rules in CIFAR- 10, and 4 PCs and 187 knowledge rules in AwA2. We also provide detailed steps of PC construction in appendix
Certified Coverage under Bounded Perturbations. We evaluate the certified coverage of COLEP certification in Thm. 3 Certified coverage indicates the worst-case coverage during inference in the adversary setting, hence higher certified coverage indicates more robust conformal prediction and tigher certification. We compare the certified coverage of COLEP with the SOTA baseline RSCP (Theorem 2 in (Gendler al. 2022)). ) The comparison of certified coverage between CCLEP and RSCP is provided in Figure The results indicate that COLEP consistently achieves higher certified coverage under differrntt & norm bounded perturbations, and COLEP outperforms RSCP by a large margin under a large perturbation radius 5 = 0.5. Note that an obvious upper bound of the certified coverage in the adversary setting is the guaranteed coverage without an adversary, which is 0.9 in the evaluation. The closeness between the certified coverage of COLEP T(eet) and the upper bound of coverage guarantee Ticerj shows the robustness of COLEP and tightness of our certification.
given new test sample X,+1 with bounded perturbation (ldl 5) based
Prediction Coverage and Prediction Set Size under Adversarial Attacks. We also evaluate the marginal coverage and averaged set size of COLEP and baselines under adversarial attacks. COLEP constructs the certifiably robust prediction set following Thm. 2 We compare the results with the standard conformal prediction (CP) and the SOTA conformal prediction with randomized smoothing (RSCP). For fair comparisons, we apply PGD attack (Madry et al. 2018) with the same parameters on CP, RSCP, and COLEP. For COLEP, we consider the adaptive PGD attack against the complete learning-reasonic size for CP, RSCP, and COLEP under PGD attack (6 = 0.25) provided in Figure The results indicate that the marginal coverage of CP is below the nominal coverage level 0.99 under PGD attacks as data exchangeability is violated, while COLEP still achieves higher marginal coverage than the nominal level, validating the robustness of COLEP for conformal prediction in the adversary setting. Compared with RSCP, COLEP achieves both larger marginal coverage and smaller set size, demonstrating that COLEP maintains the guaranteed coverage with less inflation of the prediction set. The observation validates our theoretical analysis in Thm. that COLEP can achieve better coverage than a single model with the power of kwowledge-enabled logical reasoning. We provide more evaluations of different coverage levels - different perturbation bound 8, different conformal prediction baselines, and contributions of different knowledge rules in Appendix [.2
pipeline. The comparison of the marginal coverage and averaged set
Conclusion In this paper, we present COLEP, a certifiably robust conformal prediction framework via knowledge-enablle logical reasoning. We leverage PCs for efficient reasoning and provide robustness certification. We also provide end-to-end certification for snite-sample certified coverage in the presence of adversaries and theoretically prove the advantage of COLEP over a single model. We included the discussions of limitations, broader impact, and future work in Appendix A

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work partially supported by the National Science Foundation under grant No. 1910100, No. 2046726, No. 2229876, DARPA GARD, the National Aeronautics and Space Administration (NASA) under grant No. 80NSSC20M0229, the Alfred Sloan Fellowship, the Amazon research award, and the eBay research award.
ETIICS STATEMENT
We do not see potential ethical issues about COLEP. In contrast, with the power of logical reasoning, COLEP is a certifiably robust conformal prediction framework against adversaries during the inference time.
REPRODUCIBILITY STATEMENT
The reproducibility of COLEP span theoretical and experimental perspectives. We provide complete proof' of all the theoretical results in appendices. We provide the source codes for implementing COLEP at athttps: /ettpp:///ithuiie wtw.. wttp://...o/eeemmmtnnnnnooo/o...
REFERENCES
Milton Abramowitz and Irene A Stegun. Handbook of mathematical functions with formulas, graphs, and mathematical tables, volume 55. US Government printing office, 1948.
funciontiicaalnntionn
Kareem Ahmed, Stefano Teso, Kai-Wei Chang, Guy Van den Broeck, and Antonio Vergari. Semantic probabilistic layers for neuro-symbolic learning, Advances in Neural Information Processing Systems, 35:29944-2999 29959, 2022.
Anonymous. Provably robust conformal prediction with improved efficiency. In Submitted to The Twelfth International Conference on Learning Representations, 2023. URL https:77
openreview wttpleew.eeeeeeeeeeee wor jx jeG under review.
Mislav Balunovic, Maximilian Baader, Gagandeep Singh, Timon Gehr, and Martin Vechev. Certifying geometric robustness of neural networks. In Advances in Neural Information Processing Systems, pp. 15287-15297, 2019.
Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan J Tibshirani. Conformal prediction beyond exchangeability. arXiv preprint arXiv:2202.1 13415, 2022.
Frank Markham Brown. Boolean reasoning: the logic of Boolean equations. Courier Corporation, 2003.
Daniel D Caminhas. Detecting and correcting typing errors in open-domain knowledge graphs using semantic representation of entities. 2019.
Yulong Cao, Ningfei Wang, Chaowei Xiao, Dawei Yang, Jin Fang, Ruigang Yang, Qi Alfred Chen, Mingyan Liu, and Bo Li. Invisible for both camera and lidar: Security of multi-sensor fusion based perception autonomous driving under physical-wotd attacks. 2021 IEEE Symposium Security and Privacy (SP), pp. 176-194. IEEE, 2021.
Jiaoyan Chen, Xi Chen, Ian Horrocks, Erik B. Myklebust, and Ernesto Jimenez-Riin Correcting knowledge base assertions. In Proceedings of the Web Conference 2020, pp. 1537-1547, 2020a.
Qingrong Chen, Chong Xiang, Minhui Xue, Bo Li. Nikita Borisov, Dali Kaarfar, and Haojin Zhu. Differentially private data generative models. arXiv preprint 1812v:1812.022777 2018.
Xiaojun Chen, Shengbin Jia, and Yang Xiang. review: Knowledge reasoning over knowledge graph. Expert Systems with Applications, 141:1 141:112949 12948, 2020b.
Arthur Choi and Adnan Darwiche. On relaxing determinism arithmetic circuits, In International Conference Machine Learning, pp. 825-833. PMLR, 2017.
10

---

Published as a conference paper at ICLR 2024
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In international conference on machine learning. pp. 1310-1320. PMLR, 2019. Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In International conference machine learning, pp. 2206-2216. PMLR, 2020.
Adnan Darwiche. Compiling knowledge into decomposable negation normal form. IJCAI, volume 99, pp. 284-289. Citeseer, 1999.
Adnan Darwiche. Decomposable negation normal form. Journal of the ACM 48(4))008 647,
2001.
Adnan Darwiche. logical approach to factoring belief networks. KR, 2:409-420, 2002.
Adnan Darwiche. A differential approach inference in bayesian networks. Journal of the ACM (JACM), 50(3)2280-305, 2003.
Kevin Eykholt, Ivan Evtimov, Earlence Fernandes, Bo Li, Amir Rahmati, Chaowei Xiao, Atul Prakash, Tadayoshi Kohno, and Dawn Song. Robust physical physical-world attacks on deep learning visual classification. In Proceedings of the IEEÉ conference on computer vision and pattern recognition, pp. 1625-1634, 2018.
Artur d' Avila Garcez, Sebastian Bader, Howard Bowman, Luis C Lamb, Leo de Penning, BV Illumi- noo, Hoifung Poon, and COPPE Gerson Zaverucha. Neural-symbolic learning and reasoning: A survey and interpretation. Neuro-Symbolic Artificial Intelligence: The State of the Art, 342(1):327, 2022.
Asaf Gendler, Tsui-Was Weng, Luca Danicl, and Yaniv Romano. Adversarially robust conformal prediction. In International Conference Learning Representations, 2022. URL https
//openreview fott:// 4wPHH
Subhankar Ghosh, Yuanjie Shi, Taha Belkhouja, Yan Yan, Jana Doppa, and Brian Jones. Probabilisti- cally robust conformal prediction. In Uncertainty in Artificial Intelligence, pp. 681-690. PMLR. 2023.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6577 2014.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint
2018.
Nezihe Merve Gürel, Xiangyu Qi, Luka Rimanic, Ce Zhang, and Bo Li. Knowledge-enbanced machine learning pipeline against diverse adversarial attacks. In International Conference on Machine Learning, 2021.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
P Hitzler and MK Sarker. Tractable boolean and arithmetic circuits. Neuro-Symbolic Artificial Intelligence: The State of the Art, 342:146, 2022.
Ying Jin, Zhimei Ren, and Emmanuel J Candès. Sensitivity analysis of individual treatment effects: A robust conformal inference approach. Proceedings of the National Academy of Sciences, 120(6): e2214889120. 2023.
Mintong Kang, Linyi Li, Maurice Weber, Yang Liu, Ce Zhang, and Bo Li. Certifying some distribu- tional fairness with subpopulation decomposition. Advances in Neural Information Processing Systems, 35:31045-3100 31058, 2022.
Mintong Kang, Bowen Li, Zengle Zhu, Yongyi Lu, Elliot K Fishman, Alan Yuille, and Zongwei Zhou. assemble Leveraging multiple datasets with partial labels. 2023 IEEE 20th International Symposium Biomedical Imaging (ISBI), pp. 1-5. IEEE, 2023a.
11

---

Published as a conference paper at ICLR 2024
Mintong Kang, Linyi Li, and Bo Li. Fashapley: Fast and approximated shapley based model pruning towards certifiably robust dnns. In 2023 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pp. 575-592. IEEE, 2023b.
Mintong Kang, Zhen Lin, Jimeng Sun, Cao Xiao, and Bo Li. Certifiably byzantine-robust federated conformal prediction. 2023c.
Mintong Kang, Nezihe Merve Gürel, Ning Yu, Dawn Song, and Bo Li. C-rag: Certified generation risks for retrieval- -aggeeted language models. arXiv preprint arXiv:2402.03/81, 2024a.
Mintong Kang, Dawn Song, and Li, Diffattack: Evasion attacks against diffusion- basssdd adversarial purification. Advances in Neural Information Processing Systems, 36, 2024b.
Doga Kisa, Guy Van den Broeck, Arthur Choi, and Adnan Darwiche. Probabilistic sentential decision diagrams. In Proceedings of the 14th international conference on principles of knowledge representation and reasoning (KR), pp. 1-10, 2014.
Aounon Kumar, Alexander Levine, and Soheil Feizi. Policy smoothing for provably robust reinforce- ment learning. In International Conference on Learning Representations, 2022.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 JEEE Symposium on Security and Privacy (SP), pp. 656-672. IEEE, 2019.
Jing Lei, James Robins, and Larry Wasserman. Distribution-free prediction sets. Journal of the American Statistical Association, 108(501):278-22 287, 2013.
Jing Lei, Max G'Sell, Alessandro Rinaldo, Ryan Tibshirani, and Larry Wasserman. Distribution-free predictive inference for regression. Journal of the American Statistical Association, 113(523): 1094-1111, 2018.
Bo Li, Kevin Roundy, Chris Gates, and Yevgeniy Vorobeychik. Large-scale identification of malicious singleton files. Proceedings of the seventh ACM on conference on data and application security and privacy, pp. 227-238, 2017.
Linyi Li, Zexuan Zhong, Bo Li, and Tao Xie. Robustra: Training provable robust neural networks over reference adversarial space. In IJCAI, pp. 4711-4717, 2019.
Linyi Li, Maurice Weber, Xiaojun Xu, Luka Rimanic, Bhavya Kailkhura, Tao Xie, Ce Zhang, and Bo Li. TSS: Transformatioon-seecffe smoothing for robustness certification. In Proceedings the 2021 ACM SIGSAC Conference on Computer and Communications Security, pp. 535-557, 2021. ISBN 97844503845
Linyi Li, Jiawei Zhang, Tao Xie, and Bo Li. Double sampling randomized smoothing. In International Conference on Machine Learning, 2022a.
Linyi Li, Tao Xie, and Bo Li. Sok: Certified robustness for deep neural networks. In 44th IEEE Symposium on Security and Privacy, SP 2023, San Francisco, CA, USA, 22-26 May 2023. IEEE, 2023.
Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schritwieser,, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. Competition-level code generation with alphacode. Science,
1092-1997, 2022b.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant to adversarial attacks. In International Conference on Learn- ing Representations, 2018. URL
net. wow.ee/ooorumnni.....1.f...
Robin Manhaeve, Sehastijan Dumancie, Angelika Kimmig, Thomas Demeester, and Lue De Raedt. Deepproblog: Neural probabilistic logic programming. Advances in neural information processing systems, 31, 2018.
Pascal Massart. The tight constant in the dvoretzky- kinezzky-kieferr-wlloowtt inequality. The annals of Probability, pp. 1269-1283, 1990.
12

---

Published as a conference paper at ICLR 2024
André Melo and Heiko Paulheim. An approach to correction of erroneous links in knowledge graphs. In CEUR Workshop Proceedings, volume 2065, pp. 54-57. RWTH Aachen, 2017.
Xinlei Pan, Chaowei Xiao, Warren He, Shuang Yang, Jian Peng, Mingjie Sun, Jinfeng Yi, Zijiang Yang. Mingyan Liu, Bo Li, et al. Characterizing attacks on deep reinforcement learning, AISTATS, 2019.
Bhaskar Ray Chaudhury, Linyi Li, Mintong Kang, Bo Li, and Ruta Mehta. Fairness in federated learning via core-stability. Advances in neural information processing systems, 35:5738-577 2022.
Matthew Richardson and Pedro Domingos. Markov logic networks. Machine learning, 62:107-136. 2006.
Yaniv Romano, Matteo Sesia, and Emmanuel Candes. Classification with valid and adaptive coverage. H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 3581-3591. Curran Asso- ciates, Inc., 2020. URL https: htt.tpppp//prooeedigg..... htw.:ediiiiinn..e.reooeoe neurips cc/ wttppppppppppppppcccccpcpppppppa file/ [Beedd/855sss1100000111111155523
pdf
Amirmohammad Rooshenas and Daniel Lowd. Learning sum-product networks with direct and indirect variable interactions. In Eric P. Xing and Tony Jebara (eds.). Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pp. 710-718, Bejing, China, 22-24 24 Jun 2014. PMLR. URL httphttss//proceeeiiii mlr www.presssvee v3/ www.sooosssss...o html
Hadi Salman, Jerry Li, Ila Razenshteyn, Pengchuan Zhang. Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In Advances in Neural Information Processing Systems, pp. 11289-1133 11300, 2019.
Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research, 9(3), 2008.
Sahil Singla, Surbhi Singla, and Soheil Feizi. Improved deterministic 12 robustness on CIFAR-10 and 100. In International Conference Learning Representations, 2022.
Aldo Solari and Vera Djordjilović. Multi split conformal prediction. Statistics & Probability Letters, 184: 109395, 2022.
Johannes Stallkamp, Mare Schlipsing, Jan Salmen, and Christian Igel. Man vs. computer: Bench- marking machine learning algorithms for traffic sign recognition. Neural nefworks, 32:323-332, 2012.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In Yoshua Bengio and Yann LeCun (eds.), 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. mipschitz-margin training: scalable certification of perturbation invariance for deep neural networks. In Advances in Neural Information Processing Systems, 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Iliia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning random world, volume 29, Springer, 2005.
Volodya Vovk, Alexander Gammerman, and Craig Saunders. Machine-learning applications of algorithmic randomness. 1999.
13

---

Published as a conference paper at ICLR 2024
Boxin Wang. Weixin Chen, Hengzhi Pei, Chulin Xie, Mintong Kang, Chenhui Zhang, Chejian Xu, Zidi Xiong, Ritik Dutta, Rylan Schaeffer, et al. Decodingtrust: A comprehensive assessment of trustworthiness in gpt models. arXiv preprint arXiv:2306. 1698, 2023.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pp. 5286-5295, 2018.
Fan Wu, Linyi Li, Zijian Huang. Yevgeniy Vorobeychik, Ding Zhao, and Bo Li. CROP: Certifying ro-
bust policies for reinforcement learning through functional smoothing. International Conference on Learning Representutions, 2022a.
Fan Wu, Linyi Li, Chejian Xu, Huan Zhang, Bhavya Kailkhura, Krishnaram Kenthapadi, Ding Zhao, and Bo Li. Copa: Certifying robust policies for offline reinforcement learning against poisoning attacks. In International Conference on Learning Representations, 2022b.
Yongqin Xian, Christoph H Lampert, Bernt Schiele, and Zeynep Akata. Zero-shot learning a comprehensive evaluation of the good, the bad and the ugly. IEEE transactions on pattern analysis and machine intelligence, (199)2251-2266 2018.
Chaowei Xiao, Jun Yan Zhu, Bo Li, Warren He, Mingyan Liu, and Dawn Song. Spatially transformed adversarial examples. In 6th International Conference on Learning Representations, ICLR 2018, 2018.
Chulin Xie, Minghao Chen, Pin-Yu Chen, and Bo Li. Crfl: Certifiably robust federated learning against backdoor attacks. In International Conference on Machine Learning, pp. 11372-11382. PMLR, 2021.
Chulin Xie, Yunhui Long, Pin-Yo Chen, and Bo Li. Uncovering the connection between differential privacy and certified robustness of federated learning against poisoning attacks. arXiv preprint arXiv:2209.04030) 2022.
Chejian Xu, Wenhao Ding, Weijie Lyu, Zuxin Liu, Shuai Wang, Yihan He, Hanjiang Hu, Ding Zhao, and Bo Li. Safebench: benchmarking platform for safety evaluation of autonomous vehicles. Advances in Neural Information Processing Systems, 1-255677-25682 2022a.
Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Broeck. semantic loss function for deep learning with symbolic knowledge. In International conference on machine learning, pp. 5502-5511. PMLR, 2018.
Xiaojun Xu, Linyi Li, and Bo Li. Lot: Layer-wise orthogonal training on improving 12 certified robustness. In Advances in Neural Information Processing Systems, 2022b.
Yachong Yang and Arun Kumar Kuchibhotla. Finite-sample efficient conformal prediction. arXiv
preprint arxiv: 104. 13871, 2021.
Zhuolin Yang, Zhikuan Zhao, Boxin Wang, Jiawei Zhang. Linyi Li, Hengzhi Pei, Bojan Karlaš, Ji Liu, Heng Guo, Ce Zhang, and Bo Li. Improving certified robustness via statistical learning with logical reasoning. In Advances in Neural Information Processing Systems 35 (NeurIPS 2022), 2022.
Kexin Yi, Jiajun Wu, Chuang Gan, Antonio Torralba, Pushmeet Kohli, and Josh Tenenbaum. Neural- symbolic vqa: Disentangling reasoning from vision and language understanding. Advances in neural information processing systems, 31, 2018
Huan Zhang, Tsui-Wei Weng, Pin- Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. In Advances in neural information processing systems, pp. 4939-4948, 2018.
Jiawei Zhang, Linyi Li, Ce Zhang, and Bo Li. CARE: Certifiably robust learning with reasoning via variational inference. In First IEEE Conference on Secure and Trustworthy Machine Learning, 2023. httlltttp/pppennteee att
14

---

Published as a conference paper at ICLR 2024
Appendix
Contents
A Discussions, Broader Impact, Limitations, and Future Work
16
More related work
17
Preliminaries
18
Probabilistic Circuits
18
Multiple PCs with coefficients 3, in the combination of PCs
18
C.3
Randomized Smoothing
19
Conformal Prediction with COLEP
D.I Flexibility of user-defined coverage level
19
D.2 Illustrative example
20
Overview of Certification
20
Omitted Proofs in Section
20
Proof of Thm.
20
Proof of Thm.
23
F3
Thm. with sample errors by randomized smoothing
24
R4 Proof of Thm.
26
Finite-Sample Certified Coverage
27
H
Omitted Proofs in Section
28
Proof of Lemmal
28
Proof of Thm.4
32
Proof of Thm.
34
Lower Bound of A 2 COLES D
34
J
Experiment
37
Implementation Details
37
2
Additional evaluation of COLEP
38
Overview of notations
40
15

---

Published as a conference paper at ICLR 2024
A DISCUSSIONS, BROADER IMPACT, LIMITATIONS, AND FUTURE WORK
Broader Impact. In this paper, we propose certifiably robust conformal prediction framework COLEP via knowledge-enabled logic reasoning. We prove that for any adversarial test sample with 22-norm bounded perturbations, the prediction set of COLEP captures the ground truth label with a guaranteed coverage level. Considering distribution shifts during inference time and weakening the assumption of data exchangeability has been an active area of conformal prediction. COLEP demonstrates both theoretical and empirical improvements in the adversarial setting and can inspire future work to explore various types of distribution shifts with the power of logical reasoning and the certification framework of COLEP. Furthermore, robustness certification for conformal prediction can be viewed the generalization of certified prediction robustness, which justifies certifiably robust prediction rather than a prediction set. Considering the challenges of providing tight bounds for certified prediction robustness, we expect that COLEP motivate the certification of prediction robustness to benefit from a statistical perspective.
Limitations. A possible limitation may lie in the computational costs induced by pretraining knowledge models. 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 knolwedge. The training cost is worthy 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 (Chen et al., 2020b) 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 that application. There is probably no universal strategy on how to aggregate knowledge for any arbitrary application, and rather application-specifs constructions are needed. This is where the power as well as limitation of our framework comes from.
Future work. The following directions are potentially interesting future work based on the framework of COLEP: 1) exploring different structures of knowledge representations and their effectiveness on conformal prediction performance, 2) proposing more systematic way of designing logic rules based on domain knowledge, and 3) initiating better understanding of the importance of different types of knowledge rules and motivating better design of rule weights accordingly.
Discussions. We will consider the cases where the knowledge graph is contaminated by adversarial attackers or contains noises and misinformation in this part. The robustness of COLEP mainly originates from the knowledge rules via factor function F(.)) 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 I can be viewed as complete model. According to the adversarial attack settings in the literature Goodfellow et al. (2014); Gendler et al. (2022), the model weights can be well protected in practical cases and the attackers can only manipulate the inputs but not the model, and thus, the PC graph (i.e., the source of side information) which is a part of the augmented model can not be manipulated by adversarial attacks. On the other hand, it is an interesting question to discuss the case when the knowledge rules may be contaminated and contain misinformation due 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 well-explored by a line of research Melo & Paulheim (2017): Caminhas (2019); Chen et al. (2020a), which basically detects and corrects false logical relations in the semantic embedding space via consistency- techniques. It is also interesting to leverage more advanced large language models to check and correct human-des ouman-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.
Alternative certification. There are two general certification directions for certifiably robust confor- mal prediction: (1) plugging in the standard score for for test example, and the quantile is computed
16

---

Published as a conference paper at ICLR 2024
on the worst-case scores for each calibration point as in our paper; (2) plugging in the worst-case score for the test example and the standard score for each calibration point. We can also adapt the results with the second line based the symmetry between x and z' is indeed interesting point. Specifically, given perturbed x' during test time, we can compute the bounds of output logits in the ō-ball, which will also cover the clean Since the logit bounds also hold for clean œ; we can compute the worst-case scores based on the bounds and finally construct the prediction set with the clean quantile value. The two lines of certification are 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.
Discussions of selection of rule weights. If a knowledge rule is true with lower probability, then the associated weight rule should be smaller, and vice versa. For example, there might be a case that a knowledge rule only holds with probability 70%. In the example, the probability is with respect to the data distribution, which means that 70% of data satisfies the rule "[sStopSign=IISocteee Besides, other factors such 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 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 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.
B MORE RELATED WORK
Certified Prediction Robustness To provide the worst-case robustness certification, a rich body of work has been proposed, including convex relaxations (Zhang et al.] 2018 Li et al., 2019 Kang et al., 2023b). hipschitz-bounded model layers (T Tusuzuu et al. 2018 Singla et al. 2022 Xu et al. 2022b). and randomized smoothing (Cohen et al. 2019 Salman et al. 2019 Li al. 2021: 2022a). However, existing work mainly focuses on certitying the prediction robusiness rather than the prediction coverage, which is demonstrated to provide essential uncertainty quantification in conformal prediction (Jin et al. 2023). In this work, we aim to bridge worst-cast robustness certification and prediction coverage, and design learning frameworks to improve the uncertainty certification.
Knowledged-Ennbbll Logical Reasoning Neural-symbolic methods (Ahmed et al. 2022 Garcez
et al., 2022 Yi et al. 2018) use symbols to represent objects, encode relationships with logical rules, and perform logical inference on them. DeepProbL (Manhaeve et al.) 2018) and Semantic loss (Xu et al. 2018 are representatives that leverage logic circuits Brown (2003) with weighted mode counting (WMC) to integrate symbolic knowledge. Probabilistic circuits (PCs) (Darwiche) 2002 2003 Kisa et al. 2014) are another family of probabilistic models which allow exact and efficient inference. PCs permit various types of inference to be performed in linear time of the size of circuits (Hitzler Sarker 2022 Choi & Darwiche 2017 Rooshenas & Lowd 2014).
Worst-case Certification. In particular, considering potential adversarial manipulations during test time, where a small perturbation could mislead the models to make incorrect predictions (Szegedy et al. 2014 Madry et al., 2018 Xiao et al.) 2018) Cao et al.) 2021), different robustness certification approaches have been explored to provide the worst-case prediction guarantees for neural networks. For instance, range of deterministic and statistical worst-case certifications have been proposed for a single model (Wong & Kolter 20018] Zhang et al.) 2018 Cohen et al.) 2019 Lecuyer et al., 2019),
reinforcement learning (Wu al.; 2002al Kumar et al. 20022 Wu et al. (022b). federated learning
paradigms (Xie et al., 2021;2022). and fair learning (Kang et al. 2022; Chaudhury et al. 2022
under constrained perturbations (Balunovic et al. 2019
Li et al. 2021 2022a).
17

---

Published as a conference paper at ICLR 2024
C PRELIMINARIES
C.I PROBABILISTIC CIRCUITS
Definition 1 (Probabilistic Circuit). A probabilistic circuit (PC) P defines a joint distribution over the set of random variables X and can be defined as tuple (g, v) where & represents an acyclic directed graph (V,E), and V >> 2* the scope function that maps each node in V to a subset of X (i.e., scope). This scope function maps the nodes in the graph to specific subsets of random variables X. A leaf node Ouar of G computes probability density over its scope (Oirr)) All internal nodes of G are either sum nodes (5) or product nodes (P). A sum node S computes convex combination of its children: S = Σ cebcs)) Ws.N N where cS( denotes the children of node S. A product node computes product of children: P= [N N.
The output of PC typically the value of the root node Oroet. We mainly focus on the marginal probability computation inside PCs (e.g., P(a, = 1] =xex_=;=1 (z)) Szex Oroa (roa( (z) The inference of marginal probability is tractable by imposing structural constraints of smoothness and decomposability' (1) decomposabilit:: for any product node P E V. (0(m1) ) n 1b(2)) = 0, for 02 E ch(P), V1 * 12, and 2) smoothness: for any
node S V, ((())) (12)), for v1, U/ E ch(S). With the constraint of decomposability. the integrals on the product node / can be factorized into integrals of children nodes ch(P), which be formulated follows:
/ P(x)de= JEX
/
II N(x)dr
FEX NEch(P)
(22)
[/
II NEeh(P)
U N(x)dx
With the constraint of smoothness, the integrals on the sum node S can be decomposed linearly to integrals the children nodes ch(S), which can be formulated as:
[ J
S(x)dx
=
E
WS.N (.,NN((x)ee (x)dxx
JXEX NEch(S)
(23)
V (z)ddz
WSSN
EEX
NEdi(S)
We can see that the smoothness and decomposability PCs enable the integral computation on parent nodes to be pushed down to that children nodes, and thus, the integral Jæex.2y=1 (vo)())
or Jrex O (x) can be computed by a single forwarding pass of the graph G. In total, we only need two forwarding passes in the graph G to compute the marginal probability P[z, = 1] Snex..y=1 r (x)/ JAEX O (x)dx.
Knowledge rules PCs. For the implication rule - B, we define A as conditional variables and B consequence variables. Suppose that the r-th PC encodes set of implication rules defined over the set of Boolean variables V,. The PC is called a homogeneous logic PC if there exists bipartition Vra and Vrs (Vrd U Vrs V, Vra Vrs = 0) such that all variables in Vra only appear as conditional variables and all variables in Vys only appears as consequence variables. We construct homogeneous logic PCs to follow the structural properties of PCs (i.e., decomposability and smoothness) and can show that such construction is intuitive in real- world applications. For example, in the road sign recognition task, we construct PC with the knowledge of shapes. We encode set of implication rules A = B where A is the road sign, and B is the corresponding shape (e.g., a road sign can imply an octagon shape). We can verify that such a PC a homogeneous PC and follow the structural constraints in the computation graph G, as shown in Figure I
C.2 MULTIPLE PCS WITH COFFFICIENTS 3, IN THE COMBINATION OF PCS
Let us consider the case with R PCs. The conditional class probability of the j-th class corrected by r-th PC can be formulated as:
18

---

Published as a conference paper at ICLR 2024
E EpeM, M, ny= Opod (1)
ΣyEm, a1 exp
Noth.
(( kw) F+(H) (24)
(x)
iv=l
ΣyEM (%0)())
ΣnEM exp
Eiv== T( (z): (r((e)
where My denotes the j-th element of vector μ. and T (a, b) log(ab (1 a) - b)). and F.(p)
exp E Warllfu Ka-lJ. Hr. Khr, war are the number of knowledge rules, the h-th logic rule, and the weight of the 1e-th logic rule for the r-th PC. Note that the numerator and denominator of eq. (24) can be exactly and efficiently computed with a single forwarding pass PCs (Hitzler & Sarker 2022 Choi & Darwiche, 2017 Rooshenas & Lowd 2014). Specifically, the inference time complexity of one PC defined on graph (V,&) with node set V and edge set is ((V)))
We improve the expressiveness of the reasoning component by combining R PCs with coefficients 3, for the r-th PC. Formally, given data input z, the corrected conditional class probability 45ouse can be expressed as:
#COLEP
Σ B { (x)
(25)
TEJM
We also note that the coefficients correspond to the accuracy of r-th PC normalized over all PC accuracies. The core of this formulation is the mixture model involving a latent variable ree representing the PCs. In short, T #COLEP (a)) the marginalized probability over the latent variable rPC: such as:
write : (x) as (x) PP y|X 2, TrC r]. and
# #OOLEP (x) = Pl|Y = y|XX = x
Σ rE
P[rpc r] P[Y = y|X = 2,
(26)
Pirec = r] 23 (z).
(x).
rE [2]
Hence, the coefficient 3, for the r-th PC are determined by P(rre 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.
C.3 RANDOMIZED SMOOTHING
Lemma C.1 (Randomized Smoothing (Cohen al.] 2019)). Considering the class conditional
probability ž. Rd + [0, 1). we construct a smoothed model g;(;;0) = E. ( n))
With input perturbation |/e||a S 8, the smoothed model satisfies:
④( (o) o)) 8/0) S 91(x + + S 4( (I,(z;))) (1(
(27)
where t is the Gaussian cumulative density function (CDF) and --1 is its inverse.
In practice, we can estimate the expectation in 9 σ by taking the average over many i.i.d. realizations of Gaussian noises following (Cohen et al. 2019). Thus, the output probability of the smoothed model can be bounded given input perturbations. Note that the specific ways of certifying the learning component are orthogonal to certifying the reasoning component and the conformal prediction procedure, and one can plug in different certification strategies for the learning component.
D CONFORMAL. PREDICTION WITH COLEP
D.1 FLEXIBILITY OF USER-DEFINED COVERAGE LEVEL
In this part, we illustrate the flexibility of COLEP to use different miscoverage levels ar for different label classes [N.] and prove the guaranteed coverage. Recall that in the standard conformal prediction setting, we are given desired coverage - a and construct the prediction set of new test sample Cn (Xx+1) with the guarantee of marginal coverage: P|Y,+1 S Cn,a((xx1)) 2 1 - a. In
COLEP, construct the prediction set CRoip (X (x++)) for the j-th class (j [N.) as in Equation 7
19

---

Published as a conference paper at ICLR 2024
and construct the final prediction set n1,a (Xx+1) as in Equation 8 Then we have the following:
P
Y & CCOLEP (Xn+1))
(28)
P
& Cn,a,
Co (Xn+1)
(29)
P
SpcoLed Yn+1
(Xn+1: 1) > Q1 Q1-a (Sagars (f M1 (M-i
(30)
max ]E[Ne]
P
S Sqgaur (Xn+1, [[o-==))) > Q1-a, (S ((X,, JD (ES=))EEAa))
(31)
max Qj jE[Ne]
(32)
Therefore, conclude that as long set maxxe(Na](as} S we have the guarantee of The flexibility of COLEP various coverage levels for different label classes is advantageous in addressing problems related to the imbalance of classes. For example, when samples of class j are extremely vulnerable to attacked by the adversary, we can set higher miscoverage level ag for class to consider the class-specific vulnerability instead of setting a higher a for all classes which may affect the performance on other classes.
marginal coverage: TP Y CROLEP (Xn+1) 2 1
D.2 ILLUSTRATIVE EXAMPLE
Let us consider the example of classifying whether the given image has stop sign in Figure | The main model generates an estimate (x). meaning that the image æ has stop sign with probability (z). Suppose that we have a knowledge model to detect whether the image has an object of octagon shape with an estimate (z)),, meaning that the image has an object of octagon shape with probability (x)) Then we can encode the logic rule "IsStopSign = IsOctagon" with weight w in the PC, as shown in Figure [ The PC defines a joint distribution over the Bernoulli random variables IsStopSign and IsgtopSign and computes the likelihood of an instantiation of the random variables at its output (e.g., p(IsStopSign = 1, IsOctagon = 0)). The represented joint distribution in the PC is determined by the encoded logic rule with the pattern in the top PC of Figure [ We can see that only the assignment (IsStopSign = 1, IsOctagon = 0) is not multiplied by the weight w due to the contradiction of the rule. Therefore, the probability of instantiations of random variables with such contradictions will be down-weighted after the correction of the PC. In the simple PC, we formally compute the class probability as:
PlIsttopSign 1) = Sp((sStopSign IsOctagon 0) plsSttopSign 1, ISOctagon 1)}/
{p(IsStopSign 1, pIsOeetagon = 0) + plssttopSign = 1, IsOctagon = 1) +p(lsStopSign O, IsOctagon 0) p(IsStopSign 0, I,Ocagonnn 1)}
(33)
Note that the nominator and denominator can be tractably computed by forwarding pass of the PC graph. COLEP can enlarge the probability estimate p( p(ISttopSign = 1) when ir is a stop sign and reduce it when not stop sign by leveraging additional concept information p(IsStopSign, as rigorously analyzed in Lemma 5.1
E OVERVIEW OF CERTIFICATION
We provide the overview of certification flow in Figure 4 for a better understanding the connections and differences of certifications in COLEP.
F OMITTED PROOFS IN SECTION
F.1 PROOF OF THM. I
Theorem 1 (Generalization of Thm. [ multiple PCs). Given any input and perturbation bound we let j (1), ftyy (x:) be bounds for the estimated conditional class and concept probabilities by
20

---

Published as a conference paper at ICLR 2024
poIlin (e) masering prediction coverage (() gunaa (?) schieves higher prediction accuracy [Thoorem
prediction (00LE1 a
cneerage gueeattee (1 (1-43)
(Tuxorm 21
somples perturtation [--
Main of ourput (RUE).TUE)
Kroncledger
Reasoning Componeet
Iounnd of output likethhod afte the reasoning component [ CD] Uja Uja ([]]]]]]]
prediction -2 (2
AAchteved by robusness contifiction mechodk randomized smoothing!
(Thoorm
coverage (1 -
(Theesen 3)
Figure 4: Overview of prediction certification of COLEP. The certification setting is that the inference time adversaries violate the data exchangeability assumption, compromising the guaranteed coverage. Therefore, the certification generally achieves the following three goals. (1) We can preserve the guaranteed coverage using prediction that takes the perturbation bound into account (Thm. (2). achieved by computing the probability bound models before the reasoning component (by randomized smoothing) and the bound after the reasoning component (by Thm. [ (2) We prove the worst-case coverage (a lower bound) if we use the standard prediction set as before (Thm. 3). (3)
We theoretically show that COLEP can achieve a better prediction coverage (Thm. and prediction accuracy (Thm. 5) than a data-driven model without the reasoning component.
the models with je E [No + L}. Let Vå be the set of index of conditional variables in the r-th PC except for j [Ne) and V be that of consequence variables. Then the bound for COLEP-correcee estimate of the conditional class probability aooLse is given by:
(1 (1- (x)))())) Σ exp
Σ (TT) + Σ T(jj
F+(1)
Mg K==0
SVEV
U[#5oLse (x:) = Σ Br
+1
rE(R]
7y(1) exp
T(tr,()) ΣT (x),
Fr(1)
SVEV
(x)))) Σ exp 4==0
E (t), Σ T( (z),
F.(1)
jveVi
WEE
[ (10C0LS((>))
(x:) Σ Br
+1
FE(R]
1x(x)) exp 11
exp
(T( (TT Frlu)
(iEE
SVEV2
(34)
where (aa log(ab + (1 a1 - b)).
Proof of Thm. 7 We first provide a lemma that proves the monotonicity of the complex function with respect to the estimated condition probabilities of conditional variables and consequence variables within PCs as follows.
Lemma F. (Function Monotonicity within PCs). We define the target function G(q, d) (x), (r))), where q E IN T.J{fs> and M,a = {u M : :i = d} (d E (), Then we have @ S 0 if class label q corresponds to conditional variable in the PC and 0G ( if class label q corresponds to a consequence variable in the PC.
ΣnEMi exp EivEENN+LIMU
Proof of Lemma F.I monotonicity, we only need to determine the sign of the coefficients of (x). We first consider the case where class label g corresponds to a conditional variable. We can rearrange the expression of G(g, d) follows:
Note that the function G(g, d) is linear with respect to (x) To explore the
21

---

Published as a conference paper at ICLR 2024
G(o.d)
Σ exp
Σ
T(Asy (0) F.(m)
Σ
Σ The (s))
Fr(a) + E exp
E
T(A (t)) Frlw)
(NEENe+ZRRG
= Σ exp
Σ (1)
F.00) +(1-)((()()))
exp REMyding
E (t) F((0) JeE(NNtNMMM
MEMyding
(x)
Σ exp
F((0) E exp
E T(ssy( Fr(u))
me me Mydung=1
JyE(NetAMMONN
NE HEMyaingED
exp
Σ
(1), F-(m)
PEMja-Pu=
Then we rearrange the coefficients of (x) as follows:
Σ exp HEM
Σ (( Fr(m) E exp
Σ (t) F2(1))
N
Σ exp
Σ
(( (F)( -F+(()
=
(36)
where R(u,q) : {0, 1N x + {0, 13.11 rewrites the q-th dimension of vector μ. to 1. Note that when 9 is the index conditional variable, given any implication logic rule Kar, we have I[((,, 2) ~ Karl I IIu Karl Therefore, (.( g)) Fr(n) I O holds and aG/0ã,(t (x) I 0.
Similarly, when q is the index of consequence variable, given any implication logic rule K we have [[R(p, q) Kirl 2 Ul ~ Karl- Therefore, (,(((,.))) (,( 2 O holds and @G/Ot,, (z) 2 O.
Consider the r-th PC. We first rearrange the formulation of the class conditional prohability #j (w) to the pattern of function G(-) and then leverage Lemma to derive the upper and lower bound. The reformulation of + is shown as the following:
=(()(x))
*) (z) Σ ΣpEM, =y=1 exp EN (z), Fr(m)
(37)
ΣpEM exp Eiv T(t (z), (zx (r(m) FF(m)
(38)
+ EyEM, 0,=00 exp
Not T(t)) Fr(N)
ΣyEM, u==1 exp
Liv=l ( Fr(n)
NotL
(39)
(1 -1- +x)) EyEM, n3 exp
E ((F) Fr(u)
1+
(x(x) 1y=1 exp E (z), F2(H)
Next, we focus deriving the lower bound (x:), and the upper bound can be derived similarly.
(x:)
22

---

Published as a conference paper at ICLR 2024
1 (1 Tt (x)) EyEM, ny = exp
EivE(N (1), Fr(H))
3/ x ( 2
az(#) EpEM, n==1 exp [ENvENN-LINO) ((ps())) Fe(1))
(40)
(1 - fz(2)) (1-4z(2))
U [uEEM, Lu
=0 exp
Fr(m))
(x) L EuEM, 1,-1 exp (ENEIN+HUN)) T() Fr(m))
(41)
In Equation 41,, we relax the numerator and denominator separately and then will show how to derive the upper bound of the numerator and the lower bound of the denominator in Equation 41 We can apply Lemma F.1 for any q [NVe + LMV and get the following:
Σ
exp
Σ (T)
F((1) S Σ (z) Σ
(x)
R,M, #y=0
AVEIN++LM
SVEVi
SVEVE
Σ exp
E (() LEEN
F.(1) Σ (2)
Σ (1)))
NEM, Py=0
SVEV
SVEVY
(42)
where V rd is the set index of conditional variables the r-th PC except for j E [N₂] and V
that of consequence variables.
From Equation 41 and Equation 42 we can derive the final bound of (çoLke(s) by considering all the PCs:
(1 (1- (1-))(2)) Σ exp
Σ (T) + Σ T(a (()
F-(1))
U[a COLEP (x) = Σ 8,
===0
AVE
JVEV
rE(R)
7g(2) exp
(Tir ET (x),
Frle)
JVEVZ
SVEV
(1) exp
Σ T( (T). Σ T( (x)
F+(1))
jVERS rd
VVE
[[ (x)] = Σe. Br
ME[R]
(x(x)) exx exp ===1
(T) + Σ T (1 (2),
Frlu)
JVEV
SVEV2
(43)
F.2 PROOF OF THM. 2
Theorem 2 (Recall). Consider
test sample Xn+1 drawn from Pxy. For any bounded perturbation ||l]| < 8 in the input space and the adversarial sample 8 := X we have the following guaranteed marginal coverage:
P|Y,+1
OCCLEPS (Xn+1)) a
(44)
we construct the certified prediction set of COLEP where
GCOLER& n,a
(Xx+1)= = {i [No] S
Sapou coum (Xm+1, 1) s Q1-a(15, p cour, (X,, Ip Iimea)) (45)
23

---

Published as a conference paper at ICLR 2024
and caurss (:y.) is a function of worst-case non-confommity score considering perturbation radius 6:
U& U&( COLEP (X+)) + u(1 - U (xi)),,
Y; # j
S cearn (X,; [(y;=)))
(46)
- g (X:)] + uL. ( (Xi)),
Y =
with U& (0)
[ (x)) = max 1l # goonne (x + 1) and Lgf ( (x)] = min wla58 a aCOLEe (x + 17).
Proof of Thm. 2 We can upper bound the probability of miscoverage of the main task with the probability of miscoverage of label classes follows:
P (Yut & CROLEPE (Xn+2)]
(47)
< max P c[[N.]
[[Yan==)] & Coous (oof(((8x4)) (Xn+1)
(48)
max ]E[N.]
IP
Sagarss
Q 10-a Q cour, (1X,,
(49)
max TP
S gouer
n. yourn ((X; In==s > Q1
(50)
JE[No]
(51)
where Onool (X (X++1) = n" E 1): S Supurr (x=+1,)) y) S Q1-a g
ooerg ((Xi, =x==)
the certified prediction set for the class label j.
Note that Equation
50 holds because we have
S Seans M1
S Sagurer II Next, we will prove Equation the probability miscoverage conditioned on Yn+1 =j.
50 rigorously. We first consider
Sacazr (Xat1, (I > Q1 Qi-a(S 4, ((x,, [Ix hezu |V++1 =]]
(52)
<P 1 - (1 - -u) u) (Xn+1) > Q1-a #,
enar (fX;, [y: = MEII. (Y++ = :
(53)
<P 1 (1 u) L AgOLEP (Xn+1)) > Q1-a ( courr (1X,, IIx heZ.) |n+1 =
(54)
<P S ( corns (Xa+1, f ==)) > Qi-a(S panss ((X,, Iy==J) |Y = j
(55)
Similarly, we consider the probability of miscoverage conditioned on Y,+1 + j.
P
S Sagurr (8n+1. II,. ==i1) Q1
Somer (S ((X,, [y:=s]) |n+ }
(56)
7;
<P
u + (1 - -u) (xn+1)= 1) > Q1-a QS-a coLNs ((X,, [[r==]] )iez.) | # $
(57)
n; (S Ri
<P
u + (1 - u)) u). U CCCLEE (Xn+z)) > Q1-a(S,
cours
(1 [ )ez..) Vn+1 # }
(58)
<P [ Suurs (Xx+1, Ip. 1 (=) Qi-a(S a
mukers ((X, I [y hez..) |Yn-1 +
(59)
Combining Equation (55) and Equation 59.. we prove that Equation 50 holds. Finally, from Equation 51) we prove that:
TP Vutt E &COLEP& (ooLeP&(Xntt) (Xnt1)] 2 1 -a
(60)
F.3 THM. 2 WITH FINITE-SAMPLE ERRORS BY RANDOMIZED SMOOTHING
Theorem 6 (Thm. 2 with finite-sample errors of learning component certification by randomized smoothing). Consider new test sample X drawn from Pxx. For any bounded perturbation
24

---

Published as a conference paper at ICLR 2024
||ela S 8 in the input space and the adversarial sample Xn+1 Xn+1 + have the following
guaranteed marginal coverage:
P[Y++1
Cuaa (X++1)] 2 11--
(61)
if we construct the certified prediction set of COLEP where
CooaET's (xa+1) = { [Naa]] Segues (X=+1,1) & Q Q1-a+20(1S,, qmm (Xi, (x=,))))))
(62)
and S gquerr (1-) is a function worst-case non-conformity score considering perturbation radius 8:
U (Xi)] + u(1 Up 101 (x.)..
Y x
Symur (X,, T(r(-s)) =
(63)
1 1 ( cones (X:)] + uLss, [st, COMER (X:)l. Y
(x)] and Lاg s olt (x)) are computed by plugging the 3-confidence prob- ability bound J (x: 3), R. (z; B)] into Thm. The high-confidence bound [a (x; (x; 3)] can be obtained by randomized smoothing as the following:
where U8. f
jy (z: 3) (($ - (x bHoe 5//0) -Beer (3)
(64)
(r; =) ④ [BBltj (xr + to) + (B)I - 5/0) + brema (3)
(65)
where E is the empirical mean of Nuc Monte-Carlo samples during randomized smoothing
and (B) /ln1/9 is the Hoeffding's finite-sample error and (Be v 2N
/2V In 2/B
NMC
2/B is the Berstein's 's finite-sample error.
3(NMC 1)
Proof of Thm. 0
Bounding the samile error of randomized smoothing similarly as Theorem
in Anonymous
2023
get that for given jv E [Ne L]. we have the following:
COLEP
Jj
(Xn+1)) S $ #COLEF (Xn+1) $ U3,5
CCOLEP
(Xn+1)]
1-22
(66)
We can upper bound the probability of miscoverage of the main task with the probability of miscover- age of label classes as follows:
P Ynt1
OCOLEPA
(Xn+z)) CCCLEe((((nt))
(67)
max JE(N.]
TP
TYYnI=J) & Cnaag (Xa+1))
(68)
max P JE[N.]
SACULD (Xn+1, I Ipp Q1-a+23 3 can, ([X,, In (iez.
(69)
max P JE[N.]
S umaes ( > Q1 Q1 yoers ((X,, Iy; + +
(70)
2,3 + 28
(71)
<a
(72)
(ggger where &COLEP' (Xx+1) : { 9d E (0,1): S Saguer (Xn+1.9) S Q1-a-20($ quars Tm (ezz
is the certified prediction set for the class label j.
Note that Equation 70 holds because
we
have
S Sauur (Xa+1, (pre 2
Sagurr (Xn+1, [p Next, will prove Equation
70 rigorously.
We first consider
25

---

Published as a conference paper at ICLR 2024
the probability of miscoverage conditioned on Yn+1 =j-
P S Sgans (X > Q Q1-0020(S, gmen, ((Xi, 4 4m= (1411 =i]
(73)
=P (1 u) (X > Q1-a+20($, sums (1x, UM= 1x+1=1) = =]]
(74)
(1 - u) p ( (X (Xntt)] > Q1- com (1X,, In= Yn+1 =
(75)
+ L3,6 (13 ( (Xn+1) S ]
2OOLEP
(Xn+z)]
(76)
<P S Sqqueer (Xn+1: JIx..11))) [==)| Q1 qquers (1 [I==s (a+1 = + 2/ (77)
Similarly, we consider the probability of miscoverage conditioned on Yn+1 $
S Sqgare (Xn+1, ((a)1==1) > Q1 Q1- g ((X,, (1==s)) (v+11 *j]
(78)
<P (1 -u) SOLER (Xn+1) > Q1 Q1-a+22(5 cours (1x; [I==s Yn+1 # 5 ",
(79)
<P
(1 u) U3S A (Xn+1) Q 2 yoers IM= Yn4 *
(80)
+P UBs Up. [AjouRe (Xx+1)) 2 Rj #COLEP (Xn+1)
(81)
<P S oaaso (Xn+1, [[N > Q1- Q1-a+22(S goase
#
+ 233 (82)
Combining Equation (77) and Equation (8)) we prove that Equation 770 holds. Finally, from Equation (2). we prove that:
P Yatz E Cnna (Kn+1)
(((+1)(((n+1)) 2 1 -1-a
(83)
F.4 PROOF OF THM. 3
Theorem 3 (Recall). Consider the new sample X,+1 drawn from Pxy and adversarial sample
X,+1 -x,t1 + with any perturbation |c]|2 S in the input space. We have:
P|Y+41 E ACOLEP
n,a (X,++1] 2 cOLEP=> = min { COLEP }.
(84)
jE[No]
where the certified coverage of the j-th class label T
COLEP is formulated as:
Co max (T Q+(15 cousy (Xi, [[==s) ) S Q QI-a((S5pgna (Xi, Ni,Tir=s))iizau
Tj
(85)
Proof of Thm. 3
We can bound the probability of coverage of the main task with the probability of coverage of label classes as follows:
Yn-1 E OCoLEP (Xn+1))
(86)
min je[Na]
IP
Uy.-== E n.aj (Xn+1)
(87)
min JE[N.]
TP
Sggare , [Va41==]) S Q1 Q1-a ((Xi, | bEZuJ)
(88)
min Je[N.]
I
Secaro (X I[Vo41=1)) S Q cocteor (S cours (1 I|n 1
(89)
min Je[N.]
I
ooues (Xn+1. : IP S _0 colenee (S (1X;, 4p -
(90)
min
(T COLEPON }
(91)
[[N.
26

---

Published as a conference paper at ICLR 2024
where Equation (90) holds because S ccars, (Xx+1: (Y (1)
Sagerr (Xn+1, (Pa and is
proved rigorously in the proof of Thm. in Appendix F22
G FINITE-SAMPLE CERTIFIED COVERAGE
In this section, we consider the sample error induced by the finite size of the calibration set Teal- We provide the finite-sample certified coverage in the adversary setting as follows.
Corollary (Certified Coverage with Finite Samples). Consider the new sample Xn+1 drawn from Pxy and adversarial sample Xn+1 == Xa+1 + with any perturbation ||e]|2 S 6 in the input space. We have the following snite-sample certified coverage:
v 12g(2)/2 22/(1 log(2) + 8/7)
P|Yn+1 OCOLEE (Xu+1))
1+
min JE[N,]
COLERW
[Trat]
Teal
(92)
where Teal is the size of the calibration set in conformal prediction.
Proof sketch and remarks. Leveraging corollary Massart 1990) and following the sketch in (Yang & Kuchibhotla] (021). we can prove the finite-sample error bound. Combining the finite- sample error with the certified coverage bound in Thm. B concludes the proof. Note that the union bound is applied to multiple models (Yang & Kuchibhotla, 2021) while circumvent it by aggregating individual results for class labels subtly, and thus, COLEP achieves an improved sample complexity of conformal prediction compared with ensemble learning given the same tolerance of finite-sample error.
Proof of Corollary
7
From Corollary of Massart 1990), we have that for all c > 0,
P
P
S comny (Xu+1, Yuts) S 2 e Iaal
s 2exp -
tER
Tcal
coLRP,
(93)
For ease of notation, we let:
W
TTaa sup 1ER
Σ ie
S Samn (Xn+1, Mn+1) 5
(94)
[Taal
s (s.quers (X) (X.V)))
We let f = Q couenen (S
(S sours (fX; Iivams) (ez..) It implies that:
IP s corss (Xn+1, Yn+1) S omepra (S corns ((X,, Ipr: Jezzm))
W
Ieall
couer (X.,Y)&R couarer e (S couny (1 ((X1di);=s)hez
Teall
[(1
ITaal 1T,
COLRF
W
(95)
Teall
Zaal
(1 1
1
CoTRR
W
Tcall
/ Zeal
27

---

Published as a conference paper at ICLR 2024
Then using Equation
93
we can bound E[W] as follows:
B[
IP I u| du
(96)
1og(2)/2
P I 2 u|
du +
P IW 2 u/ du
(97)
Vlo(2)/22
S (/log(2)/
+
exp(-2u2 2--2222
(98)
Vlog(2)/2
V2/2
1og(2)/2
(99)
2 llgg(2) + 4//
Inequality (a) follows from Formula 7.1.13 of (Abramowitz & Stegun 1948 Finally, combining the results in Thm. we get:
P ORCLER (Xa+1)] 2 (1+
min JE[Nc]
{7, COLERE }
/log( (2) /log(2)/2
v2/(1///////g/// /l/(2))(22)) +
8/7))
Teal
ViTaal
(100)
H OMITTED PROOFS IN SECTION 5
H.1 PROOF OF LEMMA
Lemma 6.1 (Recall). For any class probability within models j E [Ne] and data sample (X, Y)
drawn from the mixture distribution Dm, we can prove that:
E
COLER
(X) *
(() 5,0 1V $
COLES #3
(X)
2 R (X)
+ 5.11 Y =
(101)
6,0 Σ PD EBuffo De(
100
4
5 #, + (1
/
[r]
Σ 8r rEPx()
ny + (1 n
TT)
(EPa(()
3,
j.D
9,1 = Σ DE(De, Db)
Br (EPa())
)
R2 + Σ S,U,(T) ((r)
A2 + (1 1/ #
nj
4t. + (1 - 4. /
rEP,()
(102)
where 1 1/20 (1/T//) j.D - - 1) and we shorthand (X) as ,
We first consider one PC and then analyze the effectiveness of R linearly combined PCs. Without loss of generality, we focus on the class conditional probability by the r-th PC (r E [R] for the class label j E [No]]
Proof of Lemma 5./
Recall that we map set of implication rules encoded in the r-th PC an undirected graph G. (V,,E,) where V, [No + LJ corresponds to the Boolean vector of class and concept predictions in the learning stage. There exists an edge between node j1 V, and node jz E V,, iff they are connected by an implication rule j1 = j2 or ju = J1. Let Ar be the set of nodes in the connected component of node jv except for node jv (i.e., Jv & (jv)). Let Arv C A,viv) be the set of conditional variables and (jv) C Arvv) be the set of consequence variables. Denote M, be the universal set of assignments except for the j-th element. Let Pa(i) and Pa(j) be the set of PC index where appears as conditional variables and consequence variables, respectively.
We consider a mixture of benign and adversarial distributions denoted by Dm, which indicates that an input is either benign example drawn from D, with probability PD, := Ppxx Do] or an adversarial example drawn from D. with probability Pp. := -P(x- ~ Da), where PD, + PD. = 1. We analyze the effectiveness of PCs in four cases: case (1) r Pa(j) and Y # j. case (2) Pa(i) and
Y == j. case (3) r E (J(j) and Y = j. and case (4) r E P,()) and Y j. We leave the probability conditions on Y j or Y * j in each case for simplicity and consider them in the conclusions.
28

---

Published as a conference paper at ICLR 2024
Case (1) r E Pa(f) and Y + j. We can derive the class conditional probability by PCs follows:
Σ ENEM, my=1 exp Σ [(tj (z)) Fr(1)
()((())
(103)
EpEm exp E T ( (z)) (gw)) (r(
(104)
ΣHEM, my=0 exp
Σ M= T (zv) (1(
+
ΣpEM, 11=1 exp
2i0==1 T( (t), mbx) (r(
-1
1+ (1 (t)) M,=0 exp Σ EivE(N+EMMM (o) Fr(N))
R (x) EPEM, 1y= My= exp [ESVENN+LIMD T(2,(t)) Fr(())
(105)
Note that since r E Po(j). we have ΣHEM, a,=0 exp {DOELN+HDNN) T(t (1))) Fx(1) 2
ENEM, 1y-1 cxp E>jE[N+ T(#t(()), (m)) } (r),), and thus, (f) S (z(x) holds. Next, we analyze the gap get a tight bound based on the distribution of the Boolean vector of the ground truth class and concepts v.
Case (la): If 3iv Ar, Usv = O, then have:
ENEM, =0= exp E [SNEEN++OIG (o),
Fr(m)
(106)
EyEM, 11=1 1 exp
(EWEIN++LIMD T( pz)) Fr(m))
exp {EIVEINAHNNG) T( (z), vz)) Ey(v)
>
(107)
EnEM, My exp (SVEINAAMMO ((f))()), (z)) (r(
e- w + Enj= exp EEVEIN-4NGD 1R62 (T(f))()) - ((f (x), F. F+(n)/P(())
(108)
When we have models such that スz. BV buye = =1 Biv E Ar(j) (with probability 1 - z/10), we leverage the general bound in the case,
Liv.D |u = 00 or )
(E) + 5 (x) + jl
(109)
When we have models of high quality such that ã (x) S 1 - ijv 1y = 0 and (x)()) >
1 Liv.D 10 =1, Vjv E Ar(i) (with probability //D)), we can derive a tighter bound as follows:
Σ exp
Σ
- (2),
F.(N)/F.())
(110)
My=
ivE[N++L\VG)
exp
Σ
-T
(111)
#==1,
1 LivDD
(112)
D
(i)
1
- 1: = 1/T
10 -
(113)
11
29

---

Published as a conference paper at ICLR 2024
In inequality (a), plug in the lower bound of confidence of correct prediction f,DD and the upper bound of confidence of a wrong prediction 1 - tjv for label jv.
Combining Equations
109) and
113).
get the following bound for case (la):
()(x)
1 (x)|> + S
(1 - ())))
2/3 # イ + (1 n (t))
(114)
where 1/12 (1/Tg, -e- - 1).
j,D
Case (Ib): If V/ (n) V/v 1, then we use the general bound in the case:
(x))Y + i < B(fr(=)\Y + j]
(115)
Note that case (Ia) is with probability 0 and case (1b) is with probability 1 - D Combining Equation (114) in case (la) and Equation 115 in case (Ib), we have:
Elf (x))Y j sB
U
(1
3.1
(r)
(x)
(1 Uf (5) $
1イ (1 R, (x))/A
<
(イ(x)
0f 2
(z(
(x)
n, (x))) + (1 (1- (2))
(116)
Case (2): r E Pa(i) and Y = Since in the r-th PC j is the index of a conditional variable, we have Vjv E (i), Viv 1, where is the ground truth Boolean vector. Then we have the following:
Σ ESVE(N+HANG No ny exp
T(xs Fr(e)
(117)
EnEM, -1=1 exp
E (() (2), Fr(m)
ENEM, n,=0 exp E EDVENN+AINN T(f Fr(H)
(118)
exp
[ivElN T( (1), (v(
II
[+ 1 1-110 = 1/T
(119)
LDv
Then the following holds in case (2):
,x(x)
n
(x) = 2
Y =
(120)
(z)x)) + (1-
Case (3): r E Pa(i) and j. As in Case (I), we similarly consider cases based on the distribution of ground truth Boolean vector v to get tighter bound.
Case (3a): Ajv Ar,(j), Ujv 1.
When we have models such that (x) 1 1j. 10j0 = 0 or (x)
tV |y =1, Biv E Ar(i) (with probability 1 2 we leverage the general bound in
the case,
B[a (x) + o < (x+) ド Equation 121) holds because in case (3), j corresponds to consequence variable in the r-th PC, and thus, we a always have:
(121)
Σ exp
Σ (() Fr(m) Σ exp
Σ (T)
Fr(m))
PEM, my=0
JVE(NetRIVG)
(122)
30

---

Published as a conference paper at ICLR 2024
When we have models of high quality such that (2) I 1 jj My 0 and ())(2) 2
1 1 P3 =,, Viv E Ar) (with probability z 2,D)), we can derive a tighter bound as follows:
ny my exp
EivelN+t (ND) (() F.(1)
(123)
EHEM, My=1 exp
EMEINAANND T(# (z), (b))) (r(
ENEM, m==0 Zu=M,ny=OeNt exp
[EVEIN++AIND T( (2), p(je) Fr(m)
(124)
exp [iiVEIN+AINGG T( (2), Pz,) (2())
(1+ (1+1-
1- LiviD ()nn
Lexp + II
- 1 1= 10
(125)
Liv.0
JvEA,()
Therefore, the following holds in case (3a);
(x(
E + (z) (x) - 2 E (1 (1-2
23 (1)))(())) + 2
1 j
(126)
j.D
n (T)
(1-
+
Case (3b): Vjj Arali), Vsv = 0, then leverage the general bound:
( = 2 (t) Y =]
(127)
Note that case (3a) is with probability 7/ and case (3b) is with probability 1 - Uf") Combining
Equations (126) and (127). the following holds:
+1) (1)))))))))) - +5(x)) ) Y
(x)
E
2 Y 5
2 E (x(x) + + 2/1
(128)
Case (4): r E Po(i) and Y $ j. Since is the index of a consequence variable, we have Vjv
(T), Vjy = O. Then we can lower bound the coefficients as follows:
EvEM, =,= no exp
ENvENN+AMNO ((fg) Fr(H)
(129)
EvEM, m1=1 exp
[SNEENN+ (2), Mm)) Fr(m)
exp f [SIVELNLLMM! T( (x) mz)) (v)
(130)
Σ ENEM, WEM, my=1 exp
[Eve(N++<ING) (1) p&w) Fr(H)
1
T/16
(131)
1+ 1 - t2mD
1-
I1
Liv.0
Thus, in case (4) we have:
(o)L
Y
+
(132)
(t( (1 n mT
(r) J.D
Then we consider all R PCs to get the effectiveness of COLEP on the class conditional probability.
Combining Equation (116) in case (1) and Equation [32 in case (4), we finally have:
E (
COLEP (X) Y +il < El Ej.0 IY +il
(133)
where
6 = Σ pd EBuTso
R n (1 R
Σ 3r rEP,U)
#
300 4
)/1 (r)
n, (1
R 1T
(D,, Da) (EPa())
(134)
31

---

Published as a conference paper at ICLR 2024
Combining Equation
120
in case (2) and Equation 128 in case (3), finally have:
COLEP
(X) Y = _] E (X) + Y =j]
(135)
where
9,1 Σ PD (s)
ΣB. Br (EPa())
3j
R3 + B.uufoo
4j
f
n3 + (1 /
11 + (1
Rz
rEPa()
(136)
H.2 PROOF OF THM.
Theorem 4 (Recall). Consider the adversary setting that the calibration set Teal consists of nD
samples drawn from the benign distribution DD, while the new sample (X (Xn+1. Yn41) is drawn np, times from the adversarial distribution D.. Assume that A( Da) < 0.5 < A(fy, Db) for [Ne].
where A(ty, D) is the expectation prediction accuracy of fty on D. Then we have:
P[Yn-1 C (Xn+1)) > P| E e).
1- max (exp p-2nD, (0.5 A(t,, D D. +nmeexpl- 2np, ((A(f) Db) Dn) JE[No]
0.5) >
cE
(137)
where Pjo ID,, 1o [1) and Pj1 IP,, [rx=)) class probabilities benign distribution.
Proof of Thm. The following holds based on the definition of n1.00
ÔCOLEP (.) in Equation (8)
P Yu+1 & CCOLEP (Xn+1) IP S (Xu+1, 1) > Q1-a(1aaafaaeeea
[
aepuer (X,, Ip, Y, Mell
(138)
Similarly, the following holds for C.)a()).
P (Yut Cna(Xnnt)) TP [Sarau) (Xu+1, 1) Q1-a((Strmnp (Xi, (Xi:Tyx=Y+=ullez
(139)
We can transform the objective of comparison of marginal prediction coverage into comparison of non-conformity scores as follows:
P|Yn+1 E ACOLEP (Xn+1)) > P[Yn+1 E Cn (Xatil]
(140)
n,a
=P IP You! & CnoRRR
( (Xn+1)
& P YYr+ & (8n()n+1)]]
(141)
2P Supprer (Xn+1, S Sayne, (Xn+1,1))
(142)
IP (15agta 4x=
(143)
Next, we individually bound the probability formulation in Equations 142 and (14
Case (1): to bound
Saperr (Xa+1, 1) S Say.e, (8]+1.1).. w+1
We first compute E Sagure (Xa+1, 1) Sky, (Ru+1, 1) and then leverage tail bounds to derive
the lower bound the probability formulation.
Case (la): +-) correctly classifies the sample Xn41 ~ Dd (with probability A( (ity..1)) (.),,,))))) Da)). Since we assume Cj.,DD > 0 for E [Ne], c E {0, and D E {Da, Dz}. #COLEP (Xn+1) also correctly classifies the sample X.+1 Ds, and thus, we have the following:
B Saguurr (8n+1, 1) - Say (Xn+1,11)
E
COLEE "Ynts
(Xn+1) &yam (8ati))
(144)
32

---

Published as a conference paper at ICLR 2024
Case (1b): 4t (.) wrongly classifies the sample Xn+1 (with probability 1 A(fxx. (a)). We have the following:
B aqpues (X - SaY.es (Xnt1, 1) -
COLEP Yat1
(Xu+1) - 2 nrntt (8 (Xx+1))
"
(145)
Combining Equation (144) in case (la) and Equation
145) in case (lb), we have:
E Sagurs (Xa+1, 1) SRY (x++1.1)
(146)
<(A(frnn (), - 0.5) AooLer (Xx+1) - fya. (Xntz) (1) -..5)e)
6..
(147)
Then from Equation (147). the following holds by applying Hoeffding's inequality.
Securs (Xo+1, 1) SEr, (Xn+1, 1) > 0f < exp { -2np. (A(#x.+; (), - 0.5) 1..
(148)
Therefore, we have:
Seperr (Xn+1; 1) S Sayn4a (Xn+1.1) 2 1 21-exp ( 0.5) ") 1..
I.
(149)
Case (2): bound
QI (Xx, MIl 2 QQi (X,, Ip; .. I.ET
We first consider an individual sample (X,, Yi) and then apply the union bound the quantile.
Similar to case (I), first derive the bound for the expectation of the difference of non-conformity scores:
E
S +gguer
(Xi, (x=+41)) - Savnia (Xo, (x Yuu1 2(A(ft..)))))))))) 0.5) 1.DD,
(150)
E Suguer (X,, (x) Sarnes (Y=, IY = (AA(f),,)()DD)) 0.5)
1.P%
((++1)
(151)
Then with Hoeffding's ss inequality and the union bound, we have:
(19 (X,, I xx 2 QQiaa((Say, (X (y
(152)
21 no, exp { 2nr, ((A(fr,, (),.)) 0.5) Σ Pjeer. p...r. cE(1.))
where Pyo Pp. [g] and Pj1 IP,, []] are class probabilities on benign distribution.
Combining Equations 149h and 152 and plugging them into Equations (122) and (143). finally get:
p P[Yn+1 E ÓCDLEP (Xn+1)) PP (n.a(Xn+1))
21 exx {
2np, (A(fty,, (-), Da) 0.5) (.
nD, exp 2nD, ( ((A(Ty.4) (),D)) 0.5) Σ PjcCYmmi.eDD.
cE(0,1}
(153)
exp { -2nD, (A (). 0.5)² 2
> max Je[N.]
+ ND, expl { 2nDD ((A(fr... (b) - -0.5) Σ
Pjcer P.
cE(0.1)
33

---

Published as a conference paper at ICLR 2024
H.3 PROOF OF THM. 5
Theorem 5 (Recall), Suppose that we evaluate the expectation of prediction accuracy of # (.)
and (-) on samples drawn from Dm and denote the prediction accuracy as A A (.), Dm)
and A (R)(), Pm.. Then we have:
A(a) (-), Dm) 2 A),,(), w.p. 1- E PD Σ
PD = = ex (-2m(E),..)))
De(Pe:Do) cE(0,1)
(154)
Proof of Thm. S We can formulate the accuracy of ât(()) on Dm as:
A( mm) = P(Y * (X) < 0.5|Y # + P|Y -)P( 2 0.5|Y = (155)
Similarly, A A( (-), mm) can be formulated as:
A(#5OLE (.), = IP(Y * || (x) <.5 # j] + P|y = j| (X) 2 0.5 =
(156)
Let A,() == #COLEP (.) - t,).) From the results in Lemma 5.1 we have ( Y * j] -
=,,,,D and E E (X) = =-] 1,1,D. Note that we have 6,0,D > 0 and 1,I.D > 0 by assump- tion.
Then by rearranging the terms and Hoeffding's 's inequality, we can derive as follows:
Pla (X) , (X) 0|Y イ -P|A, > OJY +
(157)
=P|A, (X) - -
(158)
(X) - [X), EjO,D Y *
(159)
<exp (22c
(160)
Similarly, we consider the case conditioned on = j.
P COLLE (X) - -x;(x)xxx)-))))) < 0
= (X) < O/Y =j]
(161)
=P[A - E[A, < -XIA(
(162)
<P|A, - [XA] -EE,I Y j]
(163)
<exp 1 2nc,
(164)
Note that from Equations 160 and 164 we have the following relation:
P [A(# (.), Dm) A(ft( Dm) 20]
(165)
<P [ COMRP (X)- (X) 0 Y # +1++Ply 1|1P14500PP (X) -X) xx)
-
0|Y = j]]
(166)
Y cxp { -2m Ply = أ exp { 22c
(167)
Finally, by considering both the adversarial distribution and benign distribution, we can conclude that:
IP( (P(A(15Om (a5oTo (.), Dm.) Pm)))
Σ PD
Σ PD jxexpp {- 2n 2n(Ejj,
DE(D.,D.) cE(0.1)
(168)
I LOWER BOUND OF A(AÇOLER D,m)
Theorem 7 (Lower Bound of Alaqouee Dm))). Let E = ED.,, (X) d) for
d (0, 1}. Assume that the class probability computed by the r-th PC #COLEP conditinally
34

---

Published as a conference paper at ICLR 2024
independent of "j,-- for 2 2 - R and 2,0 ",,0 < 0.5 < j.1 E,T Assume that aggregate PCs
by taking the average (i.e., 3, R/R.. Then have:
A(*5 (mm) 1-1 * exp { -3 55,0 // --PlY P(Y 5] jjexp (3((E -0.5) /m5)
(169)
Proof sketch. We construct sequence {J.],R_ in specific way and prove that it is super- martingale or martingae with bounded differences conditioned based on the true label. Then Azuma's inequality to bound the objective A(#5OLEP, Pm)) in different cases and combine them with union bound.
5.1 indicates that better utility of knowledge models and implication rules can indicate a smaller _,,0 and larger 3,1 which can further imply a tighter lower bound of prediction accuracy according toThm. 7 Furthermore, according to the proof, we know that 3,0 1 negatively correlates with the number of PCs It and E has positive correlation with R, indicating that more PCs (i.e., knowledge rules) implies a better prediction accuracy.
Remarks. Lemma
Proof Thhm.
7 Consider R PCs. We construct a sequence (J,) such that Jx(X) =
(4) Eyerr " (X), where a(0)( (.) is defined Equation (24).
We first consider the case conditioned on Y # j. Without loss of generality, assume that # (x) 2
# (2) (X) 2 .... 2 $ (R) (X). Then we can prove {Jr) R is super-martingale since we have the
following:
r+1
Jo41 - Jr
(9) (X) - Σ - (X)
(170)
9=1
(r+1) (X) r(( + Σ (9) (X)
(171)
r ++ 1
q=1
(x++) (x)
r3 (r+1)
(X)
(172)
++1
r(r
<0
(173)
(J,]R also has bounded difference since have the following:
++
J Jr+1
#
(X)
Σ
# (X)
(174)
r
r
9=1
-=1
1
(1+1)
(X)
r 1 #
(X)
(175)
r(r +1)
++1 G+1
(176)
Also note that we have:
E (X)))))) (,())
r+1 - J((X
1+1* #
1
(r+1))
(177)
35

---

Published as a conference paper at ICLR 2024
Therefore, (J,) is conditionally independent. Then by using Azuma's inequality, derive as follows:
(0.5 E(
P - E[JA] 2 0.5 - E[JA]] eexp
(178)
2 9=1 %
(0.5 B[Jnl)
<exp
(179)
2 2 n
1²) q
(a)
(0.5 B(Jnl)2
S cxp
(180)
2 π
6
3(0.5 )2
S Sexp
(181)
T²
Inequality (a) holds because the inequality Σx11
Rt
1 q3
<
x²
holds. Finally, the following holds.
3(0.5 E[JR))
P[Ja(X) < 0.5 1 0 exp
(182)
x²
Then consider the case conditioned on Y = j. Similarly, construct sequence {JA) such that (X) = r - a(0) (X), where # ( (-) is defined as Equation (4). Without loss of
generality, assume that # (x) S # (X) S ... S # (R)
(X). Then we can prove {JA) is
sub-martingale since we have the following:
1/41 J
(X) Σ
3j
(9)
(X)
(183)
1
q=1
q=1
#1
(r+1))
(X)
(X) r(r + 1) q
(0) (X) (X)
(184)
r ++1
++1 "
1
(x+1)
(X) r(r + 13
(r+ (X)
(185)
20
(186)
Again, we can show that (J)R has bounded difference:
r+1
J/+1 J.
Σ
+ 1 (X)
(9)
Σ (X)
(187)
r
q=1
9=1
r+1 "1
(r+1) (X)
r(r + 9=1
オ
(4) (X)
(188)
= c++1
(189)
r+1
Also note that we have:
E (xX)
(((X) (r+1)
(X)
(190)
r+1
r r+
36

---

the attack objective of Published as a conference paper at ICLR 2024
Therefore, (JA) is conditionally independent. Then by using Azuma's inequality, derive as follows:
(E - 0.5)
P E[Ja] S 0.5
E[JA]] Sexp
(191)
2 2 R (cg)
[B|J&l 0.5)
- exp
(192)
2 2Σ 9
1)
(R[J') 0.5)
S cxp
(193)
π 2 2
6
3((E 0.5)
Sexp
(194)
Finally, the following holds.
3(E[Jnl 0.5)²
P[Ja(X)= 0.5 Y = exp
(195)
π²
Note that we formulate A( Dm)) as:
A COLER Dm) = PIY + j| (X) < 0.5 + + +P | COLEP (X) > 0.5 =
(196)
Combining Equations 182 and 195). we have:
A(a) A(RCOLEP (m)) 2 1-P + exp
3(0.5 E ELOLEP )²/ /
-PPY /
5] exexp -3((E,,000 0.5)) /
(197)
J EXPERIMENT
J.1 IMPLEMENTATION DETAILS
Dataset & Model. We evaluate COLEP on three datasets, GTSRB, CIFAR-10, and AwA2. GTSRB consists of 12 types of German road signs, such as "Stop" and "Speed Limit 20". CIFAR-10 includes 10 categories animals and transportation. AwA2 contains 50 animal categories. We use GTSRB- CNN architecture (Eykholt et al., 2018), ResNet-56 (He et al., 2016). and ResNet-50 (He al.) 2016) as the architecture of models on them, respectively. For fair comparisons, we use the same model architecture and training smoothing factors for models in COLEP and SOTA baselines CP and RSCP. We perform smoothed training (Cohen et al.) 2019) with the same smoothing factor for models. We use the official validation set of GTSRB including 973 samples, and randomly select 1000 samples from the test set of CIFAR-10 10 and AwA2 as the calibration sets for conformal prediction with the nominal level the test set of GTSRB and the remaining samples of the test set of CIFAR-10 and GTSRB. GTSRB and CIFAR-10 10 contain images with the size of 32 32. AwA2 contains images with the size of 224 x 224. GTSRB and CIFAR-10 are under the MIT license. AwA2 is under the Creative Commons CoabuutionnNonCComerriiiiii Alkee (CC BY-NC-SA) license.
0.9 across evaluations. The evaluation is performed on
Implementation details. We run evaluations using three different random seeds and report the averaged results. We omit the standard deviation of the results since we observe they are of low variance due to a large sample size used for calibration and testing. All the evaluation is done on a single A6000 GPU. In the evaluation of certified coverage, we compute the smoothed score or prediction probability 100, 000 times for randomized smoothing and fix the ratio of perturbation bound and the smoothing factor during certification 8/0... as 0.5 for both RSCP and COLEP. In the evaluation of marginal coverage and set size under PGD attack,
37

---

Published as a conference paper at ICLR 2024
cross-entropy loss for RSCP. For COLEP, the objective is the same cross-entropy loss for the main model and the binary cross-entropy loss for the knowledge models.
Knowledge Rules & Reasoning. In summary, we have 3 PCs and 28 knowledge rules in GTSRB, 3 PCs and 30 knowledge rules in CIFAR-I0 10, and PCs and 187 knowledge rules in AwA2. Based on the domain knowledge in each dataset, we encode encode a type of implication knowledge with disjoint attributes. In GTSRB, we have a PC of shape knowledge (e.g.."og "octagon", "square"), 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 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"), PC of appearance (e.g., "big ears", "small eyes"), and PC of fur color knowledge (e.g., "green", "gray", "white").
of implication rules into PCs. In each PC, we
For example, in the PC of shape knowledge in GTSRB, we can encode the implication rules related to the shape knowledge such as IsStopSign = IsOctagon (stop signs are octagon) with weight w1. IsSpeedLimit = IsSquare (speed limit signs are square) with weight w2, and IsTurLLeft = IsRound (turn left signs are round) with weight W3. To implement the COLEP learning-reatt 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₂ class labels and L. concept labels (e.g., p(IsSpeedLimmi = 1) M.p. p (IsSquare = 1) Aag). (2) We compute the factor value F(u) for any possible assignment μ {0, 1) N.N+ as F(R) = =xp Wnll
11) = e twg since the assignment satisty all three knowledge rules above). (3) We construct 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 and the constant factor values of assignments (e.g., B(Asp), B(1 Hap), =f B(1 *x,),.., F(1, 1, OJ), 1,,,,,1,111 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 (c.g.. Tap X fug x x F(1,, 1, 1, 1, 1, IJ)). and (c) the top layer is sum node computing the summation of the products. (4) We linearly
combine multiple PCs that encode different types of knowledge rules (c.g., 3 PCs in GTSRB: PCs of shape/color/content knowledge). We compute 34 based on the utility of the k-th PC on the calibration set and manually set the weights of knowledge rules based on their utility.
Codes are available htttts::/g http:///wt......oooo/aooo///o/a/ http:///ww....oooa/mnnntttto///a
J.2 ADDITIONAL EVALUATION OF COLEP
Table 1: Comparison of the runtime (millisecond) of COLEP per forward time between a standard model and COLEP. The evaluation is done on RTX A6000 GPUs.
GTSRB
CIFAR-10
AwA2
standard model COLEP
13.2
15.5
35.2
13.5
15.7
35.6
Visualization of the contribution of different knowledge rules. 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 Appendix J.I. We provide the visualization of contributions of different types of knowledge rules in Figure The results show that the rules related to the color knowledge in GTSRB and space knowledge in CIFAR-10 benefit the certified coverage more, but collectively applying all the well-designed knowledge rules leads to even better coverage. The effectiveness of these types of knowledge attributes to higher utility of the knowledge models (i.e., the accuracy of concept detection). Concretely, the feature of these concepts is relatively easy to learn and can be more accurately detected (e.g., color concepts 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
38

---

Published as a conference paper at ICLR 2024
0.05
0.04
0.04
0.03
0.03
0.02
0.02
0.01
0.01
Shape
Color
Content
All
Category
Space
Feature
All
GTSRB
CIFAR-I0
Figure 5: Certified coverage of COLEP under bounded perturbation å = 0.25 on GTSRB and CIFAR- 10 with different types knowledge rules.
Runtime evaluation of COLEP. Since the knowledge models in the learning component are simple neural networks and can perform forward passes in parallelism. the additional computational com- plexity of COLEP comes mainly from the overhead of the reasoning component (i.e., PC). Given PC defined on the directed graph (V, E), the time complexity of probabilistic inference is O(V)). according to the details illustrated in Appendix C.I Therefore, the additional time complexity of COLEP is ((V))) linear to the number of nodes in PC graph. We empirically evaluate the runtime of a forward pass of COLEP and compare it with a standard model. The results in Table show that COLEP only achieves little higher runtime compared with single standard model.
Table 2:
Marginal coverage average set size of RSCP and COLEP under AutoAttack with & bounded perturbation of 0.25 on GTSRB, CIFAR-10 10, and AwA2. The nominal level a is 0.9.
GTSRB
CIFAR-10
AwA2
RSCP
0.9682 / 2.36
0.9102/3.55
0.923 / 5.98
COLEP
0.9702 2.13
0.9232/2.5
0.952 4.57
Table Marginal coverage average set size of RSCP and COLEP under PGD Attack with multiple desired coverage levels 1 with & bounded perturbation of 0.25 on GTSRB.
1 - = 0.85
1 - = 0.9
- a 0.95
RSCP
0.9029 1.63
0.9682 / 2.36
0.9829 / 2.96
COLEP 0.9053 1.34
0.9702 2.13
0.9859 / 2.53
Evaluations with difffernt types of adversarial attacks. To evaluate the robustness of COLEP under various types of attacks, we further consider the AutoAttack method [Croce & Hein (020)) which uses an ensemble of four diverse attacks reliably evaluate the robustness: (1) APGD-CE attack, (2) APGD-DLR attack, (3) FAB attack, and (4) square attack. APGD-CE and APGD-DLE 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 a query-efficient black-box attack. We evaluate the prediction coverage and averaged set size of COLEP and SOTA method RSCP with l bounded perturbation of 0.25 GTSRB, CIFAR-IO, 10, and AwA2. The desired coverage - a = 0.9 the evaluation. The results in Table 2 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.
Evaluations with various nominal levels. We further evaluate COLEP with multiple nominal levels of coverage 1 a. We provide the results with multiple coverage levels 1 in Table 3 The
39

---

Published as a conference paper at ICLR 2024
results demonstrate that for different parameters of a, (1) COLEP always achieves 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.
Selection of weights of knowledge rules. 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 TtitopSign = IsOclagon should be useless and assigned with 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 searching. The results inspire to fix as 1.5, and the evaluations demonstrate that it is sufficient achieve good robustness in different settings. One can also model the weight selection problem as a combinatorial optimization, which is non-trivial but better unleash the power of COLEP. We leave more intelligent and automatic approach of knowledge weight selection for future work.
K OVERVIEW OF NOTATIONS
In this section, we provide overviews of used notations for better understanding of the analysis of COLEP. Specifically, we provide an overview of notations related to models in Table 4 notations related to conformal prediction in Table 5 notations related to certification in Section in Table 6 and notations related analysis in Section in Table
Table 4: Notations related to models in COLEP.
Notation
Meaning
N.
number of class labels
j
E [N.] to index outpul of the main model
L
number of concept labels, number knowledge models
E [L] to index I. knowledge models/concept labels
(x)
the output likelihond the main model for the j-th class lahel (j E [Na)) given input a: the output likelihood of the I-th knowledge model (1 E [4] given input
(a())
:= [لي]]ر||N N..p [+(1) [t((4)] E NeNe concatenated vector of class and concept prohabilities jv E [N + L) to index (the concatenation the output of the main model and concept models)
de
(a)
the output likelihood the j-th class label (iy & [N₂ + LJ) before the reasoning component
so (x)
the output likelihood of the j-th class label (j E [Na]) after the reasoning component
(KO)
II propositional logic rules
wh
the weight of the h-th logic rule (h {H))
Ig
indicator function
# M (0, 1) NotL, the index variable the feasible assignment set M F(u) exp <> W/ factor value of the ussignment j
Flu)
T(a.b) 6)
T(a, b) == log ab + a)(1 b)), introduced for ease of notation
Opet. Opoek
leaf node and root node in the PC
R
number of prohabilistic circuits coefficient the r-th PC
r [R index the r-th PC
40

---

Published as a conference paper at ICLR 2024
Table 5: Notations related conformal predictions.
Notation
Meaning
n
number calibration data samples i-th data sample with input X; and label V; (i E [n|)
Vi)
(Xu+1. Yn-1)
the test sample
label space [N,] := {1, 2..., N.....,.. No}
E y to index labels in the label space y
random variable draw from uniform distribution U(00) 1)
Qi-a
a quantile value
(1( v)
APS non-conformity score of sample (z. y) given probahility estimate * APS score with &CLLEP (output likelihood of the j-th class label after the reasoning component)
S Da (2)
(2)
Cra(z) (x) C V is the conformal prediction set of input æ without COLEP
OROLEE (2))
Chatae (ar S {0, 1] is the conformal prediction set the j-th class label
CCCLiE (2))
R.a (æ) S y is the conformal prediction set of input with COLEP
9"
9b {0, index in label space {0, 1}
Table Notations related to certification in Section
Notation
Mcaning
(yy (ar
upper bound of (ar) (likelihood without reasoning component) with bounded perturbation lower bound of (,) (ar) (likelihood without reasoning component) with bounded perturbation upper bound of #/OORR (a)) (likelihood with reasoning component) with bounded perturbation
(ar)
kemkae (x)]
L My
SOURE (x)
lower bound of aboure
Ry (x) (likelihood with reasoning component) with bounded perturbation
V
index set conditional variables (left operand of rule A = index set conditional variables (right operand of rule =
B) the PC except for B) in the PC except for
V
the j-th element of assignment 1 adversarial perturbation
5 Xa+1
bound of perturbations such that ||<||2 s 5
X,+1 X,+1 adversarial test sample certified prediction set with perturbation bound 8
ÓCOLEE (Xn+1)
worst-case non-conin con-conformity score for the j-th class label with bounded perturbation 8 lower bound of the coverage guarantee within bounded perturbation
COLEE DOURB
lower bound of the coverage guarantee the j-th class label within bounded perturbation
Table 7: Notations related to analysis in Section 5
Do
benign data distribution adversarial data distrihution mixed data distribution portion distribution 2D D...
Dm
Pr G. (V) (,()v)
undirected graph encoded with rules in r-th PC node set connected components of node jv in graph node set of conditional variables connected components node Jy in graph G, node jv graph G. boolean vector ground truth class and concepts given sample i as input the threshold of confidence for the ju-th label probability matching this threshold for the jy-th label
Analiv)
Aralr))
node set of consequence variahles connected components
v(x)
1,,00
multiplication of f the r-th PC
2
multiplication of 2jv.D p the r-th PC the set of PC index where j appears conditional variables and consequence variables
Pa(i). P.()
utility of associated knowledge rules within the r-th PC for the j-th class characterization of probability correction by COLEP conditioned on ground truth label 0 and 1 f, E (xx,r)==(55,ole,
9,044
65,0,D
0,, expectation of 6j,0
611.D
E B(x,r)=ole u 1 expectation of 65.1
A(R,D)
accuracy of probability estimator data distribution D
41


Reviews:
[{"review_id": "CnUdC79aFk", "reviewer": "Reviewer_TP2m", "summary": "COLEP is a learning-reasoning framework for conformal prediction that provides improved certified prediction coverages under adversarial perturbations. The framework is composed of a learning/sensing component followed by a knowledge-enabled logical reasoning component. The learning component consists of several deep learning models while the reasoning component consists of one or more probabilistic circuits. Alongside the main classification task, the deep learning models are used to predict and estimate the probabilities of other concepts in the input e.g. shape, color etc. The PCs in the reasoning component encode domain knowledge specified as propositional rules over the class and concept variables and helps to ensure robustness against $\\ell_2$ bounded adversarial perturbations to the input variables. The experiments show that COLEP achieves higher prediction coverages as well as smaller prediction set sizes compared to other SOTA methods.", "questions": "1. How many PCs were considered in each of the experiments? Can the authors give an idea on the complexity of the PCs? \n\n2. Can the scope of the evaluation be extended to include the performance of COLEP against  other forms of adversarial attacks? \n\n3. Why wasn't the effect of varying the parameter $\\alpha$ and $\\rho$ on COLEP's performance analyzed?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper presents a novel idea to improve certified robustness of conformal prediction using deep learning models. To the best of my knowledge, this is the first work on using tractable probabilistic circuits to improve the coverage of conformal prediction.\n   \nA positive side of the work is its theoretical analyses. The authors have derived certified coverage for COLEP under both $ell_2$ and finite calibration sample size. And then show that COLEP received higher certified coverage compared to a single model. \n\nExperimental results are also promising.", "weaknesses": "The manuscript is strong overall, but there are areas where it could benefit from further elaboration and additional empirical support. \n\n1. The reasoning part seems to be missing significant details to understand how the PCs are working together to reduce the error produced by the main classifier. The paper makes a strong assumption that the reader will be familiar with semantics of PC structures. There should be some brief introduction to these models. \n\n2. The leaf weights (factor weights) are assumed to be prespecified and then there are also the Bernoulli parameters estimated by the neural networks.  It is unclear how these estimated parameters, predictions (classes and concepts) and user defined knowledge rules are combined together to make robust decisions. The coefficients of the component PCs $\\beta_k$ should be more clearly specified in the main manuscript.  \n\n3. The theorems in the main paper need a more detailed discussion. Having only a short paragraph for each theorem doesn't fully explain the complexities and nuances involved, which doesn't give the paper's theoretical contributions their due.\n\n4. To make the empirical evaluation stronger, the authors could consider using more datasets or testing against different types of attacks. This will help confirm that COLEP is robust and works well in various situations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ElAWKNaPAF", "reviewer": "Reviewer_MM5a", "summary": "The authors applied conformal prediction to a conformity score incorporating logic reasoning based on prior knowledge graphs and demonstrated that the resulting prediction intervals achieved desired coverage while being narrower compared to RSCP on three real data sets under l2 norm perturbations.", "questions": "1. Is the F(mu) prefixed function with H rules? Is mu observed only for the training? (the knowledge graph encodes the relationship between, e.g.,  \"stop\" and shape info, but the goal is to predict if it is a stop sign).  I am confused about how pi_j(x) is calculated when mu is unknown.\n\n2. It seems that the gain of COLEP originates from utilizing the prior knowledge graph through F(u) and u: The knowledge graphs incorporated are side information with both the graph relationship and u remained true against attacks. How robust does the method perform against contaminated graphs/u?\n\n3. Is it easy to calculate max|η|2≤δ ˆ πj (x + η) and min|η|2≤δ ˆ πj (x + η) for general probability assignment function pi_j(.)? The two main Theorems are from a brute-forth search of the worst-case scenario under perturbations, which are intuitively correct but it seems more important to show the feasibility of achieving this for general functions.\n\n4. How are the weights w chosen in F(mu)?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The authors adapted conformal prediction to a new scenario where a reliable knowledge graph is available and showed empirically that incorporating this side information can improve the efficiency of conformal predictions.", "weaknesses": "See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qYuuPIGYo4", "reviewer": "Reviewer_GJ8Z", "summary": "The paper offers a new construction for a conformal prediction pipeline that offers guaranteed coverage both in the exchangeable and in the adversarial perturbations case, and generally should offer improved adaptivity and set size whenever domain-specific learning-reasoning rules are provided. The main new component is the integration of probabilistic circuits into the construction of a nonconformity score of the APS (Romano et al) type, where an underlying model's class probabilities output is postprocessed according to a collection of reasoning rules, which help correct each class's predicted probability before plugging it into the APS score. The benefits of the reasoning components are investigated theoretically, by means of a theorem stating that under some assumptions marginal coverage will be strictly better with than without these components, as well as experimentally over three datasets and compared to two benchmark conformal method (one with adversarially robust guarantees).", "questions": "1. The experimental section needs strengthening; please see above for suggestions/guidelines on directions.\n2. In discussing experimental results, it is of especial interest to discuss which learning-reasoning components were used in each domain. Other details are quite standard and common in the conformal literature, but this one is novel and thus should be propagated to the main part rather than left in the appendix. The current running example is the stop sign example, but it would be very useful to have a walk-through of how the rules were implemented in actual experiments.\n3. In the same vein, right now the experimental part only features plots of standard metrics (coverage, set size, ..) Meanwhile, I would like to see a visualization of what the learning-reasoning components do to the predictions of the underlying model --- e.g. which rules turned out to correct the initial estimates by the largest amount, etc.\n4. Notation needs to be significantly improved and clarified to achieve readability.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper essentially constructs a novel type of score for conformal prediction; rather than the simple softmax layer-based constructions of some recent nonconformity scores like APS and RAPS, the idea here is to take such a softmax output from e.g. a neural net and, using domain specific learning-reasoning rules, postprocess each individual class's predicted probability to become appropriately corrected, and only then use them in an APS score-like fashion.\n\nThese corrections imply both the robustness properties (at least to l2 perturbations), as well as offer (subject to mild assumptions) theoretically guaranteed improvement over just using the underlying model's softmax outputs.  It is also more generally easy (as the authors show) to propagate estimation uncertainty through the learning-reasoning pipeline. This type of provable guarantees is, to my knowledge, novel and has not come up in the conformal literature before.\n\nMoreover, the proposed technique is more flexible than standard conformal prediction, in that it can provide guarantees not just over all classes, but also for each class separately (at its own coverage threshold).\n\nThese above technical innovations, as well as the practical potential of learning-reasoning components to improve domain-specific performance of conformal prediction, lead me to conclude that the proposed paper would be a novel and interesting addition to the conformal literature.", "weaknesses": "1. Empirical evaluation is quite limited, which is quite unfortunate given that including more settings beyond datasets as simple as CIFAR-10, as well as more benchmarks, would likely let the guarantees afforded by the learning-reasoning setup shine even more: both in terms of the ability to construct rules specific to each considered setting, as well as the resulting adaptivity compared to other conformal scores/methods.\n\nRelevantly, I was quite confused when the authors repeatedly call the APS score of Romano et al (2020) 'SOTA'. It is certainly one of the existing reasonable conformal approaches to use, but by no means state of the art when it comes to adaptivity and especially set size. For instance, its generalization and improvement, the RAPS nonconformity score introduced in \"Uncertainty Sets for Image Classifiers using Conformal Prediction\", may still be considered close to the SOTA frontier for many domains --- and it would be very pertinent to include it, along with further improved conformal methods developed thereafter. Also, CIFAR 10 not quite sounding like the natural domain to apply potentially highly complex learning-reasoning boosts, it'd be wise to show the performance of the framework on Imagenet; as a byproduct, it would help me convince myself of the tractability of useful learning-reasoning in more challenging settings. In any case, having just three relatively simple datasets and only two comparison methods, Romano et al and Gendler et al, appears insufficient to fully explore the relative advantages of learning-reasoning.\n\n2. The main other weakness to me is the overbearing nature of the notation used, and the overall presentation. It took me many hours to internalize the type of the guarantees that learning-reasoning components lead to, and even the notation itself. Moreover, especially the multi-subscript-superscript notation involved in both theorem statements and proofs related to the learning-reasoning component was very hard to parse and even read. The notational review in the last appendix was a nice touch, but only marginally helpful as it only listed some of the relevant notation; Diagram in Figure 4, describing the overall certification flow, also felt confusing and didn't really help, making me resort to understanding text only. Instead of structured definitions of the main notations and concepts (using appropriate latex environments), everything was crammed into the paragraphs, thus diluting the structure of the presentation and making it hard to backtrack to the context in which a piece of notation was originally defined.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0yEpC0S4cn", "reviewer": "Reviewer_qYpF", "summary": "This paper introduces COLEP a certifiably robust learning-reasoning conformal prediction framework. Authors leverage probabilistic circuits for efficient reasoning and provide robustness certification. They also provide marginal coverage guarantees using conformal prediction methods. Finally, by performing several experiments, they highlight the relevance of their proposal.", "questions": "Why is COLEP better suited to conformal prediction than already existing methods?\n\nWhat does \"certified conformal prediction\" mean? Is this different from saying that we have a marginal coverage guarantee?\n\nThe paper claims that it achieved \"a certified coverage of COLEP\" but, for example in Figure 2, the coverage obtained with COLEP is well below 0.9. Can you explain this in more detail?", "limitations": "", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "First, I would like to make it clear that this paper is not in my area of expertise. That is why I had some difficulty understanding it. However,\n\n1) the contributions of the paper seem to be significant.\n\n2) experience suggests that COLEP is competitive with previous work.", "weaknesses": "The paper is very dense and difficult to read.\n\nCitations are not appropriate. For example, in the related work on conformal prediction, the first sentence mentions articles from 2021, and the seminal articles, notably by Vovk and others, are not cited.\n\nThere is no \"limitation\" in the conclusion. This section should be added.\n\nMinor:\n\n\"with the guarantee of marginal prediction coverage:...\" the inclusion should be a $\\in$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oJh6LLL4zX", "reviewer": "Reviewer_nQJc", "summary": "The authors propose conformal prediction sets that are robust to adversarial perturbations -- they maintain the nominal coverage for any perturbed input in the threat model. The main idea is to leverage a learning-reasoning component which can improve the worst-case bounds on the predicted conditional class probabilities. Constructing the prediction sets using the worst-case scores derived from the worst-case (corrected) class probabilities yields adversarially robust coverage.", "questions": "1. How does COLEP perform when accounting for finite-sample errors when estimating randomized smoothing expectations?\n2. In section 3 you have \"assume that the data samples are drawn i.i.d. (thereby exchangeably)\". Is the i.i.d. assumptions necessary for the learning-reasonig component, or can this be relaxed to just exchangeability as with vanilla CP?\n3. Is the PGD attack adaptive, i.e. takes the reasoning component into account?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "In terms of originality, the approach can be seen as the clever combination of two main ideas:\n- improved worst-case bounds on the class probabilities using a reasoning component\n- using worst-case bounds on the conformity scores to get robust sets \n\nBoth ideas have been explored in the literature, but their combination leads to improved results. Specifically, more efficient (smaller) sets compared to RSCP while having the same guarantee, and larger worst-case lower bound.\n\nThe technical and theorethical components of the paper are sufficiently detailed and rigorous. Theorem 3 can be seen as a generalization of Theorem 2 by Gendler et al. The analysis in Section 6, while making stronger assumptions, is interesting and shows when we can expect improvement.\n\nThe exprimental results are expected since the derived bounds are tighter.\n\nThe contribution is significant, as is the improvement over the previous SOTA.", "weaknesses": "While the authors do consider the finite-sample error induced by the finite size of the calibration set, they fail to account for the finite-sample error due to the Monte-Carlo sampling (they use 10000 samples) when estimating the expectations under the randomized smoothing framework. Therefore, the resulting sets are only asymptotically valid.\n\nAs pointed out by a concurent ICLR submission (https://openreview.net/forum?id=BWAhEjXjeG) RSCP also suffers from the same issue and it is non-trivial to correct for this. The same issue is also discussed among the reviewers and the RSCP authors on their respective openreview page (https://openreview.net/forum?id=9L1BsI4wP1H). Naively, one would have to apply a union bound over all examples in the calibration set and the test example such that each of the randomized smoothing expectations hold simultaneously. There is also a subtler alternative solution. When correcting RSCP for this error the resulting sets end up returning all labels, i.e. they are useless. It is not clear to which degree COLEP suffers from the same issue. In any case, the \"fix\" proposed by the concurent submission is orthogonal and can be applied to COLEP as well. Still, this finite-sample issue needs to be addressed in the paper, especially given that the goal is to produce a sound certificate. \n\nThe second weakness is in the PGD attack. The authors state \"For fair comparisons, we apply PGD attack (Madry et al., 2018) with the same parameters on CP, RSCP, and COLEP\". However, it is unclear whether the PGD attack is adaptive, i.e. it takes the learning-reasoning component into account. An adaptive attacker can in fact know that a reasoning component is used, and thus can try to perturb the input such that both the class and the concept probabilities are suitably changed as to fool the entire pipeline. While this is not critical, not using adaptive attacks makes the conclusions drawn from Figure 3 less reliable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)