Improving Certified Robustness via Statistical Learning with Logical Reasoning
Authors: Zhuolin Yang
Zhikuan Zhao
Boxin Wang
Jiawei Zhang
Linyi Li
Hengzhi Pei
Bojan Karlaš
Ji Liu
Heng Guo
Ce Zhang
Bo Li
Venue: NeurIPS 2022 Accept (2022)
Keywords: certified robustness
logical reasoning

Abstract: Intensive algorithmic efforts have been made to enable the rapid improvements of certificated robustness for complex ML models recently. However, current robustness certification methods are only able to certify under a limited perturbation radius. Given that existing pure data-driven statistical approaches have reached a bottleneck, in this paper, we propose to integrate statistical ML models with knowledge (expressed as logical rules) as a reasoning component using Markov logic networks (MLN), so as to further improve the overall certified robustness. This opens new research questions about certifying the robustness of such a paradigm, especially the reasoning component (e.g., MLN). As the first step towards understanding these questions, we first prove that the computational complexity of certifying the robustness of MLN is #P-hard. Guided by this hardness result, we then derive the first certified robustness bound for MLN by carefully analyzing different model regimes. Finally, we conduct extensive experiments on five datasets including both high-dimensional images and natural language texts, and we show that the certified robustness with knowledge-based logical reasoning indeed significantly outperforms that of the state-of-the-arts.

Improving Certified Robustness via Statistical Learning with Logical Reasoning
Zhuolin Yang
Zhikuan Zhao
Boxin Wang UICC
UICC
ETH Zürich zhikuan, zhao@inf
2huolinSeillinois.com
ethz. www.eeinf.ettee.ccmmmmmeee
boxinv201llinois. edu
Jiawei Zhang
Linyi UIUC liny:29illinois.edd
Hengzhi Pei UICC hpei4@illinoie edu
UICC jiaveiz7@illinois.eed
Bojan Karlaš
Ji Liu Kwai Inc. ji. uwisc@gmail...... com com
Heng Guo
ETH Zürich
University of Edinburgh
karlasb@inf eetz..ch
hguoßinf ed. ac. uk
Ce Zhang
Bo Li UIUC
ETH Zürich
ce zzang@inf........ ettz...h ch
lbo@illinois.edu
Abstract
Intensive algorithmic efforts have been made to enable the rapid improvements of certificated robustness for complex ML models recently. However, current robustness certification methods are only able to certify under limited pertur- bation radius. Given that existing pure data-driven statistical approaches have reached bottleneck. in this paper, we propose integrate statistical ML mod- els with knowledge (expressed as logical rules) as a reasoning component using Markov logic networks (MLN), bustness. This opens new research questions about certifying the robustness such paradigm, especially the reasoning component (e.g., MLN). As the first step towards understanding these questions, we first prove that the computational com- plexity of certifying the robustness of MLN is #P-hard. Guided by this hardness result, we then derive the first certified robustness bound for MLN by carefully analyzing different model regimes. Finally, conduct extensive experiments on five datasets including both high-dimensional images and natural language texts, and show that the certified robustness with knowledge-basse logical reasoning indeed significantly outperforms that of the state-of-the-ane
to further improve the overall certified ro-
Introduction
Given extensive studies on adversarial attacks against ML models recently 3 13 24
64
53
building models that are robust against such attacks is an important and emerging topic. Thus, plethora of empirical defenses have been proposed to improve the ML robustness [3 59
43 53
52]; however, most of these are attacked again by stronger adaptive attacks 3 [
[146] To end such
repeated security cat-and-ne aot-and-mouut mouse games, there a line of research focusing on developing certified
defenses for DNNs under certain adversarial constraints g 26
25
54
28
61
27
60 58)
"The first two authors contribute equally to this work.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Though promising, existing certified defenses are restricted to certifying the model robustness within a limited l, norm bounded perturbation radius [56 8 One potential reason for such limitations for existing robust learning approaches is inherent in the fact that most of them have been treating machine learning as a "pure data-driven" technique that solely depends on a given training set, without interacting with the rich exogenous information such as domain knowledge (e.g., a stop sign should be of the octagon shape); while we know human, who has knowledge and inference abilities, is resilient to such attacks. Indeed, recent seminal work (17) illustrates that integrating knowledge rules can significantly improve the empirical robustness of ML models, while leaving the certified robustness completely unexplored.
In this paper, we follow this promising Dearming+Reasoninn paradigm [17] and conduct, to our best knowledge, the first study on certified robustness for it. Actually, such Learning-Reaoom
paradigm has enabled a diverse range of applications [38 62 2 37
32 55 17] including the ECCV'14 14 best paper (10) that encodes label relationships as a probabilistic graphical model and improves the empirical performance of deep neural networks on ImageNet. In this work, we first provide a concrete Sensing-reace reasoning pipeline following such paradigm to integrate statistical learning with logical reasoning as illustrated in Figure [ In particular, the Sensing Component contains a set of statistical ML models such as deep neural networks (DNNs) that output their predictions as a set of Boolean random variables; and the Reasoning Component takes this set of Boolean random variables as inputs for logical inference models such as Markov logic networks (MLN) [40] or Bayesian networks (BN) 36 to produce the final output. We then prove the hardness of certifying the robustness of such pipeline with MLN for reasoning. Finally, we provide an algorithm to certify the robustness of sensing-reasoning pipeline and we evaluate it on five datasets including both image and text data.
However, certifying the robustness of sensing- reasoning pipeline is challenging, especially given the inference complexity of the reasoning component. Our goal is to take the first step in tackling this challenge. In particular, the robust- ness certification of consing-reasonin can be expressed as the confidence interval of the marginal probability for the final output of reasoning component. That is to say, we can use existing state-of-the-ar methods to certify the robustness of the sensing component that contains DNNs or ensembles 8 57 Thus, to provide the end-to-end certification for the whole pipeline, what is left is to understand how to certify the reasoning component, which is the focus of this work.
@ Connnol cortify Robesteess Cortifictts
Ceriified!
STOP
Improsse Kilumms Ceriifoooo
S
DS
Pyrer"
1102:101
S [160-100
Erepsige
2 JMJ5 1M1
pipeline
Pa 1.]
D
# 10.5 14
Seroing Compineat
Bessoning Corepanent
Stristioal Eeorning
Eagiont Recuoring
Aettrr Cortjioi
(Markee Eaglt Netuoeri)
The sensing- reasoning pipeline, i.e. sensing component consists of DNNs and a reasoning compo- nent is constructed as MLN. The goal of this paper is provide certified robustness for such pipeline, espe- cially the reasoning component.
Figure 1:
Compared with previous efforts focusing on certified robustness of neural networks, the reasoning component brings its own challenges and opportunities. Different from neural network whose inference can be executed in polynomial time, many reasoning models such as MI.N can be #P- complete for inference. However, as many reasoning models define a probability distribution in the exponential family, we have more functional structures that could potentially make the robustness optimization (which essentially solves a min-max problem) easier. In this paper, we provide the first treatment to this problem characterized by these unique challenges and opportunities.
We focus on MLN as the reasoning component, and explored three technical questions, each of which corresponds to a technical contribution of this work.
1. Is certifying robustness for the reasoning component feasible when the inference of the reasoning component is #P-hard? (Section 3) Before any concrete algorithm can be proposed, it is important to understand the computational complexity of the robustness certification. We first prove that the famous problem of counting in statistical inference [49] can be reduced to the problem of checking the certified robustness of general reasoning components and MLN. Therefore, checking certified robustness is no easier than counting on the same family of distribution. In other words, when the reasoning component is a graphical model such as MLN, checking certified robustness is no easier than calculating the partition function of the underlying graphical model, which is #P-hard.
2. Can we efficiently reason about the certified robustness for the reasoning component when given an
oracle for statistical inference? (Section 4.2) Given the above hardness result, we focus on certifying
2

---

the robustness given an inference oracle. However, even when statistical inference can be done by given oracle [2T] [8]. is still challenging to certify the robustness of MLN. Our second technical contribution is to develop such an algorithm for MIN as the reasoning component. We prove that providing certified robustness for MLN is possible because of the structure inherent in the probabilistic graphical models and distributions in the exponential family, which could lead to monotonicity and convexity properties under certain conditions for solving the certification optimization.
3. Can a reasoning component improve the certified robustness compared with the state-of-the-art certification methods? (Section 5) We test our algorithms on multiple in which the sensing components contain the state-of- tfae-of-thhe-rt deep neural networks. We construct these pipelines to cover range of applications including image classification and natural language processing tasks. We show that based on our certification method on the reasoning component, the wewwledgeeerrcchee sensing-reasoning pipelines achieves significantly higher certified robustness than the state-of-the- art certification methods for DNNs.
pipelines,
The rest of the paper is organized as follows. We will first introduce the design of the sensing- reasoning pipeline in Section 2.1 followed by concrete illustrations taking the Markov Logic Networks as an example of the reasoning component in Section 2.2 Next, to certify the robustness of the sensing-reasoning pipeline, especially for the reasoning component, we first prove that certifying the robustness of the reasoning component itself -omcoleeete (Section B), and therefore we propose a certification algorithm to upper/lower bound the certification in Section We provide the evaluation
of our robustness certification considering different tasks in Section S
2 Robust Statistical Learning with Logical Reasoning
In this section, we first provide a sensing-reasoning reasoning pipeline and then formally defined its certified robustness, and particularly links it to certifying the robustness for the reasoning component.
2.1 Sensing-Reasoning Pipeline
bal Sensing Companent
Ici Ressoning Comp. (Factor Gosph
A sensing-reasoning pipeline contains a set of n sensors (E.jeen)) and reasoning component R.
Impu. X
Dog Servire
Ring (
Each sensor is a binary classifier (for multi-class classifier it corresponds to a group of sensors)
Seroir
Fex
Rosinaa
given an input data example X. each of the sen- sor St outputs probability (XX) (i.e., if S₁ is neural network, (x(X) represents its output after the final softmax layer). The reasoning compo- nent takes the outputs of all sensing models as its inputs, and outputs a new Boolean random variable R (X.(
MLN Program am
anedicatirs
Sarter
fordew Sutrtion
anintr
Doggi Carki; AnimalXi
fox
Tag (v)
1og 1
Po
nule
10.3
Dogihi Animalixi
fena
m1 401 o)
10.5 oll -a 5.3
5.3
Canoi) AnimaliX)
Figure 2: A sensing-reasoning pipeline with MLN as the reasoning component.
One natural choice of the reasoning component to use a probabilistic graphical model (PGM). In the following subsection, we will make the reasoning component R more concrete by instantiating it as a Markov logie network (MLN). The output of example X is the expectation of the output of reasoning component R: E, (X)(())
pipeline on the input data
pipeline provides a generic, principled way of integrating domain knowledge with the output of statistical predictive models such as neural networks. One such example (TO) the task of ImageNet classification. Here each sensing model corresponds to the classifier for one specific class in ImageNet, e.g., Sdng (X) and Sanimat (X). The reasoning component then encodes domain knowledge such that "If an image is classified as a dog then must also be classified as animal" using PGM. There is no prior work considering the certified robustness of such knowledge-enabled ML pipeline. Figure 2 illustrates a concrete censing-reasonie pipeline, in which the reasoning component is implemented as an MLN.
Example. A
2.2 Reasoning Component as Markoy Logic Networks
Given the generic definition of ment the reasoning components. In this paper, we focus on Markov logic networks (MLN), which is a popular way to define a probabilistic graphical model using first-order logic [41). Concretely, we define the reasoning component implemented as an MIN, which contains set of weighted first-order logic rules, as illustrated in Figure Bb). After grounding, an MIN defines a joint probabilistic
pipeline, one can use different models to imple-
distribution among collection of random variables, as illustrated in Figure C(). We adapt the
3

---

standard MLN semantics to a sensing- reasoning pipeline and use slightly more general variant compared with the original MLN [4I]. Each MLN program corresponds a factor graph Due to the space limitation, we will not discuss the grounding part and point the readers to [1 We focus on defining the result after grounding. i.e., the factor graph.
Specifically, a grounded MLN is a factor graph G = (V,F), where V is a set of Boolean random variables. Specific a sensing-reasoning pipeline, there are two types of random variables V XUU:
1. Interface Variables X' = { hejj] Each sensing model S; corresponds to one interface variable v, in the grounded factor graph;
2. Interior variables y {yr hejm are other variables introduced by the MLN model.
Each factor F E F contains weight wy and factor function fr defined over subset of variables VE C V/ that returns {0, 10. There are two sets of factors F = U.:
1. Interface Factors G: For each interface variable I;, we create one interface factor G, with weight wG; = loglp:(X)/(C (X)]] and factor function Sa, (a) = I(a 1] defined over fe, = {
2. Interior Factors H. are other factors introduced by the MLN program.
Remarks: MLN-specific Structure. Our result applies to a more general family of factor graphs and not necessarily specific those grounded by MLN. Moreover, MLN provides an intuitive way of grounding such a factor graph with domain knowledge, and factor graphs grounded by MLN have certain properties that we will use later, e.g., all factors only return non-negative values, and there no unusual weight sharing structures.
The above factor graph defines joint probability distribution among all variables V. We define possible world as a function a : - (0, 1} that corresponds to one possible assignment of values to each random variable. Let Σ denote the set of all (exponentially many) possible worlds.
The statistical inference process of reasoning component implemented using MLNs 41 the marginal probability of given variable v E V:
computes
E[RALE (fp. = Pr [v = 1] = Z, 2((ee()))een))2(((x())))))
where the partition functions 2 and Zz are defined as
Zi (((((())))m))
wa.a((s)) + Σ wusH(o(va))
exp
(c)
G:E0
HeN
(x(fx(()))eel)) Σ exp
wa, wa (xx) +
Σ
wH wafulo(vu)
G,ED
HEHl
Why wG. =
px When the MLN does not introduce any interior variables and interior factors, it is easy to see that setting wG, (x']p((X)/() (X)) probability of each interface variable equals to the output of the original sensing model (X). This means that if we do not have additional knowledge in the reasoning component, the pipeline outputs the same distribution as the original sensing component.
(X))] ensures that the marginal
Learning Weights for Interior Factors? In this paper, we view all weights for interior factors as hyperparameters. These weights can be learned by maximizing the likelihood with weight learning algorithms for MLNs (29].
Beyond Marginal Probability for Single Variable. We have assumed that the output of a sensing- reasoning pipeline is the marginal probability distribution of a given random variable in the grounded factor graph. However, our result can be more general given function over possible worlds and outputs {0, }. the output of a pipeline can be the marginal probability of such a function. This will not change the algorithm that we propose later.
3 Hardness of Certifying Reasoning Robustness
Given a reasoning component Rt how hard is it to reason about its robustness? In this section, we aim at understanding this fundamental question. In order to provide the certified robustness of the reasoning component, which is defined the lower bound of model predictions for inputs considering

---

an adversarial perturbation with bounded magnitude [8. we need to analyze the hardness of this certification problem first. Specifically, we present the hardness results of determining the robustness of the reasoning component defined above, before we can provide our certification algorithm in Section [.2 We start by defining the counting (49) and robustness problems on general distribution. We prove that counting can be reduced to checking for reasoning robustness, and hence the latter is at least as hard; We then prove the complexities of reasoning with MLN.
3.1 Harness of Certifying General Reasoning Model
Let X (2,,,2 , be of variables. Let T. be distribution over Dini defined by set of parameters
plmi, where D is the domain of variables, either discrete or continuous, and P is the domain of parameters. We call accessible if for any E Díni, Ta(a) x w(o;a), a), where Din] p(m] + 2 is polynomial-time computable function. We will restrict our attention to accessible distributions only. We use Q Dí + {0, 1} to denote Boolean query, which is polynomial-tinn computable function. We define the following two oracles:
Definition 1 (COUNTiNG). Given imput polynomial-time computable weight function w(.) and query function ((-). parameters a, real number 0, COUNTING oracle outputs a real number Z that
Z
S 1 c.
Bla ~ Ra ~ Q(T)
Definition 2 (ROBUSTNESS). Given input polynomial-time computable weight function w(+) and query function Q(-), parameters a, two real numbers > 0 and > 0, a ROBUSTNESS oracle decides, for any a' E piml such that ||a - a' al11,0 S e, whether the following true:
|Eo ((a)) Elo ned [Q())) 8.
We can prove that ROBUSTNESS is at least as hard as COUNTING by reduction argument.
Theorem 1 (COUNTING S. ROBBSTNESS). Given polynomial-tie
computable weight function
w(-) and query function Q(-), parameters a and real number e > the instance of COUNTING, (w, E) can be determined by up to 0(1/=²) queries of the ROBUSTNESS oracle with input perturbation = (se))
Proof-sketch. We define the partition function Z; = -o w(a; and Blo [a]Q())= ZZo 11). We then construct new weight function a( == w(a:a) exp(3((o)) by intro- ducing an additional parameter 3, such that rg(o) x 3); and Ejg Tg]Q(a) = Zo-e² Z O(e,) and query the ROBUST-
2%
Then consider the perturbation 3r =B + with NESS oracle with input (t, Q, e, multiple times to perform a binary search å to esti- mate |B|o (a) E/o TT (or)). Perform a further "outer" binary search to find the which maximizes the perturbation. This yields good estimator for log &. which in turn gives Elo (a)) with e, multiplicative error. We leave detailed proof to Appendix A
3.2 Hardness of Certifying Markov Logic Networks
Given Theorem I we can now state the following result specifically for MLNs:
Theorem 2 (MLN Hardness). Given an MLN whose grounded factor graph is = (V.F)
(V.F) in which the weights for interface factors are wG, = log (1x))((11p(XX) and constant thresholds 8, [C.]ie(n) deciding whether
V(c)hE()) (Vi. leil < C.)
ERMIN (( ca)=e(=))
is as hard as estimating ERMLN (or (Ip: (X):()) up to e. multiplicative error, with e; = O(e))
Proof. Let (X)] query function Q(.) = RALLN(, (.) and a. defined by the marginal dis- tribution over interior variables of MLN. Theorem [ directly implies that ((1/=)) queries of ROBUSTNESS oracle can be used to efficiently estimate ERMLN ( (()((X))
[
In general, statistical inference in MLNs is #P-complete, and checking robustness for general MLNs is also #P-hard.
Certifying the Robustness of Reassnng Pipeline
Given a sensing-reasoning pipeline with n sensors [Si)sejn and a reasoning component R, we will first formally define its end-to-end certified robustness and then its connection to the robustness
5

---

of each component. In particular, based on the above hardness result for certifying the robustness of the reasoning component in Section 3 we will provide an effective certification method to upper/llwer bound the certification, taking any oracle for the inference of the reasoning component into account. With the certification of the reasoning component, we will finally provide the robustness certification for the sensing-reasoning pipeline by combining the certification of sensing and reasoning components.
Definition ((Cr, CF. Cr..p))robustnesss sensing-reasoning pipeline with a sensors (Si and a reasoning component is (Cr, CE. po-buuust on the input X, if for imput perturbation 17, ||ll S Cj
[[](()((XX)))))))) ([R( + n) he)))) - Cg-
Le., a perturbation ||ll| < C7 on the imput only changes the final pipeline output by at most Cg. Sensing Robustness and Reasoning Robustness. We decompose the end-to-end certified robustness of the pipeline into two components. The first component, which we call the sensing robustness, has given a perturbation ||vlep < C₁ on
been studied by the research community recently 200 45 8
the input X, we say each sensor S, (C1, C( P)) -ob-utt if
Vn, lmlll S C₁ = Ix:(X) - ( + n) S CS
The robustness of the reasoning component R is defined as: Given perturbation leal c(i) (1)
s on the output of each sensor S,(X), we say the reasoning component R is {(S he]m)) Cg) -robust if
VEL, ..., Ens (Vi. |ea| S CS$
(1)
-
+ ex) S Ce.
is easy to see that when the sensing component is (Cr, {CS he(()) p) rrobust and the reasoning component is (IC)) hee[n) CB rrobust on X, the Since the sensing robustness has been intensively studied by previous work, in this paper, we mainly focus on the reasoning robustness and therefore analyze the robustness of the pipeline.
pipeline is (Cz: Ca robust..
4.1 Certifying Sensing Robustness
There are several existing ways to certify the robustness of sensing models, such as Interval Bound Propagation (IBP) [16), Randomized Smoothing (8). and others (63] 51]. Here will leverage
randomized smoothing to provide an example for certifying the robustness of sensing components.
Corollary 1. Given a sensing model St, we construct a smoothed sensing model (X;0) =
B3 p: (X+ + E). With input perturbation ||m]|2 I C1, the smoothed sensing model satisfies
Φ ( (xx(X: - C1/0)= S 9x(X + 17, a) < Φ + 1 (9:(X;))) + C1/0)
where & is the Gaussian CDF and 4 as its inverse. Thus, the output probability of smoothed sensing
Algorithm 1 Algorithms for MLN robustness up- per bound (algorithm of lower bound is similar)
model can be bounded given input perturbations. Note that the specific ways of certifying sensing ro- bustness is orthogonal to certifying reasoning robust- ness, and one can plug in different sensing certifica- tion strategies.
input Oracles calculating Zi and Z2; maximal pertur- bations (C:)ee()
output An upper bound for input RELN RAMEN((P ((p(()) + (;)
Rmin +-1
4.2 Certifying Reasoning Robustness
2: initialize
Given the hardness results for certifying reasoning ro- bustness in Section 3.2 in this paper, we assume that
3: for b E search budgets do
4:
A -> update( (p]]te([A]:A: E (-]o,,
we have access to an oracle for statistical inference,
5:
for í to do
and provide a novel algorithm to certify the reasoning
X; 2 then
7:
6, C, ci - Ci
robustness. Le., we assume that we are able to cal- culate the two partition functions Zi (X)::X)))etta) and Zz (X)))())))
8:
else if X; < - then
9:
Ci. C Ci
10:
end if
11: R+ (((())im 72(()))
Lemma 4.1 (MLN Robustness). Given access
to partition functions Z=((p((X))eet)) and Ze ((pt(X)) and maximum perturbations
12: R.n. min Rman; R)
13: end for
14: end for
15: return Romi

---

(Ciliejn) VeI, Eni En. if Vi. lesl < C₁ we have that Vii E R.
max (lalk0t))
In InE[RMLN(( +ahew))) (k(l001))
max
(((e))ee))) (l<]<C,)
min
Z
min InB[RMLN((H((2)) + +a)eet)) 2 (k((e)))
min Zi((eshett)) - max Zz((eiheta)) (fo/kC.)
(((()))
where
Z.(feshee() = In 2. (()t())))) + Σ Ares.
We leave the proof to the Appendix B The high-level proof idea is decouple Z1 Z into two sub-proie propplooblss via a collection of Lagrangian multipliers, i.e., {A₂]. For any assignment of {Ar]. we obtain valid upper/lower bound, which reduces the certification process the process of searching for an assignment of these multipliers that minimize the upper bound (maximize the lower bound).
To efficiently search for the optimal assignment of {}a}. it is crucial to consider the interactions between these {A:} and the corresponding solution of Z,, which hinges on the structure of MIN. In
particular, we can prove the following (Detailed proofs and discussions in Appendix O
Proposition (Monotonicity). When X; 2 Z, ((ea))))) monotonically increuses w.r.t eG When
A; 1, Z, (f())em()) monotonically decreases w.r. G2.
Proposition 2 (Convexity). Z ((E))) is convex function in E,, Vi with
(1 (xx)))))xxxx
& log
(xx
Implication. Given the monotonicity region, the maximal and minimal of Z, are achieved at either 6, = -C, or 6 C, respectively. Given the convexity region, the maximal is achieved at 6, E {-C,, C,), and the minimal is achieved at e, E {-C,, C,} or at the zero gradient of Z, (1& He(m)) As a result, analysis leads to the following certification algorithm.
Algorithm of Certifying Reasoning Robustness. Algorithm [ illustraates the detailed algorithm based on the above result to upper bound the robustness of MLN. The main step is to explore different regimes of the {- In this paper, we only explore regimes where À E (-o0, -1] J [0, +00) as this already provides reasonable solutions in experiments. The function update ((x,) defines the exploration strategy - Depending on the scale of the problem, one can explore {A,} using grid search, random sampling, even pradeent-based methods. For experiments in this paper, we either grid search or random sampling. It is an exciting future direction to understand other efficient exploration and search strategies. We leave the detailed explanation of the algorithm Appendix C
5 Experiments
We conduct intensive experiments on five datasets to evaluate the certified robustness of the sensing- reasoning pipeline. We focus on two tasks with different modalities: image classification task on Road Sign dataset created based on GTSRB dataset [44) following the standard setting as [[7]; and information extraction task with stocks news on text data. We also report additional results on two other image classification tasks (Word50 (6) and PrimateNet, which is a subset of ImageNet ILSVRC2012 [9] with natural knowledge rules Appendix
G and Appendix FF We also report results on standard image benchmarks (MNIST and CIFAR10) 10) with manually constructed knowl- edge rules in Appendix H The code is provided at //ttttt://giiaaai com www./enninn-RRssonnnnn.. Sensingg Reasoning Pipeline
5.1
Experimental Setup
Datasets and Tasks. For the road sign classification task, we follow [17 and use the same dataset GTSRB [44), which contains 12 types of German road signs ("Stop". "Priority Road", "Yield", "Construction Area", "Keep Right", "Turn Left", "Do not Enter", "No Vihicles", "Speed Limit 20". "Speed Limit 50", "Speed Limit 120", "End of Previous Limitation") ). It consists of 14880 training
7

---

samples, 972 validation samples, and 3888 testing samples. We also include 13 additional detectors for knowledge integration, detecting attributes such as whether the border has an octagon shape (See Appendix D for a full list).
For the information extraction task, we use the HighTech dataset which consists of both daily closing asset price and financial news from 2006 to 2013 [12]. We choose 9 companies with the most news, resulting in 48 10 articles related stocks filtered by company name. We split the dataset into training and testing days chronologically. We define three information extraction tasks as our sensing models: StockPrice (Day, Company, Price), StockPri Cehhaer (Day, Company, Percent), Swwckpri ceGain (Day, Company). The domain knowledge that we integrate depicts the relationships between these relations (See Appendix[E] for more details).
Knowledge Rules. We integrate different types of knowledge rules for these two applicatiios.. We provide the full list of knowledge rules in the Appendix D
For road sign classification, we follow [17), which includes two different types of knowledge rules- Indication rules (road sign class indicates attribute v) and Exclusion rules (attribute classes and with the same general type such as "Shape". "Color", "Digit" or "Content" are naturally exclusive).
For information extraction, we integrate knowledge about the relationships between the sensing mod- els (e.g., StockPrice, StockPri cechange, StockPriceGain). For example, the stock prices of two consecutive days, StockPrice d1. Company, P1) and StockPrice Company, P2), Company, p). i.e., p = (f2 p1)/p1-
should be consistent with StockkriceChangell
Implementation Details. Throughout the road sign classification experiment, we implement all sensing models using the GTSRB-CNN [13] architecture. During training, we train all sensors with Isotropic Gaussian ~ (0, o² 1a) augmented data with 50000 training iterations until converge and tune the training parameters on the validation set, following
We use the SGD-momentum with the initial learning rate as 0.01 and the weight decay parameter as 10- to train all the sensors for 50000 iterations with 200 as the batch size, following [17. During certification, we adopt the same smoothing parameter for training to construct the smoothed model based on Monte-Carlo sampling.
For information extraction, we use BERT final hidden state of the first token [CLS] from BERT as the representation of the whole input and apply dropout with probability p 0.5 on this final hidden state. Additionally, there is fully connected layer added on top of BERT for classification. To fine-tune the BERT classifiers for three information tasks, we use the Adam optimizer with the initial learning rate 10-5 and the weight decay parameter as 10-4, We train all the sensors for 30 epochs, and the batch size 32.
model architecture. During training,
the
Evaluation Metries. We adopt the standard certified accuracy as our evaluation metric, defined by the percentage of instances that can be certified under certain ép norm bounded perturbations. Specifically, given the input z with ground-trute -ruth label y. once can certify the bound of the model's output confidence on predicting label under the norm-bounded perturbation as [C, the certified accuracy can be defined by: 1 Σ i= I[[C, > 0.5]) where II()) denotes the indicator function. Since each sensing component's certification is performed by randomized smoothing, which yields the failure probability characterized by Co. we will control the failure probability & for the whole sening-reasoning pipeline pipeline with sensing models as Ço = 1 - (1 - 1) by applying the union bound. Throughout all the experiments, ( is kept to 0.001 so our end-to-end certification is guaranteed to be correct with at least 99.9% confidence.
N
5.2 Results of Road Sign Classification
In this section, we evaluate the certified robustness of our censing-reasoning pipeline under the f2-norm bounded perturbation. We first report the l certified accuracy of our sensing-rcasoning pipeline and compare it to strong baseline as a vanilla randomized smoothing trained model (without knowledge). Note that it is flexible to replace the sensing component with other robust training algorithms. We conduct our evaluation under different smoothing parameters # = (0.12, 0.25, 0.50) and various la perturbation magnitudes on the input image C₁ = {0.12, 0.25, 0.50, 1.00} (Table I.. During certification, we evaluate our certification time per sample with 25 sensors as 5.39s, which shows that the overall certification time is generally acceptable.
As shown in Table []] we can see that with knowledge integration, sensing-reasoning pipeline achieves consistently higher certified accuracy compared to the baseline smoothed ML model without
8

---

Table 1:
(Road sign classification) Certified accuracy under different input perturbation magnitudes (C₁). Models are smoothed with different Gaussian noises ~ NN 8 Ia), & E (0.12, 0.25, 0.503. Rows with denote the best certified accuracy among all the smoothing parameters for cach method. The hold numbers show the higher certified accuracy under the same (Cr, o) setting and the numbers with underline show the highest certified accuracy for each C₁ among different smoothing parameters. (All certificates hold with p = 99.9%)
Methods
C 0.12
C 0.25
C
0.50
C
1.00
0.12
90.8
87.1
0.0
0.0
Vanilla Smoothing
0.25
89.6
88.4
71.6
0.0
(w/o knowledge)
0.50
84.0
80.2
73.2
61.7
90.8
88.4
73.2
61.7
0.12
96.0
89.0
73.2
24,2
Sensing- Reasoning Pipeline
0.25
93.4
91.0
74.0
49.2
(w/ knowledge)
0.50
89.3
85.4
75.5
62.5
96.0
91.0
75.5
62.5
knowledge under all the perturbation magnitudes Cf and smoothing parameter ē settings. Under the small perturbation magnitude cases, our improvement is very significant (around 5%). More interestingly, given large C₁ but small smoothing parameter o, vanilla randomized smoothing- certification directly fails (0% certified accuracy) due the looseness of the hypothesis testing bound, while the sensing-rees reasoning pipeline could still achieve reasonable certified robustness (over 71% % on C 0.50, 49% on C₁ L.00) under the same (C,, 6) settings. This indicates very realistic case: we always under-estimate the attacker's ' ability easily under the real-world setting in this case, the sensing-reasoning pipeline could remain robust even provide reasonable certified accuracy with a conservative smoothing parameter.
5.3 Results of Information Extraction
In this section, we conduct the certified robustness evaluation the information extraction task text data. Since there is no good certification method on discrete NLP data for sensing models, we directly assume the maximal perturbation on the output of sensors (Cs). Table shows the certified accuracy on the final outputs of the reasoning component. We see that the meassnnge pipeline provides significantly higher certified robustness, and even under high perturbation magnitude on all sensing models' output confidence (C's 0.5), which means the reasonnne pipeline can still leverage the knowledge to help enhance the robustness given strong attacker. To further illustrate intuitively why such knowledge-bert based reasoning helps, Figure 3 shows the "margin" the probability of the ground truth class minus the probability of the wrong class with or without knowledge integration. We see that, with knowledge integration, we can significantly increase the number of examples with large "margin" under adversarial perturbations. This explains the improvement of certified robustness, which highly relies on such prediction confident margin.
Table 2: (Information extraction) Certified
racy under different perturbation magnitudes (Cs) based on the sensing models' output uncertainty. (All certificates hold with 99.9% confidence)
Methods
Cy = 0.1
C2 =
Cs 0.9
Vanilla
(wie knowledge?
99.7
94.7
38.4
Sensing- Reasoning Pipeline
(w/ knowledge)
100.0
We also conduct experiments on PrimateNet, Word50, MNIST, CIFARIO datasets for the image classification tasks in Appendix Appendix H We observe similar results that knowledge integration significantly boosts the certified robustness.
6 Related Work
Robustness for Single ML model and ML Ensemble. Lots of efforts have been made to improve the
robustness of single ML or ensemble models. Adversarial training [15). and its variations [47] 53 have generally been more successful in practice, but usually come at the cost of accuracy and
increased training time 48 [53. To further provide certifiable robustness guarantees for MI models,
various certifiable defenses and robustness verification approaches have been proposed [20 45 8 27
25). Among these strategies, randomized smoothing [8] has achieved scalable performance. With improvements in training, including pretraining and adversarial training, the certified robustness

---

better
Whong
Correct
Eneguncy
0.8
knowledge
0.8
0.5
0.8
0.6
0.6
without knowledge
P[serrececlas)
class]
Picorrec class PPtup wrongcloo)
Picorrectclass: 0
wrongelas)
Plcorrect Pitop class) (d) c,5 0.9
(a) C 0.1
(b) C, 0.2
(c) C,S. 0.
Figure (Information extraction) Histogram the robustness margin (the difference between the prohahility the correct class (lower bound) and the top wrong class (upper bound)) under perturbations. If such a difference is positive, it means that the classifier makes the right prediction under perturbations.
bound can further improved 42 In addition the single ML model, some work proposed to promote the diversity of classifiers and therefore develop a robust ML ensemble [34] 59 57 58
Although promising, these defense approaches, either empirical or theoretical, can only improve the robustness of single ML ensemble model. Certifying or improving the robustness of such single or pure ensemble models is very challenging, given that there no additional information that be utilized. In addition. the ML learning process usually favors pipeline that is able to incorporate different sensing components as well as domain knowledge in practice. Thus, certifying the robustness of such pipelines is of great importance.
Robustness of End-to-end MI. Systems. There have been intensive studies on joint inference between multiple models, and the predictions based on joint inference can help to further improve the clean accuracy of ML pipelines
(53] 10 38 33 5J. which have been applied to a range of real-world applications 2 37 32 Often, these approaches use different statistical inference models such as factor graphs (50). Markov logic networks (4T, and Bayesian networks (35] as a way to integrate domain knowledge. In this paper, we take different perspective this problem - instead of treating joint inference as way to improve the clean accuracy, we explore the possibility using it exogenous information to improve the end-to-end certified robustness of ML pipelines. A recent work [17] explores the empirical robustness improvement via knowledge integration, while there is robustness guarantee provided. As we show in this paper, by integrating domain knowledge, are able to improve the certified robustness of the ML pipelines significantly.
7 Conclusions
We provide the first certifiably robust soning. We theoretically prove the certified robustness of such ML pipelines, and provide complexity analysis for certifying the reasoning component. Our extensive empirical results demonstrate the certified robustness of sensing-reasoning reasoning pipeline, and we believe our work would shed light on future research towards improving and certifying robustness for general ML frameworks as well as different ways to integrate logical reasoning with statistical learning.
pipeline with knowledge-based logical rea-
Acknowledgements This work is partially supported by the NSF grant 1910100 NSF CNS No. 204676, C3 AI, and Alfred P. Sloan Foundation. CZ and the DS3Lab gratefllly acknowledge the support from the Swiss State Secretariat for Education, Research and Innovation (SERI) under contract number MB32.00033 (for European Research Council (ERC) Starting Grunt TRIDENT 101042665), the Swiss National Science Foundation (Project Number 20002 __146628, 197485), Innosuiss:/SNF BRIDGE Discovery (Project Number 40B2-0_ 187132), European Union Horizon 2020 Rescarch and Innovation Programme (DAPHNE, 957407), Botnar Research Centre for Child Health, Swiss Data Science Center, Alibaba, Cisco, eBay, Google Focused Research Awards, Kuaishou Oracle Labs, Zurich Insurance, and the Department of Computer Science at ETH Zurich. HG has received funding from the European Research Council (ESCC under the buropean Union's Horizon research innovation programme (grant agreement 947778).
10

---

References
[1] Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In International Conference on Machine Learning, pages 274-283, 2018.
[2] Marenglen Biba, Stefano Ferilli, and Floriana Esposito. Protein fold recognition using markov logic networks. In Mathematical Approaches to Polymer Sequence Analysis and Related Problems, pages 69-85. Springer, 2011.
[3] Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks, In 2017 ieee symposium on security and privacy (sp), pages 39-57. IEEE, 2017.
[4] Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, Percy Liang, and John C Duchi. Unlabeled data improves adversarial robustness. arXiv preprint arXiv:/955.33777
2019. [5] Deepayan Chakrabarti, Stanislav Funiak, Jonathan Chang, and Sofus A Macskassy. Joint inference of multiple label types in large networks. arXiv preprint arXiv:1401.7700 2014.
[6] Liang-Chied Chen, Alexander Schwing, Alan Yuille, and Raquel Urtasun. Learning deep structured models. In International Conference on Machine Learning, pages 1785-1794.
PMLR, 2015.
[7] Liwei Chen, Yansong Feng. Jinghui Mo, Songfang Huang, and Dongyan Zhao. Joint inference for knowledge base population. In Proceedings the 2014 Conference Empirical Methods in Natural Language Processing (EMNLP), pages 1912-1923, Doha, Qatar, October 2014.
Association for Computational Linguistics.
[8] Jeremy M Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. arXiv preprint arXiv: 1902.00912, 2019.
[9] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hicrarchical Image Database. In CVPR09, 2009.
[10] Jia Deng, Nan Ding, Yangqing Jia, Andrea Frome, Kevin Murphy, Samy Bengio, Yuan Li, Hartmut Neven, and Hartwig Adam. Large-scale object classification using label relation graphs. In European conference on computer vision, pages 48-64. Springer, 2014.
[11] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In Jill Burstein, Christy Doran, and Thamar Solorio, editors, NAACI-HLL, pages 4171 1177-1186. Association for Computational Linguistics, 2019.
[12] Xiao Ding, Yue Zhang, Ting Liu, and Junwen Duan. Using structured events to predict stock price movement: An empirical investigation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1415-1425, 2014.
[13] Kevin Eykholt, Ivan Evtimov, Earlence Fernandes, Bo Li, Amir Rahmati, Chaowei Xiao, Atul Prakash, Tadayoshi Kohno, and Dawn Song. Robust physical-world attacks on deep learning visual classification. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1625-1634, 2018
[14] Christiane Fellbaum. Wordnet. The encyclopedia of applied linguistics, 2012.
[15] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adver- sarial examples. ICI.R 2015.
[16] 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 arXiv: 18 10. 12715, 2018.
[17] Nezihe Merve Gürel, Xiangyu Qi, Luka Rimanic, Ce Zhang, and Bo Li. Knowledge enhanced machine learning pipeline against diverse adversarial attacks. ICML, 2021.
[18] Tuyen N Huynh and Raymond J Mooney. Max-margin weight learning for markov logic networks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 564-579. Springer, 2009.
[19] Jongheon Jeong and Jinwoo Shin. Consistency regularization for certified robustness of smoothed classifiers. Advances Neural Information Processing Systems, 13:10558-10570, 2020.
11

---

[20] J Zico Kolter and Eric Wong. Provable defenses against adversarial examples via the convex outer adversarial polytope. arXiv preprint arXi:: 2017.
[21] Ondrej Kuzelka. Complex markov logic networks: Expressivity and liftability, In Conference on Uncertainty in Artificial Intelligence, pages 729-738. PMLR, 2020.
[22] Bo Li and Yevgeniy Vorobeychik. Feature cross-substitution in adversarial classification. In Advances in neural information processing systems, pages 2087-2095, 2014.
[23] Huichen Li, Linyi Li, Xiaojun Xu, Xiaolu Zhang, Shuang Yang. and Bo Li. Nonlinear gradient estimation for query efficient blackbox attack. In International Conference on Artificial Intel- ligence and Statistics (AISTATS 2021), Proceedings of Machine Learning Research. PMLR,
13-15 Apr 2021.
[24] Huichen Li, Xiaojun Xu, Xiaolu Zhang, Shuang Yang, and Bo Li. Qeba: Query-efficient boundary-based blackbox attack. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages I 1221-1230, 2020.
[25] Linyi Li, Xiangyu Qi, Tao Xie, and Bo Li. Sok: Certified robustness for deep neural networks. arXiv, abs/2009.04134 2020.
[26] Linyi Li, Maurice Weber, Xiaojun Xu, Luka Rimanic, Bhavya Kailkhura, Tao Xie, Ce Zhang, and Bo Li. Tss: Transformation-speeie -ppeciiiii smoothing for robustness certification. In ACM Conference on Computer and Communications Security (CCS 2021), 2021.
[27] Linyi Li, Jiawei Zhang, Tao Xie, and Bo Li. Double sampling randomized smoothing. In International Conference on Machine Learning. 2022.
[28] Linyi Li, Zexuan Zhong, Bo Li, and Tao Xic. Robustra: training provable robust neural networks over reference adversarial space. In Proceedings of the 28th International Joint Conference Artificial Intelligence, pages 4711-4717. AAAI Press, 2019.
[29] Daniel Lowd and Pedro Domingos. Efficient weight learning for markov logic networks. In Joost N. Kok, Jacek Koronacki, Ramon Lopez de Mantaras, Stan Matwin, Dunja Mladenič, and Andrzej Skowron, editors, Knowledge Discovery in Databases: PKDD 2007, pages 200-211, Berlin. Heidelberg, 2007. Springer Berlin Heidelberg.
[30] Xingjun Ma. Bo Li, Yisen Wang. Sarah M Erfani, Sudanthi Wijewickrema, Grant Schoenebeck, Dawn Song, Michael E Houle, and James Bailey. Characterizing adversarial subspaces using local intrinsic dimensionality. arXiv preprini
026113,, 2018.
[31]
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: (70.00/00000083 2017.
[32] Emily K. Mallory, Ce Zhang, Christopher Ré, and Russ B. Altman. Large-scale extraction of gene interactions from full-text literature using DeepDive. Bioinformatics, 32(1):106 113, 09 2015.
[33] Andrew McCallum. Joint inference for natural language processing. In Proceedings of the Thirteenth Conference Computational Natural Language Learning (CoNLL-2009), page 1, Boulder, Colorado, June 2009. Association for Computational Linguistics.
[34] Tianyu Pang, Kun Xu, Chao Du, Ning Chen, and Jun Zhu. Improving adversarial robustness via promoting ensemble diversity. arXiv preprint arXiv: 1901.08866, 2019.
[35] Judea Pearl. Causality; Models, Reasoning, and Inference. Cambridge University Press, USA, 2000.
[36] Judea Pearl. Bayesian networks. 2011.
[37] Shanan E. Peters, Ce Zhang, Miron Livny, and Christopher Ré. A machine reading system for assembling synthetic paleontological databases. PLOS ONE, (12):1122, 12 2014.
[38] Hoifung Poon and Pedro Domingos. Joint inference in information extraction. In AAAI, volume 7, pages 913-918, 2007.
[39] Haonan Qiu, Chaowei Xiao, Lei Yang, Xinchen Yan, Honglak Lee, and Bo Li. Semanti- cadv: Generating adversarial examples via attribute-conditioned image editing. In European Conference on Computer Vision, pages 19-37. Springer, 2020.
[40] Matthew Richardson and Pedro Domingos. Markov logic networks. Machine learning, 62(1- 10:107 2006.
12

---

[41] Matthew Richardson and Pedro Domingos. Markov logic networks. Machine Learning, 62(1- 2):107-136, 2006.
[42] Hadi Salman, Jerry Li, Ilya 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, pages 1128--1330,, 2019.
[43] Ali Shafahi, Mahyar Najibi, Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry S Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! arXiv preprint arXiv: 12843, 2019.
[44] Johannes Stallkamp, Marc Schlipsing, Jan Salmen, and Christian lgel. Man vs. computer: Benchmarking machine learning algorithms for traffic sign recognition. Neural networks, 32:323-333 332, 2012.
[45] Vincent Tjeng, Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. arXiv preprint 1rXi::111.0033300 2017.
[46] Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry, On adaptive attacks to adversarial example defenses. arXiv preprint arXiv:2002.08344 2020.
[47] Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Dan Boneh, and Patrick McDaniel. Ensem- ble adversarial training: Attacks and defenses. ICLR, 2018.
[48] Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry, Robustness may be at odds with accuracy). ICLR 2019, 2018
[49] L.G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189-2011 1979.
[50] Martin J. Wainwright and Michael I. Jordan. Graphical models, exponential families, and variational inference. Foundations and Trends@ in Machine Learning, 1(1-2):1-305, 2008
[51] Lily Weng, Huan Zhang, Hongge Chen, Zhao Song. Cho-Jui Hsich, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning, pages 5276-5285, 2018.
[52] Chaowei Xiao, Ruizhi Deng, Bo Li, Taesung Lee, Benjamin Edwards, Jinfeng Yi, Dawn Song. Mingyan Liu, and Ian Molloy. Advit: Adversarial frames identifier based on temporal consistency in videos. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 3968-3977. 2019.
[53] Chaowei Xiao, Ruizhi Deng, Bo Li, Fisher Yu, Mingyan Liu, and Dawn Song. Characterizing adversarial examples based spatial consistency information for semantic segmentation. In Proceedings of the European Conference on Computer Vision (ECCV), pages 217-234, 2018.
[54] Kaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang, Kai- Chang, Minlie Huang, Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsich. Automatic perturbation analysis for scalable certified robustness and beyond. Advances in Neural Information Processing Systems, 33, 2020.
[55] Zhe Xu, Ivan Gavran, Yousef Ahmad, Rupak Majumdar, Daniel Neider, Ufuk Topcu, and Bo Wu. Joint inference of reward machines and policies for reinforcement learning. arXiv preprint 1tXiv:1909.059//1 2019.
[56) Greg Yang, Tony Duan, J Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In International Conference on Machine Learning, pages 10693-10705. PMLR, 2020.
[57] Zhuolin Yang. Linyi Li, Xiaojun Xu, Bhavya Kailkhura, Tao Xie, and Bo Li. On the certified robustness for ensemble models and beyond. ICLR, 2021.
[58] Zhuolin Yang, Linyi Li, Xiaojun Xu, Bhavya Kailkhura, Tao Xie, and Bo Li. On the certi- fied robustness for ensemble models and beyond. In International Conference on Learning Representations, 2022.
[59] Zhuolin Yang. Linyi Li, Xiaojun Xu, Shiliang Zuo, Qian Chen, Pan Zhou, Benjamin P. Rubinstein, Ce Zhang, and Bo Li. Tis: Transferability reduced ensemble via promoting gradient diversity and model smoothness. Neural Information Processing Systems (NeurIPS 202/), 2021.
13

---

[60] Zhuolin Yang, Linyi Li, Xiaojun Xu, Shiliang Zuo, Qian Chen, Pan Zhou, Benjamin I P Rubinstein, Ce Zhang, and Bo Li. Trs: Transferability reduced ensemble via promoting gradient diversity and model smoothness. In Advances in Neural Information Processing Systems, 2021.
[61] 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. NeurIPS, 2022.
[62] Ce Zhang, Christopher Ré, Michael Cafarella, Christopher De Sa, Alex Ratner, Jacho Shin, Feiran Wang. and Sen Wu. Deepdive: Declarative knowledge base construction. Commun.
ACM, 60(5):93-10,, April 2017.
[63] Huan Zhang. Tsui-Wei Weng. Pin-Y Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. In Advances in neural information processing systems, pages 4939-4948, 2018.
[64] Jiawei Zhang. Linyi Li, Huichen Li, Xiaolu Zhang. Shuang Yang. and Bo Li. Progressive-scale boundary blackbox attack via projective gradient estimation. ICML, 2022.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We have mentioned the future
improvement of our work the related work part.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] This work will not infer obvious negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes] The assump- tions have been all mentioned in the main paper and appendices.
(b) Did you include complete proofs of all theoretical results? [Yes] The whole proofs are provided in Appendix C
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)?
[es]] The code is provided at https://githuu: httts////ghhhuu...m///iininngg Seam//Snninnn-Raaonn
maaniinggReasnnng-PPiae
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] All the training details have been provided in the Appendix D
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes] The confidence of the reported certification results in the paper is guaranteed to be at least 99.9%, as mentioned our main paper.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] The detailed information is mentioned in Appendix D
4. If you are using existing assets (e.g., code, data, models) or curating/relcusing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [Yes] We only use public and commonly used data.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [Yes] We only public and commonly used data.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "lv-0cku2K4j", "reviewer": "Reviewer_ApnS", "summary": "This paper proposed to integrate statistical ML models with knowledge as a reasoning component using Markov logic networks in order to improve certified robustness. They start from a sensing-reasoning pipeline, followed by deriving the hardness of certifying general reasoning model, and finally certifying the robustness of sensing-reasoning pipeline. Experiments on five datasets show that their method outperforms models from prior work. ", "questions": "N/A", "limitations": "Same as the weakness point mentioned in the above section.", "rating": 8, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I'm not an expert in this area so I didn't check the correctness of the math thoroughly. \n\nOverall I think this is a nice paper with thorough theoretical analysis and solid experiments. The paper is well written.\n\nOne weakness that I can think of is that it would be great if you could provide more experiments on large-scale datasets.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "PJuISe3xL53", "reviewer": "Reviewer_g8Bp", "summary": "This paper investigates a couple different things, but at its core its investigating the certified robustness of systems that leverage \"logical reasoning\" (i.e. Markov Logic Networks) on top of regular statistical learning neural networks (what this paper calls a \"sensing-reasoning\" pipeline).\n\nThis paper has 3 primary contributions:\n1. It examines the problem of certifying robustness for graphical models as well as its computational complexity.\n2. It proposes an approach for certifying robustness for these models.\n3. It demonstrates that on a variety of tasks it looks at, this sensing + reasoning pipeline can lead to better robustness than pure sensing.\n\n", "questions": "One thing that was confusing to me was what the baseline \"sensing only\" models actually *were*? For example, on the PrimateNet tasks, there are a bunch of \"leaf sensing\" nodes that the reasoning component leverage to make its final prediction. However, how is the model without the \"reasoning\" actually arriving at its final prediction?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. I hadn't thought about this particular angle before, but I think it's a very interesting and relevant problem to tackle. One pitch for hybrid neuro-symbolic approaches for quite some time has been robustness, but I haven't seen any papers tackle certified robustness for these systems before, which made their claims of \"robustness\" less convincing.\n2. The proof of the difficulty of certifying robustness on the reasoning component seems useful, although I lack the expertise to verify how interesting it is (the reduction wasn't obvious to me at least).\n3. The approach for certifying robustness of the reasoning component seems reasonable and fairly interesting to me.\n4. The authors demonstrate that their sensing+reasoning pipeline achieves better certified robustness than pure sensing approaches on a wide array of datasets/tasks, which is great!\n5. I also appreciated the intuitive examples of why sensing + reasoning would lead to better robustness compared to pure sensing.\n\nWeaknesses:\nThe main issue I have about this paper relate to the specific tasks it uses, which is related to the specific kinds of \"sensing + reasoning\" networks it uses. As a result of the particular kind of pipeline it requires, the tasks it evaluates on are not standard \"certified robustness\" tasks, as far as I can tell. This means that they do not compare against any existing papers/baselines on their tasks, only the baselines they've created for these tasks. This is somewhat worrisome, although the baselines they choose do seem reasonable.\n\nIt would be much  more convincing to me if the authors were able to demonstrate SOTA robustness results against standard robust baselines.\n\nOverall, the authors do a great job of introducing the task of certified robustness to a new class of (quite interesting!) models, examine its difficult and computational complexity, and evaluating its robustness on a wide array of tasks. However, the lack of experiments against standard established baselines and tasks gives me some pause. Still, I think this paper is quite interesting and should be accepted.\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "40nFD_uEo6X", "reviewer": "Reviewer_ZvBd", "summary": "This paper tries to introduce certified robustness into a probabilistic reasoning system. First, Markov logic network (MLN) is used as a generic model that can represent every probabilistic logical reasoning system. Then, the authors proved that the complexity of certifying a MLN model reasoning model robustness is #P-Hard. Furthermore, a novel algorithm to certify the reasoning robustness is proposed with an assumption that two partition functions are available. Experimental results on both road sign classification and information extraction show that sensing-reasoning pipeline can have much higher certified accuracy. Detailed analysis showed that by incorporating reasoning components, the number of examples with a large “margin” under adversarial attacks significantly increased.", "questions": "1.\tIs there a clear definition of \\textit{certified robustness}? The paper should include this definition for self-completion. \n2.\tSome notions are used but not defined. For example, at line#154, what is $f_H()$?\n3.\tIn section 4.2, the partition functions $Z_1$ and %Z_2$ are assumed to be available beforehand. How are these functions obtained for the two tasks in the experiments?\n4. What is the key point the authors want a reader should take away from this paper? I am confused by the independent points in this paper.", "limitations": "Certified robustness is an important topic that can be beneficial to societal good through building robust and trustworthy machine learning models.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \\\n1.\tCertified robustness is a very important research topic.\\\n2.\tTheoretical analysis in this paper is valuable.\n\nWeaknesses:\\\nIt is not clear what the key idea the paper wants to deliver is. There are several points in this paper: \\\na. the complexity of certifying robustness; \\\nb. an algorithm to estimate the upper/lower bound; \\\nc. experimental results show that incorporating reasoning components can improve the certified robustness. \\\nHowever, it seems they are all independent between each other. I cannot see a coherent story line in this paper. For example, experimental results show that incorporating reasoning components can significantly improve robustness. But, how are these results related to the proposed algorithm on upper/lower bound estimation or the complexity?\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "0vv3-E3x4fQ", "reviewer": "Reviewer_7FcD", "summary": "This paper proposes to improve robustness certification by leveraging a reasoning component based on Markov logic networks (MLN). Human knowledge (i.e., logical rules) are formalized as variables and factors in the reasoning component, thereby guiding the sensing-reasoning pipeline to exhibit better certified robustness. Concretely, the contribution of this paper is three-fold:\n\n1. This paper proves that the computational complexity of certifying the robustness of MLN is #P-hard. The basic idea is to reduce the famous #P-complete COUNTING problem to checking for reasoning robustness. This hardness result tells us why this task is challenging, indicating that the key points to mitigate it are: (1) choosing a \"good\" reasoning component that have efficient inference algorithm; (2) find an efficient approximation algorithm that can reduce the problem of cerifying the robustness to the statistical inference oracle, and prove how good (the bounds) the algorithm is.\n2. This paper complete the two key points mentioned above. The reasoning component is designed as Markov logic networks (MLN), of which the inference is #P-complete but has efficient approximation algorithms that can be regarded as oracles. Based on this, the authors provide an effective certification method for reasoning robustness.\n3. Experimental results on several applications demonstrate the robustness of such ML pipelines.", "questions": "Q1: maybe the authors can provide an explicit definition of \"Statistical Inference\" as background knowledge. In Figure 1, it looks like statistical inference is done by the sensing component, which is decoupled with the reasoning component. However, in Section 3 and 4, we say \"statistical inference of the reasoning component\".\n\nQ2: In Section 4, the authors use the wording \"we assume that we have access to an oracle for statistical inference\". I think it could be better if the authors can explicitly tell us what the concrete oracles are.\n\nQ3: L86 \"Surprisingly, providing certified robustness for MLN is possible because of the structure inherent in the probabilistic graphical models and distributions in the exponential family.\" Maybe the authors can explain more about this point as it is still unclear for me how this point is concluded from Section 4.", "limitations": "Q4: (about the limitation) what is the limitation of MLN comparing to other statistical inference models? Can the methodology proposed in this paper generalize to others?", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n- Certified robustness is an important topic in machine learning, and it is promising that introducing human knowledge expressed as logical rules can further improve the overall certified robustness. This topic is challenging, as discussed in Section 3.\n- Knowledge is expressed in the framework of Markov logic networks. This is elegant and easy-to-understand. This design choice also helps the authors propose the efficient algorithm.\n- Key points in this paper are well formulated and proven.\n- Good experimental results on different applications, with good result analysis.\n\nCons:\n- It is quite hard for me to understand the relationships among Section 2, 3, and 4 (especially how Section 4 is based on Section 3), as I'm not an expert in this area. I try to summarize my understanding in the \"Summary\" part above, but I'm not sure whether it is correct or not. I hope that the authors can point out incorrect understandings in my summary in the rebuttal. Moreover, I also list detailed questions that are still unclear for me as follows.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept