Softened Symbol Grounding for Neuro-symbolic Systems
Authors: Zenan Li
Yuan Yao
Taolue Chen
Jingwei Xu
Chun Cao
Xiaoxing Ma
Jian L\"{u}
Venue: ICLR 2023 poster (2023)
Keywords: neuro-symbolic learning
symbol grounding problem
projection-based sampling

Abstract: Neuro-symbolic learning generally consists of two separated worlds, i.e., neural network training and symbolic constraint solving, 
whose success hinges on symbol grounding, a fundamental problem in AI. This paper presents a novel, softened symbol grounding process, bridging the gap between the two worlds, and resulting in an effective and efficient neuro-symbolic learning framework. Technically, the framework features (1) modeling of symbol solution states as a Boltzmann distribution, which avoids expensive state searching and facilitates mutually beneficial interactions between network training and symbolic reasoning; (2) a new MCMC technique leveraging projection and SMT solvers, which efficiently samples from disconnected symbol solution spaces; (3) an annealing mechanism that can escape from sub-optimal symbol groundings. Experiments with three representative neuro-symbolic learning tasks demonstrate that, owing to its superior symbol grounding capability, our framework successfully solves problems well beyond the frontier of the existing proposals. 

Published as a conference paper at ICLR 2023
SOFTENED SYMBOL GROUNDING FOR NEURO- SYMBOLIC SYSTEMS
Zenan Li", Yuan Yao', Taolue " Xu', Chun Cao', Xiaoxing Ma', Jian Lü
State Key Lab of Novel Software Technology. Nanjing University, China
2 DDeparmennt of Computer Science, Birkbeck, University of London, UK
1i z smail. ju.. edu. cn, t. wwwn@bbk..c..... ac. fy- yao, yin.yaa,,ngeeii.... jingweix, caochun, xxm, ju. edd.
ABSTRACT
Neuro-symbolic learning generally consists of two separated worlds, i.e., neural network training and symbolic constraint solving, whose success hinges on sym- bol grounding, fundamental problem in AL. This paper presents a novel, softened symbol grounding process, bridging the gap between the two worlds, and result- ing in an effective and efficient neuro-symbolic learning framework. Technically. the framework features (1) modeling of symbol solution states Boltzmann distribution, which avoids expensive state searching and facilitates mutually ben- eficial interactions between network training and symbolic reasoning; (2) new MCMC technique leveraging projection and SMT solvers, which efficiently sam- ples from disconnected symbol solution spaces; (3) annealing mechanism that can escape from sub-optimal symbol groundings. Experiments with three rep- resentative meuro-symbolic learning tasks demonstrate that, owing to its superior symbol grounding capability, our framework successfully solves problems well beyond the frontier of the existing proposals.
INTRODUCTION
Neuro-symbolic systems have been proposed to connect neural network learning and symbolic con-
straint satisfaction (Garcez et al., 2019 Marra et al. 2021 Yu et al. 202T Hitzler 2022). these
systems, the neural network component first recognizes the raw input as symbol, which is further
fed into the symbolic component to produce the final output YYi et al. 2018 Li et al. 2020 Liang
iet al. 2017). Such a neuro-symbolic paradigm has shown unprecedented capability and achieved
impressive results in many tasks including visual question answering Yi et al. 2018 Vedantam et al. 2019 Amizadeh et al. 2020), vision-language navigation (Anderson et al. 2018 Fried et al. 2018) and math word problem solving (Hong et al. 2002 Qin et al. 2021). ) to name a few.
As exemplified by Figure 1 maximize generalizability, such problems are usually cast in weakly-supervised setting (Garcez et al., [202)]: the final output the neuro-symbolic computa- tion is provided as supervision during training rather than the label of intermediate symbols. Lack- ing direct supervised labels for network training appeals for an effective and efficient approach to solve the symbol grounding problem, i.e., establishing a feasible and generalizable mapping from the raw inputs to the latent symbols. Note that bypassing symbol grounding (by, e.g., regarding the problem as learning with logic constraints) possible, but cannot achieve satisfactory perfor- mance (Manhaeve et al.) 2018 Xu et al.) 2018 Pryor et al.] 2022). Existing methods incorporating symbol grounding network learning heavily rely on good initial model and perform poorly when
starting from scratch (Dai al. 2019 Li et al. 2020 Huang al. 2021).
A key challenge of symbol grounding lies in the semantic gap between neural learning which is stochastic and continuous, and symbolic reasoning which is deterministic and discrete. To bridge the gap, we propose to soften the symbol grounding. That is, instead of directly searching for a deterministic input-symbol mapping,
optimize their Boltzmann distribution, with annealing strategy to gradually converge to the deterministic one. Intuitively, the softened Boltzmann distribu- tion provides playground where the search of input-symbol mappings can be guided by the neural

---

Published as a conference paper at ICLR 2023
Raw imput x
Latent symbol 748-5-9
Output
5-4
42.0
Network M
Fval
Supervisiog Me
Improving C+
Information
Projection-
8++
Inference
MCMC sampling
7*8-5-9
Learinng
On-demand
Boltzmann distribution Q+ over solution space Sy
SMT solving
Figure I: An example surall-ymbolic system for handwritten formula evaluation. takes hand- written arithmetic expression x as ipput and evaluates the expression to output The neural net- work component MM recognizes the symbols (i.e., digits and operators) in the expression, and the symbolic component evaluates the recognized formula by, e.g., the Python function 'eval'. The challenge in training Ma comes from the lack of explicit z to bridge the gap between the neural world (x to z) and the symbol world (z to y). Through softened symbol grounding, the model train- ing and the constraint satisfaction join force to resolve the latent z to fit both the given x and y.
network, and the network training can be supervised by sampling from the distribution. Game the- ory indeed provides theoretical support for this strategy (Conitzer) 2016): the softening makes the learning process series of mixed- -trattgy games during the annealing process, which encourages stronger interactions between the neural and symbolic worlds.
The remaining challenge how to efficiently sample the feasible input-symbol mappings. Specifi- cally, feasible solutions are extremely sparse in the entire symbol space and different solutions are poorly connected, which prevents the Markov Chain Monte Carlo (MCMC) sampling from effi ciently exploring the solution space. To overcome this deficiency. we leverage the projection tech- nique to accelerate the random walk for sampling (Feng et al. 2021b), aided by satisfiability modulo theory (SMT) solvers (Nieuwenhuis et al., 2006 Moura & Björner 2008). The intuition is that dis- connected solutions in high-dimensional space may become connected when they are projected onto diwdeeensional space, resulting in rapid mixing time of the MCMC sampling (Feng al.) 2021a). The SMT solver, which is called on demand, is used as generic approach to compute the inverse projection. Although MCMC sampling and SMT solvers may introduce bias, the theoretical result confirms that it can be pleasantly offset by the proposed stochastic gradient descent algorithm.
SOFTENING SYMBOL GROUNDING
Throughout this paper, we refer X' as the input space of the neuro-symbolic system, and as its symbol space or state space (e.g., all legal and illegal arithmetic expressions in the HWF task). We consider the neuro-symbolic computing task which first trains a neural network (parameterized by 0). mapping raw input distribution Pe (z)x).. The state z is further fed into predefined symbolic reasoning procedure to produce the final output y. The training data contains only the input x's and the corresponding y's, which casts the problem into the so-called beakkl-suupervsed setting. In general, we formulate the pre-defined symbolic reasoning procedure and the output y symbol space. For instance, in Figure I the constraint specifies that the arithmetic expressions must evaluate to 42. We say a state z is feasible or satisfies the symbolic constraint if E Sy.
X' to some latent state z Z with (variational) probability
of symbolic constraint Sy on the
The major challenge in this neuro-symbolic learning paradigm lies in the symbol grounding prob- lem, i.c. establishing mapping h: X' - Z from the raw input to a feasible state that satisfies the symbolic constraint. Specifically, an effective mapping h should enable the model to explain as many observations as possible. a result, the symbol grounding problem on given dataset (xx, bee "=..... N can be formulated as
N
min min ((0) := log Po(2(x))) s... z' h(x²)) E Ey,, 1,...,A N.
(1)
0
2

---

