PaperlayerView exact revision on arXiv

Source-linked AI summary

Improving Certified Robustness via Statistical Learning with Logical Reasoning

Zhuolin Yang, Zhikuan Zhao, Boxin Wang, Jiawei Zhang, Linyi Li, Hengzhi Pei, Bojan Karlas, Ji Liu, Heng Guo, Ce Zhang, Bo Li

arXiv:2003.00120v9cs.LGcs.CRstat.ML

TL;DR

Existing certified defenses cover limited perturbation radii, and certified robustness for knowledge-enriched learning-and-reasoning pipelines had not been studied. The paper analyzes certification for DNN-to-MLN pipelines and reports significantly higher certified robustness than state-of-the-art DNN certification methods across image and text tasks.

  • Problem

    Existing certified defenses cover only limited ℓp-bounded perturbation radii, while certified robustness for knowledge-rule integration had remained unexplored despite prior empirical robustness gains.

    Source: §1 · p. 2

  • Method

    The paper models DNN predictions as inputs to MLN reasoning, proves certification hardness, and derives robustness bounds using an inference oracle and structural properties under certain conditions.

    Source: §1 · pp. 2–3

  • Results

    Knowledge-enriched sensing-reasoning pipelines achieve significantly higher certified robustness than state-of-the-art DNN certification methods across image-classification and natural-language-processing tasks.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The authors position this work as a first step toward studying robustness certification for broader ML frameworks and integrations of logical reasoning with statistical learning.

    Source: §7 · p. 10

    The analysis is restricted to accessible distributions, and the NLP evaluation assumes maximal perturbation on sensor outputs.

    Source: §3.1 · p. 5, §5.3 · p. 9

Abstract

from arXiv · show

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.

1 Introduction

Certified defenses cover limited perturbation radii, while the certified robustness of knowledge-enriched learning-and-reasoning pipelines remained unexplored. The paper studies DNN-to-MLN pipelines, establishes the hardness of certifying MLN reasoning, develops a certification approach, and reports higher certified robustness than state-of-the-art DNN methods.

1 Introduction

  • Existing certified defenses cover only limited ℓp-bounded perturbation radii, and the certified robustness of knowledge-rule integration remained unexplored despite prior empirical gains [17].The paper identifies this as a gap in pure data-driven robustness approaches.Source: §1 · p. 2
  • The pipeline feeds Boolean predictions from statistical models such as DNNs into logical reasoning models such as MLN, which produce the final output.The paper presents this as its first study of certified robustness for the Learning+Reasoning paradigm [17].Source: §1 · p. 2
  • For MLN reasoning, checking certified robustness is at least as hard as counting on the same distribution family, including computing the graphical model's partition function.The paper reduces counting in statistical inference to checking robustness.Source: §1 · p. 2
  • Even with an inference oracle, certification remains challenging; the proposed approach uses graphical-model and exponential-family structure to obtain monotonicity and convexity under certain conditions.These properties support solving the certification optimization.Source: §1 · p. 3
  • Knowledge-enriched sensing-reasoning pipelines achieve significantly higher certified robustness than state-of-the-art DNN certification methods across image-classification and natural-language-processing tasks.The evaluation covers multiple pipelines with state-of-the-art neural sensing components.Source: §1 · p. 3

2 Robust Statistical Learning with Logical Reasoning

The section defines a sensing-reasoning pipeline that combines sensor probabilities with a reasoning component and gives MLNs as one implementation. In the MLN formulation, sensor outputs become interface variables, while additional variables and factors encode logical knowledge.

2.1 Sensing-Reasoning Pipeline

  • Sensor classifiers provide probabilities to a reasoning component, whose expected output defines the pipeline’s prediction.The reasoning component can encode domain knowledge, such as the rule that a classified dog is also an animal.Source: §2.1 · p. 3

2.2 Reasoning Component as Markov Logic Networks

  • A grounded MLN represents the joint distribution as a factor graph with sensor-linked interface variables and additional interior variables and factors.Interface-factor weights are set from sensor probabilities; without interior variables or factors, the pipeline preserves the sensors’ output distribution.Source: §2.2 · p. 4
  • MLN inference computes a variable’s marginal probability using partition functions, and the pipeline can also output the marginal probability of a Boolean function over possible worlds.The latter generalization does not change the proposed algorithm.Source: §2.2 · p. 4

3 Hardness of Certifying Reasoning Robustness

The section studies the complexity of certifying a reasoning component’s robustness, first reducing a general counting problem to robustness certification and then applying the result to MLNs. It concludes that MLN inference is #P-complete and MLN robustness checking is #P-hard.

3.1 Harness of Certifying General Reasoning Model

  • For accessible distributions, the reduction establishes that ROBUSTNESS is at least as hard as COUNTING.The counting task estimates the expectation of a Boolean query under the distribution.Source: §3.1 · p. 5
  • The reduction tilts the distribution by exp(βQ), uses perturbations in β and binary searches to estimate a partition-function ratio, then recovers the query expectation.The resulting estimate has εc multiplicative error.Source: §3.1 · p. 5

3.2 Hardness of Certifying Markov Logic Networks

  • MLN inference is #P-complete, and checking robustness for general MLNs is #P-hard.The MLN result applies when interface-factor weights are set from the sensor probabilities, with robustness determined by bounded perturbations.Source: §3.2 · p. 5

4 Certifying the Robustness of Sensing-Reasoning Pipeline

The section defines end-to-end robustness through bounded changes in the pipeline output, then combines certificates for sensing and reasoning. For sensing it uses randomized smoothing as an example; for MLN reasoning it derives an oracle-based certification algorithm from structural properties.

4 Certifying the Robustness of Sensing-Reasoning Pipeline

  • End-to-end certification combines bounds for the sensing and reasoning components to bound changes in the pipeline’s final output under input perturbations.The paper focuses on reasoning robustness, while sensing robustness has been studied previously.Source: §4 · p. 6

4.1 Certifying Sensing Robustness

  • Randomized smoothing bounds each sensor’s output probability under ℓ2-bounded input perturbations, and other sensing-certification strategies can be plugged in.The authors present randomized smoothing as an example and describe the sensing-certification choice as orthogonal to reasoning certification.Source: §4.1 · p. 6

4.2 Certifying Reasoning Robustness

  • Given partition-function inference oracles, the MLN certificate searches multiplier regimes and uses monotonicity and convexity to reduce perturbation optimization to boundary or zero-gradient candidates.The explored regimes are λ_i ∈ (−∞, −1] ∪ [0, +∞); the paper uses grid search or random sampling and leaves other efficient search strategies for future work.Source: §4.2 · pp. 6–7

5 Experiments

Experiments evaluate certified accuracy for image classification and information extraction, using sensing-reasoning pipelines with domain knowledge. The reported comparisons show gains over knowledge-free smoothing on road signs and higher certified robustness for information extraction, with similar gains on four additional image datasets.

5.1 Experimental Setup

  • The evaluation covers road-sign classification and stock-news information extraction, with domain rules encoding sign attributes or relationships among stock-price sensing tasks.The study reports five datasets overall; road-sign sensors use GTSRB and information extraction uses HighTech stock news.Source: §5 · p. 7, §5.1 · p. 8

5.2 Results of Road Sign Classification

  • Over 71% certified accuracy at CI = 0.50 and 49% at CI = 1.00, while vanilla smoothing has 0% in the large-CI, small-σ settings.With knowledge, certified accuracy is consistently higher across tested (CI, σ) settings; the cited large-CI outcomes use the same settings as the vanilla baseline.Source: Table 1 · p. 9, §5.2 · p. 9

5.3 Results of Information Extraction

  • At CS = 0.5, the information-extraction pipeline still provides significantly higher certified robustness under perturbations to all sensing models’ output confidences.The authors attribute the improvement to more examples having large prediction margins with knowledge integration.Source: Table 2 · p. 9, §5.3 · p. 9
  • PrimateNet, Word50, MNIST, and CIFAR10 experiments report similar results, with knowledge integration significantly boosting certified robustness.The additional image-classification results appear in Appendices F–H.Source: §5.3 · p. 9

6 Related Work

Prior certification work focuses on single models or pure ensembles, while joint inference has often been studied for clean-accuracy gains. This paper instead examines domain knowledge through joint inference as a route to end-to-end certified robustness.

Robustness for Single ML model and ML Ensemble

  • Prior certified defenses and robustness verification methods target single models or pure ensembles, which lack additional information to exploit for robustness.The related-work discussion notes that adversarial training can cost accuracy and training time, while randomized smoothing offers scalable certification.Source: §6 · p. 10

Robustness of End-to-end ML Systems

  • Joint inference with factor graphs, Markov logic networks, or Bayesian networks has been used to integrate domain knowledge and improve clean accuracy in ML pipelines.The cited applications span several real-world domains.Source: §6 · p. 10
  • This work shifts the focus from clean accuracy to using joint inference as exogenous information for end-to-end certified robustness.A prior study [17] explored empirical robustness improvement via knowledge integration but did not provide a robustness guarantee.Source: §6 · p. 10

7 Conclusions

The paper presents a certifiably robust sensing-reasoning pipeline with knowledge-based logical reasoning, supported by theoretical analysis and empirical results.

7 Conclusions

  • The work provides a certifiably robust sensing-reasoning pipeline with logical reasoning, proves robustness theoretically, and reports extensive empirical results.The authors identify future research on certifying general ML frameworks and integrating logical reasoning with statistical learning.Source: §7 · p. 10

Checklist

The checklist reports that the paper includes theoretical assumptions and proofs, reproducibility details, and discussion of limitations and societal impact. The supplementary material gives a counting-to-robustness reduction and uses Lagrange multipliers to derive an MLN robustness bound.

Checklist

  • The checklist marks the theoretical assumptions and proofs, experimental reproducibility materials, asset attribution, and discussion of limitations and societal impact as included or addressed.It also reports that the experiments use public and commonly used data.Source: Checklist · p. 15

A Hardness of General Distribution; Proof of Theorem 1

  • Theorem 1 reduces COUNTING to ROBUSTNESS, connecting approximate counting of a weighted query to robustness-oracle calls.The proof constructs a parameterized distribution and estimates the target probability through robustness queries and binary searches.Source: Proof of Theorem 1 · pp. 16–17

Proof of Theorem 1

  • The proof uses a parameterized distribution to estimate the target probability, with an estimator whose multiplicative deviation from R is bounded by e^x.The supplied proof passage states e^-x < R e^β0 < e^x.Source: Proof of Theorem 1 · pp. 16–17

Lagrange multipliers

  • The Lagrange-multiplier formulation adds λ(x1 − x2) to the objective while retaining the original constraints h(x1), k(x2) ≥ 0.The supplied discussion uses the equality-constrained problem and its multiplier formulation to motivate the subsequent bound.Source: Lagrange multipliers · p. 17

Proof of Lemma 4.1

  • Lemma 4.1 gives an MLN robustness bound using partition functions and maximum perturbations, with upper and lower bounds expressed through Lagrange multipliers.The supplied passages state the lemma and describe deriving its upper and lower bounds through multiplier choices.Source: Proof of Lemma 4.1 · pp. 17–18

C Supplementary Results for Algorithm 1

The supplementary result establishes monotonicity conditions for the multiplier-based objective used in the robustness analysis. Its direction depends on the sign range of λ_i.

Supplementary Results for Algorithm 1

  • For λ_i ≥ 0, the objective f_Zr increases with ϵ_i; for λ_i ≤ −1, it decreases with ϵ_i.The proof uses convexity in the transformed perturbation and σ(x_i) ∈ {0, 1} to establish these directions.Source: C Supplementary Results for Algorithm 1 · p. 19

D Image Classification on Road Sign Dataset

The road-sign pipeline encodes indication and exclusion relations between sign classes and attributes, while the stock-news pipeline checks consistency among extracted prices, percentage changes, and rise-or-fall predictions. The examples describe how rule violations can lower confidence in attacked predictions.

D Image Classification on Road Sign Dataset

  • The road-sign task uses 12 GTSRB sign classes and 13 attribute classes, with 14,880 training, 972 validation, and 3,888 test samples.The attributes cover border shape, border color, digits, and content.Source: D Image Classification on Road Sign… · p. 20
  • Road-sign knowledge combines indication rules linking sign classes to attributes with exclusion rules for mutually incompatible attributes.The example uses a predicted Stop Sign alongside a detected Triangle border to illustrate conflicting rules; the passage cautions that structural knowledge can fail when a sensor is completely fooled.Source: D Image Classification on Road Sign… · p. 20

E Information Extraction on Stock News

  • The stock-news pipeline extracts prices, percentage changes, and rise-or-fall labels using BERT-based binary sensors, then reasons over the resulting tuple.Its rules require prices to agree with the direction label and approximately follow the percentage change; the threat model perturbs sensor confidence values within a bound.Source: E Information Extraction on Stock News · pp. 21–22
  • When one extracted stock price is perturbed across the other price, the resulting inconsistency with the direction rule reduces confidence in that wrong extraction and increases confidence in the ground truth.The example describes this adjustment as a potential recovery of the correct prediction.Source: E Information Extraction on Stock News · p. 22

F Image Classification on PrimateNet Dataset

On PrimateNet, the knowledge-based sensing-reasoning pipeline generally improves certified robustness over smoothed sensing models, especially when the attack ratio is small. The advantage narrows under attacks on many sensors, and the authors identify structural knowledge as a limitation in that regime.

F Image Classification on PrimateNet Dataset

  • Without attacks, the knowledge-based pipeline outperforms the single model by about 0.7% across smoothing parameters σ.The authors say this suggests knowledge integration can relax the tradeoff between benign accuracy and robustness.Source: Table 3 · p. 24, F Image Classification on PrimateNet… · p. 25
  • With small sensing attack ratios, the knowledge-based pipeline has significantly higher Certified Robustness and Certified Ratio than the smoothed-model baseline; at 50% attacks, both are low and the gap is small.The comparison covers different smoothing parameters and perturbation bounds CI = {σ, 2σ}.Source: F Image Classification on PrimateNet… · pp. 24–25, Table 4 · p. 24
  • At high attack ratios, structural rules can favor the wrong prediction when their solution is non-unique; the authors call for more robust knowledge beyond hierarchy.Their example also notes that completely fooling a sensor can leave related classes indistinguishable.Source: F Image Classification on PrimateNet… · pp. 24–25
  • When CI = 2σ, the performance gap between the knowledge-based pipeline and baseline grows larger than when CI = σ.The passage reports that the knowledge-based pipeline performs consistently better at CI = σ as well.Source: F Image Classification on PrimateNet… · p. 25
  • Across attack scenarios, the pipeline yields more positive robustness margins and frequently larger margins, indicating more instances certified with correct predictions and stronger confidence bounds.Figure 5 defines the margin as the lower bound for the true class probability minus the upper bound for the top wrong class probability.Source: F Image Classification on PrimateNet… · p. 25, Figure 5 · p. 25
  • Using only hierarchical or only exclusive knowledge decreases robustness compared with using the full knowledge set.The comparison is reported in the appendix.Source: F Image Classification on PrimateNet… · p. 25

G Image Classification on Word50 Dataset

The Word10 experiments combine character-level logical knowledge with image classification and report improved certified accuracy over the vanilla randomized-smoothed baseline. On MNIST and CIFAR10, the pipeline also beats state-of-the-art baselines using simple generated knowledge rules.

G Image Classification on Word50 Dataset

  • Word50 contains five-character words; the experiment selects 10 of 50 words, with blurry character images perturbed by scaling, rotation, and translation.Character combinations provide prior knowledge; the training, validation, and test sets contain 2, 049, 408, and 423 variations, respectively.Source: G Image Classification on Word50 Dataset · p. 26
  • Word-level deduction rules link words to characters at positions, while exclusion rules mark characters that cannot co-occur at a position.Five character classifiers contribute their top two outputs alongside the 10-way word classifier, giving the MLN 20 input dimensions.Source: G Image Classification on Word50 Dataset · p. 26
  • Extra knowledge improves certified accuracy over the vanilla randomized-smoothed baseline across the tested smoothing and perturbation settings.Table 5 reports Word10 results for smoothing parameters 0.12, 0.25, and 0.50 and perturbation magnitudes 0.12, 0.25, 0.50, and 1.00.Source: G Image Classification on Word50 Dataset · p. 27, Table 5 · p. 27

H Image Classification with Constructed Knowledge Rules

  • For MNIST and CIFAR10, the authors generate pseudo-attributes and connect them to digit or category labels with indication and exclusion rules.MNIST digits receive two of five pseudo-attributes each; CIFAR10 uses ten pseudo-attributes, each assigned to 3–7 categories.Source: H Image Classification with… · p. 27
  • With simple generated rules, the pipeline beats state-of-the-art baselines on MNIST and CIFAR10.The paper notes that natural, meaningful rules may yield higher certified robustness, citing its road-sign and information-extraction tasks as examples.Source: H Image Classification with… · p. 27, Table 6 · p. 28, Table 7 · p. 28

I Ablation Study on Partial Knowledge Enrichment.

The PrimateNet ablation finds that partial knowledge can be fragile under severe scenarios, whereas complete enrichment performs better than no knowledge. The Bayesian-network analysis establishes a hardness result for general certification and gives a tractable, tight approach for binary trees.

I Ablation Study on Partial Knowledge Enrichment.

J Reasoning Component as Bayesian Networks

  • A Bayesian network represents variables and conditional dependencies with a directed acyclic graph; the paper focuses on binary-tree structures for tractable certification.The section uses this setting to examine robustness hardness and construct an efficient certification procedure.Source: J Reasoning Component as Bayesian… · p. 29

J.1 Hardness of Certifying Bayesian Networks

  • For Bayesian networks, deciding the robustness threshold is at least as hard as estimating the target probability to multiplicative error, with perturbations of order O(ε_c).This result concerns the difference between the target probability before and after parameter perturbation.Source: §J.1 · p. 29

J.2 Certifying Bayesian Networks

  • Binary-tree structure makes perturbation optimization and robustness checking tractable, and the resulting bounds can be tight.The authors contrast this case with the general optimization, which the theorem identifies as hard.Source: §J.2 · p. 30, §J.1 · p. 30

Proof of Lemma J.1

  • For a binary-tree node, the proof reduces robustness to maximizing and minimizing a function of its perturbed parent probabilities, then computes network robustness recursively from leaves upward.The node-level expression uses pre-computable constants derived from the network parameters.Source: §J.2 · p. 30, Proof of Lemma J.1 · p. 31
Loading 2003.00120v9…