Learning with Logical Constraints but without Shortcut Satisfaction
Authors: Zenan Li
Zehua Liu
Yuan Yao
Jingwei Xu
Taolue Chen
Xiaoxing Ma
Jian L\"{u}
Venue: ICLR 2023 notable top 25% (2023)
Keywords: training with logical constraints
logical formula encoding
variational learning
stochastic gradient descent ascent

Abstract: Recent studies have started to explore the integration of logical knowledge into deep learning via encoding logical constraints as an additional loss function. However, existing approaches tend to vacuously satisfy logical constraints through shortcuts, failing to fully exploit the knowledge. In this paper, we present a new framework for learning with logical constraints. Specifically, we address the shortcut satisfaction issue by introducing dual variables for logical connectives, encoding how the constraint is satisfied. We further propose a variational framework where the encoded logical constraint is expressed as a distributional loss that is compatible with the model's original training loss. The theoretical analysis shows that the proposed approach bears some nice properties, and the experimental evaluations demonstrate its superior performance in both model generalizability and constraint satisfaction.

LEARNING WITH LOGICAL CONSTRAINTS BUT WITH- OUT SHORTCUT SATISFACTION
Zenan Li', Zehua Liu?, Yuan Yao', Jingwei Xu', Taolue Chen', Xiaoxing Ma', Jian Lü
State Key Lab of Novel Software Technology, Nanjing University, China 2 Department of Mathematics, The University of Hong Kong, Hong Kong DDpartmentt Computer Science, Birkbeck, University of London, UK 1i znθ smail www..nj.du..... edu. en, 1 Liuzehua@connect hku. hk, t Schenbbb..cc ac. uk, {y- yao, jingwei x, xxm, 15) @nju. innju.duu edu, on
ABSTRACT
Recent studies have explored the integration of logical knowledge into deep learning via encoding logical constraints as an additional loss function. However, existing approaches tend to vacuously satisfy logical constraints through shortcuts, failing to fully exploit the knowledge. this paper, we present new framework for learning with logical constraints. Specifically, we address the shortcut satisfaction issue by introducing dual variables for logical connectives, encoding how the constraint is satisfied. We further propose variational framework where the encoded logical constraint is expressed as a distributional loss that is compatible with the model's original training loss. The theoretical analysis shows that the proposed approach bears salient properties, and the experimental evaluations demonstrate its superior performance in both model generalizability and constraint satisfaction.
INTRODUCTION
There have been renewed interests in equipping deep neural networks (DNNs) with symbolic knowl- edge such as logical constraints/formulas (Hu et al.) 2016 Xu et al. 2018: Fischer et al., 2019)] Nandwani et al. 2019: Li & Srikumar 2019][Awast et al. 2020; Hoernle et al. 2021). Typically, existing work first translates the given logical constraint into a differentiable loss function, and then incorporates it as a penalty term in the original training loss of the DNN. The benefits of this integration have been well-demmonstrated: it not only improves the performance, but also enhances the interpretability via regulating the model behavior satisfy particular logical constraints.
Despite the encouraging progress, existing approaches tend to suffer from the shortcut satisfaction problem, i.c., the model overfits to particular (easy) satisfying assignment of the given logical constraint. However, not all satisfying assignments are the truth, and different inputs may require different assignments to satisfy the same constraint. An illustrative example is given in Figure T Essentially, the example considers a logical constraint P + Q. which holds when (P, (P.Q)= (T, T)
or (P, Q) = (F, F)/(F, (F, T). However, is observed that existing approaches tend to simply satisfy the constraint via assigning F to P for all inputs, even when the real meaning of the logic constraint
arguably (P. Q) (T, T) for certain inputs (e.g., class '6' in the example).
To escape from the trap of shortcut satisfaction, we propose to consider how a logical constraint is satisfied by distinguishing between different satisfying assignments of the constraint for different inputs. The challenge here is the lack of direct supervision information of how constraint is satisfied other than its truth value. However, our insight that, by addressing this "harder" problem, we can make more room for the conciliation between logic information and training data, and achieve better model performance and logic satisfaction at the same time. To this end, when translating a logical constraint into loss function, we introduce dual variable for each operand of the logical connectives in the conjunctive normal form (CNF) of the logical constraint. The dual variables, together with the softened truth values for logical variables, provide working interpretation for the satisfaction the logical constraint. Take the example in Figure I for the satisfaction of P - Q, consider its CNF -P v Q and introduce two variables Ti and 72 indicate the weights of the

---

DL2: Shortcut satisfaction
Ours: Useful satisfaction
Training data:
Classification loss
O
1
2
3
4 9
Accursy
80.3%
3
K
6
7
8
Labels for class "6" removed
Sattrtttnn P Barsturtin
Baristtttson P. P.Sulitatioo
False
Logic Knowledge:
where
500
000
1900
1000
130
P: ((R()( 9,
Q
False
True
(:f(x) = 6
9
Logic loss
Iteration
Denation
R: image rotation
Accuracy and logic satisfaction for images class "6"
Figure 1: Consider a semi-supervised classification task of handwritten digit recognition. For the illustration purpose, we remove the labels of training images in class '6', but introduce logical rule P == (f()) 9) + Q == (f(x) 6) to predict '6', where R(x) stands for rotating the image x by 180% The ideal satisfying assignments should be (P, Q) = (T, T) for class '6', However, existing methods (e.g.. DL2 (Fischer et al. (019)) tend to vacuously satisfy the rule by discouraging the satisfaction of P for all inputs, including those actually in class *6', In contrast, our approach successfully learns satisfy when P holds for class '6', even achieving comparable accuracy (98.8%) to the fully supervised setting.
softened truth values of -P and Q, respectively. The blue dashed lines in the right part of Figure ! (the P-Satisfaction and Q-Satisfaction subfigues) indicate that the dual variables gradually converge to the intended weights for class '6'.
Based on the dual variables, we then convert logical conjunction and disjunction into convex combi- nations of individual loss functions, which not only improves the training robustness, but also ensures monotonicity with respect to logical entailment, i.e., the smaller the loss, the higher the satisfaction. Note that most existing logic to loss translations do not enjoy this property but only ensure that the logical constraint is fully satisfied when the loss is zero; however, it is virtually infeasible to make the logical constraint fully satisfied in practice, rendering an unreliable training process towards constraint satisfaction.
Another limitation of existing approaches lies in the incompatibility during joint training. That is, existing work mainly treats the translated logic loss penalty under multi-objective learning framework, whose effectiveness strongly relies on the weight selection of each objective, and may suffer when the objectives compete (Kendall al. 2018 Sennr & Koltun 2018) In contrast, introduce an additional random variable for the logical constraint to indicate its satisfaction degree, and formulate a distributional loss which is compatible with the neural network's original training loss under variational framework. We cast the joint optimization of the prediction accuracy and constraint satisfaction as game and propose a stochastic gradient descent ascent algorithm to solve it. Theoretical results show that the algorithm can successfully converge to superset of local Nash equilibria, and thus settles the incompatibility problem to large extent.
In summary, this paper makes the following main contributions: 1) new logic encoding method that translates logical constraints to loss functions, considering how the constraints are satisfied, in particular, to avoid shortcut satisfaction; 2) variational framework that jointly and compatibly trains both the translated logic loss and the original training loss with theoretically guaranteed convergence; 3) extensive empirical evaluations various tasks demonstrating the superior performance in both accuracy and constraint satisfaction, confirming the efficacy of the proposed approach.
2 LOGIC TO LOss FUNCTION TRANSLATION
2.1 LOGICAL CONSTRAINTS
For a given neural network, we denote the data point by (x.y) E x V/ and use w to represent the model parameters. We use variable denote the model's behavior of interest, which is represented
2

---

a function fw (x. y) parameterized by For instance, (predictive) confidence of y = given x. We require fw (x. y) to be differentiable with respect to w.
define Pw 1 x) as the
An atomic formula is in the form of x where DIIE (s, and is constant. We express a logical constraint in the form of a logical formula, consisting of usual conjunction, disjunction, and negation of atomie formulas. For instance, we can Pw (y 1 x) 0.95 V Pw (y = x) & 0.05 to specify that the confidence should be either no less than 95% or no greater than 5%. Note that v e can be written as 2 c S C, so henceforth for simplicity, we only have atomic formulas of the form v S c.
We use é indicate a state of v, which is concrete instantiation of u over the current model parameters w and data point y). We say state ê satisfies logical formula a, denoted by }= a, if holds under è. For two logical formulas a and 3. we say a }= | if any that satisfies a also satisfies B. Moreover, we write a B if a is logically equivalent to 33 i.e., they entail each other.
2.2 LOGICAL CONSTRAINT TRANSLATION
(A) Atomic formulas. For an atomic formula a == v S c, our goal learn the model parameters w to encourage that the current state 0* = fw- (x. can satisfy the formula for the given data point y). For this purpose, we define a cost function
Sa(v) == max(u- - 0),
(I)
and switch to minimize it. It is not difficult to show that the atomic formula holds if and only if wt is an optimal solution of minw S(w) mf (x.
c, 0) with S(w*) O.
For example, for the predictive confidence Pw ing cost function is defined as max(0.95 Pw (3/ 1 x), 0), which is actually the norm distance between the current state 0 and the satisfied states of the atomic constraint. Such translation not only allows to find model parameters w' efficiently by optimization, but also paves the way to encode more complex logical constraints as discussed in the following.
x) 2 0.95 introduced before, the correspond-
(B) Logical conjunction. For the logical conjunction 1 11 S ci A U/2 C2, where e2 fw.i i..i(x,, (x. y) for = 1, We first substitute the atomic formulas by their corresponding cost functions as defined in equation [ and rewrite the conjunction (5(v)) = 0) (S(v2) 0). Then, the conjunction can be equivalently converted into a maximization form, i.e., max S(v2) = O. Based on this conversion, we may follow the existing work and define the cost function of logical conjunction as (1) := max(S((1)) (S(2)))(()) S(2)). However, directly minimizing this cost function is less effective as cannot well encode how the constraints are satisfied, and it also not efficient since only one of (m1) and 5(12) can be optimized in each iteration. Therefore, we introduce the dual variable for each atomic formula, and further extend it to the general conjunction case for 1 Alt A " S c, as
Sx max Th
TTS( TI...., Th 2 0, TI + Tk
1.
(C) Logical disjunction. Similar to conjunction, the logical disjunction 1 := v 2/2 S q. can be equivalently encoded into minimization form. Hence, the corresponding cost function is follows,
S²(1 = min
Sy,(),), TI...., Tk 20,
Ti +
+ Tk =
Th
(D) Clausal Formulas. In general, for logical formula a = Mez VjeJ Viy I city in the conjunctive normal form (CNF), the corresponding cost function can be defined
(v) max min
Σ
#4 pi- max(us cij,0)
Pi
IEI
JEJG)
s.t. Σ 14
Σ Vij 1, Ur. 2 0,
IE
(
where p4(i E I) and vi E ( are the dual variables for conjunction and disjunction, respectively.
The proposed cost function establishes an equivalence between the logical formula and the optimiza- tion problem. This is summarized in the following theorem, whose proof included in Appendix A
3

---

Theorem 1. Given the formula Mez VJEJ Vij Cij. the dual variables {pi, I) and (Vig.j E J] of Sa converge to {pr, E I) and [Vi E J then the cost function of a can be computed as (u) = max,ez minje. (Sij == max(U;j - Cij. 0)}. Furthermore, the sufficiens and necessary condition of i fw- X F is that w is the optimal solution of min Sa (w), with the optimal value Sa 0.
2.3 ADVANTAGES OF OUR TRANSLATION
Monotonicity. As shown in Theorem the optimal w" ensures that model's behavior 8* fw- (x, y) can satisfy the target logical constraint a. Unfortunately, w' usually cannot achieve the optimum due to the coupling between the cost function (v) and the original training loss as well as the fact that (v)v) is usually non-convex. This essentially reveals the main rationale of our logical encoding, and we conclude it in the following theorem with the proof given in Appendix B
(a) and -iez VjEJ dij have Theorem 2. For two logical formulas Nie VjEJ Oij + 3 if and only if (v) 2 Sp(v) holds for any state of v.
Remarks. Theorem 2 essentially states that, when dual variables converge, we can progressively achieve a higher satisfaction degree of the logical constraints, as the cost function continues to decrease. This is especially important in practice since it is usually infeasible to make the logical constraint fully satisfied.
The introduced dual variables control the satisfaction degree of each individual atomic formula, and gradually converge towards the best valuation. Elaborately, the dual variables essentially learn how the given logical constraint can be satisfied for each data point, which resembles the structural parameter used in [Bengio et al. (2020) to disentangle causal mechanisms. Namely, the optimal dual variables r" disentangle the satisfaction degree of the entire logical formula into individual atomic formulas, and reveal the contribution of each atomic constraint to the entire logical constraint in discriminative way. Consider the cost function Si(v) max-e[o,1] 7S(11) + (1 ())( for I := aj V a2 The expectation E, [r*] estimates the probability of p(a: + x). and larger E, [r*] indicates greater probability that the first atomic constraint is met.
Interpretability.
Robustness improvement. The dual variables also improve the stability of numerical computations. First, compared with some classic fuzzy logic operators (c.g., directly adopting max and min operators to replace the conjunction and disjunction (Zadeh) 1965 Elkan al.) 1994 Häjjkk (2013)) the dual variables alleviate the sensitivity to the initial point. Second, compared with other commonly- used translation strategies (e.g., using addition and multiplication in DL.2 (Fischer al.. (019)), the dual variables balance the magnitude of the cost function, and further avoid some bad stationary points. Some concrete examples are included in Appendix C
3 A VARIATIONAL LEARNING FRAMEWORK
3.1 DISTRIBUTIONAL LOss FOR LOGICAL CONSTRAINTS
Existing work mainly adopts a multi-objectivy learning framework to integrate logical constraints into DNNs, which is sensitive to the weight selection of each individual loss. In this work, we propose a variational framework (Blei al. 2017) achieve better compatability between the two loss functions without the need of weight selection. Generally speaking, the original training loss for neural network is usually a distributional loss (e.g., cross entropy), which aims to construct a parametric distribution pw x that is close to the target distribution pxy(x). To keep the compatibility, we extend the distributional loss to the logical constraints. More concretely, we define an additional m-dimensional random variable z for the target logical constraint a and define z (v). where fw (x, .). Here, we use vector to indicate the combination of multiple variables (e.g.. U1 Cm in the logical constraint for training efficiency.
Note that can be considered as random variable even when the data point (x. y) is given hecause there usually exists randomness when training the model (e.g., dropout, batch-normaliztiion. etc.).
4

---

Next, we frame the training as the distributional approximation between the parametric distribution and target distribution over y and z, and choose the KL divergence as the distributional loss,
N
min
2xx)) z())).
(5)
By using Bayes' theorem, ply, 2 x can be decomposed as ply, 2/x) p(z (x, p(y|x), There- fore, we can reformulate equation
N
mii
(y: + |
(Z;: x;, xi))]
(6)
The detailed derivation can be found in Appendix D In equation 6 the first term is the original training loss, and the second term the distributional loss of the logical constraint.
The remaining question how to model the conditional probability distribution of the random indicates that the target logical constraint is satisfied. Thus, the target
variable Note that distribution of z can be defined as a Dirac delta distribution (Dirac 1981 Sec. 15), i.e., p(z] y) zero-centered Gaussian with variance tending zero (Morse & Feshbach 1954 Chap. 4.8). Furthermore, considering the non-negativity of z, we form the Dirac delta distribution as the limit of the sequence of truncated normal distributions on [0, +00):
p y) = lim TN 0, 1 lim
where of-) is the probability density function the standard multivariate normal distribution. For the parametric distribution of z, we model pw pw(2) (z|x, y) as the truncated normal distribution on [0, + with mean f = Sa(w) and covariance (8").
4
Pw (z
v /diag(0
1
where (-) is the cumulative distribution function of the standard multivariate normal distribution, and A denotes element-win wise division of vectors μ and Hence, the final optimization problem of our learning framework is
min W.6
Σ
KL (x)p (x:)s)) log (dia((5)
!1 log(1
pi
(7)
where ,4; - Sv.),,,, (x, y.). Different from the probabilistic soft logic that estimates the probability for each atomic formula, we establish the probability distribution TN μl, diag(o?)) of the target logical constraint. This allows directly determine the variance 8² of the entire logical constraint rather than analyzing the correlation between atomic constraints.
be viewed as competitive game (Roughgarden, 2010 Schaefer & Anandkumar 2019). Roughly speaking, they first cooperate to achieve both higher model accuracy and higher degree of logical constraint satisfaction, and then compete between these two sides to finally reach a (local) Nash equilibrium (even though it may not exist). The local Nash equilibrium means that the model accuracy and logical constraint satisfaction cannot be improved at the same time, which shows compatibility in the sense of game theory.
Moreover, the minimizations of w and
3.2 OPTIMIZATION PROCEDURE
Note that the dual variables and of the cost function μ4 = Sa(v;) also need to be optimized during training. solve the optimization problem, we utilize stochastic gradient descent ascent (SGDA) algorithm (with min-oracle) (Lin et al. 2020). and the details of the training algorithm summarized in Appendix[F] Specifically, we update w and Ty through gradient descent, update TA through gradient ascent, and update ò by its approximate min-oracle, i.c., via its upper bound (L(p(z)x,, y wp (z|x,
(exxx)) y)) < log (diag(5) 6)|+ } connst. Thus, the update of each iteration 82 = EN ii EN (v:).
5

---

The update of å plays an important role in our algorithm, because the classic SGDA algorithm (i.e., direct alternating gradient descent on w and d) may converge to limit cycles. Therefore, updating 6 via its upproximate min-oracle not only makes the iteration more efficient, but also ensures the convergence of our algorithm as summarized in Theorem 3
Theorem 3. Let v(-) ming L(-, 8), and assume L(-) is L-Lipschitz. Algorithm 7 with step size f/w 7/VT + ensures the output w of iterations satisfies
2 + Ao)
Bll / W 1
7/++1
where (-) is the Moreau envelop of v(-).
Remarks. Theorem states that the proposed algorithm with suitable stepsize can successfully converge to a point (w", 6", T Tύ)) where (w",8") is an approximate stationary point and (TA: TV) is global minimax point. More detailed analysis and proofs are provided in Appendix
EXPERIMENTS AND RESULTS
We carry experiments on four tasks, i.e., handwritten digit recognition, handwritten formula recognition, shortest distance prediction in a weighted graph, and CIFAR100 image classification. For each task, we train the model with normal cross-entropy loss on the labeled data as the baseline result, and compare our approach with PD (Nandwani et al. 2019) and DL2 (Fischer et al. 2019), which are the state-of-the-art approaches that incorporate logical constraints into the trained models. For PD, there are two choices (Choice and Choice 2 named by the authors) to translate logical constraints into loss functions which are denoted by PD and PD2, respectively. We also compare with SL (Xu et al.) 2018) and DPL (Manhaeve et al.) 2018) in the first task. These two methods are intractable in the other three tasks as they both employ the knowledge compilation (Darwiche Marquis 2002) to translate logical constraint, which involves implicit enumeration of all satisfying assignments. Each reported experimental result is derived by computing the average of five repeats. For each atomic formula
< c, consider it is satisfied if < tol where tol is predefined tolerance threshold to relax the strict inequalities. We set tol = 0.01 on the three classification tasks and tol = on the regression task (shortest distance prediction), respectively. More setup details can be found in Appendix H The code, together with the experimental data, is available at https: /gthhbb...bb. con/ Softwiser goriigrruupppe /eey without Shortcuts
4.1 HANDWRITTEN DIGIT RECOGNITION
In the first experiment, we construct a semi-supervised classification task by removing the labels of '6' in the MNIST dataset (LeCun et al. 1989) during training. We then apply a logical rule to
predict label '6' using the rotation relation between '6' and "9" f(x) = 9 + f fx) 6, where the input, and x denotes the result of rotating x by 180 degrees. We rewrite the above rule as the
disjunction (f(*) # 9) V (f(x) 6). We train the LeNet model on the MNIST dataset, and further
validate the transferability performance of the model on the USPS dataset (Hull 1994).
The classification accuracy and logical constraint satisfaction results of class '6' are shown in Table The -P-Sat. and Q-Sat. in the table indicate the satisfaction degrees of f(x) * 9 and f(x) = 6. respectively. At first glance, it is a bit strange that our approach significantly outperforms some alternatives on the accuracy, but achieves almost the same logic rule satisfaction. However, taking a find that alternatives satisfaction (i.e., fxx * 9) for the logical constraint, and thus cannot further improve the accuracy. In contrast, our approach learns to satisfy fx) 6 when (R(x)) 9, which is supposed to be learned from the logical rule.
closer look at how the logic rule is satisfied,
all prone learn an shortcut
On the USPS dataset, we additionally train a reference model with full labels, and it achieves 82. 1 1% accuracy. Observe that the domain shift deceases the accuracy of all methods, but our approach still obtains the highest accuracy (even comparable with the reference model) and constraint satisfaction. This is due to the fact that our approach better learns the prior knowledge in the logical constraint and
'The set of stationary points contains local Nash equilibria Jin al. 2020 In other words, all local Nash cquilibria are stationary points, but vice versa.

---

Table Results (%) the handwritten digit recognition task. The proposed approach learns how the logical constraint is satisfied (i.e., the Q-Sat.) while the existing methods fail.
MNIST
USPS
Method
Acc.
Sat.
-P-Sat.
Q-Sat.
Acc.
Sat.
-P-Sat.
Q-Sat.
Baseline
89.4
27.4
27.4
0.0
75.4
81.1
81.1
0.0
SL
85.5
97.0
97.0
0.0
48.7
98.8
98.8
0.0
DPL
88.0
78.0
78.0
0.0
25.6
8.8
8.8
0.0
PD1
89.2
44.2
44.2
0.0
73.7
87.0
87.0
0.0
PD2
89.3
63.1
63.1
0.0
74.3
87.6
87.6
0.0
DL.2
89.3
91.3
91.3
0.0
69.9
98.8
98.8
0.0
Ours
98.8
98.9
49.7
97.7
80.2
98.8
90.5
75.2
Table 2: Results (%) of the handwritten formula recognition task. The proposed approach achieves the best results.
Table 3: Results on the shortest distance pre- diction task. The proposed approach achieves the best results.
2/80* Split
5/20*
Split Sat.
Method
Acc.
Sat.
Acc.
Method
MSE / MAE
Sat. (%)
Baseline
57.4
64.0
75.6
81.5
Baseline
8.90 2.07
43,9
PD1
62.1
63.2
76.5
78.6
PD2
9.11 2.11
46.1
PD₂
62.5
62.5
76.4
78.4
DL.2
14.21 2.68
65.3
DL.2
62.9
57.5
79.3
86.6
Ours
7.09 1.87
69.0
Ours
65.1
82.4
79.5
92.8
It refers to the proportion of labeled and unlabeled data used from the training set.
thus yields better transferability, An additional experiment of a transfer learning task on the CIFARIO dataset showing the transferability of our approach can be found in Appendix
4.2 HANDWRITTEN FORMULA RECOGNITION
We next evaluate approach training formulas and 2K test formulas (Li et al., 2020). The task to predict the formula from the raw image, and then calculate the final result based on the prediction. We adopt simple grammar rule in the mathematical formula, i.e., four basic operators (+, x, +) cannot appear in adjacent positions. For example, "3 + x9" is not valid formula according the grammar. Hence, given formula with i symbols, the target logical constraint is formulated
handwritten formula (HWF) dataset, which consists of 10K
^/- (an a.2), with a. : (x.) + Adigiit (X++1) = 2 and a,2 == Pops (x:) + Pops (x.+1) 1, where Pdigits (x) and Pops (x) represent the predictive probability that is digit or an operator, respectively. This logical constraint emphasizes that either any two adjacent symbols are both numbers (encoded by a,1). ) or
only one of them is a basic operator (encoded by a,2).
To show the efficacy of our approach, we cast this task in a remi-supervised setting, in which only very small part of labeled data available, but the logical constraints of unlabeled data can be used during the training process. The calculation accuracy and logical constraint satisfaction results are provided in 2 In the table, we consider two settings data splits, i.e., using 2% labeled data and 80% unlabeled data, as well using 5% labeled data and 20% unlabeled data in the training set. observed that our approach achieves the highest accuracy and logical constraint satisfaction in both cases, demonstrating the effectiveness of the proposed approach.
4.3 SHORTEST DISTANCE PREDICTION
We next consider regression task, i..., to predict the length of the shortest path between two vertices in a weighted connected graph g (V,E), Basic properties should be respected by the model's prediction f()), i.e., for any Uj Ug 77 V. the prediction should obey (1) symmetry:
7

---

95.1
Accu rayy (%%
0130141
60
43-
15
20
voars
Redker50
V0016
Repheri0
(a) Accuracy class classification
Accuracy of superclass classification
The accuracy results (%) of image classification on the CIFAR100 dataset. The proposed approach outperforms the competitors in all the three cases for both class and superclass classification.
Figure 2:
f(e,, 0ÿ) = fly,, v.) and (2) triangle inequality: f(v., uy) S f(e, 2k) + f(uk, 1y). We train an MLP that takes the adjacency matrix of the graph the input, and outputs the predicted shortest distances from the source node to all the other nodes. In the experiment, the number of vertices is fixed to 15, and the weights of edges are uniformly sampled among (1.2....,9)
The results are shown in Table 3 We do not include the results of PD; as it does not support this regression task (PD, only supports the case when the softened truth value belongs [0, 1J.. It is observed that our approach achieves the lowest MSE/MAE with the highest constraint satisfaction. We further investigated the reason of the performance gain, and found that models trained by the existing methods easily overfit to the training set (e.g., training MSE/MAE nearly vanished), In contrast, the model trained by our method well regulated by the required logical constraints, making the test error more consistent with the training error.
4.4 IMAGE CLASSIFICATION
We finally evaluate our method on the classic CIFARI00 image classification task. The CIFARI00 dataset contains 100 classes which can be further grouped into 20 superclasses (Krizhevsky et al. 2009). Hence, we use the logical constraint proposed by Fischer et al. (2019), i.e., if the model classifies the image into any class, the predictive probability of corresponding superclasses should first achieve full mass. For example, the people superclass consists of five classes (baby, boy, girl, man, and woman), and thus Ppeople (x) should have 100% probability if the input x is classified as girl. We can formulate this logical constraint as AsEspperclasses (p. (x) = 0.0% V p. (x(x) = 100.0%). where the probability of the superclass is the sum of corresponding classes' probabilities (for example, Ppeopie (x) Phahy (x) + Pboy (x) Pgirl (x) Pman (x) + Pwoman (x)).
construct a labeled dataset of 10,000 examples and an unlabeled dataset of 30,000 examples by randomly sampling from the original training data, and then train three different models (VGG16 ResNe150, and DenseNet100) to evaluate the performance of different methods. The results of classification accuracy and constraint satisfaction shown in Figure and Table respectively, We can observe significant enhancements in both metrics of our approach.
RELATED WORK
Learning with constraints. Research on linking learning and logical reasoning has emerged for years (Roth & Yih 2004:Chhagg et al.) 2008 Cropper & Dumančió 2020). Early research mostly concentrated on mining well-generalized logical relations (Muggleton) 1992). i.e., inducing a set of logical (implication) rules based on given logical atoms and examples. Recently, several work switch to training the model with deterministic logical constraints that are explicitly provided (Kimmig
al. 2012 Giannini et al.) 2019 Nandwani et al. 2019: van Krieken et al. 2022 Giunchiglia et al. 2022). They usually use an interpreter to soften the truth value, and utilize fuzzy logic (Wierman
2016) to encode the logical connectives. However, such conversion is usually quite costly, they
necessitate the use an interpreter, which should be additionally constructed by the most probable explanation (Bach et al. 2017). Moreover, the precise logical meaning is lost due the introduction of
8

---

Table 4: The constraint satisfaction results (%) of image classification on the CIFARI00 dataset. The proposed approach outperforms the competitors in all the three cases.
Method
VGG16
ResNet50
DenseNet100
Baseline
63.0
48.5
39.7
PD1
57.7
63.9
53.5
PD₂
57.5
69.2
54.9
DL2
31.2
78.4
62.2
Ours
81.1
87.2
88.2
the interpreter and is also unclear if such encoding bears important properties such monotonicity. To address this issue. Fischer issue,Fischhr et al. (2019) abandon the interpreter, and use addition/multiplicatiinn
to encode logical conjuncttion/dssuunttionn Yang al. (2022) apply straight-throug estimators to encode CNF into a loss function. However, both of them still lack the monotonicity property. Xu et al. (2018) propose semantic loss to impose Boolean constraints
the output layer ensure the monotonicity property. However, its encoding rule does not discriminate different satisfying assignments, causing the shortcut satisfaction problem. HHeerll et al. (202I) aim training a neural network that fully satisfies logical constraints, and hence directly restrict the model's output to the constraint. Although they introduce a variable choose which constraint should be satisfied, the variable is categorical and thus limited to mutually exclusive disjunction.
Neuron-symbolic learning. Our work is related to neuro-symbolic computation (Garcez al. 2019, Marra et al. (021). In this area, integrating learning into logic has been explored in several directions including neural theorem proving (Rocktäschel & Riedel, 2017,Minert
et al. 2020),
extending logic programs with neural predicates (Manhaeve et al.) | Yang et al. 2020). encoding algorithmic layers (e.g., satisfiability solver) into DNNs (Wang et al. 2019 Chen et al. [2020), using neural models to approach executable logical programs (Li & Srikumar 2019 Badreddine et al.
2022
Ahmed et al. 2022). as well as incorporating neural networks into logic reasoning (Yang et al.
Evans & Grefenstette 2018 Dong et al. 2019). Along this direction, there are other ways to integrate logical knowledge into learning, e.g.. knowledge distillation (Hu et al. (016), learning embeddings for logical rules Xie et al.] 2019), treating rules noisy labels (Awasthi al. 2020).
2017
and abductive reasoning DDai et al. 2019 Zhou 2019).
Multi-objective learning. Training model with logical constraints is essentially a multi-objectivv learning task, where two typical solutions exist (Marler & Arora, 2004). i.e., the e-construiní method and the weighted sum method. The former rewrites objective functions into constraints, i.e., solving min, (z), s.t., g(x) < é instead of the original problem min (x)) g(x)). E.g., Donti et al. 20021 directly solve the learning problem with (hard) logical constraints via constraint completion and correction. However, this method may not be sufficiently efficient for deep learning tasks considering the high computational cost of Hessian-vector computation and the ill-conditionedness of the problem. The latter method is relatively more popular, which minimizes proxy objective, i.e., weighted average min, Wi (ff(()) + wzg(2). Such method strongly depends on the weights of the two terms, and may be highly ineffective when the two losses conflict (Kendall et al. 2018: Sener & Koltun 2018).
6 CONCLUSION
In this paper, we have presented new approach for better integrating logical constraints into deep neural networks. The proposed approach encodes logical constraints into a distributional loss that is compatible with the original training loss, guarantecing monotonicity for logical entailment, significantly improving the interpretability and robustness, and avoiding shortcut satisfaction of the logical constraints large. The proposed approach has been shown to be able to improve both model generalizability and logical constraint satisfaction. A limitation of the work is that we set the target distribution of any logical formula as the Dirac distribution, but further investigation is needed to decide when such setting could be effective and whether an alternative could be better. Additionally. our approach relies on the quality of the manually inputted logical formulas, and complementing with automatic logic induction from raw data is an interesting future direction.

---

ACKNOWLEDGMENT
We are thankful to the anonymous reviewers for their helpful comments. This work is supported by the National Natural Science Foundation of China (Grants #62025202, #62172199). T. Chen is also partially supported by Birkbeck BEI School Project (EFFECT) and an overseas grant of the State Key Laboratory Novel Software Technology under Grant #KFKT2022A03. Yuan Yao (y. yaoenjuu..... edu. en) and Xiaoxing Ma ju. edu. en) are the corresponding authors.
REFERENCES
Leonard Adolphs. Non convex-concave saddle point optimization. Master's thesis, ETH Zurich, 2018.
Kareem Ahmed, Stefano Teso, Kai-We Wei Chang, Guy Van den Broeck, and Antonio Vergari. Semantic probabilisticc layers for neuro-symbolic learning. arXiv preprint arXiv:2206.00426. 2022.
Abhiject Awasthi, Sabyasachi Ghosh, Rasna Goyal, and Sunita Sarawagi. Learning from rules generalizing labeled exemplars. In International Conference on Learning Representations, 2020.
Stephen H Bach, Matthias Broecheler, Bert Huang, and Lise Getoor. Hinge-loss markov random fields and probabilistic soft logic. 2017.
Samy Badreddine, Artur d' Avila Garcez, Luciano Serafini, and Michael Spranger. Logic tensor networks. Artificial Intelligence, 303:103649, 2022.
Yoshua Bengio, Tristan Deleu, Nasim Rahaman, Rosemary Ke, Sébastien Lachapelle, Olexa Bilaniuk, Anirudh Goyal, and Christopher Pal. A meta-transfer objective for learning to disentangle causal mechanisms. In International Conference on Learning Representattinns 2020.
David M Blei, Alp Kucukelbir, and Jon D McAuliffe. Variational inference: A review for statisticians. Journal of the American statistical Association, 112(518):59--87) 2017.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Ming-Wos Wei Chang, Lev-Arie Ratinov, Nicholas Rizzolo, and Dan Roth. Learning and inference with constraints. Proceedings of the 23rd national conference on Artificial intelligence, pp-
1518-1518, 2008.
Xinshi Chen, Yufci Zhang, Christoph Reisinger, and Le Song. Understanding deep architectures with reasoning layer. Advances in Neural Information Processing Systems, 2020.
Rizwan A Choudrey. Variational methods for Bayesian independent component analysis. PhD thesis, University of Oxford Oxford, UK, 2002.
Andrew Cropper and Sebastijan Dumančić. Inductive logic programming at 30: a new introduction.
arXiv preprint urXiv:2008.07912, 2020.
Wang-Zhou Dai, Qiuling Xu, Yang Yu, and Zhi-Hua Zhou. Bridging machine learning and logical
reasoning by abductive learning. In Advances in Neural Information Processing Systems, pp- 2815 2816, 2019.
Adnan Darwiche and Pierre Marquis. A knowledge compilation map. Journal of Artificial Intelligence Research, 17:229-264, 2002.
Damek Davis and Dmitriy Drusvyatskiy. Stochastic subgradient method converges at the rate Ok44 on weakly convex functions. arXiv preprint arXiv: 1802.02888,, 2018.
Paul Adrien Maurice Dirac. The principles of quantum mechanics. Number 27. Oxford university press, 1981.
Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. Neural logic machines. In International Conference Learning Representations, 2019.
10

---

Priya L Donti, David Rolnick, and Zico Kolter. De3: A learning method for optimization with hard constraints. In International Conference on Learning Representations, 2021.
Dmitriy Drusvyatskiy and Courtney Paquette. Efficiency of minimizing compositions of convex functions and smooth maps. Mathematical Programming, 178(1):503-558 2019.
Charles Elkan, HR Berenji, B Chandrasekaran, CJS De Silva, Y Attikiouzel, D Dubois, Prade, P Smets, C Freksa, ON Garcia, et al. The paradoxical success of fuzzy logic. IEEE expert, 94): 3-49, 1994.
Richard Evans and Edward Grefenstette. Learning explanatory rules from noisy data. Journal of Artificial Intelligence Research, 61:1-64, 2018.
Mare Fischer, Mislav Balunovic, Dana Drachsler-Cohen Timon Gehr, Ce Zhang, and Martin Vechev. DI2: training and querying neural networks with logic. In International Conference on Machine Learning, pp. 1931-1941. PMLR, 2019.
A Garcez, M Gori, LC Lamb, Serafini, M Spranger, and SN Tran. Neural-symbolic computing, An effective methodology for principled integration of machine learning and reasoning. Journal of Applied Logics, 1-632, 2019.
Francesco Giannini, Giuseppe Marra, Michelangelo Diligenti, Marco Maggini, and Marco Gori. On the relation between loss functions and t-norms. In International Conference on Inductive Logic Programming, pp. 36-45. Springer, 2019.
Eleonora Giunchiglia, Mihaela Catalina Stoian, and Thomas Lukasiewicz. Deep learning with logical constraints. urXiv preprint arXiv:2205.0055: 2022.
Petr Hájek. Metamathematics of fuzzy logic, volume 4. Springer Science & Business Media, 2013.
Nicholas Hoernle, Rafael Michael Karampatsis, Vaishak Belle, and Kobi Gal. Multiplexnet: Towards fully satisfied logical constraints neural networks. arXiv preprint arXiv:2111.01564, 2021.
Zhiting Hu, Xuezhe Ma, Zhengzhong Liu, Eduard Hovy, and Eric Xing. Harnessing deep neural networks with logic rules. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, pp. 2410-2420, August 2016.
Jonathan J. Hull. A database for handwritten text recognition research. IEEE Transactions on paltern analysis and machine intelligence, 16(5):550-554, 1994.
Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex-nonconeave minimax optimization? In International Conference on Machine Learning, pp. 4880-4889. PMLR, 2020.
Alex Kendall, Yarin Gal, and Roberto Cipolla. Multi-task learning using uncertainty to weigh losses for scene geometry and semantics. In Proceedings of the IEEE conference on computer vision and paltern recognition, pp. 7482-7491, 2018
Angelika Kimmig, Stephen Bach, Matthias Broecheler, Bert Huang, and Lise Getoor. A short introduction to probabilistic soft logic. In Proceedings of the NIPS Workshop on Probabilistic Programming: Foundations and Applications, pp. 1-4, 2012.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Bernhard Boser, John Denker, Donnie Henderson, Richard Howard, Wayne Hubbard, and Lawrence Jackel. Handwritten digit recognition with a back propaprrpagatton network. Advances in neural information processing systems, 2, 1989.
Qing Li, Siyuan Huang, Yining Hong, Yixin Chen, Ying Nian Wu, and Song- Chun Zhu. Closed loop neural-symbolic learning via integrating neural perception, grammar parsing, and symbolic reasoning. International Conference on Machine Learning, pp. 5884-5894. PMLR, 2020.
Tao Li and Vivek Srikumar, Augmenting neural networks with first-order logic. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguisties, pp. 292-302, July 2019.
11

---

Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-coneawe concevee minimax problems. In International Conference on Machine Learning. pp. 6083-6093, PMLR, 2020.
Songtao Lu, Mingyi Hong, and Zhengdao Wang. Pa-gd: On the convergence of perturbed alternating gradient descent to second-order stationary points for structured nonconvex optimization. In International Conference on Machine Learning, pp. 4134-4143, PMLR, 2019.
Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Deepproblog: Neural probabilistic logic programming. Advances Neural Information Processing Systems, 31 51:3749-3759, 2018.
R Timothy Marler and Jasbir S Arora. Survey of multi-objecctvve optimization methods for engineering. Structural and multidisciplinary optimization. 26(6):369-395, 2004.
Giuseppe Marra, Sebastijan Dumančić, Robin Manhaeve, and Lue De Raedt. From statistical relational to neural symbolic artificial intelligence: a survey, arXiv preprint arXiv:2108. 1451,, 2021.
Antonio Martinón. Distance to the intersection of two sets. Bulletin of the Australian Mathematical Society, 70(2):329-341, 2004.
Pasquale Minervini, Sebastian Riedel, Pontus Stenetorp, Edward Grefenstette, and Tim Rocktäschel. Learning reasoning strategies in end-to-end differentiable proving. In International Conference on Machine Learning, pp. 6938-6949, PMLR, 2020,
Philip M Morse and Herman Feshbach. Methods of theoretical physics. American Journal of Physics, 22(6):410-413, 1954.
Stephen Muggleton. Inductive logic programming. Number 38. Morgan Kaufmann, 1992.
Yatin Nandwani, Abhishek Pathak, Mausam, and Parag Singla. A primal dual formulation for deep learning with constraints. In H. Wallach, H. Larochelle, A. Beygelzimer, F. dAlché Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Angelia Nedić and Asuman Ozdaglar. Subgradient methods for saddle-point problems. Journal of optimization theory and applications, 142(1):205-228, 2009.
Michael JD Powell. On search directions for minimization algorithms. Mathematical programming, 4(1):193-201, 1973.
Ralph Tyrell Rockafellar. Convex analysis. Princeton university press, 2015.
Tim Rocktäschel and Sebastian Riedel. End-to-end differentiable proving. In Advances in Neural Information Processing Systems, pp.
2017.
Dan Roth and Wen-tau Yih. A linear programming formulation for global inference in natural language tasks. Technical report, Illinois Univ Urbana- Champapan Dept of Computer Science, 2004.
Tim Roughgarden. Algorithmic game theory. Communications of the ACM, 53(7):78-88 2010.
Florian Schaefer and Anima Anandkumar. Competitive gradient descent. In H. Wallach, H. Larochelle, A. Beygelzimer, F. dAlché Buc, E. Fox, and R. Garnett (eds.), Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Ozan Sener and Vladlen Koltun. Multi-task learning multi-objective optimization. In Advances in Neural Information Processing Systems, pp. 525-536, 2018
Emile van Krieken, Erman Acar, and Frank van Harmelen. Analyzing diffcrentiable fuzzy logic operators. Artificial Intelligence, 302: 103602, 2022.
Re-Wei Wang, Priya Donti, Bryan Wilder, and Zico Kolter. Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. In International Conference on Machine Learning, pp. 6545-6554 PMLR, 2019.
12

---

Mark J Wierman. An introduction the mathematics of uncertainty: including set theory, logic, probability, fuzzy sets, rough sets, and evidence theory. Creighton University. Retrieved, 16, 2016.
Yaqi Xie, Ziwei Xu, Mohan S Kankanhalli, Kuldeep S Meel, and Harold Soh. Embedding symbolic knowledge into deep networks. In Advances in Neural Information Processing Systems, pp. 4233-4243, 2019.
Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Broeck. A semantic loss function for deep learning with symbolic knowledge. In International conference on machine learning, pp-
5502-5511. PMLR, 2018.
Fan Yang. Zhilin Yang, and William W Cohen. Differentiable learning of logical rules for knowledge base reasoning. In Advances in Neural Information Processing Systems, pp. 2316-2325, 2017.
Junchi Yang. Antonio Orvieto, Aurelien Lucchi, and Niao He. Faster single-loop algorithms for minimax optimization without strong concavity. arXiv preprint arXiv:21 2021.
Zhun Yang, Adam Ishay, and Joohyung Lee, Neurasp:
Embracing neural networks into answer set programming. In Christian Bessiere (ed.), Proceedings of the Twenty-Ninhh International Joint Conference on Artificial Intelligence, IJCAI-20, pp. 1755-1762. International Joint Conferences Artificial Intelligence Organization, 7 2020. doi: 10. 0t.24493/jeaii22202255 URL https
//doi. 0ttp:/10..4993//42 /at.:////aa....//// 2020/242 Main track.
Zhun Yang, Joohyung Lee, and Chiyoun Park. Injecting logical constraints into neural networks via straight-through estimators. In International Conference Machine Learning, pp. 25096-25122. PMLR, 2022.
L.A. Zadeh. Fuzzy sets. Information and Control, 8(3):338- --33388-33,-1 1965.
Zhi-Hua Zhou, Abductive learning: towards bridging machine learning and logical reasoning. Science China Information Sciences, 62:1-3, 2019.
13

---

A PROOF OF THEOREM
A. TRANSLATION EQUIVALENCE OF LOGICAL CONJUNCTION
The following proposition shows the equivalence of our translation and the original expression of logical conjunction.
Proposition 1. Given :- Ni=1 v G. where vi [ y) and S; max(c; Css 0) for k, if (T, 1 Fi=1 are the optimal solution of the cost function (I))).
Σ ri S(v)) max(S(())....
Furthermore, = (x. y) - if and only if ww is the optimal solution of minw S^(w) (w), with the optimal value
S^(w") = max(SS (w"), ",(").,S((w"..)) 0.
Proof. For the minimization of the cost function Sx
min Sx (w) max(S (w).... , Sk(w)),
(8)
we introduce slack variable and rewrite Eq. equation 8 as
min t, s.t., t 12 Si(w), i I.......
(9)
w.t
The Lagrangian function of Eq. equation is
L(w, NW,.TT,..... ,,, Th) = Σ ((:((w)- -t),
where T; = = 1...., k. Let the gradient of t vanish, we can obtain the dual problem:
max min Ti (w) + .... S. Sk(w),
Toorkh
s.t.
T + ... + 05 < 1, 1,...,k.
By using the max-min inequality, have
max min Ti S,S, + ... Sx (w) < min max Ti Si +... (w)) Ti....Te
Therefore, the cost function (w( of the logical conjunction can be computed by introducing the dual variables T, 1,...,ke k:
Sx(w) 10.
max
+ ... (w)).
+n==1
The Karush (KKT) condition of Eq. equation 9 is
7I (w) +... Th (w))
Ti + Th =
t> S,),, Ti 2 0, i= --....,k
7,(t - ((t-S((w)) = 0, i= 1....
We denote the index set of the largest element in the set {S }/= by I. Suppose dual variables (Tr)/_) converge to {Tī ] then 7 = 0 for any j & I, and thus Eier Tf 1. Since S; S:(w) (w)...., for any i E I, we have
SA (w) 5 (w) ..... Sx())
Σ 7,5,(w) (w)...
1ET
14

---

Furthermore, if w is the optimal solution and Sx(w*) O, we have
Si (ww") = Sx. (w)) O,
which implies that w ensures the satisfaction of the constraint A U; G.
On the other hand, if v* = fw- (x.y) entails the logical conjunction A 2/ S c. then we have (,(w)) for i 1...., Therefore, we have w is the optimal solution of Sw(w) with SA (w*) =
A.2 TRANSLATION EQUIVALENCE OF LOGICAL DISJUNCTION
We also have the following proposition demonstrating the equivalence between the cost function (I) and the original expression of logical disjunction.
Proposition 2. Given V v S ca. where v; = (x. and S; := max("; Ct, 0) for
h. if (T; 1i=1 are the optimal solution of the cost function (1),,, we have
k
Σ
T. S(,,) min(S(u)).....((u..))
Furthermore, = fw. (x. y) F 1 and only if ww is the optimal solution of minw S. (w), with the optimal value
Sy(w") = (w.)
Proof. For the minimization of the cost function Sy Sy(w)
min (w): (
Sx(w)),
(10)
we introduce slack variable and rewrite Eq. equation a0
min max t, s.t., t S Si(w), i I....,A. w
(11)
The corresponding dual problem is
min min (w) + ... Sx(), Thoorh
s.t.
T + Tk 1, s < 1, I.
Therefore, the cost function Su(w) of the logical disjunction can be computed by introducing the dual variables Tg I,...
(w) min S1() E
(w))
Similar to the proof of Proposition I by using the KKT condition of Eq. equation II and supposing dual variables (r converge to (T we can obtain that
(w) = Si
Sww)
Σ S[S)(w) min(S (w). ..... ..., Sx())).
SEI
If w is the optimal solution and (w")) O, there exists Si(w*) 0, which implies that w ensures the satisfaction the constraint Vi_ v. S c..
On the other hand, if w* entails the logical disjunction V 14 S cr then there exists S;(w*) 0. Therefore, we have w is the optimal solution of Sv(w") with Sy(w*) = O.
A.3 PROOF OF THEOREM 1
The proof can be directly derived from Proposition and Proposition 2
15

---

B PROOF OF THEOREM 2
Proof. We first denote all variables Ui..... involved in the logical constraint by a vector e, and in this sense the corresponding constants C22 2 1,..., k, in the logical constraint should be extended to I U {+00} such that the constraints a and / can be written as
at = Nez VjEz (o S Cij (o0)
B == Nie VjEJ (0 S (9))
For the sufficient condition, suppose that v* }= Then, we have Sa by using Theorem Since Sa (v) 2 S2(v) holds for any v E V, and the cost function is non-negative, we can obtain that (p("") which implies that v" + B.
For the necessary condition of Theorem
2
we introduce the following proposition.
Proposition 3. Given the underlying space for any point u E V and subset C C V. we define the distance of 'o from C'
dist(v, C) = inf (disst(r, u) C...
Moreover, let A and B be two closed subsets V, , if A is not an empty set, then the sufficient and necessary condition for A C B is that
dist(v, dist(v, B), Yu E V.
Therefore, let A and B be two sets implied by and B, i.e.
(a) A = niez UJes {v S Sjj
B = niez Ujes {o lolus ci ) }.
by using Proposition V E V.
obtain that - B if and only if dist(u, A) 2 dist(v, B) for any
S C2. the corresponding cost functions (v) max(v - CI, 0) and S2(v) = max 0 c2, 0), respectively. Then, the cost functions are essentially the (Chebyshev) distances of
Given atomic formulas a₁ S C₁ and 02
the constraints {v v Ci and {o v S c2). respectively. (It should be noted that v < c can be decomposed into the conjunction of us S C,, 1.....k) k). Hence, through Proposition the sufficient and necessary condition of a1 } 02 that
Sa, (v) 2 S., for any v E V.
Now, the rest to prove that the cost functions logical conjunction and disjunction are still the distance of from the corresponding constraint, and it is not difficult to derive the results through a few calculations linear algebra. One can also obtain a direct result by using Martinón (2004 Theorem 1).
C CONCRETE EXAMPLES IN ROBUSTNESS IMPROVEMENT
(1) Let consider logical constraint (v2 -1) (3v 2 2). the corresponding cost function based on the min and max operators is S(v) = min(2² + max - 3r, 0)). If we directly minimize Sv)) and V ((vo) -2n 0. Hence,
and the initial point by vo vo has already been an optimal solution of min S(v). In this case, the conventional optimization technique not effectual, and cannot find feasible solution that entails the disjunction even though it exists. Nevertheless, with the dual variable т, the minimization problem is min T(v2 + 1)
will have S(vo) of +1
- (max((2 v, 0)). Given initial points to and Tu 0.5, one can easily obtain feasible solution x* = 1.5 via the coordinate descent algorithm.
(2) For translation strategy used in DI.2, the cost functions of conjunction an 02 and disjunction a1 V 02 are defined by (v) S(e)) + S(2)) and (v) S(v1) S(22), respectively. The conjunction translation is essentially a special case our encoding strategy (i.e., Ti and 72 are fixed to 0.5). For the disjunction, the multiplication may ruin the magnitude of the cost function, making it no longer a reasonable measure of constraint satisfaction. Moreover, this translation method also brings more difficulties to numerical calculations. For example, considering the disjunction constraint (v = 1) V (u = 2) V (v = 3). Sy()), = S(1)) S(e)) S(vy) induces two more bad stationary points (i.e., 0 1.5 and 2.5) compared with min,,r Sv(v) (1S(1) 72S(22) + (v)).
16

---

D THE COMPUTATION OF KL DIVERGENCE
For input-output pair (x,y), with the logical variable 2, the KI. divergence
KL(ply,2 z x) Pw (y, 2 x))
ply,2 x) log ply, x)
Pw (y, 2 x)
yz
ply x)
p(z x, Pw (z x, y)
ply,2 z x)
log
+ log
Pw (y |x)
yza
For the first term in RHS,
/
ply x)
ply, 2 x) log
KL(p(y xx) xx)llww(y x));
Pwly ly x)
yzz
and for the second term in RHS.
J ply, 2 x) log
pl2 x,
[ ply xx)((z) x, log
p(z x)
Pw x,y)
Pw x,
= =Eylx / pla x, x,y) log
p(z x,
Pw (z x,y)
E x,y)llp
x.y)]].
It follows that KT(p(y, 2 ()) x)) = KL(ply x))lpw(yy x)) + EyIx x,y) x,y))]-
E KL DIVERGENCE OF TRUNCATED GAUSSIANS
Given two normal distributions truncated on [0. 4oo) with means μn and μr2 and variances of and oz. the KI. divergence can be computed as (Coourrey
[Appendix A.5]
(M - 22)
IL(TNNIITNN) =
log
+
2
02
o2
2p1
σ1
)/11
02
02
v 2T
exp
2
[1 erf(
20
/2o
crf(
log
V2az
orf(
Mi
where crf(.) is the Gauss error function.
Let μ4 = 0 and σj limit to zero. We can obtain that
lim KL(77W/0..))))7N3222.....0 = log 02 + 01
31 20
logg(1 erf( 122
)).
V202
F THE ALGORITHM OF LOGICAL TRAINING
In practice, set lower bound (0.01) for the variance 52 considering the numerical stability.
G OPTIMALITY OF ALGORITHM
G.1 CONVERGENCE OF DUAL VARIABLES
We first discuss the optimality of dual variables (T), T²). Since fu is convex w.r.t. to Tx and Tv- and L(w, o; TxS TV) is strietly increasing and convex w.r.t. st; [0, fo0), can derive that
17

---

Algorithm Logical Training Procedure
Initialize: w randomly; T and T uniformly; 8 fort = 0, .,....du do
Draw collection of i.i.d. data samples ((x;
w w 1/w V [.w, 8; TA, Tv).
8
VEN Ei=1 pt)/N.
[+1 T + T) VT, I(w, Th, TV).
TV TV ny V Lo, 6: Tn. TV).
4+1
end for
L(w, 6; TAi Tv) is convex w.r.t. Ty and Ty. via the convexity of composite functions (Boyd al. 2004, Sec. 3.2). Hence, min,, max,, L(w. 5; TA, Tv) is in fact convex-concave optimization, and the PL assumption satisfied (Yang et al. (02T), thus the GDA algorithm with suitable step size can achieve global minimax point (i.e., saddle point) in O(e iterations (Nedić & Ozdaglar 2009 Adolphs 2018). Some more properties of (Tx TT) are also detailed in Proposition and Theorem
Next, we confirm that, the PL condition holds when the logical constraints are not sufficiently satisfied. Since L(w, 8; TA Tv) is strictly increasing and convex w.r.t. μe [0, +oo), we instead analyze the cost function, i.e., [4; = S.vv..
Proposition 4. Given logical constraint a, assume its corresponding cost function Sa(v), and maX+, milr, S. (v) 2 K with constant >> O. Then, the PL property for any Th i.e.
|V Sa Tv)]
mmaxx Sa(v; TA: TV) Sa(v: TAi Av)l
To
holds for any TA
Proof. Let lij max(vij - Cij. 0), we have
| T.
-
Σ
Miglis)
iEI
JEJ
and
Tr, max (A; = max
Vistiy).
EE
JEJ
Since
max VEI
Vighis
max min tij 2 K. NEI JEJ
JEJ
we can obtain that
IV Sa(; 21 2 (max
Σ Vistio) 2 6 max
Σ Mitii= - Sa (a; TA; TV). ta
SEI
REI
JEJ
JEJ
Now, we can complete the proof by using the non-negativity of (a TA TV).
G.2 CONVERGENCE OF MODEL PARAMETERS
For the minimization of L(w, 8; TAI TV) w.r.t. and d, it can be viewed as competitive optimization with
min Crraining (w) élogie (w. 8), min Alogic (w, 8),
where Leraining (w) and llogio (w, 8) are training loss and logical loss, i.c.
liratuing (w)
KL(p |x))lpw((r xx)).
N Σ
flogic(w 5) Ey.. [L(ppz (x))))) xx,y:)).
18

---

A direct method to solve this problem is conducting the gradient descent (w, 6) together. However, it is highly inefficient since we have to use smaller step size to ensure the convergence (Lu et al. 2019). An alternative choice is alternating gradient descent cycle or saddle point (Powell 1973). Algorithm| can indeed ensure w to be an approximately stationary point (i.e., the norm of its gradient is small). Follow the proof of Davis & Drusvyatskiy (2018) Theorem 2.1), we present the convergence guarantee as follows.
and Ó, but it may converge a limit
We start with the weakly convexity of function miny f(:.y).
Proposition 3, Suppose f: X' x y + R is e--smooth, and v5(+) = arg miny f(--y) is continuously differentiable with Lipschitz constant Læ,, then v(-) miny f(:.) is @-weakly convex, where == 1 = L.).
Proof. Let ((xx) and y (x)). Since f f -smooth, we can obtain that u(x) = f(x', wY) 2 fxx () V fx, 8).x - x)
Ef (1|x -x12 + 11 -11²)
V (x, y).y J' y)
2
(12)
2 u(x) (Vxu(x),x -x) l ||x - -x'11
LyLy
2 ||x x'11
which finishes the proof.
The p-weakly convexity of v()) implies that vxx + (0/2)|[x|] is a convex function of x. Next, we introduce the Moreau envelope, which plays important role in proof.
Proposition 6. For a given closed convex function from a Hibert space H. the Moreau envelope of is defined by
exf(x) min yEH
f(v)
+ 1y x11?
1
2t
where || the usual Euclidean norm. The minimizer of the Moreau envelope etf is called the proximal mapping of f at v, and we denote it by
Proxi5(#) = arg min f(y) + yCH
7 11y - x012
1
21
It is proved in Rockafellar (2015) Theorem 31.5) that the envelope function exf(.) is convex and continously differentiable with
Verf(z) - -e (x= (rroox:(()))
(13)
The following theorem bridges the Moreau envelope and the subdifferential of a weakly convex function (Jin al. 2020. Lemma 30). For details, small gradient [[Ve,(x)] implies that x is close to nearly stationary point & of v(-).
Theorem 4. Assume the function is g-weakly convex. For any X 1/0. let x Proxxo || (x)ll < e, then
1 x S Ac, and min
|g||| S gedu(k)
This theorem is an immediate result of the fact that stationary points of v(-) coincide with those of the smooth function exv()), and one can refer Drusvyatskiy & Paquette (2019 Lemma 4.3) for more details. Now, we are ready to prove the convergence of Algorithm!!
Theorem 5. Suppose arg miny f(,y)) The iterative updating of minimization minx,y f(x,y) is
f-smooth and Lipischciitz define v(-) miny f(.y) and v--)
Xt+1 = X; - xxxx(xx
Y++1 = p(xx+1), s.t. lyt+1 - (xx++1]]l Se.
Assume that (b))) and (p-) are Lipschitzian with modules Ly and Lig, and let e == l + L3) and p ( 21²)). Then, with step size 1) = 7/VT+ +I, the output x of iterations satisfies
40²
(ev/20(X0) minx v(x)) + pr? 1.? + pl
p(p + ej
T/T+ +1
19

---

when p p2e p. and
40² e(3g- - p)
(Ev/2e(X0) - minx v(x)) + eTpL3 L3
E| E/]Ver//2
+ telge)
TVT +1
otherwise.
Proof. We have
lf lly. - -212
v(x') = f(x'F) 2 f(x'x))
f f),, - 8))
2
l f(x'
2 llve - y/ 2/12
E x - xx11 x=12-
E/ lly. -1112
2 y1) + (Vx/ yx), x - -x1)
2
2
lg +lyy 8'1??.
2 v(x)) + (1), x -xi)
11x x, 112
2
Since
Ilye- - 5'12- = I - 'xx')l )² < 2(1yy; (xx'Il + l1x((x)) +xxx'(l1
S 2(1xx - (xx') +c) = 2(11)(x,)) - xxx))| + +) S 2 - x112² + c),
where the second inequality is derived by using the Cauchy- Schwarz inequality. Hence, we have E, + 28 L2
v(x')= 2 vxxx) e + (Vx((x)))))x xx)) - (
)Xx'Xxxx x11
(14)
Let p - 26, 12 Next, we discuss two cases of p 2 e and p S o. respectively.
If p 22 0. then let x Prox./22(Xx) = arg minx v(x) + p||x xxl We can obtain that (x/20(x(+1) min {u(x) + p||x- - 11+
x
S ((())) + /||x++11 - -²,11
v(x)) + p||x: -vV2f((X y1) - 12
= =(())) + pl|x: 8, + 2mp (Vx (x). 8 xx) + + V (x),
(x,) ) + 2np (Vxf y1), 8, xx) 1 pl Vxf N()
S <x0/20(x)) 2np (u())) vxx) + Eye + 2 | x.11²) + r7 pL.
and the last inequality is derived by Eq. equation 14
Taking a telescopic sum over L, we have
(xT))(XT) S (x)) + 2np Σ ((()) - u(x:) + Ege + -1lxxx - x111²) + 1I1T.
Rearranging this, we obtain that
(((x)) - uxx)) f1xx x1112 S Cv122((00) - minx (xx)
+ Eye + nL3
(15)
T+1
2n0T
Since v(x) is (e/2)-weakly convex, and thus v(x) + pl|x - xel12 is (e/2) strongly convex when 2 Therefore, we can obtain that
e(x,) v(x,) 1 ||x, - 12
vxx)) + p||x x11 - v(xe) p||se xxel12 + P
/ |x -x,1
= (u(xi)= + -x min (u(x) + p||x - xel xx1(²) + P ||x - x111
2
x
p + ! I|x - xx112 - 0 (x,))(xxx)11
2 2
8Ø²
20

---

where the last equation holds by using Eq. equation 13 One can prove the result by combining this
with Eq. equation 15
If p e. then let & (x arg minx u(x) + e||x - -xell 31. We can obtain that
(x(+1) = min {u(x) + Ø||x - x(+1l13}
I v(x)) + e||x++1 - 1112²
=((,) + e||x -'V y1) &11
v(x.) e||x; 1 2 20e VVx yr). xx) r/ ell (xx,
Ex/20 xx) 2no (Vxf y1), _, xx) 22200 ell (xf(xx.)))) yill
S Scn/22 (x,) 2n ((x)) vxx,) ) +,c + 1/2 | - xx.1²) + n eL
Taking a telescopic sum over we have
(XT) S (x02 + 2n Σ ((xe) - u(x)) ) + Eye +1xxx -x112) + r"² OL?TT.
Rearranging this, we obtain that
T+1 Σ ((x)) - v(x:) - G1xx - -21113 s C0/20((0) - minx vxx)
+ E + nL?
(16)
2nel''
Since v(x) is obtain that
convex, v(x) + 0||x xi112 is (e/2) strongly convex. Then, we can
vxx)) - v8x)) L- ||x: 8111
= -((x)) + ee|xx - xx112 - v(xi) e||s: xel12 + (0 P
2 [)1x, - -xell
= (u(x)) + =||xx - =x,11 minn { (((x) + 0||x xx113) xxel
+ (e 2 2)11 - -Rell
2
2 (o+ + 2- - P ||x; - x 32- P e (x, (x1
2
8g²
and we finish the proof with plugging this into Eq. equation 16
Theorem can be derived by setting
Au = (x)) ming v(x), K
4g²
if p p< 0.
pl++g)
An (x)) ming vxx,,
K e(3e-
if p2
Finally, we confirm the assumptions in our theorems. To ensure the Lipschitz continuity of L(w, 8) in our problem, we practically impose interval [8 Oupper]. Furthermore, although we can obtain the closed-form expression of (pw), i.e.,
N
s (w)
Σ
pi
N
it is difficult to compute the closed-form expression of ((w) = arg ming L(w, 6) in our work. However, for any v(w) ((w), it holds that
8
1 N
Σ 5
43 14 000000 of
8
where means the Hadamard product. Since μi, o ó( 4 bounded, we can obtain that (b(w)
also bounded, and thus satisfies the assumption in Theorem 5
21

---

H ADDITIONAL DETAILS FOR EXPERIMENTS
We implemented our approach via the PyTorch DL framework. For PD and DL2, we use the code provided by the respective authors. The experiments were conducted on GPU server with Intel Xeon Gold 51 18 CPU@2.30GHE 400GB RAM, and 9 GeForce RTX 2080 Ti GPUs. The server ran Ubuntu 16.04 with GNU/Linux kernel 4.4.0.
Handwritten Digit Recognition. For this experiment, we used the LeNet-5 architecture, set the batch size to 128, the number of epochs to 60. For the baseline, DL2, and our approach, we optimized the loss using Adam optimizer with learning rate 1e-3. For the PD method, we direct follow the nyper-parameters provided in Github repository. For the SL method, we set the weight of constraint loss by 0.5, and optimized the loss using Adam optimizer with learning rate 5e-4 (which is used in its Github repository).
Handwritten Formula Recognition. For this experiment, we used the LeNet-5 architecture, set the batch size to 128, and fixed the number of epochs to 600. For the baseline, DL2, and our approach, optimized the loss using Adam optimizer with learning rate 1e-3 and weight decay 1c-5. For the PD method, we direct follow the hyper-parameters parameters provided in its Github repository.
Shortest Path Distance Prediction. We used the multilayer perceptron with V x [V] input neurons, three hidden layers with 1,000 neurons each, and an output layer of [V] neurons. We used the first node (with the smallest index) as the source node. The imput is the adjacency matrix of the graph and the output is the distance from the source node to all the other nodes. We applied ReLU activations for each hidden layer and output layer (to make the prediction non-negative) The batch size and the number of epochs were set to 128 and 300, respectively. The network was optimized using Adam optimizer with learning rate lc-4 and weight decay 5c-4.
CIAFRIOO Image Classification. In this task, we set batch size by 128, and the number of epochs by 3,600. We trained the baseline model by SGD algorithm with learning rate 0.1, and set the learning rate decay ratio by 0.1 for each 300 epochs. For other methods, we used Adam optimizer with learning rate 5e-4.
I TRAINING EFFICIENCY BY INJECTING LOGICAL KNOWLEDGE
38
20.
05
3.6
0.6
044
TOst RES-00OUIO
04
Trakee
0.2
Origin
0.1
Orggn
Orian
Origin
Logic
Logic
-Logic
Logic
(a) The training and test curves using 2% labeled data. (b) The training and test curves using 5% labeled data.
Figure 3: The learning curves of different settings. Our algorithm with logical constraints (the red curves) significantly boosts the training efficiency compared to the plain case (the blue curves).
On HWF dataset, we also investigate whether the logical knowledge can boost the training efficiency. In details, we use the labeled data only (i.e., 2% and 5% of training data) to train the model with/without the logical constraints. Figure 3 plots of training and test accuracy with different iterations. The results illustrate the high efficiency of our logical training algorithm compared with the plain training.
J RESULTS OF TRANSFER LEARNING EXPERIMENT
To show the robustness of the proposed approach in transfer learning, the STL10 dataset to evaluate a ResNet18 model trained on the CIFARIO dataset. We set the batch size of 100, and the number of epochs by 300. For both baseline and approach, remove the data augmentation
22

---

operators in training process, and optimize the loss by Adam optimizer with learning rate 1e-3. The model is trained using 3,000 labeled images and 3,000 unlabeled images (only used for our approach). We design a similar logical constraint to that in the CIFARIO0 experiment. For details, define two superclasses for CIFART 10 dataset, i.e., machines (denoted by m)) and animals (denoted by a), and the constraint is formulated
(pm (x) 0.0% V Pm (x) 100.0%) A (pa (x) 0.0% V pa (x) 100.0%)
The results are shown in Table 5
We do observe that the logical rule is more stable compared with model accuracy. Moreover, although such weak logical constraint only slightly improve the model (class and superclass) accuracy on CIFARIO, this increment is still preserved when domain shift occurs.
Table 5: Results from CIFARIO to STLIO.
Datasets
Class Acc. (%)
Superclass Acc. (%)
Sat. (%)
Baseline
65.8 + 32.6
92.7 + 76.4
90.1 + 88.4
Ours
68.1 + 35.4
93.9 + 78.1
92.6 91.9
K RESULTS OF TRAINING EPOCH RUNTIME
For the convergence rate, Theorem 3 states that algorithm has the same convergence order with the baseline (stochastic (sub)gradient descent) algorithm. We further show the runtime of each epoch of the CIFAR experiment Table We can observe that, each epoch, our method introduces little extra computational cost.
Table 6: Runtime of each training epoch.
Runtime
VGG16
ResNet50
DenseNet100
Baseline
30.2s 32.5s
26.4s 27.0s
26.7s
Ours
28.1s 1s
L RESULTS WITH STANDARD DEVIATION ON CIFARI00
For task 4, we include detailed results with Standard Deviation as follows.
23

---

Table 7: Accuracy of class classification on CIFARI00 dataset.
Method
VGG16
ResNet50
DenseNet100
Baseline
51.0(::0.52)
46.6(1:1.38)
36.2(1:0.11)
PD1
46.7(#0.99)
52.7(=0.86)
42.3(=0067)
PD₂
46.9(=:0.10)
54.2(+:0.58)
42.4(=0.48)
DL2
32.6(19.66)
45.3(+:1.37)
40.8(=0.50)
Ours
53.4(:L0443)
56.0(+:1.78)
51.4(
Table 8: The constraint satisfaction results (%) of image classification on the CIFAR10K 100 dataset.
Method
VGG16
ResNet50
DenseNet100
Baseline
63.0(++0.74)
48.5(+-2.37)
39.7(+
PD1
57.7(13.011) 63.9(+00.22)
53.5(=0.46)
PD2
57.5(+1.886)
69.2(11090)
54.9(10091)
DL.2
31.2(++17.9)
78.4(++1.2))
62.2(+0.56)
Ours
81.1(+0..77)
87.2(+:0.22)
88.2(+0.27)
24


Reviews:
[{"review_id": "uoVVgZBA8yL", "reviewer": "Reviewer_UtYh", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper tackles the problem of \"shortcut satisfaction\" in the context of neuro-symbolic integration (their results are however of interest for statistical relational learning at large).  Shortcut satisfaction, in this context, refers to models allocating most probability mass to \"easy to satisfy\" variable configurations.  This is a well-known and central (but sadly overlooked) problem in NeSy and SRL.  The authors propose a technique reminiscent of T-norm approaches to constraint satisfaction, which however involves injecting dual variables into the formulation of the knowledge-based loss which control what parts of the various formulas are active.  The authors also derive an alternating SGD optimization algorithm.  Experimental results in four tasks against SOTA competitors illustrate the efficacy of the proposed approach in avoiding shortcut satisfaction while retaining high accuracy and even outperforming the competitors.", "summary_of_the_review": "Very solid and significant contribution that tackles an overlooked open problem.", "strength_and_weaknesses": "PROS\n----\n\n- Crisply written, if a bit dense in parts.\n- Tackles an underappreciated but very central issue in NeSy integration and SRL.\n- Provides a very clear formulation and diagnosis of the problem.\n- Proposed technique is creative and non-trivial.\n- Very sensible (and surprisingly intuitive) optimization algorithm.\n- Contribution is carefully compared to relevant literature.\n- Empirical results are very convincing.\n\nCONS\n----\n\n- Some parts of the text are a bit dense and would benefit from in-line concrete examples.\n- Does not entirely explore limits of the proposed approach.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "rK_-esGVnfq", "reviewer": "Reviewer_LWuq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new way of integrating logical constraints in the training of deep neural networks. In particular, the authors try to solve the problem that the current models often learn to satisfy the constraints by learning the *obvious solution* (e.g., given $A \\to B$ the models learn to set $A = \\bot$). The logical constraints taken in considerations by the authors are written in CNF and the atoms in the formula are $v \\cdot c$, where: \n- $v$ is a variable\n- $\\cdot \\in \\{ \\le, \\ge, <, >, =, \\not = \\}$\n- $c$ is a constant. \nIn order to avoid the obvious solution the authors propose to associate a a dual variable to each logical connective.\n", "summary_of_the_review": "TL;DR: The paper seems novel and interesting, it needs to improve on clarity ", "strength_and_weaknesses": "**Strength:**\n\n1) The paper identifies an interesting problem in the current state-of-the-art models \n2) The solution proposed seems very interesting\n\n**Weaknesses:**\n\n1) I don't know variational learning well, but I know Neurosymbolic learning quite well and I struggled to follow the paper. A bit more explanations on the variational learning framework could really help somebody with my background.\n2) The theoretical part seems to be disconnected from the experimental analysis. Indeed, in the theoretical analysis the authors state that all the atoms in the formulas are of the type $v \\cdot c$, but then in the experimental analysis we have constraints of the type $v_1 +v_2 \\cdot c$. Suppose we simply set $v = v_1 + v_2$ in the constraint $v \\cdot c$ do all the theorems still hold? Do they also hold if we have multiple constraints sharing the same variables (e.g., $v_1 + v_2 < c$ and $v_3 - v_2 > c$). \n3) In the experimental analysis the authors compare only with PD and DL2. I would suggest to also add as baseline DeepProbLog [1] as it is one of the most well known methods for including the constraints. \n4) In Table 2 the authors report the results with 2% and 5% of the data. This is a very little amount. Could the authors produce the results also for 10% 20% and 50%?\n5) The authors are missing some related works which they should discuss. In particular: [2,3,4,5,6]. \n6) Are the experiments run for only one seed? Ideally we should have 5 runs and we should have average and std. (I am asking because from what I know variational learning based methods tend to be quite unstable, so it would be useful to asses the stability of the proposed model)\n\n\n**References:**\n\n[1] Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. DeepProbLog: Neural probabilistic logic programming. In Proc. of NeurIPS, 2018.\n\n[2] Samy Badreddine, Artur d’Avila Garcez, Luciano Serafini, and Michael Spranger. Logic tensor networks. Artif. Intell., 303, 2022.\n\n[3] Eleonora Giunchiglia and Thomas Lukasiewicz. Multi-label classification neural networks with hard logical constraints. JAIR, 72, 2021.\n\n[4] Tao Li and Vivek Srikumar. Augmenting neural networks with first-order logic. In Proc. of ACL, 2019.\n\n[5] Zhun Yang, Adam Ishay, and Joohyung Lee. NeurASP: Embracing neural networks into answer set programming. In Proc. of IJCAI, 2020.\n\n[6] Ahmed, Kareem, Stefano Teso, Kai-Wei Chang, Guy Van den Broeck, and Antonio Vergari. Semantic Probabilistic Layers for Neuro-Symbolic Learning. arXiv preprint arXiv:2206.00426, 2022.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "HI1y9Am-4s", "reviewer": "Reviewer_X3bi", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": " In this paper, a new framework for learning with logical constraints is proposed. The shortcut satisfaction issue is addressed by introducing dual variables for logical connectives, encoding how the constraint is satisfied. A variational framework is proposed where the logical constraint is expressed as a distributional loss that is compatible with the model’s original training loss. Theoretical analysis shows that the proposed approach bears some nice properties, and experimental evaluations demonstrate its superior performance in both model generalizability and constraint satisfaction.", "summary_of_the_review": " In this paper, a new framework for learning with logical constraints is proposed. The shortcut satisfaction issue is addressed by introducing dual variables for logical connectives, encoding how the constraint is satisfied. A variational framework is proposed where the logical constraint is expressed as a distributional loss that is compatible with the model’s original training loss. Theoretical analysis shows that the proposed approach bears some nice properties, and experimental evaluations demonstrate its superior performance in both model generalizability and constraint satisfaction. The paper is clearly state and the content is well organized. The work successfully addressed the shortcut satisfaction issue and proposed a variational framework where the logical constraint is expressed as a distributional loss that is compatible with the model’s original training loss. ", "strength_and_weaknesses": "The work successfully addressed the shortcut satisfaction issue and proposed a variational framework where the logical constraint is expressed as a distributional loss that is compatible with the model’s original training loss. However the design lacks theoretical support.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Cn9Fl1TiYZQ", "reviewer": "Reviewer_C2ss", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In the setting of constrained deep learning, a key challenge is to inject logical constraints as loss functions while preserving the semantics of their truth tables. Notably, some logical constraints such as material implications have *preferred tuples* which should be reached whenever possible. This paper aims at addressing this challenge by providing a new translation of CNF formulas into loss functions and a variational learning framework. One of the key ideas of the translation is to map simple conjunctions and disjunctions as optimization functions into corresponding simplices. This translation satisfies desirable properties such as monotonicity, and interpretability. The variational learning framework takes the form of a nonzero-sum game for which local Nash equilibria are searched using a stochastic gradient-ascent algorithm with min-oracle. Experiments on various problems corroborate the effectiveness of this approach.\n", "summary_of_the_review": "This is a conceptually simple, flexible, and robust approach to neural network learning with logical constraints. In a nutshell, a good paper. \n", "strength_and_weaknesses": "Overall, the paper is well-motivated and well-written. I found the logic-to-loss translation in Section 2 very intuitive. Based on this translation, the use of a stochastic gradient descent-ascent learning algorithm is quite natural. The convergence analysis is, however, much more difficult to establish, and as far as I could check, the proof looks correct. Finally, experimental results reported for various constrained learning tasks highlight the merits of this framework. \n\nI did not find any real weakness in this paper. I just have some minor recommendations, detailed below.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%