Published as a conference paper at ICLR 2023
A straightforward solution the above formulation would first train network for each feasible mapping, and then select the one that achieves the final output y with a maximum likelihood. How- ever, this solution is impractical since the number of feasible mappings grows exponentially.
An obvious shortcoming of the above solution is that the neural network learning process makes no use of the knowledge embodied in the symbolic constraint. Vice versa, searching for the best map- ping is not guided by the network. To overcome this shortcoming, one can switch the minimization order in problem ( and obtain new but numerically equivalent problem:
min min ((0) = Σ log Pa(z'(x)) 0
s.t. z' x²=h(x') E Sys, = -iii=,,.... I,....N..
The optimization problem first determines a "best" mapping based on the initial model, and then updates the model to fit this mapping. The two steps are iterated until improvement can be made. However, this grounding strategy may easily get trapped into a local optimum. The reason is that, every time feasible mapping h is achieved, / tends to direct the neural network (over)fit itself. Because the mappings are deterministic and discrete, there is no smooth route to alternative feasible mappings that would further improve the network. This insufficient information exchange between network training and symbolic reasoning makes the success of symbol grounding highly dependent on the quality of the initial model.
In this work, we propose to soften the symbol grounding to facilitate the interaction between neural perception and symbolic reasoning. Instead of directly searching for a deterministic mapping h, we first pursue an optimal probability distribution of h. and then gradually "sharpen" the distribution to obtain the final deterministic h. Formally, for each input x, we introduce a Boltzmann distribution Qs over Sy, parameterized by Φb to indicate the probability of each feasible state that satisfies the symbolic constraint. Then, the softened symbol grounding problem can be formulated as follows:
N
min 0
1(0, = Σ Σ
2z(zz) log Po + 700((') log (z'z²)
F=1 ESy
(P)
s.t. ( S Syr, i= N,
where supp(Qœ) denotes the support of QΦ- The entropy term Exes, (z(z) log (z) is intro- duced to control the sharpness of QΦ MacKay et al. 2003), and the decreasing of its coefficient ensures that the grounding can converge to a deterministic mapping h. Except for the case y which yields the KL divergence between Po and Qa, we also examine two extreme cases: (1) when 7 + +0c, Qø is forced towards the uniform distribution, and thus the minimization only aims to re- strict the support of Po to Sy: (2) when - O, Q+ is confined to a one-hot categorical distribution, reducing to directly search for the deterministic mapping h.
Ad Advantages. Game theory provides a perspective to understand why our softened strategy improves over problems [ and (2) with better interaction between model training and symbolic reasoning. can be viewed as pure-strategy Stackelberg game. That both the model training and the symbolic reasoning are forced to take a certain action (e.g.. selecting a deterministic mapping h) during optimization. In contrast, problem (P) can be seen as a Stackelberg game with mixed strategies, where the player takes a randomized action with the distribution Q Compared with the pure strategy, a mixed strategy does provide
Either problem I
information of the game, and thus strictly improves the utility of model training (Letchford et al. 2014 Conitzer] 2016).
In addition, this softening technique also avoids enumeration and thus improves efficiency. In prob- lem I for each input x, the minimization in its corresponding symbol z needs searching over the whole Sy (i.e., enumerating all feasible states satisfying the symbolic constraint). This generally an intractable #o-complete problem in theory (Arora & Barak] (2009). Problem (P) circumvents this costly computation by estimating the expectation over Qø, which can be efficiently computed with a tailored sampling strategy discussed in the next section.
3 MARKOV CHAIN MONTE CARLO ESTIMATE VIA PROJECTION
To simplify presentation, in this section, we consider a single data sample. Specifically, by removing the summation over all samples and dropping the superseripts, problem (P) can be formulated as
3

---

Published as a conference paper at ICLR 2023
min (0, 0.0
lol (olzx) + (Q((z) log Qa(z), supp(QØ) C Sy-
ZESy
This problem can be solved by alternating between the gradient descent step in and the minimiza- tion step in Φ. The updates of f and Φ at the k-th iteration are
0 = 02 V 2x). Φx+1 = arg min ((x+1.0).
(4)
<lsupp(Qa)
Note that the closed-form solution Qø- exists when Po is fixed, ensuring the convergence of gradient descent in A (Jin et al. 2020 Theorem 31). For details, the lower-level problem, i.e., ming {(O, Φ), is strictly convex, and thus contains the unique minimum:
QΦ- {0.
(o(2)x)+/Exzee Po(x'xx), if z E Sy: 70.
(5)
otherwise.
Given the closed-form solution QΦ', the loss function ((0 Φ*) and its gradient Vel(O, can be estimated through Monte Carlo sampling on Qø..
The remaining problem is how to sample Qø which is challenging due to the unknown structure of Sy. Existing methods usually sample from the entire symbol/state space Z, and then either reject the state z & Sy (e.g., policy-gradient method (Williams 1992)), or project the infeasible state to Sy (e.g., back- search method (Li et al., 20200). Untortunately, these methods suffer from the sparsity problem, i.e., feasible z's are very sparse in 2, causing the policy-gradient gradient to vanish and the back-search to fail.
To overcome the sparsity problem, we propose to directly sample from the symbolic constraint Sy (i.e., the solution space). By applying the Metropolis algorithm (Bhanot 1988 Beichl & Sullivan 2000). the acceptance ratio of jumping from one feasible state to another one z' does not vanish, and can be computed as
Qsi (2')
Po(zix) (
Po ()) $
T
(z)
Hence the problem becomes: (1) how to generate initial state 2, and (2) how jump from to z'. For the former, a natural way is to leverage SMT solvers (Moura & Bjørnrr 2008 For the latter, the most commonly used strategy is achieve the new state via random walk (Sherlock al., 2010). However, there lacks a systematic random walk approach in the solution space, because the solution space likely unconnected [Wigderson 2019), creating the so-called connectivity barrier.
Uncoonected whlttonss in high-dimooviin space
Figure Sampling unconnected solutions via projection. For our running example, we use : i.e., dropping the first and the last digits. The current state = [; x; +;3; +;3] is pro- jected to II(z)
the projection IT ([[2i;...;> ; 27))
z'= 1::38:33311
[x; +:]. We then randomly select an individual component, say, '9', and update it to '8'. Next, new feasi- ble state (e.g., 4x8+3+7-42) is derived by computing the inverse projection of IT(z') [x; +;3; +;] with an SMT solver.
Projection
Inverse projection via SMT
Random walk in low-dineusion space
Inspired by Feng et al. (2021a), we propose to overcome the connectivity barrier by the projection technique. Elaborately, introduce projection operator II(:): Z Ω that maps the state space 2 to lower-dimension space Ω, and then apply the single-site Metropolis algorithm in Ω. The projection essentially compacts the state space, and thus significantly improves the connectivity of the solution space. Figure 2 illustrates the key idea. Consider the running example in Figure I where Sy requires that all expressions are evaluated to 42. The SMT solver. together with the standard single-site Metropolis (a.k.a. Metropolis-ing -nnbbbss) (Metropolis et al. 1953 Bai 2009),
'Current SMT solvers mainly designed for the satisfaction problem, namely, they efficient in finding solution, but underperform in generating all solutions.
4

---

Published as a conference paper at ICLR 2023
easily derive an initial state (e.g., 4x9+343=42) satisfying the symbolic constraint. but cannot further explore other feasible states due to the connectivity barrier (Ermon et al. 20122) In contrast, in the lower-dimension space 22 it is much easier to jump to another feasible state.
4 ALGORITHM AND ANALYSIS
The overall algorithm of our neuro-symbolic learning is shown in Alg. [ In nutshell, we first conduct a few random walk steps to sample a new state z on the distribution Qø"; we then estimate the gradient based z, and conduct one stochastic gradient descent step. As shown by Feng et al. (021a), under some proper assumptions, the Metropolis algorithm enjoys the rapid mixing property on the projection space (Levin & Peres] 2017). Therefore, we can efficiently construct the approximate sampling on Qø", without taking too many steps in the Metropolis algorithm. Additionally, both the sampling method and the SMT solver be paralleled for different examples. hence the batch gradient descent is well supported in our framework.
Algorithm Neural Symbolic Learning Procedure
Set an initial value of 7. Calculate an initial state z E Sy for each input-output pair (x,y) via the SMT solver. for 0, ... K do Randomly draw an example yx from training data {x)
for t = 0, 1,, T do
Generute state Compute the projection = [T) E Ω.
Obtain u' by randomly selecting and updating component of u.
Calculate the inverse projection = 1I (u') via the SMT solver, as a new state. Accept/reject new state
Calculate the acceptance ratio 7 = Generate uniform random number E [0, 1).
Update the state z to if T. end for
Train the network
Estimate the gradient (e) = - Ve log Po(z)x).
Update network parameters 0 by the stochastic gradient decent. Decrease the coefficient
end for
Convergence. In the ideal case, the gradient estimate (E(0) is unbiased, and the gradient descent in (i.e., the network parameters) can converge. However, the bias introduced due to: 1) the approx- imate sampling of Metropolis algorithm (Jacob al. 2017); 2) the inverse projection implemented by the SMT solver (Moura & Björner 2008). For the former, we have to increase the number of inner iterations in algorithm consider adaptive variants of the Metropolis algorithm. For the latter, we can alter the projection operator during the training process, or increase the dimension of projection space. Nevertheless, none of these methods can fully avoid the bias of gradient estimate. To this end, we provide a convergence result for the stochastic gradient descent with limited bias.
Proposition Assume the loss function E(O) is I.-Lipschitz and E-smooth, and let the actual sam- pling distribution be Q. Then, if the total variation distance da ( Q²) is bounded by it holds after K steps of the stochastic gradient descent with learning rate r = aa(VT+1)
1 K
(oo (802+ Ao + (ncI.)
Σ I11(0112
(avT+I)
K
where 4. E(Og) min ((0), and n is the cardinal number of supp((").
To maintain stability, the single-site Metropolis conducts random walk a component-win wise way. That is, in each iteration, it randomly selects and updates an individual component in the current state z to generate new state z'. However, it can he observed that the update of any individual component (i.e., '4', 'x', '9', '+', 3", '+', :3") will result feasihle new states.
5

---

Published as a conference paper at ICLR 2023
Remarks. A proof is given in Appendix A.1 This proposition states that the stochastic gradient descent with MCMC gradient estimate converges to an approximate stationary point. Moreover, the bias term is gradually wiped out in the training process, since the decreasing of y shrinks the support of Q", making the gradient estimate finally align with the true one.
Generalization of existing methods. Existing neuro-symbolic learning frameworks, viz. semantic loss (Xu et al., 2018), deepproblog (Manhaeve et al., 2018). and neural-grammar--ymbolll. learn- ing (Li al. (020), can be understood special cases of our framework.
Proposition 2. All three frameworks (semantic loss, deepproblog, and suaral-rammar--yybboiic learning) share the same loss function
N
((0) == 2'E2'
log Pa(z'1x'),
and they are equivalent Problem (P) with a fixed y (7= 1). Here, the equivalence means that the problems have the same optimal solution and gradient descent dynamics.
Remarks. The proof is in Appendix A.2 Compared with minimizing é, our framework enjoys two advantages: (i) the Boltzmann distribution Q is explicitly expressed, making the sampling tractable and easy implement even when the state space is very large; (ii) the annealing strategy of y largely alleviates the sensitivity to the initial point, guiding to a better optimal solution.
Annealing strategy. Next, we discuss the decreasing strategy of y. By setting 02 log Po (z|x) as the entropy for each state z (Thomas & Joy 2006), we can obtain that
exp(-$2/7)
Q (2) Exes, exp( (xx(-<E//)) Φ2/7)"
It should be noted that the entropy 0 is essentially the energy of that state z, and the coefficient plays role of temperature in the Boltzmann distribution (LeCun al. 2006). From this perspective, it is natural to use some classic annealing (or cooling) schedules to decrease 7 (Hajek) 1988 Nourani & Andresen 1998 Henderson et al. 2003). this work, we consider the following three schedules: (1) logarithmic cooling schedule, i.c., Vt 70/log(1 1 t); (2) exponential cooling schedule, i.e., Y/- Yaa": (3) linear cooling schedule, i... Yt- = To at.
Furthermore, after the annealing stage, i.e., when the temperature is decreased to small value, we will directly set 7 = 0, and train the network by a few more epochs. Note that in this zero-degree stage, the problem is essentially reduced to semi-supervised setting (Lee et al. 2013). That is, Q shrinks to a one-hot categorical distribution when = O, contributing some (pseudo) labels for the learning process. Some semi-supervised techniques could be applicable to this case, but not sufficiently efficient due to the massive state space. Therefore, we use the simplest strategy, i.c., only train by those examples with predicted symbols satisfying the symbolic constraint.
EXPERIMENTS AND RESULTS
We carry out experiments on three tasks, viz. handwritten formula evaluation (HWF), visual Sudoku classification (Sudoku), and single-destination shortest path prediction in weighted graphs (SDSP). For the proposed approach, split into two stages, i.e., Stage I: Annealing (7-decreasing) stage, and Stage II: Zero-degree (y 0) stage, and separately evaluate Stage I and Stage I+II. For the first state, we employ three different cooling schedules (Log, Exp. and Linear) as discussed in Section 4 The projection operator is specific to each task, and the corresponding inverse projection operator is implemented by the 73 SMT solver (Moura & Bjørner 2008). Through parallel computation (Joblib) Development Team 2020). Z3 solves the inverse projection (on average) in 2.8ms~6.44s per ample, which is generally acceptable for batch gradient descent.
We compare approach with the existing state-of-the-art methods, which can be divided into two approaches, and symbolic- perlicc-paeer---e based approaches. The for-
categories, viz.. mer includes RL (i.e., learning with REINFORCE) and MAPO (Liang al., 2018) (i.e., learning by Memory Augmented Policy Optimization). For the latter, most existing methods (c.g.. seman- tic loss (Xu et al., 2018) and deepproblog (Manhaeve al. 2018)) intractable in the studied

---

Published as a conference paper at ICLR 2023
Method
Symbol
Calculation
RL
6.5
0.0
63.7
63.8
64.7
65.4
MAPO
8.7
0.0
54.1
Accuracy (%)
Baseline
NGS
8.1
0.0
50
SSL
70.5
8.4
NA
55.1
2.83
Log
81.4
23.2
Ours
Exp
82.6
25.7
(Stage I)
Linear
79.9
19.9
Log
91.0
52.2
Ours (Stage I+II)
Exp
98.6
90.7
MAPO
SSL
Log
Exp
Linear
SUP
Linear
97.6
85.0
Table 1: Accuracy (%) of the HWF task. Our meth- ods (i.e., Stage I+II) perform much better than com- parison methods.
Figure 3: Accuracy (%) of the SDSP task. Our methods are better than competitors and close to the direct supervision case.
tasks (Huang al., 2021 Hence, based on Proposition X and borrowing our projection-based MCMC technique, we implement stochastic version for them (referred to as SSL henceforth) for comparison. More implementation details can be found in Appendix B The code available at http::////ttub.../ com/ SoftW: wow.Wiser-grrooooooooo wer.sseeurrrsotoeeeeeeeeeee
NeSy-
SesSSy-leaaae learn Bignnnn
5.1 HANDWRITTEN FORMULA EVALUATION
We first evaluate our approach on the handwritten formula dataset provided by Li et al. (020)) Since the original dataset consists of formulas with lengths varying from to 7, which may lead to the label leakage problem, we only take the 6K/1.2K formulas with length 7 as the training/test set. In this neuro-symbolic system, the neural network is required recognize symbols including digits 1-9 and basic operators (+, X, +). The symbolic module evaluates the expression via the Python program 'eval'. this task, we also compare with the neural- neural-grammar-sye grammar-symbolic (NGS) method (Li et al. 2020), and special case of our approach with no-annealing strategy (NA) where we fix y 0.001. For SSL,, NA, and our approach, we define the projection operator as [T(z;;... [2:; R2; 24; Z6; 27], i.e., drop the third and fifth symbols in the formula
We report the symbol accuracy (i.e., the percentage of symbols that are correctly predicted) and the calculation accuracy (i.e., the percentage of final results that are correctly calculated) in Table Observe that our approaches (Log, Exp, and Linear) significantly outperform the competitors. Addi- tionally, when Stage II is included, both symbol accuracy and (especially) calculation accuracy can be further improved. Overall, our two-stage algorithm with the Exp annealing strategy achieves the best performance on both symbol accuracy and calculation accuracy. The Log annealing strategy in Stage cannot obtain a comparable result with the other two strategies, because its temperature is not reduced to sufficiently low value. Additional learning curve results and analysis can be found in Appendix B.4
5.2
VISUAL SUDOKU CLASSIFICATION
We next evaluate our approach on visual Sudoku classification task (Wang et al. 2019). where the neural network recognizes the digits (i.e., MNIST images) in the Sudoku board, and the symbolic module determines whether a solution is valid for the puzzle. To evaluate the sample efficiency of approach, we vary the size of the training set by 50, 100, 300, and 500, and the size of the test set is fixed at 1,000. Note that the solution space in this task is intrinsically connected. For example, can easily obtain this strategy without the projection (denoted by MCMC) as a baseline.
solution by permuting any two digits. Therefore, additionally include
We observe that the solution space is well-connected through different projections. For example, for the used projection with initial to 1.0, around 46% solutions successfully jump to other solutions in an epoch.

---

Published as a conference paper at ICLR 2023
For given 4-by-4 Sudoku puzzle, we divide it into four disjoint 2-by-2 subboards, and the projec- tion drops the anti-diagonal two. the projection space, we randomly switch two digits in different rows or columns, and the following example illustrates the whole projection process.
4
3
2
1
2
2
4
3
4
Projection
3
Random walk
3
Inverse projection
3
2
1
3
3
1
4
2
1
2
4
2
4
1
3
4
Table 2 shows the accuracy result, i.e., the percentage of correctly predicted boards. can be that RI, MAPO, and SSL. fail obtain sensible result across all cases. Although the crude MCMC method can achieve good result, it is still sigmificantly outperformed by our approaches. The reason that the Markov chain obtained in the original space has a slow mixing time. making the MCMC algorithm prone to getting stuck at local minima. To investigate the grounding effect and the sample efficieccy, we also report the number of training examples that are correctly grounded (i.e., satisfying the symbolic constraints) in the brackets of Table The result shows the high sample efficiency our approach. Particularly, with the number of training puzzles increased, the rate of correctly grounded examples has exceeded 90%.
Table 2: Accuracy (%) of the Sudoku task. Our methods significantly outperform the competitors.
Number training puzzles
Method
50
100
300
500
RL
0.0
0.0
0.0
0.0
MAPO
0.0
0.0
0.0
0.0
Baseline
SSL
5.8
1.6
0.0
0.2
MCMC
24.3
49.5
63.4
69.8
Log
30.7
74.7
85.9
86.0
Ours
Exp
33.6
76.5
77.4
89.3
(Stage
Linear
46.3
66.8
79.4
84.1
Log
64.8 (35)
82.2 (85)
93.5 (279)
92.9 (474)
Ours
Exp
66.3 (39)
85.5 (94)
92.3 (274)
95.4 (480)
(Stage I+II)
Linear
66.9 (41)
81.5 (85)
90.8 (273)
94.0 (478)
5.3 SHORTEST PATII SEARCH
We finally conduct single-destination shortest path search task. In this neuro-symbolic system, the symbolic reasoning part implements an A" search algorithm (Russell 2010), which maintains priority queue of the estimated distance d(n)) g(n) + fn()), where the next node the path, g(n) is the known distance from the start node to and fe (n) is the shortest distance from to the destination heuristically predicted by neural network. For simplicity, we set the queue length to i... only visit the node with the shortest estimated distance. We randomly generate 3K/IK graphs as training/test set through NetworkX (Hagberg et al. 2008). each graph, the number of vertices is fixed to 30, and the weights of edges are uniformly sampled among (1,2.....9)
For this regression task. we define the symbol as multivariate Gaussian with diagonal co- variance, i.e., z ([fo(x))o²1) where fo(x) indicates the predicted distances from all nodes the given destination. The dimension of 30, and the projection is defined by dropping [25, Z10, 215, Z20. Z25]. The random walk in each step selects component of and adds uniform noise from [-5, 5] on it.
Figure 3 shows the accuracy results, i.e., the percentage of shortest paths that are correctly obtained. To better understand the effectiveness, we additionally train a reference model (denoted as SUP) with directly supervised labels (i.e., the actual distance from each node to the destination). It can be observed that, our approaches not only outperform the existing competitors, but also achieve a comparable result with the directly supervised model SUP.
8

---

Published as a conference paper at ICLR 2023
6 RELATED WORK
Neuro-symbolic learning. To build a robust computational model integrating concept acquisition and manipulation (Valiant 2003), neuro-symbolic computing provides an attractive way to recon- cile neural learning with logical reasoning. Numerous studies have focused on symbol grounding to enable conceptualization for neural networks. An in-depth introduction can be found in recent surveys (Marra et al. [02T]] Garcez et al.] 2022). According to the way the symbolic reasoning component handled, we categorize the existing work as follows.
Learning with logical constraints. Methods in the first category parse the symbolic reasoning into an explicit logical constraint, and then translate the logical constraint into differentiable loss function which is incorporated as constraints or regularizations in network training. Although several meth- ods, e.g., s.. Hu et al. (2016); Xu et al. (2018); Nandwani et al. (201)); Fischer et al. (2019); Hoernle et al. (2022), are proposed to deal with many different forms of logical constraints, most of them tend to avoid the symbol grounding. In other words, they often only confine the network's 's behavior,
but do not guide the conceptualization for the network.
Learning from symbolic reasoning. Another way is to regard the network's 'ss output as a predicate, and then maximize the likelihood of correct symbolic reasoning (a.k.a. learning from entailment (Raedt
eet al.
2016 Sec. 7)). In some of these methods (Manhaeve et al.] 2018 Yang et al. (020) Pryor
al.
2022: Winters et al. 2022), the symbol grounding is often conducted in an implicit manner
(as shown by Proposition P. which limits the efficacy of network learning. Some other methods (Li
al.
2020 Dai et al. 2019) achieve an explicit symbol grounding in an abductive way, but still
highly depend on good initial model. Our proposed method falls into this category, but it not only explicitly models the symbol grounding, but also alleviates the sensitivity of the initial model by enabling the interaction between neural learning and symbolic reasoning.
Differentiable logical reasoning. This line of work considers emulating symbolic reasoning through a differentiable component, and embedding it into complex network architectures. To achieve this goal, series of techniques (Trask et al., 2018 Grover et al. 2019: Wang et al. 2019 Chen et al.) 2021 are proposed to approximate different modules in logical reasoning. Despite the success, these methods still succumb to the symbol grounding problem, and cannot achieve a satisfactory performance without explicit supervision (Topan et al. 2021b.
Constrained counting and sampling. Quite a few neuro-symbolic learning methods (Manhaeve et al.
2018 Xu et al.] (018) rely knowledge compilation (Darwiche & Marquis 2002). which
implements the exact constrained counting based on Binary Decision Diagram (BDD) (Akers 1978)
or Sentential Decision Diagram (SDD) (Darwiche) 2011). Some approximate versions (De Raedt
et al.
2007] Manhaeve et al. 2021) are proposed to overcome the computational hardness (Valiant Jerrum al.) 1986), but are still inefficient and poorly scalable large-size problems.
1979
Aided by the progress of SAT/SMT solving (Malik & Zhang 2009 Vardi 2014), randomized ap-
proximate constrained counting/samplingg approaches have been proposed. which are based on hash- ing (e.g., Chakraborrt et al. (2013); MMel et al. (2016)) or MCMC (e.g. WWii et al. (2004); Gomes] al. 2006); (Ermon et al. (2012)) In particular, previous -CseC-based methods suffer from con- nectivity barriers. Our approach is based on MCMC, but leverages projection to overcome the connectivity barrier (Moitra 2019, Feng et al., 2021a). Moreover, our theoretical result shows that the stochastic gradient descent can offset the possible bias of the gradient estimate introduced by MCMC and SMT solvers.
[Mell)
7 CONCLUSION
In this paper, we present a new neuro-symbolli learning framework for better integrating neural net- work learning and symbolic reasoning. To focus the crucial problem of symbol grounding, limit this work to scenarios where the symbolic reasoning logic is given as a priori knowledge. The next step is to incorporate the learning of the knowledge into our framework by, e.g., inductive logic programming. Moreover, though SMT solvers make the projection feasible in a broad range of set- tings, they may become a bottleneck when instantiating our framework for more complex systems. It would be interesting to consider a substitute for SMT solvers in neuro-symbolic frameworks.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENT
We thank the anonymous reviewers for their insightful comments and suggestions. 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 of Novel Software Technology under Grant #KFKT2022A03, Xiaoxing Ma (xxmên ju edu. en) is the corresponding author.
REFERENCES
Ahmad Ajalloeian and Sebastian U Stich. On the convergence of sgd with biased gradients. arXiv preprint arXiv:2008. 00051, 2020.
Sheldon B. Akers. Binary decision diagrams. IEEE Transactions on computers, 27(06):509-56,, 1978.
Saced Amizadeh, Hamid Palangi, Alex Polozov, Yichen Huang, and Kazuhito Koishida. Neuro- symbolic visual reasoning: Disentangling. In International Conference on Machine Learning, pp. 270-290. PMLR, 2020.
Peter Anderson, Qi Wu, Damien Teney, Jake Bruce, Mark Johnson, Niko Sünderhauf, Ian Reid, Stephen Gould, and Anton Van Den Hengel. Aision-and-languag navigation: Interpreting navigation instructions in real environments. In Proceedings of the IEEE con- ference on computer vision and pattern recognition, pp. 3674-3683, 2018.
Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge Uni- versity Press, 2009.
Yan Bai. An adaptive directional metropolis-within-geee algorithm. Preprint, 2009.
Isabel Beichl and Francis Sullivan. The metropolis algorithm. Computing in Science & Engineering, 2(1)):5-69) 69, 2000.
Gyan Bhanot. The metropolis algorithm. Reports on Progress in Physics, 51(3):429, 1988.
Supratik Chakraborty, Kuldeep S Meel, and Moshe Y Vardi. A scalable approximate model counter. In International Conference on Principles and Practice of Constraint Programming, pp. 200-216. Springer, 2013.
Bingqing Chen, Priya Donti, Kyri Baker, Zico Kolter, and Mario Bergés. Enforcing policy feasibility constraints through differentiable projection for energy optimization. In Proceedings of the Twelfth ACM International Conference on Future Energy Systems, pp. 199-210, 2021.
Vincent Conitzer. On stackelberg mixed strategies. Synthese, 193(3):689-733, 2016.
"Vang-Zhou Dai, Qiuling Xu, Yang Yu, and Zhi-Hua Zhou. Bridging machine learning and logical reasoning by abductive learning. Advances in Neural Information Processing Systems, 32, 2019.
Adnan Darwiche. Sdd: new canonical representation of propositional knowledge bases. In
Twenty-Second International Joint Conference on Artificial Intelligence, 2011.
Adnan Darwiche and Pierre Marquis. A knowledge compilation map. Journal of Artificial Intelli- gence Research, 17:229-264, 2002.
Luc De Raedt, Angelika Kimmig, and Hannu Toivonen. Problog: A probabilistic prolog and its application in link discovery. In IJCAI, volume pp. 2462-2467. Hyderabad, 2007.
Stefano Ermon, Carla Gomes, and Bart Selman. Uniform solution sampling using a constraint solver as an oracle. In Proceedings of the Fiihtt-Fighuh Conference on Uncertainty in Artificial Intelligence, pp. 255-264, 2012.
Weiming Feng, Heng Guo, Yitong Yin, and Chihao Zhang. Fast sampling and counting k-sat solu- tions in the local lemma regime. Journal of the ACM (JACM), 68(6):1-42. 1-42, 2021a.
10

---

Published as a conference paper at ICLR 2023
Weiming Feng, Kun He, and Yitong Yin. Sampling constraint satisfaction solutions in the local lemma regime. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Com- puting, pp. 1565-1578, 2021b.
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.
Daniel Fried, Ronghang Hu, Volkan Cirik, Anna Rohrbach, Jacob Andreas, Louis-Philippe Morency, Taylor BerrgKKrkppatrict Kate Saenko, Dan Klein, and Trevor Darrell. Speaker-follower models for aaooo--nnd-aanguaan navigation. Advances in Neural Information Processing Systems, 31, 2018.
Artur d' Avill Garcez, Marco Gori, Luis C Lamb, Luciano Serafini, Michael Spranger, and Son N Tran. Neural-symbolic computing: An effective methodology for principled integration of ma- chine learning and reasoning. Journal of Applied Logics, 6(4):611-632, 2019.
Artur d' Avila Garcez, Sebastian Bader, Howard Bowman, Luis C Lamb, Leo de Penning, BV Illu minoo, Hoifung Poon, and COPPE Gerson Zaverucha. Neural-symbolic learning and reasoning: A survey and interpretation. Neuro-Symbolic Artificial Intelligence: The State of the Art, 342:1, 2022.
Carla P Gomes, Ashish Sabharwal, and Bart Selman. Near-uniform sampling of combinatorial spaces using xor constraints. Advances In Neural Information Processing Systems, 19, 2006.
Aditya Grover, Eric Wang, Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations. In International Conference on Learning Representations, 2019.
Aric Hagberg, Pieter Swart, and Daniel S Chult. Exploring network structure, dynamics, and func- tion using networkx. Technical report, Los Alamos National Lab.LLNN)), Los Alamos, NM (United States), 2008.
Bruce Hajek. Cooling schedules for optimal annealing. Mathematics of operations research, 13(2): 311-329, 1988.
Darrall Henderson, Sheldon H Jacobson, and Alan W Johnson. The theory and practice of simulated annealing. Handbooo of metaheuristics, pp. 287-319. Springer, 2003.
Pascal Hitzler. Neuro-symbolic artificial intelligence: The state of the art. 2022.
Nick Hoernle, Rafael Michael Karampatsis, Vaishak Belle, and Kobi Gal. Multiplexnet: Towards fully satisfied logical constraints in neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 5700-5709, 2022.
Yining Hong, Qing Li, Daniel Ciao, Siyuan Huang, and Song-Chun Zhu. Learning by fixing: Solv- ing math word problems with weak supervision. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 4959 4967, 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 (Volume Long Papers), pp. 2410-2420, 2016.
Yu-Xuan Huang, Wang-Zhou Dai, Len Cai, Stephen H Muggleton, and Yuan Jiang. Fast ab- ductive learning by similarity- basedd consistency optimization. Advances in Neural Information Processing Systems, 34:26574-2663 265884, 2021.
Pierre E Jacob, John O'Leary, and Yves F Atchadé. Unbiased markov chain monte carlo with couplings. arXiv preprint arXiv: /708 036250 2017.
Mark R Jerrum, Leslie Valiant, and Vijay V Vazirani. Random generation of combinatorial struc-
tures from uniform distribution. Theoretical computer science, 13:169-188 1986.

---

Published as a conference paper at ICLR 2023
Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex-nonconeee minimax optimization? In International conference on machine learning, pp. 4M.. PMLR, 2020.
Joblib Development Team. Joblib: running python functions as pipeline jobs, 2020. URL https: ic/
Yann LeCun, Sumit Chopra, Raia Hadsell, M Ranzato, and Huang. tutorial on energy-based learning. Predicting structured data, 1(0), 2006.
Dong-Hyun Lee et al. Pseudo-label: The simple and efficient supervise learning method for deep neural networks. In Workshop on challenges in representation learning, ICML,, volume 3, pp. 896, 2013.
Joshua Letchford, Dmytro Korzhyk, and Vincent Conitzer. On the value of commitment. Au- tonomous Agents and Multi-Agent Systems, 28(6):986-1016 2014.
David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathe- matical Soc., 2017.
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. In International Conference on Machine Learning, pp. 5884-5894, PMLR, 2020.
Chen Liang, Jonathan Berant, Quoe Le, Kenneth D. Forbus, and Ni Lao. Neural symbolic machines: Learning semantic parsers on Freebase with weak supervision. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 23-33, Vancouver, Canada, July 2017. Association for Computational Linguistics. doi: 10.18653/v1/ P17-1003. httpttss: https/////..ccchoooooooo/r//////
Chen Liang, Mohammad Norouzi, Jonathan Berant, Quoc V Le, and Ni Lao. Memory augmented policy optimization for program synthesis and semantic parsing, Advances in Neural Information Processing Systems, 31, 2018.
David IC MacKay, David IC Mac Kay, et al. Information theory, inference and learning algorithms. Cambridge university press, 2003.
Sharad Malik and Lintao Zhang. Boolean satisfiability from theoretical hardness to practical success. Commun. ACM, 52(8):6(66668 82, aug 2009. ISSN 0001-0782. doi: 10.1145/1536611.1133633 URL
3 1536663
Robin Manhaeve, Sebastijan Dumancie, Angelika Kimmig, Thomas Demeester, and Lue De Raedt. Deepproblog: Neural probabilistic logic programming. Advances in Neural Information Process- ing Systems, 31, 2018
Robin Manhaeve, Giuseppe Marra, and Luc De Raedt. Approximate inference for neural probabilis- tic logic programming. In KR, pp. 475-486, 2021.
Giuseppe Marra, Sebastijan Dumančié, Robin Manhaeve, and Luc De Raedt. From statistical re- lational to neural symbolic artificial intelligence: a survey. arXiv preprint arXiv:2108, 111.101..5... 11451, 2021.
Kuldeep S Meel, Moshe Vardi, Supratik Chakraborty, Daniel Fremont, Sanjit A Seshia, Dror Fried, Alexander Ivrii, and Sharad Malik. Constrained sampling and counting: Universal hashing meets sat solving. In Workshops at the thirtieth AAAI conference on artificial intelligence, 2016.
Nicholas Metropolis, Arianna W Rosenbluth, Marshall N Rosenbluth, Augusta H Teller, and Edward Teller. Equation of state calculations by fast computing machines. The journal of chemical physics, 1086) 1953.
Ankur Moitra. Approximate counting, the lovász local lemma, and inference in graphical models. Journal of the ACM (JACM), 66(2):1-25, 2019.
12

---

Published as a conference paper at ICLR 2023
Leonardo de Moura and Nikolaj Bjömer. Z3: An efficient smt solver. In International conference on Tools and Algorithms for the Construction and Analysis of Systems, pp. 337-340. Springer, 2008.
Yatin Nandwani, Abhishek Pathak, and Parag Singla. A primal dual formulation for deep learning with constraints. Advances in Neural Information Processing Systems, 32, 2019.
Robert Nieuwenhuis, Albert Oliveras, and Cesare Tinelli. Solving sat and modulo theories: From an abstract davis davis-putnan logemann- procedure to dpll (t). Journal of the ACM (JACM), 53(6):937-97) 2006.
Yaghout Nourani and Bjarne Andresen. A comparison of simulated annealing cooling strategies. Journal of Physics A: Mathematical and General, 31(41):8373, 1998.
Connor Pryor, Charles Dickens, Eriq Augustine, Alon Albalak, William Wang, and Lise Getoor. Neupsl: Neural probabilistic soft logic. arXiv preprint 22ti::2005.14266 2022.
Jinghui Qin, Xiaodan Liang, Yining Hong, Jianheng Tang, and Liang Lin. Neural-symbolic solver for math word problems with auxiliary tasks. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 5870-5881, Online, August 2021. Association for Computational Linguistics. doi: 10. 11853//1/20222 120.:3/////221..l.loooooggg 4566.
URL https:
aachannhollo htt. 456
Lue De Raedt, Kristian Kersting, Sriraam Natarajan, and David Poole. Statistical relational artificial intelligence: Logic, probability, and computation. Synthesis lectures on artificial intelligence and machine learning. 10(2):1-19, 2016.
Stuart Russell. Artificial intelligence a modern approach. Pearson Education, Inc., 2010.
Chris Sherlock, Paul Fearnhead, and Gareth O Roberts. The random walk metropolis: linking theory and practice through a case study. Statistical Science, 25(2): 2010.
MTCAJ Thomas and A Thomas Joy. Elements of information theory. Wiley-Interscience, 2006.
Sever Topan, David Rolnick, and Xujic Si. Techniques for symbol grounding with satnet. Advances in Neural Information Processing Systems, 14:20733-20774, 2021.
Andrew Trask, Felix Hill, Scott E. Reed, Jack Rae, Chris Dyer, and Phil Blunsom. Neural arithmetic logic units. Advances neural information processing systems, 31, 2018.
Leslie G Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Com- puting, 833):410-421, 1979.
Leslie G Valiant. Three problems in computer science. Journal of the ACM (JACM), 50(1))96-99, 2003.
Moshe Vardi. Boolean satisfiability: theory and engineering. Communications of the ACM, 57 (3):55, 2014.
Ramakrishna Vedantam, Karan Desai, Stefan Lee, Marcus Rohrbach, Dhruv Batra, and Devi Parikh. Probabilistic neural symbolic models for interpretable visual question answering. In Kama- lika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Con- ference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6428 6437. PMLR, 09-15 Jun 2019. URI. vedantam 9a. html
ngs. ml www.:nngg..m.s.sss..e.. r.press/v99/
Po-Wei Wang, Priya Donti, Bryan Wilder, and Zico Kolter. Satnet: Bridging deep learning and log- ical reasoning using a differentiable satisfiability solver. In International Conference on Machine Learning. pp. 6545-6554. PMLR, 2019.
Wei Wei, Jordan Erenrich, and Bart Selman. Towards efficient sampling: Exploiting random walk strategies. In AAAI, volume 4, pp. 670-676, 2004.
13

---

Published as a conference paper at ICLR 2023
Avi Wigderson. Mathematics and computation. In Mathematics and Computation. Princeton Uni- versity Press, 2019.
Ronald J Williams.
Simple statistical gradient-follownng algorithms for connectionist reinforcement learning. Machine learning, 8(3):229-256, 1992.
Thomas Winters, Giuseppe Marra, Robin Manhaeve, and Luc De Raedt. Deepstochlog: Neural stochastic logic programming. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 10090-10100, 2022.
Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Broeck. semantic loss function for deep learning with symbolic knowledge. In International conference on machine learning, pp- 5502-5511. PMLR, 2018.
Zhun Yang, Adam Ishay, and Joohyung Lee. Neurasp: Embracing neural networks into answer programming. In 29th International Joint Conference on Artificial Intelligence (IJCAI 2020),
2020.
Kexin Yi, Jiajun Wu, Chuang Gan, Antonio Torralba, Pushmeet Kohli, and Josh Tenenbaum. Neural- symbolic vqa: Disentangling reasoning from vision and language understanding. Advances in neural information processing systems, 31, 2018.
Dongran Yu, Bo Yang, Dayou Liu, and Hui Wang. A survey neural-symbolic systems. arXiv preprint 1 1.08164 64, 2021.
14

---

Published as a conference paper at ICLR 2023
A PROOFS
A. PROOF OF PROPOSITION 1
Proof. We define ((0) Ex~Q- log Pe (z)x) as the objective function, and consider the bias of gradient on different distributions Q and Q", which is denoted by m@0).
m()) 2 log Po(z|x) Ez~Qq V log Pa(z|x)
Σ (Q(z)-Q'() V log (z(z)x) SE
Note that our sampling strategy ensures that only feasible states will be generated, and thus we have supp(Q) C supp(Q") Sy-
Hence, through the Cauchy-Schwarz inequality, we can obtain that
[mm())]]== =1 Σ (²(2) - Q" (z)) V log Po(z
S
Σ (Q(z) (z)) =
Σ
V log Po(z|x)112 S (neL.)?
S
where Sq. represents the support of Q* and denotes cardinal number. Now, by applying
Lemma 3 in Ajalloeian & Stich 2220)) we can obtain that
K
s so lo ( 2o) (avT+I) + (nE..)²,
Σ
K
where o² the bounded variance in gradient estimate.
A.2 PROOF OF PROPOSITION 2
Proof. It be observed that the loss function ?(0) log Exss, Po(z)x) is essentially the
semantic loss (Xu al. 2018 Def. 1), as well as the loss used in Deepproblog (Raedt et al. 2016 Sec. 7) and NGS (Li et al. 2020 Eq. 7).
Now, we consider the gradient Vi(0), which can be computed as
vi(0) = Σ
1
VPo(z(x).
Ex'eS(y) Po(x'(x)
zeSly)
Po(z|x)
V log Po(z(x),
=
zES(y) Exeesty) Po(z'(x)
Let us switch to Problem P By setting y 1, for any z E S(y), we can compute Qø- by
Pa(z(x)
(z) x ES(y) Pa(2'|x)
and thus Vol(O, x*) can be rewritten as
Vi(0)
Σ (z) Po(z|x). SES,
For completeness, we also simply prove that the Qø is the optimal solution of ming {(0, Φ) with 7 1. Elaborately, the Lagrangian function of the lower-level problem is
C(o; = Σ (z) log
((s(z) Pa
x Σ
Q0(z) 11.
zES,
zESy
By computing its gradient in Q (z). and let it vanish. then
log Q (z) log (z(z) X = 0
15

---

Published as a conference paper at ICLR 2023
should hold for any E Sy. Therefore, we have
Qœ-(z) - - Po(z),
Σ
Ce--1Pa(z)
ZESy
Putting these two equalities together, we can obtain that
Po (z(
QΦ- Ex'Ss Pz(z')
which completes the proof.
B EXPERIMENTS
B. TWO-STAGE ALGORITHM
In this subsection, briefly diseuss the proposed two-stage algorithm used in Section Recall the two stages are: Stage Annealing (7-decreasing) stage, and Stage II: Zero-degree (7 0) stage.
Stage faithfully implements Algorithm [1] During Stage I training, with the temperature y de- creasing, Qø. gradually converges to one-hot categorical distribution, which will finally give a deterministic input-symbol mapping (i.e., pseudo label). Ideally, if the solution space can be properly enumerated, we can start the Stage II algorithm fully-supervised way. i.e., fine-tuning the network by these deterministic mappings. However, the solution space discrete and grows exponentially, and thus it is intractable to determine the mapping for each input.
To this end, we conduct Stage II in semi-supervised way. That is, when fine-tuning the network, we only use the deterministic mappings that can be easily determined, and drop the others. Elaborately, for the given input, the model's prediction satisfies the symbolic constraint, Qø can be directly computed according to equation 5 Hence, we only use these inputs as the training data in Stage II, leading to a semi-supervised setup.
B.2 FRAMEWORK GUIDELINE
Two key elements in our framework are annealing strategy and projection operator. Hence, we briefly discuss how set the temperature in the annealing strategy and the projection operator.
(1) The setting of temperature. Intuitively, a good initial temperature should ensure the new state will not be rejected at the first few training epochs. Therefore, setting the initial temperature large value (e.g., To = 1 in our three tasks) is generally effective. For the hyperparameter setting in the annealing strategy, we recommend to follow that of Nourani & Andresen (1998).
(2) The selection of projection operator. The selection of variables to be dropped by the projection operator very critical our framework. Feng al. (2021a) propose evaluate the quality of projection operator via entropy, which hints at choosing the variables with less entropy decreasing. more direct and practical guideline drop variables that highly correlated to others, because these variables depend on others and thus have lower entropy.
(3) The setting of projection dimension. The dimension of the projection space Ω requires trade-off: a larger dim(?) cannot effectively improve the connectivity of solutions, while smaller dim( may introduce more bias by the SMT solver. A practical method to determine dim(S) may be via wail-and-error, i.e., to gradually decrease the dimension of the projection space until the connectivity of J2 satisfactory. Furthermore, there are different methods which may be used to measure the connectivity of the solution space. In theory, one may count the number of connected components of the solution space, which is not very practical. In our experiments, as we carry out random walk, we adopt the number of random walk steps needed for the transition from the initial solution to a target solution. For example, in the HWF task, dim(A) is set as 5, since we observe that the solutions are fully connected by dropping the third and fifth symbols.
16

---

Published as a conference paper at ICLR 2023
Calculation Accuracy (%)
MAPO
NA
Symbol Accuracy (%)
80
80
NGS
Log
60
60
40
40
0K
20K
40K
60K
80K
100K
0K
20K
40K
60K
80K
100K
Iteration
Iteratiio
100
100
MAPO
NA
Symbol Accuracy (%)
80
Wal
Accuracy
80
NGS
Log
SSL
Linear
40
40
MA0 MM
0
200
400
600
800
1000
200
400
600
800
1000
Epoch
Epoch
Figure 4: Training curves (the first row) and test curves (the second row) of different approaches. We only plot the curves for some of the methods for brevity. Our approaches (Log and Linear) achieve the best symbol accuracy on the training set, and also generalize better to the test set.
B.3 EXPERIMENTAL SETTING
Model architecture, For HWF and Sudoku tasks, we used the LeNet-5 architecture; For SDSP task, we used the multilayer perceptron with 30 input neurons, one hidden layers with 128 neurons, and output layer 30 neurons.
Batch size and epoch. For all tasks, the batch size was set to 64. For all comparison methods and our Stage algorithm, the number of epochs is fixed 1,000. For Stage II algorithm. the number of epochs is fixed at 30. We fix T 10 in Alg. [ i.e.. conducting ten random walk steps before one gradient descent step.
Gradient descent algorithm. For all comparison methods, we followed the learning algorithm setting in their respective Github repository. To be specific, RL, MAPO, and SSL conducted the Adam algorithm with learning rate 5e-4. For approaches, we used the SGD algorithm with learning rate 0.1 Stage and the Adam algorithm with learning rate le-3.
Implementation. For RI, MAPO, and NGS methods, we used the code provided by NGS authors. For SSL and NA methods, we implemented them with the same projection technique and random walk strategy with our approach. The temperature is fixed to 0.001 in the NA method.
B.4 ADDITIONAL RESULTS
For the HWF task, we plot the training/test curves of our Stage algorithms (Log and Linear) and comparison methods (MAPO, NGS. SSL, and NA) in Figure 4 For our approaches, the random walk step is also counted within the iteration. First, it can be observed that the policy-gradient- based method (MAPO) cannot well fit the training data due to the issue of sparse reward. For the NGS method, it quickly overfits the training set, but cannot improving the symbol accuracy and generalizing to the test set. This result is not surprising because the back-search in NGS is too greedy and hence only works with good initial model. SSL and NA can be treated two different variants of our framework, and they learn well during the first few epochs, but then collapse due to the lack of effective grounding.
In Table 3 we further report some results additional experiments on the HWF task. We con- sider different combinations of our method with the existing methods. We first apply the Stage II
17

---

Published as a conference paper at ICLR 2023
Table 3: Results (%) of additional experiments.
Method
Symbol
Calculation
SSI. Stage II
17.4
1.41
NA + Stage II
13.0
0.41
Stage + NGS
99.5
96.6
algorithm for SSL and NA. However, such variants collapse since they cannot provide sufficient calculation accuracy, and finally converge to nearly zero calculation accuracy. We next apply the back-search in NGS after Stage I algorithm, by initializing with our Stage I models. This variant can achieve comparable results with that using direct supervision. Note that bit accuracy drop compared with that in the original NGS paper is due to that only evaluate the model on length-7 formulas. This result further verifies the effectiveness of our softened symbol grounding. However, the back-search in NGS lacks versatility in more complex settings and is not applicable other studied tasks.
18


Reviews:
[{"review_id": "XAILYgzj8Ik", "reviewer": "Reviewer_262g", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 5, "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": "This paper presents a neuro-symbolic learning framework with an explicit design for addressing the symbol grounding problem.  The key idea is softening symbol grounding by using a Boltzmann distribution to represent the entire symbol space, rather than a specific symbol grounding. Such a design achieves an efficient interaction between neural perception and symbolic reasoning. Then, a novel MCMC sampling method combined with SMT solving is proposed to facilitate learning the correct symbol grounding. Furthermore, an annealing mechanism with three different realizations is applied to avoid sub-optimal symbol groundings. Experimental evaluations show significant improvement over several state-of-the-art approaches. \n", "summary_of_the_review": "This paper makes significant progress toward addressing a fundamental problem in neuro-symbolic AI. The presented approach is novel, effective, and elegant, which is likely to have a great influence on future neuro-symbolic system design. \n ", "strength_and_weaknesses": "Strengths:\n- the paper is very well-written; all necessary background  (either classic or recent work) is carefully introduced, and related work is organized in a systematic and insightful manner.\n- the paper addresses a fundamental problem in AI from a novel and promising angle -- view symbol grounding distribution as a mixed strategy in game playing; the combination of the MCMC sampling with SMT solving is both novel and elegant\n- the paper has extensive experimental evaluations and achieves superior performance over many state-of-the-art approaches\n- the paper also presents a formal analysis of the convergence guarantee (with some mild assumptions)\n\nWeaknesses:\n- the projection and inverse operations may be quite sensitive and require some non-trivial domain expertise\n- the visual Sudoku classification task seems to be a simplified version of the original one. The 4-by-4 Sudoku puzzle used in the evaluation is much simpler than a standard 9-by-9 Sudoku. SATNet should be the state-of-the-art for the Sudoku task, which is however not included\n\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": "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": "THLtfC4YSD0", "reviewer": "Reviewer_qkDm", "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 proposes softening the symbol grounding problem in joint neural-symbolic learning. The major challenge in the neural-symbolic learning system studied in this work is the lack of supervision for the symbol grounding problem. This work presents efforts to model the symbol grounding problem as a Boltzmann distribution with efficient MCMC sampling to bridge the worlds of neural grounding and symbolic reasoning. Of particular interest is the sampling method the authors use to resolves the connectivity barrier in searching for feasible symbol representation. In experiments involving handwritten formulae, visual sudoku, and shortest path, the method shows improved performance compared to existing baselines.", "summary_of_the_review": "The paper is well done and the strengths far outweigh the weaknesses.", "strength_and_weaknesses": "As the authors mention, the key problem in the neural-symbolic systems is how to efficiently search for the feasible hidden symbol state in the exponentially large and discrete space. The authors propose a very interesting formulation to address the problem, prove the convergence and even connect with existing works. The entropy formulation that softens symbol grounding is really interesting and I quite like the accompanied sampling method proposed for the connectivity barrier. Both empirical results and the theoretical analysis are convincing enough.\n\nI do not have many technical questions but would rather like to ask some open ones.\n\nTo me, the scope of problems that this method can be applied is limited, a minor problem though. The problems studied in this work are only challenging without hidden symbol supervision. However, in practice, for the toy problems studied, it is not hard to obtain, and may take only a few hours to get enough data to train a decent symbol grounding network. Is it possible to show your method applied to problems where data is either too complex to label for humans while your method can obtain good performance, or it simply is too bordering to get labels for intermediate representation?\n\nAnother issue with the method is efficiency. I can see that the sampling process, though improved, could still be very slow (or correct me if not). SMT solvers could also be a major bottleneck for efficiency, as they might only be feasible for moderately small problem scales. Can you show some quantitative results regarding efficiency? ", "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": "JpLP9x_ahU", "reviewer": "Reviewer_78tc", "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": "This paper presents a neurosymbolic learning approach for tackling the problem of symbol grounding when the logic of symbolic constraints is provided.Their method uses an SMT solver to initialize one possible symbol grounding for a problem such that it satisfies a given “solution constraint”, and then uses a Boltzmann machine to enable sampling from a distribution over potential symbol groundings that satisfy a given solution constraint (such as a visusal equation taking on a particular value). The method is evaluated on three tasks: visual math, visual sudoku, and visual shortest path finding. The method is compared to baselines from reinforcement learning and symbolic-parser-based approaches. Across the tasks, they find that their method significantly outperforms the baselines.", "summary_of_the_review": "Despite the novel and interesting method introduced in this paper, there are major weaknesses in the clarity and quality of the paper, specifically as it relates to missing ablations, sensitivity analyses, and justification for task modifications. If the concerns can be addressed by the authors, and the paper’s clarity improved, I am willing to increase my score.", "strength_and_weaknesses": "Strengths:\n* The paper presents a reasonably straightforward but well motivated idea for allowing the perceptual and symbolic reasoning aspects of a neuro-symbolic method to interact. While I am not an expert in this kind of neurosymbolic reasoning, the method was well motivated by gaps in related work as pointed to.\n\n* The method is at least partially theoretically justified, including the use of stochastic gradient descent as a method for removing some of the sampling bias introduced by the paper’s MCMC procedure.\n\n* Neurosymbolic models have seen increasing attention over the last several years, and given this paper’s strong results, it seems well posed to have an impact in the community.\n\nWeaknesses:\n* Baselines seem especially weak and oddly chosen given the extensively cited related work that is more recent. For example, Li et al, 2020, which seems like one of the most recent and related pieces of work, is only compared on the first of the three tasks, without explanation for why it is not used for the other two. \n* The reasoning for the variants of the chosen tasks was confusing and seemed misleading. For example, the paper states “Since the original dataset (Li et al, 2020) consists of formulas with lengths varying from 1 to 7, which may lead to the label leakage problem, we only take the 6K/1.2K formulas with length 7 as the training/test set.” What does this mean? What would happen if you compared on all formulas? This seems particularly important because the performance of Li et al in this paper is *90 absolute percentage points* worse than the original paper. To ensure there isn’t a bug with the implementation, or the interpretation of the experimental results, I would like to see a comparison to their method on the full dataset as opposed to just the length 7 formulas. I also do not understand how including the whole dataset would lead to a label leakage problem.\n* The paper has several issues with clarity that would need to be improved before it could be published. \n  * For example, the authors use “Stage I” and “Stage II” to describe different aspects of their method throughout the results, but Stage I and Stage II are never defined in the text, so I was not able to follow what this was supposed to mean. \nIn proposition 2, the paper states that the method is a stict generalization of prior work which is the special case of gamma = 1. I believe this should be gamma = 0 (the deterministic case).\n  * Similarly there is jargon in several places that general machine learning readers may be unfamiliar with, for example “Either problem (1) or (2) can be viewed as a Stackelberg game with pure strategies, in which the player takes a single action (i.e., selecting a deterministic mapping h)”. What is a Stackelberg game? Why is this important?\n  * I did not understand the point about how after the annealing stage the problem becomes a semi-supervised one. Perhaps this could be spelled out a bit more clearly with some examples of what the semi-supervised problem looks like (what is the data, what parts of it are unlabeled, what are the labels).\n* The paper is missing key ablations to support the claims. \n   * In particular, a main claim is that using an annealed gamma for first having stochastic representations of symbols and then sharpening them over time is not directly ablated. It would be nice to see a comparison to the method when gamma is always fixed to be 0 from the start of training, as this is the key difference to prior work (as also noted by the paper’s proposition 2 remarks). \n   * A secondary claim relates to the projection operator, and its importance for enabling well-behaved MCMC proposals. The projection operator is chosen in a bespoke way for each problem. How sensitive is the method to the particular choice of projection operator? What happens if no projection operator is used? Given that this choice injects a significant amount of domain knowledge from a practitioner and does not appear to generalize across problems, this seems like an important experiment to run.\n\n\n\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": "Not applicable"}, "extra_text": {}}, {"review_id": "6wxitzCa64", "reviewer": "Reviewer_ypT3", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 addresses the general family of tasks when the input needs to be processed by a neural model, then processed by a symbolic model, and produce an output. \nFor example, the input may be an *image of* a handwritten arithmetic calculation, e.g. `7*8-5-9`. The neural model needs to recognize the digits and the operators, and is then allowed to use a symbolic model such as a standard simple calculator to produce the result (`42`).\nThese tasks are very difficult when we only have labels for the final answer, i.e. `42`, and no intermediate labels for the digits themselves.\n\nThe paper proposed a \"soft\" way to solve this problem by introducing a probability over the input, and a way to solve and optimize.", "summary_of_the_review": "I appreciate the difficulty of the problem that this paper is trying to solve, and the empirical results look promising.\nHowever, I could not understand most of the paper,  which sometimes seems to be written cryptically deliberately.\n\nI thus vote for rejection with low confidence, because even if the paper's solution is sound and novel, the paper will be valuable only to a very limited audience.", "strength_and_weaknesses": "## Strengths\n* The problem is interesting and important, as providing good solutions will allow neural models to leverage existing and exact tools (e.g., a calculator) instead of learning to calculate themselves, since a calculation by the neural network is expected to make mistakes, and is known to not generalize well.\n* The proposed technique sounds correct and clever, although I did not understand most of the details.\n* The approach is evaluated on three tasks and shows significant improvements over the baselines.\n\n## Weaknesses\n* Readability - I did not understand most of the technical details, and the paper is not very friendly for readers out of this sub-field.\nI did understand the general idea, but many mathematical steps are mentioned only briefly or cite a reference, which makes the reader feel that they are expected to read many references before being able to understand the paper.\nI do believe that the paper could have been written in a way that will make it more readable to the broad ICLR audience.\nSee details in the next section.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster