Neural-Symbolic Recursive Machine for Systematic Generalization
Authors: Qing Li
Yixin Zhu
Yitao Liang
Ying Nian Wu
Song-Chun Zhu
Siyuan Huang
Venue: Submitted to ICLR 2023 (2023)
Keywords: Systematic Generalization
Compositional Generalization
Neural-symbolic

Abstract: Despite the tremendous success, existing machine learning models still fall short of human-like systematic generalization—learning compositional rules from limited data and applying them to unseen combinations in various domains. We propose Neural-Symbolic Recursive Machine (NSR) to tackle this deficiency. The core representation of NSR is a Grounded Symbol System (GSS) with combina- torial syntax and semantics, which entirely emerges from training data. Akin to the neuroscience studies suggesting separate brain systems for perceptual, syntactic, and semantic processing, NSR implements analogous separate modules of neural perception, syntactic parsing, and semantic reasoning, which are jointly learned by a deduction-abduction algorithm. We prove that NSR is expressive enough to model various sequence-to-sequence tasks. Superior systematic generalization is achieved via the inductive biases of equivariance and recursiveness embedded in NSR. In experiments, NSR achieves state-of-the-art performance in three benchmarks from different domains: SCAN for semantic parsing, PCFG for string manipulation, and HINT for arithmetic reasoning. Specifically, NSR achieves 100% generalization accuracy on SCAN and PCFG and outperforms state-of-the-art models on HINT by about 23%. Our NSR demonstrates stronger generalization than pure neural networks due to its symbolic representation and inductive biases. NSR also demonstrates better transferability than existing neural-symbolic approaches due to less domain-specific knowledge required.

Under review as a conference paper at ICLR 2023
HEURAL-SYMBER RECURSIVE MACHINE FOR SYSTEMATIC GENERALIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Despite the tremendous success, existing machine learning models still fall short of human-like systematic generalization
compositional rules from lim- ited data and applying them to unseen combinations various domains. We pro- pose Neural- -aubll-ymbollic Recursive Machine (NSR) to tackle this deficiency. The core representation of NSR Grounded Symbol System (GSS) with combi- natorial syntax and semantics, which entirely emerges from training data. NSR implements a modular design for neural perception, syntactic parsing, and se- mantic reasoning, which are jointly learned by We prove that NSR is expressive enough to model various tasks. Superior systematic generalization is achieved via the inductive biases of equivariance and recursiveness embedded in NSR. experiments, NSR achieves state-of-the-ard performance in three benchmarks from different domains: SCAN for semantic parsing, PCFG for string manipulation, and HINT for arithmetic rea- soning. Specifically, NSR achieves 100% generalization accuracy on SCAN and PCFG and outperforms state-of-the oatte-of-the-art models on HINT by about 23%. Our NSR demonstrates stronger generalization than pure neural networks due to its sym- bolic representation and inductive biases. NSR also demonstrates better trans- ferability than existing neubol-symbolic approaches due to less domain-specific knowledge required.
-abluciion-abduction algorithm.
INTRODUCTION
A remarkable property underlying human intelligence is its systematic compositionaliyy the alge- braic capacity interpret an infinite number of novel combinations from finite known components (Chomsky, (55))-infinite use of finite means" (Chomsky, 1965). This type of compositionality is central to the human ability to generalize from limited data to novel combinations (Lake et al., 2017). Recently, several datasets have been proposed to test systematic generalization of machine learning models-SCC SCAN (Lake & Baroni, 2018), PCFG (Hupkes et al., 2020), CFQ (Keysers et al., 2020), and HINT (Li et al., 2021). to name few. While conventional neural networks fail dramatically on these datasets, certain inductive biases have been explored to improve systematic generalization. Csordás et al. (2021); Ontanón al. (2022) improve Transformers' generalization performance by using relative positional encoding and sharing weights between layers. Chen et al. (2020) introduce a neural-symbolic stack machine achieve nearly perfect accuracy on SCAN-like datasets. Despite the improved performance, these neural- neural-symbolic methods often require domain-specific knowledge design non-trivial symbolic components and are difficult transfer other domains.
To achieve human-like systematic generalization in a wide range of domains, we propose Neural- Symbolic Recursive Machine (NSR), which integrates the joint learning of perception, syntax, and semantics in a principled framework. The core representation of NSR is a Grounded Symbol System (GSS) (see Fig. 1), which entirely emerges from training data without domain- sppciffc knowledge. NSR implements a modular design for neural perception, syntactic parsing, and semantic reasoning. Specifically, we first utilize a neural network as the perception module to ground symbols on the raw inputs. Next, the symbols are parsed into syntax tree of the Grounded Symbol System by transition cunsition-based neural dependency parser (Chen Manning, 2014). Finally, we adopt functional programs to realize the semantic meaning of symbols (Ellis et al., 2021). Theoretically. we show that the proposed NSR is expressive enough to model various inductive biases of equivariance and recursiveness, encoded in each module, enable NSR to break
tasks. Critically, the

---

Under review as a conference paper at ICLR 2023
down the long input into small components, process them progressively, and compose the results, encouraging the model to learn meaningful symbols and their compositional rules. Such inductive biases are the crux of NSR's 's superb systematic generalization.
is challenging to optimize NSR in an end-to-end fashion since annotations for the internal GSS oftentimes unavailable and NSR is not fully differentiable. To tackle this issue, present probabilistic learning framework and derive a novel deeduction-abductionn algorithm to coordinate the joint learning of different modules. In the learning phase (see also Fig. 2), the model first performs greedy deduction over these modules to propose an initial GSS, which may yield wrong results. Next, a bearch-based abduction is applied top-down to search the neighborhood of initial GSS for possible solutions; such abduction revises the GSS until it generates the correct result. As plausible solution, the revised GSS provides pseudo supervision to train each module, facilitating the learning of individual components in NSR.
We evaluate NSR on three benchmarks from various domains to study systematic generalization: (1) SCAN (Lake & Baroni, 2018), mapping natural language commands to action sequences; (2) PCFG (Hupkes et al., 2020), predicting the output sequences of string manipulation commands; (3) HINT (Li et al., 2021), predicting the results of handwritten arithmetic expressions. All these datasets include multiple splits for evaluating different aspects of systematic generalization. NSR achieves slate-of-the-ar performance
all these benchmarks. Specifically, NSR obtains 100% generaliza- tion accuracy on SCAN and PCFG and improves the state-of-the-art accuracy on HINT by about 23%. Result analyses reveal that NSR possesses stronger generalization than pure neural networks due to its symbolic representation and inductive bias. It also demonstrates better transferability than existing neural-symbolic approaches due to less domain-specific knowledge required. We also eval- uate NSR on a proof-of-concep machine translation task from Lake & Baroni (2018) and the results demonstrate the promise of applying NSR to realistic domains.
2 RELATED WORK
There has been an increasing interest in studying the systematic generalization of deep neural net- works. Started by the SCAN dataset (Lake & Baroni, 2018), multiple benchmarks across various domains have been proposed, including semantic parsing (Keysers et al., 2020; Kim & Linzen, 2020), string manipulation (Hupkes et al., 2020), visual question answering (Bahdanau al., 2019), grounded language understanding (Ruis et al., 2020), and mathematical reasoning (Saxton et al., 2018; Li et al., 2021). These datasets serve as the test bed for evaluating different aspects of gen- eralization, including systematicity and productivity. A line of research has developed different techniques for these datasets by injecting various inductive biases into deep neural networks. We categorize previous approaches into three classes by how they inject the inductive bias:
Architectural Prior The first class of methods explores different architectures of deep neural net- works for compositional generalization. Dessi & Baroni (2019) found that convolutional networks are significantly better than recurrent networks in the "jump" split of SCAN. Russin et al. (2019) improved the standard RNNs by learning separate modules for syntax and semanties. Gordon et al. (2019) proposed the equivariant seq2seq model by incorporating convolution operations into RNNs to achieve local equivariance over permutation symmetries of interest, which are provided before- hand. Csordás et al. (2021) and Ontanón et al. (2022) observed that relative position encoding and sharing weights across layers significantly improve the systematic generalization of Transformers.
Data Augmentation The second class of methods designs different schemes to generate auxiliary training data for encouraging compositional generalization. Andreas (2020) performed data augmen- tation by replacing fragments of training samples with other fragments from similar samples, and Akyürek et al. (2020) trained a generative model to recombine and resample training data. The meta sequence-to-sequence model (Lake, 2019) and the rule synthesizer (Nye et al., 2020) are trained with samples drawn from a meta-grammar with a format close to the SCAN grammar.
Symbolic Scaffolding The third class of methods bakes symbolic components into neural ar- chitectures for improving compositional generalization. Liu et al. (2020) connected a memory- augmented neural model with analytical expressions, simulating the reasoning process. Chen et al. (2020) integrated a symbolic stack machine into a seq2seq framework and learned a neural con- troller to operate the machine. Kim (2021) learned latent neural grammars for both the encoder
2

---

Under review as a conference paper at ICLR 2023
(1) SCAN
(2) PCFG
(3) HINT
junp lift after walk roice
agyend suup C. rggat RE
2+
after 12 [WALK, WALK, LTURN, JUMP)
append 53 [C, B,
+ +0
lift ILTURN, JUMP]
twice [WALK, WALK]
soap 51 [C.
BJ
rggaal 52 (B.
2 2.2 X 12
jump [JUMP]
wark
[WALK]]
A [A] BI
C2|C]
B B1
E [
33
4 9.9
Figure I: Examples of Grounded Symbol Systems, which are interpretable and illustrate a human-like reasoning process. (1) SCAN: each node is triplet of (word, symbol, action sequence); (2) PCFG: each node is triplet of (word, symbol, letter list). (3) HINT: each node is triplet of (image, symbol, value). Each symbol denoted by its index.
and the decoder in seq2seq framework. These methods achieved strong generalization by inject- ing a symbolic scaffolding into their models. However, these symbolic components require domain knowledge for specialized modules and complicated training procedures, such as hierarchical rein- forcement learning in Liu et al. (2020) and expensive search process for execution traces in Chen et al. (2020), which often have to be constrained under carefully designed curriculum in prac- tice. In contrast, the proposed NSR model requires less domain-specific knowledge for designing its modules and the proposed deduction-abduction algorithm for learning NSR does not require specialized curriculum, leading to better transferability and easier optimization.
3 NEURAL-SYMBOLLE RECURSIVE MACHINE
3.1 REPRESENTATION GROUNDED SYMBOL SYSTEM (GSS)
Two schools of thought, connectionism and symbolism, have long debate about the proper rep- resentation of the human mind (Fodor et al., 1988; Fodor & Lepore, 2002; Marcus, 2018). Central to connectionism is distributed representations (Hinton, 1984), arguing that certain concept or meaning is represented by pattern of activity across many neurons. In contrast, symbolism pos- tulates a physical symbol system (Newell, 1980), wherein each symbol alone represents an atomic concept, and more complicated concepts are formed by combining multiple symbols with certain syntax (Chomsky, 1965; Hauser al., 2002; Evans & Levinson, 2009). Symbol systems are more interpretable and support stronger abstraction and generalization than distributed representations (Launchbury, 2017). However, handcrafting a symbol system for a domain requires lot of domain- specific knowledge, and the constructed system is fragile and suffers from the notorious symbol grounding problem (Harnad, 1990).
In this work, propose a grounded version of the symbol system as the internal representation for systematic generalization. Such a Grounded Symbol System (GSS) provides a principled integration of perception, syntax, and semantics, directed tree 7 =< (I, s, v), e > Each node is a triplet of the grounded input x. the abstract symbol 8, and the semantic meaning v. Each edge denotes the semantic dependency between the parent and the child node; an edge i - j denotes that the node i's semantic meaning depends on node j's.
exemplified by Fig. 1. Formally, GSS is defined
Despite their nice properties, handcrafted symbol systems inevitably fragile and labor-intensive. Therefore, it is essential to ground symbol systems on raw inputs and learn their syntax and seman- ties from the training examples, which we will discuss next.
3.2 MODEL: NEURAL-SYMBOLE SYMBOLIC RECURSIVE MACHINE (NSR)
We now describe the proposed NSR that induces a GSS from training data. As illustrated in Fig. 2, the NSR consists three learnable modules: A neural perception module for grounding symbols on the raw input, dependency parser for predicting the dependencies between symbols, and a program synthesizer for predicting the semantic meanings. Since the ground-trume truth GSS is unavailable during training, these three modules ought to be learned in end-to-end fashion without intermediate supervision. Below, we first describe the three modules of NSR and then discuss how to learn NSR end-to-end with our proposed deduction-abducee
algorithm.
Neural Perception
The role of the perception module is to map raw input x (e.g., handwritten expression) into symbolic sequence s (denoted by a list of indices). This perception module handles
3

---

Under review as a conference paper at ICLR 2023
Grounded Symbol System
Inference
Abudction
T =< (x,s,
Learning
X
Neural Perception
S
Dependency
S,
Program Induction
Parsing
Figure The pipeline of inference and learning NSR.
the perceptual variance from raw input signals, such that each predicted token wy E is grounded in a certain part of the input x; E v. Formally, we have:
p(s| 0p)
I p( (
my 0p)
I softmax (eftumx((((;;.0.. x4; Bp));
(1)
where o(w;, myz 0p) is a scoring function parameterized by neural network with parameters 0p. The architecture of the perceptual neural network depends on the format of the raw input, which could be pre-trained; for example, we use pre-trained convolutional neural network for images.
predict the dependencies between symbols, we adopt a transition- -base neural dependency parser (Chen & Manning, 2014), commonly used for parsing natural language sentences. The transition- dependency parser relies on a state machine that defines the possible transitions to parse the input sequence into dependency tree. The parser constructs the parse tree from the input sequence by recursively applying the predicted transition to the state machine until the parsing process ends; see Fig. A1 for illustration. At each step, the parser predicts one transition based on the state representation. The state representation is constructed from local window and contains: (i) the top three words in the stack and buffer, (ii) the first and second leftmmsstrrihhmmost children of the top two words in the stack, and (iii) the leftmost of lefttnost/rightmost of rightmost children of the top two words in the stack. Given the state representation, we adopt two-layer feed-forward neural network to predict the transition. Formally, given the input sentence s, we have:
Dependency Parsing
p(e|s; 0.) = p( [s;00,, 0.) = II p(t,)c,00). T
where 0g is the parser's parameters, = (4,, (2,...,4 43 += e the transition sequence that generates the dependencies e, and c; the state representation at the i-th step. In practice, use greedy decoding strategy to predict the transition sequence for the input sentence.
Program Induction Inspired by recent advances in program induction (Ellis al., 2021; Ba- log et al., 2017; Devlin et al., 2017), we adopt functional programs to represent the semantics of symbols and view learning program induction. Compared to purely statistical approaches, sym- bolic programs exhibit better generalizability and interpretability. and the learning is usually more sample-efficient. Formally, given the input symbols and their dependencies e, we have:
puule, 8; 0:)
I p(us) (s; (h:idreenss:)::))
where is the set of programs induced for every symbol. practice, we use symbolic programs, yielding deterministic reasoning process.
Learning semantics for symbol is equivalent searching for a program that matches the given examples. Candidate programs are composed of set of pre-defined primitives. Based on the Peano axioms (Peano, 1889), we find universal set of primitives: (1) 0; (2) inc: i -- - (4)==; (5) f: (a, b, c) - if a is true, return b, else Such simple set of primitives are provably sufficient to represent any symbolic function, which we will further demonstrate Sec. 3.4. To speed up the search process and facilitate generalization,
+ 1; (3) dec:
augment this set of primitives with a minimal subset of Lisp primitives for list processing (cons, caz, cdr, etc.) and the recursion primitive (Y-combinator (Peyton Jones, 1987)). The Y-combinator allows to represent any recursive function and the crux of extrapolation on semantics.
In practice, we adopt DreamCoder (Ellis al., 2021) for program induction, which can efficiently synthesize programs from input-output pairs across a wide range of domains. We revised the original DreamCoder to handle noise in the given examples during the search process.
4

---

Under review as a conference paper at ICLR 2023
3.3 LEARNING
Since the intermediate GSS is latent and non-differentiable, the pack-propagation is not applicable learn NSR. Previous methods usually learn such neural-symbolic models with policy gradient algorithms, such as REINFORCE (Williams, 1992). However, the policy gradient methods have been shown converge slowly or even fail converge (Liang et al., 2018; Li at., 2020); requires generating a large number of samples over large latent space with sparse rewards, hoping some samples may be lucky enough to hit high rewards for updating the policy. Due to the prohibitively large space of GSS, we have to seek for an alternative and more efficient learning algorithm.
Formally, let denote the input, T =< (x, s, v). e the intermediate GSS, and y the output. During learning, (ar, v) is observed but 7 is latent. The likelihood of the observation (x,, v) marginalized over can be decomposed as:
plyl2; θ) = Σ P(T, = Σ p(s)x;0p)p(edp pp)p(els; 8,6,0
(4)
8 l denotes the process of grounding symbols to raw signals, guided by the perception module 0p- e denotes the process of parsing the symbol sequence into a parse tree, guided by the syntax module 0g. e|s,e denotes the process of reasoning over the parse tree, guided by the semantic module 0; y a deterministic process: p(yle) = if the final output of v equals to y, otherwise 0.
From maximum likelihood estimation (MLE) perspective, the learning objective is to maximize the observed-date log- ligeeiilldood [(x, y) = log p(yl x)). Assuming 0p. fz, 8j are continuous, we take the derivative of L w.r.t. 0g: 02 8: (see Eq. (A2) for the detailed derivation):
Va, L(x,
(rr=(T|/x.)) Vo, (og((s/zz 0p)]; Vo, L(x,)) v) = (r--(7 V logr(e]s;
(S)
V L(x, v) = 1E Vo, log logp(u|s,,; 0c)
where p(T y) is the posterior distribution of T given (æ, v). Since p(ulv) can only be 0 or 1, p(T x y) can be rewritten as:
P(T 1/2:;
0, for T#Q Q
p(T (.,) v)
Σr. P(T ,)
p(T Er ((
for T' Q
where Q= (T : p(y[T) L Prt is the set of T that match y. Usually, Q is very small subset of the entire space of (s, e, i... Q Cr.
Since taking expectation w.r.t. this posterior distribution (Eq. (5)) is intractable, use Monte Carlo sampling to approximate The optimization procedure for an example (æ, y) is as follows:
1. Sample a plausible solution: / =< (xr, 8, 0), e >~ p(T v).
2. Use (x, 8) to update the perception module (0p)).
3. Use (3, é) to update the syntax module (0.).
4. Use (8, é, 0) to update the semantic module (0)).
Steps 2-4 are supervised training for each module and no longer require the continuous assumption for the derivation Eq. (5). Step requires sampling from highly sparse distribution in large space, which we describe below.
Deduction-Abduccioon The key to the above learning procedure is the efficient sampling from the posterior distribution p(T) pr, y). To tackle this problem, we develop a novel deduction-abdduction abduction algorithm, summarized Alg. AI. Concretely, for given example (x, v). we first perform greedy deduction from æ to obtain initial GSS T =< (ar, 8, 0), é >, which may yield wrong result. To find a revised T that matches the correct result y during training, we search the neighbors of T in top-down manner by performing abduction over perception, syntax, and semantics; see Alg. Al and Fig. A2 and A3, Theoretically, the above deduction-abduccie Hastings sampler for the posterior distribution p(T) Jr, y). as proven by Li et al. (2020).
process behaves as a Metropolis-
3.4 EXPRESSIVENESS. AND GENERALIZZTTON OF NSR
We now discuss NSR's 's properties. Overall, we find that NSR has the expressive power to model var- ious seq2seq tasks, and the inductive biases in NSR enhance its systematic generalization capability.
5

---

Under review as a conference paper at ICLR 2023
Expressiveness We prove that NSR has the expressive power to model various seq2seq tasks. Lemma 1. For finite unique set of (a* O,.., N. there exists neural network fp with enough capability, satisfying: Væ', fz("')
Provably, there exists a neural network that maps every element in finite set to a unique index, L.e, x² - i (Hornik et al., 1989; Lu et al., 2017). The parsing process is trivial since every input is mapped to single token.
Lemma 2. Any index space can be created from the primitives {0, inc].
All indices are natural numbers, which can be recussively defined by {0, inc]: 0 - 0, inc (0), - inc (inc (0) ), ,,3 inc (inc (inc (0) ,.... We can create indices for both inputs and outputs via this lemma.
Equipped with the above lemmas, we have the following theorem on the expressiveness of NSR: Theorem 3. For any finite dataset D = {(x', y²) : O,..,NN, there exists an NSR that can sufficiently express D using four primitives (0,
This theorem can be proven by constructing a degenerate NSR to "memorize" examples in via a long program:
NSR(x)
Ø)...)
The above program is akin to a lookup table, composed by the primitives [if,==] and the index space created by the primitives {o, inc]. Since these four primitives universal for all domains, we are assured that NSR is expressive enough to model various seq2seq tasks and thus enjoys better transferability than previous neural-symbolic approaches.
Generalization Although the degenerate program defined by Eq. (7) achieves perfect accuracy on the training set, it can hardly generalize beyond training examples. To achieve strong generalization, we have to impose certain inductive biases; these inductive biases should be minimal and applica- ble most domains. Inspired by previous progress on compositional generalization (Gordon et al., 2019; Chen et al., 2020), we hypothesize two necessary inductive biases; equivariance and recur- siveness. Intuitively, equivariance enables the model's systematicity, generalizing from ( ("run", "run twices we", "jump"] to "jump twice", whereas recursiveness enables the model's pro- ductivity, generalizing to longer sequences like "run and jump twice".
Following Gordon et al. (2019), we formalize the hypothesis of equivariance and recursiveness from the perspective of group theory. A discrete group G is a set of elements (gI.....99i) with binary group operation ".", satisfying the group axioms (closure, associativity, identity, and invertibility). For equivariance, we consider a permutation group P, whose elements are permutations of a set X. For p P, we define the permutation operation T, X' X. For recursiveness, we consider composition operation C and define Te (X,X) X) + X. Formally, we have:
Definition 1 (Equivariance), Given two sets X' and V, let P be a permutation group, whose group operations on X and y are denoted by Tр X X' and TV : y + -, respectively. A mapping T: X - y is equivariant if and only if
Vx P.P. (TT,)) (x))
Definition 2 (Recursiveness). Given two sets X' and V, let T. : (X, X) and T (V,))) - y C be two composition operations on X' and )' respectively. A mapping Φb : X - y is recursive if and only
3T., Tw Va E X2 X: ((T((1))22) =
is straightforward to see that the three modules of NSR, i.e., neural perception (Eq. (1)), depen- dency parsing (Eq. (2)), and program induction (Eq. (3)) equivariant and recursive, because they are all pointwise transformations according to their formulations. Empirically, models that achieve superb compositional generalization on certain reasoning tasks, including NeSS (Chen al., 2020), LANE (Liu et al., 2020), and the proposed NSR, are equivariant and recursive. Therefore, we pro- pose the following hypothesis about compositional generalization:
Hypothesis 1. If a model achieves compositional generalization, the mapping instantiated by the model + X - Y is equivariant and recursive.

---

Under review as a conference paper at ICLR 2023
Table 1: The test accuracy on different splits of SCAN and PCFG. "A. R." stands for "Around Right," "Sys." for "Systematicityy" and "Prod." for "Productivity." The results of NeSS on PCFG are reported by adapting the source code provided by Chen et al. (2020) on PCFG.
SCAN
PCFG
Model
Simple 99.7
Jump 1.2
A. R.
Length
IID
Sys.
Prod.
Seq2Seq (Lake & Baroni, 2018)
2.5
13.8
53
CNN (Dessi & Baroni, 2019)
100.0
69.2
56.7
0.0
85
56
31
Transformer (Csordás al., 2021)
20
96
85
Transformer (Ontanón et al., 2022)
0.0
19.6
83
63
Equivariant Seq2seq (Gordon et al., 2019)
100.0
99.1
92.0
15.9
NeSS (Chen et al., 2020)
100.0
100.0
100.0
100.0
-0
-0
~0
NSR (ours)
100.0
100.0
100.0
100.0
100
100
100
EXPERIMENTS
4.1 SCAN
The SCAN dataset (Lake & Baroni, 2018) has been widely used to evaluate the systematic general- ization machine learning models. The task aims to translate a natural language command into a sequence of actions, simulating navigation in a grid world.
Evaluation Similar to previous work (Lake, 2019; Gordon et al., 2019; Chen et al., 2020), we evaluate NSR in the following four splits. (1) Simple: randomly split samples for training and testing. (2) Length: the output sequences in the training set contain at most 22 actions, whereas the output lengths in the test set are between 24 and 48. (3) Jump: the primitive "jump" only appears alone in the training set, whereas the test set contains commands combining "jump" with other primitives. (4) Around right: the phrase "around right" is held out from the training set, but both "around" and "right" occurs in the training set separately, such as "around left" and "opposite right."
Baselines We compare NSR with the following baselines: (1) Seq2seq (Lake & Baroni, 2018); (2) CNN (Dessi & Baroni, 2019); (3) Transformer (Csordás et al., 2021; Ontanón et al., 2022); (4) Equivariant seq2seq (Gordon al., 2019), which incorporates convolutional operations into recurrent neural networks to achieve local equivariance; and (5) NeSS (Chen et al., 2020), which integrates symbolic stack machine into a seq2seq framework.
Results Tab. 1 summarizes the results. Both NSR and NeSS achieve 100% accuracy on splits requiring systematic generalization, while other models' best performance on the Length split is only 20%. This contrast demonstrates the superiority of symbolic components (i.e., the symbolic stack machine in NeSS and the Grounded Symbol System in NSR) for systematic generalization.
While both NeSS and NSR achieve perfect generalization on SCAN, we would like to highlight some key differences. First, NeSS requires a considerable amount of domain-speciffn knowledge to design the stack machine's 's components, such the stack operations and the category predictors; NeSS without category predictors drops to around 20% for 3 out of 5 runs. Second, training NeSS requires manually defined curriculum with customized training procedures for the latent category predictors. In contrast, our proposed NSR embraces a modular design with little domain sppciifcc knowledge and does not require any special training scheme like a pre-defined curriculum.
Fig. 3 visualizes the syntax and semantics learned by NSR from the SCAN Length split. The dependency parser of NSR, which is equivariant as discussed in Sec. 3.4, forms clear permu- lation equivalent groups in terms of syntax among the input words: tuurn, walk, look, run, jump), (left, right, opposite, around, twice, thrice), and, after). Note that we do not provide any prior information about these groups-they entirely emerge from the training data, unlike providing equivariant groups beforehand (Gordon et al., 2019) or explicitly incorporating a category induction procedure from execution traces (Chen et al., 2020). In the learned programs, the program synthesizer of NSR creates an index space for the target language and finds the correct programs for representing the semantics of each source word.
4.2 PCFG
Next, we conduct experiments on the PCFG dataset (Hupkes et al., 2020), in which the model learns to predict the output of command of string manipulations, e.g., append swap F H,
7

---

Under review as a conference paper at ICLR 2023
turn
turn 0 []
1 - WALK
walk
1.00
walk: 0 [inc 0]
2 LOOK
look
3 - RUN
jump
run
0.75
run : Ø - [inc inc inc 0]
look: 0 - [inc inc 0]
5 - LTRUN
JUMP
right
left
0.50 left x - cons (ine inc inc inc inc 0,x)
jump
[inc inc inc inc 0]
6 RTURN
opposite
around
0.25
right x - cons (ine inc Inc inc inc inc 0,x)
twice
thrice
opposite :X - cons (x)r)
and
0.00
around:
+(+,xxxx))
after
turn
walk
look
run
jump
left
right
opposite
around
twice
thrice
and after
twice: x - + (x,x)
thrice: x - + (+xxxx),xx
and x,y
(x,y)
ofter:x,> y-
Figure 3: Leftt the syntactic similarity between input words of NSR trained on the SCAN Length split. The similarity between word i and word is measured by the pereentage of test samples in which replacing i with j. or vice versa, does not change the dependencies predicted by the dependency parser. Right: the induced programs for input words, where x and y denote the inputs, Ø denotes empty inputs, cons inserts an item to the first position of a list, car returns the first item in a list, and + concatenates two lists.
repeat I J H G I J. The input sequences in PCFG are generated by proba- bilistic context-free grammar, and the output sequences are constructed by recursively applying the string edit operations that are specified in the input sequences. The input samples are selected to match the statistical properties of a textual corpus from natural languages, such as the lengths of the sentences and depths of the parse trees.
Evaluation We evaluate models on the following splits. (1) IID: randomly samples for train- ing and testing. (2) Systematicity: this split focuses explicitly on models' ability to interpret pairs of functions that were never seen together during training. (3) Productivity: this split focuses on generalization to longer sequences; i.e., the training samples contain up to functions, while the test samples contain at least 9 functions. We compare with the following baselines: LSTM and CNN (Hupkes et al., 2020), Transformer (Csordás et al., 2021; Ontanón et al., 2022), and NeSS (Chen et al., 2020).
Results Tab. summarizes the results. NSR achieves 100% accuracy on all splits PCFG and out- performs the previous state-of-the-an arr model (Transformer) by 4% on the "Systematicity" split and 15% on "Productivity." Notably, NeSS completely fails on the PCFG dataset, although it achieves perfect accuracy on SCAN. By inspecting the training process of NeSS on PCFG, we find that the stack operations of NeSS cannot represent the binary functions in PCFG, and the trace search pro- cess fails due to the large vocabulary and the long sequences of PCFG. Domain -specffc knowledge and significant efforts would be required to re-design the stack machine and the training procedure.
4.3 HINT
Finally, we evaluate NSR on the HINT dataset (Li et al., 2021), in which the model learns to predict the integer result of handwritten arithmetic expression without any intermediate supervision, e.g., r3+2 8 40. Compared with SCAN and PCFG, HINT is much more challenging since its perception deals with real handwritten images with high variance and ambiguity, its syntax is more complicated due to the existence of parentheses, and its semantics involves recursive functions. The HINT dataset comes with a single training set and five test subsets for evaluating different generalizations across perception, syntax, and semantics.
Evaluation Following Li et al. (2021), we train models on the single training set and evaluate them on the following five test subsets. (1) "I": expressions are seen in the training set, but composed of unseen handwritten images. (2) "SS": expressions are unseen, but their lengths and values are within the same range training. (3) "LS": expressions are longer than training. but their values are within the same range. (4) "SL": expressions have larger values and their lengths are the same as training. (5) "LL": expressions are longer, and their values bigger than training. A prediction is considered correct if and only if it is exactly equal to the ground-
result.
Baselines We compare the proposed NSR with the following baselines: the seq2seq neural models (i.e.. GRU, LSTM, and Transformer) (Li et al., 2021) and NeSS (Chen et al., 2020). Note that each model is equipped with ResNet- 18 the image encoder.
8

---

Under review as a conference paper at ICLR 2023
Table 2: The test aceuracy HINT. The results of GRU, LSTM, and Transformer cited from Li al.
(2021), and the results NeSS are reported by adapting its source code on HINT.
Symbol Input
Image Input
Model
SS
L.
SL
LL
Avg.
L.
SL.
L.
Avg.
GRU
76.2
69.5
42.8
10.3
13.1
66.
58.7
33.1
9.4
12.8
35.9
LSTM
92.9
90.9
74.9
12.1
24.3
58.9
83,9
79.7
62.0
11.2
21.0
51.5
Transformer
98.0
96.8
78.2
11.7
22.4
61.5
88.4
86.0
62.5
10.9
19.0
53.1
NeSS
~0
~0
~0
~0
~0
~0
NSR (ours)
98.0
97.3
83.7
95.9
77.6
90.1
88.5
86,2
67.1
83,2
58.2
76.0
master counting
master + and
master and
Training epochs
O: Null
0:0
0:0
0:00 inc inc
I: Null
N:Null
inc inc 0
2:ime
9: Null
inc
inc
Inc inc
inc
Noll
if 0, (ine x, y1)
+: +:ifyy 0, x) (dee
Null
Null
-: if 0,x, +doe dec y))
-: (y 0, (dec 3) (dee
Null
Null
i: 0.y.2)
0,0, (doe
Noll
irly
inc 0, (s O x, inc Ol)
4: ir(x
0,0 inc (Cr ())00)--))))) +9))
Figure 4: The evolution of learned programs in NSR for HINT. The recursive programs in DreamCoder are represented by lambda calculus (ak.a. X-calculus) with Y-combinator. Here, translate the induced pro- grams into pseudo code for easier interpretation. Note that there might he different yet annctiinalll-cquivllee programs to represent the semantics of a symbol; we only visualize a plausible one here.
Results Tab. 2 summarizes the results on HINT. Comparing NSR with seq2seq neural models, that NSR improves the state-of-the-arr performance (Transformer) by about 23%. By inspecting the results on each test subset, we find that the improvement primarily comes from better extrapolation over syntax and semanties: NSR boosts the accuracy of "LL." from 19.0% to 58.2%, while the accuracy gains on "T" and "SS" are only around 2%. Please refer to Fig. A5 for qualitative examples of NSR's predictions on HINT. Again, NeSS completely fails on HINT due to similar reasons for its failure on PCFG as discussed in Sec. 4.2.
Fig. illustrates the evolution of semanties along the training of NSR in HINT. This pattern is highly in accordance with how children learn arithmetic in developmental psychology (Carpenter al.. 1999): The model first masters the semantics of digits as counting, then learns + and as recursive counting, and finally figures out how to define and based on + and - Crucially, x and + are impossible be correctly learned before mastering and -. The model endowed with such incremental learning capability since the program induction module allows the semantics of concepts to be built compositionally from those learned earlier (Ellis et al., 2021).
CONCLUSION AND DISCUSSION
In this paper, we present NSR, which learns Grounded Symbol System from data to achieve sys- tematic generalization. The Grounded Symbol System simulates generalizable, interpretable rep- resentation and provides a principled integration of perception, syntax, and semantics. NSR adopts a modular design and encodes the inductive biases of equivariance and recursiveness in each module, which are critical for achieving compositional generalization. To train NSR without the supervision of GSS, we present a probabilistic learning framework and propose a novel deduuction-bbduction algorithm to facilitate the efficient learning of NSR. NSR achieves state-of-the-an performance on three benchmarks ranging from semantic parsing and string manipulation to arithmetic reasoning.
A proof-of-concepe machine translation experiment demonstrates the promise of applying NSR to realistic domains. At the same time, we anticipate potential challenges of applying NSR to real- world tasks: (1) The noisy and numerous concepts in real-world tasks have large space of grounded symbol system and might slow the training of NSR: (2) The functional programs in NSR are deter- ministic and thus not able to represent probabilistic semantics in real-world tasks, e.g., in machine translation, there might be multiple ways to translate a single sentence. How to solve these chal- lenges will be explored in future work.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Ekin Akyürek, Afra Feyza Akyürek, and Jacob Andreas. Learning to recombine and resample data for compositional generalization. In International Conference on Learning Representations (ICLR), 2020. 2
Jacob Andreas. Good-enough compositional data augmentation. In Annual Meeting of the Associa- tion for Computational Linguistics (ACL), 2020. 2
Dzmitry Bahdanau, Harm de Vries, Timothy J O' O'Donnell, Shikhar Murty, Philippe Beaudoin, Yoshua Bengio, and Aaron Courville. Closure: Assessing systematic generalization of clevr mod- cls. arXiv preprint arXiv:1912.055280 2019.
Matej Balog, Alexander L Gaunt, Mare Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning to write programs. In International Conference on Learning Represen- tations (ICLR), 2017. 4, Al
Thomas P Carpenter, Elizabeth Fennema, M Loef Franke, Linda Levi, and Susan B Empson. Chil- dren's mathematics. Cognifively Guided, 1999.
Danqi Chen and Christopher D Manning. A fast and accurate dependency parser using neural net- works. In Annual Conference on Empirical Methods Natural Language Processing (EMNLP), 2014. 1,4
Xinyun Chen, Chen Liang, Adams Wei Yu, Dawn Song, and Denny Zhou. Compositional gen- eralization via neural-symbolic stack machines. In Advances in Neural Information Processing Systems (NeurIPS), 2020. 1, 2, 6, 7, 8, A6
Noam Chomsky. Syntactic structures. In Syntactic Structures. De Gruyter Mouton, 1957.
Noam Chomsky, Aspects of the Theory of Syntax. MIT press, 1965. 1,3
Róbert Csordás, Kazuki Irie, and Juergen Schmidhuber. The devil is in the detail: Simple tricks improve systematic generalization of transformers. In Annual Conference on Empirical Methods in Natural Language Processing (EMNLP). 2021. 7,8
Roberto Dessì and Marco Baroni. Cnns found to jump around more skillfully than mas: Compo- sitional generalization in seq2seq convolutional networks. In Annual Meeting of the Association for Computational Linguistics (ACL), 2019. 7,
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. In International Conference on Machine Learning (ICML), 2017. 4, A1
Kevin Ellis, Daniel Ritchie, Armando Solar-Lezama, and Joshua B Tenenbaum. Learning to infer graphics programs from hand-drawn images. In Advances in Neural Information Processing
Systems (NeurIPS), 2018a. A1
Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sablé-Meyer, Lucas Morales, Luke Hewitt, Luc Cary, Armando Solar-Lezama, and Joshua Tenenbaum. Dreamcoder: Bootstrapping ductive program synthesis with wake-sleep library learning. In Programming Language Design and Implementation, 2021. 1, 4, 9, A1, A2
Kevin M Ellis, Lucas Morales, Mathias Sablé-Meyer, Armando Solar Lezama, and Joshua B Tenenbaum. Library learning for neurally-guided bayesian program induction. In Advances in Neural Information Processing Systems (NeurIPS). 2018b. A1
Nicholas Evans and Stephen C Levinson. With diversity in mind: Freeing the language sciences from universal grammar. Behavioral and Brain Sciences, 32(5):472-492, 2009. 3
Jerry A Fodor and Ernest Lepore. The Compositionaliiy Pupers. Oxford University Press, 2002. 3
Jerry A Fodor, Zenon W Pylyshyn, et al. Connectionism and cognitive architecture; A critical analysis. Cognition, 28 2811-2):3-71, 1988. 3
10

---

Under review as a conference paper at ICLR 2023
Jonathan Gordon, David Lopez-Paz, Marco Baroni, and Diane Bouchacourt. Permutation equivari- ant models for compositional generalization language. In International Conference on Learning Representations (ICLR), 2019. 2, 6,
Stevan Harnad. The symbol grounding problem. Physica D: Nonlinear Phenomena, 42(1-3):333- 346, 1990. 3
Mare D Hauser, Noam Chomsky, and Tecumseh Fitch. The faculty of language: what is it, who has it, and how did it evolve? Science, 19865598) 2002.
Geoffrey E Hinton. Distributed representations. Technical Report CMU-CS-84-157, Carnegie Mel- lon University, 1984.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are uni- versal approximators. Neural networks, 2(5):359-366, 1989. 6
Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. Compositionality decomposed: how do neural networks generalise? Journal of Artificial Intelligence Research, 67:757-795, 2020. 1,
2, 7,
Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, et al. Measuring compo- sitional generalization: comprehensive method on realistic data. In International Conference Learning Representations (ICLR), 2020. 1.2
Najoung Kim and Tal Linzen. Cogs: A compositional generalization challenge based on semantic interpretation. In Annual Conference Empirical Methods in Natural Language Processing (EMNLP), 2020. 2
Yoon Kim. poneence-t--squeene learning with latent neural grammars. In Advances in Neural Information Processing Systems (NeurIPS), 2021. 2, A6
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015. A2
Tejas D Kulkarni, Pushmeet Kohli, Joshua B Tenenbaum, and Vikash Mansinghka. Picture: A probabilistic programming language for scene perception. In Conference on Computer Vision and Pattern Recognition (CVPR), 2015. Al
Brenden M Lake, Compositional generalization through meta sequence-to-seqqennc learning. In Advances in Neural Information Processing Systems (NeurIPS), 2019. 2,
Brenden M. Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of sequence-to- -o-suueece recurrent networks. In International Conference on Machine Learning (ICML), 2018. 1, A6
Brenden M Lake, Ruslan Salakhutdinov. and Joshua B Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 15506266) 2015. A1
Brenden Lake, Tomer Ullman, Joshua Tenenbaum, and Samuel J Gershman. Building ma- chines that learn and think like people. Behavioral and Brain Sciences, 40, 2017.
John Launchbury. darpa perspective on artificial intelligence. Retrieved November, 11:2019.
2017. 3
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 (ICML), 2020. 5
Qing Li, Siyuan Huang, Yining Hong, Yixin Zhu, Ying Nian Wu, and Song-Chun Chun Zhu. A mini- malist dataset for systematic generalization of perception, syntax, and semantics. arXiv preprint arXiv:2103.01 2021. 1, 2, 8,
11

---

Under review as a conference paper at ICLR 2023
Yuanpeng Li. Liang Zhao, Jianyu Wang, and Joel Hestness. Compositional generalization for prim- itive substitutions. Anmual Conference on Empirical Methods in Natural Language Processing (EMNLP), 2019. A6
Chen Liang, Mohammad Norouzi, Jonathan Berant, Quoe V. Le, and Ni Lao. Memory augmented policy optimization for program synthesis and semantic parsing. In Advances in Neural Informa- tion Processing Systems (NeurIPS), 2018.
Qian Liu, Shengnan An, Jian GuanG Lou, Bei Chen, Zeqi Lin, Yan Gao, Bin Zhou, Nanning Zheng, and Dongmei Zhang. Compositional generalization by learning analytical expressions. In Ad- vances Neural Information Processing Systems (NeurIPS), 2020. 2, 3,
Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. Advances in neural information processing systems, 30, 2017. 6
Gary F Marcus. The algebraic mind: Integrating connectionism and cognitive science. MIT press, 2018. 3
Allen Newell. Physical symbol systems. Cognitive science, 4(2):135-183, 1980.
Maxwell Nye, Armando Solar-Lezama, Josh Tenenbaum, and Brenden Lake. Learning composi- tional rules via neural program synthesis. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Santiago Ontanón, Joshua Ainslie, Vaclav Cvicek, and Zachary Fisher. Making transformers solve compositional tasks. Annual Meeting of the Association for Computational Linguisties (ACL), 2022. 1, 2, 7, 8
Giuseppe Peano. Arithmetices principia: Nova methodo exposita. Fratres Bocca, 1889. 4
Simon L Peyton Jones. The implementation of functional programming languages. Prentice-Hall, Inc., 1987.
Laura Ruis, Jacob Andreas, Marco Baroni, Diane Bouchacourt, and Brenden M Lake. A benchmark for systematic generalization in grounded language understanding, Advances in Neural Informa- tion Processing Systems (NeurIPS), 2020. 2
Jake Russin, Jason Jo, Randall C O' O'Reilly, and Yoshua Bengio. Compositional generalization in deep seq2seq model by separating syntax and semantics. arXiv preprint arXiv: (tti::/904.09700 2019.
David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. Analysing mathematical rea- soning abilities of neural models. In International Conference on Learning Representations (ICLR), 2018.
Ray Solomonoff. A formal theory of inductive inference. part i. Information and control, 7(1): 1-22, 1964. A1
Wouter Van Gansbeke, Simon Vandenhende, Stamatios Georgoulis, Marc Proesmans, and Lue Van Gool. Scan: Learning to classify images without labels. European Conference on Com- puter Vision (ECCV), 2020. A2
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning, Machine Learning, 8(3-4):22--256, 1992.
12

---

Under review as a conference paper at ICLR 2023
ID
Stack Buffer
Transition
Dependency
Start: o= [ROOT], B Wy W,, A= Ø
0
3 3 4
x
Shift
Shift
a, w. + alw, B,
Left-Arc,
alw, y B. + alw, B. AU(rW,,w))
1
3
+
4 4 2
Shift
3. Right-Arc,
alw,/w, B. a/w, AU(r(w,w)))
2
Left-Are
--+
Finish: a [w], B
3
+
Shift
3 + 4x2
4
+ 4
Shift
5
+4x2
Left-Arc
4 +-
6
+ 2
Shift
3
X
7
+ X
Right-Are
X- 2
8
+ X
Right-Are
+-X
4
Figure A1: Applying the transition-based dependency parser example of HINT. it similar for SCAN and PCFG.
A
APPENDIX
A.1 MODEL DETAILS
Dependency Parsing Fig. A1 illustrate the process of parsing an arithmetic expression via the dependency parser. Formally, state (a,, B, A) in the dependency parser consists of a stack a, a buffer 3, and a set of dependency arcs A. The initial state for a sequence [wnw]..Wx],
WoW,...C, is terminal if the buffer is empty and
Ø. A state is regarded the stack only contains the node Root. The parse tree can be derived from the dependency ares A. Let ag denote the i-th top element on the stack, and Bg the i-th element on the buffer. The parser defines three types of transitions between states:
[Root].3
LEFT-ARC: add an are 01 + Q2 to and remove 02 from the stack a. Precondition: |a] > 2.
RIGHT-ARC: add an arc Q2 - to A and remove an from the stack a. Precondition: |a] > 2.
SIIFT: move B1 from the buffer to the stack a. Precondition: |8] > 1.
The goal of the parser is predict transition sequence from initial state to a terminal state. [LEFT-ARG RIGHT-ARC, SHIFT)
time, based (a, B, A). The state representation is constructed from local win- dow and contains following three elements: (i) The top three words on the stack and buffer: ag B, 1, 2; (ii) The first and second lefimmst/rightmost children of the top two words the stack: Ic, (a:), rC1 (az), Ic2(as), re2(a:). = 1,2; (iii) The leftmost of leftmost/rightmmost of rightmost children of the top words on the stack: lc, (lcy (a,)), rea (rc1 (a:)), i = 1,2. We use a special Null 1 token for non-existent elements. Each element in the state representation is embed- ded to d-dimensional vector E Rd. and the full embedding matrix is denoted as E E Rd where E is the concept space. The embedding vectors for all elements in the state concatenated as its representation: e = [e1 62...c,] E Rnd Given the state representation, we adopt two-layer fred-forward neural network predict the transition.
The parser predicts one transition from
on the current state
Program Induction Program induction, i.e., synthesizing programs from input-output examples, was one of the oldest theoretical frameworks for concept learning within artificial intelligence (Solomonoff, 1964). Recent advances in program induction focus on training neural networks to guide the program search (Kulkarni al., 2015; Lake et al., 2015; Balog et al., 2017: Devlin al., 2017; Ellis et al., 201 8a;b). For example, Balog et al. (2017) train a neural network to predict proper- ties of the program that generated the outputs from the given inputs and then use the neural network's predictions to augment search techniques from the programming languages community. Recently, Ellis et al. (2021) release neural- geurallguided program induction system, DreamCoder, which can effi- ciently discover interpretable, reusable, and generalizable programs across a wide range of domains, including both classic inductive programming tasks and creative tasks such as drawing pictures and building scenes. DreamCoder adopts "wake-sleepp Bayesian learning algorithm to extend pro- gram space with new symbolic abstractions and train the neural network on imagined and replayed problems.
A1

---

Under review as a conference paper at ICLR 2023
To learn the semantics of symbol from set of examples De is to find a program Pa composed from a set primitives L, which maximizes the following objective:
max p(p) p De, L) a (DDl)) p(p)L),
(A1)
where p(Delp) is the likelihood of the program p matching De, and p(p] is the prior of p under the program space defined by the primitives L. Since finding globally optimal program is usually intractable, the maximization in Eq. (A1) is approximated by stochastic search process guided by a neural network, which is trained to approximate the posterior distribution De L). We refer the readers to DreamCoder (Ellis al., 2021)² for more technical details.
A.2 LEARNING
Derivation of Eq. (5) Take the derivative of I. w.r.t. 8p-
Va, M[, v) = Va, log logp(ul>) p(ula) Vo,p(yla)
pTT,y 2)
y| p(T", , logp(s/<x0p)
(A2)
E D(T
= -ET-M(TE,.) Ve, llg 0p)]
Similarly, for 0,, 02, we have
Ve, L(r v) = m Ve, p(e)(e 0,]], Vo, [(x v) Er (. Ve, logp(u)ss, e; e;))
(A3)
Deduction-AAduuction Alg. A1 describes the procedure for learning NSR by the proposed deduction-abducctoo abduction algorithm. Fig. A2 illustrate the one-step abduction over perception, syntax, and semantics in HINT and Fig. A3 visualizes a concrete example to illustrate the deduction- abduction process. is similar for SCAN and PCFG.
A.3 EXPERIMENTS
Experimental Setup For tasks taking symbols input (i.e., SCAN and PCFG), the perception module is not required in NSR; For the task taking images as input, we adopt ResNet-18 18 as the perception module, which is pre-trained unsupervisedly (Van Gansheke al., 2020) handwritten images from the training set. In the dependency parser, the token embeddings have dimension of 50, the hidden dimension of the transition classifier is 200, and we use dropout of 0.5. For the program induction, we adopts the default setting in DreamCoder Ellis et al. (2021). For learning NSR, both the ResNet-18 and the dependency parser are trained by the Adam optimizer (Kingma & Ba, 2015) with a learning rate of 10 NSR are trained for 100 epochs for all datasets.
Qualitative Examples Fig. A4 and Fig. A5 show several examples of the NSR predictions on SCAN and HINT.
"https://gi http:////ggghhbbbcco//1111/////
A2

---

Under review as a conference paper at ICLR 2023
Algorithm A1 Learning by Deduction-Abduuction
1: Input: Training set D {( y/) i 1,2, .... N)
2: Initial Module: perception 0%% syntax ! semantics 0,0)
3: for < to T do
4: Buffer
Ø
5: for (I, y) E D do
= DEDUCE(Z, 03 0 0)())
6:
7:
I ABDUCE(T,
8:
B (T*) end for
9:
10: 0g o((+1)
1 o(++1) = learn(B, [, 0 ,000 )00))
end for
12: return (T (2) ,0(
1: function DEDUCE(2, Op 0z, 01)
2: sample & ~ p(s|a; a;; 0p), ê p(e|8;0,), ((),);0)
3: return 7 =< (x, 0),
4: end function
1: function ABDUCE(T, y)
2: (-PriorityQueue)
Q.push(root(T). 1.0)
3: while A, MA, Q.pop( do
4: A (z. w, v, arcs)
5:
if A.v = then
6: return T(A)
7:
end if
8:
Abduce perception
9:
for w/ E Σ do
10:
A' = A(w w')
11:
if A'.u YA then
12:
Q.push(At A', yA, (A.P((A))) P(A))
end if end for
14:
Abduce synlax
16:
for are E arcs do
A' rotate(A, arc) if A'.u = DA then Q.push (A', (("))
18:
20:
end if
21:
end for
22:
Abduce semantics
23:
A' = A(u - yA)
24: Q.push(A', Ma (A'))
25:
t> Top-down search
26:
for B children A) do SOLVE( B, A. yA (A(ww)
27:
28:
Q.push(IB, yB, p(B)
29: end for
end while
31:
end function
A3

---

Under review as a conference paper at ICLR 2023
3-4 X2
7 4 4
23
(1) abduce perception: change one symbol
+ 35
23
7.77
X X
28
7 7
x
16
4 77
44
4
4
4
(2) abduce syntax: rotate one arc
44
23
11
44
7
77
X
x 16
77
4
4
C
44
(3) abduce semantics: change one value
15
23
X
7 77
16
C
44
4 4
C
444
4 4
Figure A2: Abduction over perception, syntax, and semantics in HINT. Parts revised during abduction are highlighted in red.
4++11 21
Deduction
Pz
4
P4
944
2, 2
Ps
Priority Queue
Priority Queue
Priority Queue
Priority Queue
3++ [a,, 2,1
Eigy 1.)....).1111
0..9..
999)) 9d
C. (6,, 2.
(a.. 18
C9 (.44))))00 9.
Pop
2 3.333 p), 13.
(0..;)).11.p
x 18 (0),9,)) 18,77
133)
21 (a,, 02)),
Abduction
Pop
3).
X 8
Pop
42
ag
3 333 P2
P3
8
P
4
444
Pop
Abluce perception: None Abbuce gutar: None
Absuce perception: Nume Abduce yyntex: None semuntic:: x 18 (dy, n.)). 18. swarch: ( 4 0). 9.
Abahee parcaption:: 99 9990), 9.p.
( (7.90))
Abaluee systes:
( 21 02)) 21.p%
Abalce semantier::
Top-down search:
1 0), 13.
dop-dornn searchi: None
[ x.8 (o).9.)), 18.
Figure A3: An illustration of the deduuction-adduction process for an example of HINT. Given handwrit- ten expression, the system first performs greedy deduction propose initial solution, which generates a wrong result. abduction, the root node, paired with ground-truth result, first pushed to the priority queue. The abduction over perception, syntax, semantics is performed on the popped node to generate pos- sible revisions. A top-down search also applied to propagate the expected value to its children. All possible revisions are then pushed into the priority queue. This process is repeated until we find the most likely revision for the initial solution.
A4

---

Under review as a conference paper at ICLR 2023
nun aroundl left twize and rus arewod right (LTURN, RUN] 8 |RTURN, RUN)*
walk gyonitt right thrice aftir bot arownd lift roice after 12 [LTURN, LOOK] IRTURN, RTURN, WALK] 3
twice ILTURN, RUN)"
around's (RTÜRN, RUN] 4 right 6 (RTURN, RUN
thriie 10 IRTURN, RTURN, WALK]* 3
twice 9 (LTURN, LOOK]'S 8
areund [LTURNJRUN] 44
appoite 2 IRTURN, RTURN, WALK] around 8 [LTURN, LOOKI*4
Gifts s (LTURN, RUN]
run [RUN]
right 6 (RTURN, WALK]
úife s (LTURN, LOOK]
Vun 3 [RUN]
wufe a [WALK]
look 2 [LOOK]
Figure A4; Examples of NSR predictions on the test set of the SCAN Length split. We use (repeating the list) and (concatenating two lists) to shorten the outputs for easier interpretation.
Test subset I
01003323 1
OT 208-0011118113-----1 PD; (2))
(745544
205- 1
(tee:
(Rose
Hhre
(how
22
Test subset SS
1000000000000000000000-000 (096-99--)
(3-4-(3-2))- 1045
3X (4 OT:
0904
Test subset SI.
971----- 457 90:990-8/33.88
GT: (1400)))) (1-76)
(2X 2 2 X7
Test subset LS
GT. wtw.://wwww.paaa.//.///.././....
Test subset LL
11 550 000. 24
Figure A5; Examples of NSR predictions on the test set of HINT. "GT" and "PD" denote "ground- trruund-trutt" and "prediction," respectively. Each node in the tree is tuple of (symbol, value).
A5

---

Under review as a conference paper at ICLR 2023
A.4 COMPOSITIONAL MACHINE TRANSLATION
To explore how well the proposed NSR model is applicable to real-world tasks, We run a proof- of-concept machine translation experiment using the English-French translation task from Lake & Baroni (2018), which is also used by previous works (Li et al., 2019; Chen et al., 2020; Kim, 2021) to explore their methods on realistic domains. Compared synthetic tasks like SCAN and PCFG, this translation task contains more complex and ambiguous rules.
Evaluation We adopt the public data splits from Li et al. (2019). Specifically, the training set contains 10,000 English-French sentence pairs, where the English sentences begin with phrases such as "I am", "you are", and their contractions. The training set also contains 1,000 repetitions of the sentence pair ("I am daxy". "je suis daxiste"), which is the only sentence that introduces the pseudoword "daxy" in the training set. The test set contains 8 combinations of "daxy" with other phrases, e.g.. "you are not daxy", which do not appear in the training set. Note that there are 2 different French translations of "you are" that frequently appear in the training set, so both of them considered correct in the test set. We compare with the following baselines: Seq2Seq Lake & Baroni (2018), Primitive Substitution Li et al. (2019), and NeSS Chen et al. (2020).
Results Tab. Al summarizes the results of the compositional machine translation task. Similar to previous methods (Primitive Substitution and NeSS), NSR achieves a 100% generalization accuracy on this task. This experiment shows that NSR has the promise to be applied to real-world tasks. Despite the perfect accuracy in this proof-of-concept experiment, we indeed anticipate potential challenges of applying NSR real-world tasks: (1) The noisy and numerous concepts in real-world tasks have large space of grounded symbol system and might slow the training of NSR; (2) The functional programs NSR are deterministic and thus not able to represent probabilistic semantics in real-world tasks, e.g., in machine translation, there might be multiple ways to translate a single sentence.
Table A1: Accuracy on the compositional machine translation task.
Model
Accuracy
Seq2Seq
12.5
Primitive Substitution
100.0
NeSS
100.0
NSR (ours)
100.0
A.5 ABLATION STUDY ON HINT
To explore how well the individual modules of NSR are learned, we perform ablation study on HINT to analyze the performance of each module of NSR. Specifically, along with the final results, the HINT dataset also provides the symbolic sequences and parse trees for evaluation. For Neural Perception, we report the accuracy of classifying each symbol. For Dependency parsing, we report the accuracy of attaching each symbol its correct parent, given the ground-truth symbol sequence as the input. For Program Induction, we report the accuracy of final results, given the ground-truth symbol sequence and parse tree.
Table A2: Accuracy of the individual modules of NSR on the HINT dataset.
Module
Neural Perception
Dependency Parsing Program Induction
Accuracy
93.51
88. 10
98.47
Overall, each module achieves high accuracy, as shown in Tab. A2. For Neural Perception, most er- rors come from the two parentheses, "(" and ")", because they are visually similar. For Dependency Parsing, we analyze the parsing accuracies for different concept groups: digits (100%), operators (95.85%), and parentheses (64.28%). The parsing accuracy of parentheses is much lower than those of digits and operators. We think this is because, long as digits and operators are correctly parsed in the parsing tree, where to attach the parentheses does not influence the final results because paren- theses have no semantic meaning. For Program Induction, we can manually verify that the induced programs (Fig. 4) have correct semantics. The errors are caused by exceeding the recursion limit when calling the program for multiplication. The above analysis is also verified by the qualitative examples in Fig. A5.
A6


Reviews:
[{"review_id": "xJVfuaWCHp", "reviewer": "Reviewer_w6P6", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The paper proposed a new approach composed of multiple components for systematic generalization on language tasks. It achieves good results on multiple datasets including SCAN, PCFG, and a task for arithmetic reasoning. ", "summary_of_the_review": "The paper explores an important direction and show nice experiments but I believe the main issue is the model that could be improved as well as some updates to the writing, and therefore overall at this point recommend weak rejection, but at the same time I wish to encourage the authors to work on improving the paper further to make it better!", "strength_and_weaknesses": "**Strengths**: \n* **Domain**: the paper explores an important and growing domain of systematic generalization.\n* **Experiments and results**: The paper presents experiments in multiple complementary datasets covering parsing, semantic reasoning, compositional generalization and arithmetics. It achieves good results across multiple tasks, and compares to multiple suitable baselines. The descriptions in the experiments section of the tasks and the baselines are also clear, well-structured and easy to follow. \n* **Modeling section**: The discussion in the modeling section is interesting and gives solid motivation for the approach presented in the paper, and the section is structured in a good and clear way. The model is also discussed from a theoretical perspective, and formally defines its properties (equivariance and recursiveness). \n* **Related work, background and context**: the paper does a good job contextualizing the approach, providing the necessary general background, and covering the relevant related fields. I recommend moving the related work section to an earlier point in the paper (before the modeling section). \n    \n**Weaknesses**:\n* **Related work comparison to specific recent approaches**: More details on how the new approach compares to recent models on the explored tasks would be useful.\n* **Complicated approach**: The approach is a bit complicated and consists of multiple different modules that are responsible for different aspects of the problem. We know that models such as transformers do amazingly well on language tasks being more uniform, and so I recommend examining whether the model could be simplified without negatively and potentially also positively impacting its performance. \n* **Undiferentaible**: The NSR model isn’t end-to-end differentiable, making training more challenging. Having multiple units that interact through hard predictions (without a gradient) could also lead to cascade errors, where early mistakes in early modules prevent the following ones to give the right predictions.I recommend exploring ways to make it differentiable, either by relaxing some of the constraints or using techniques such as gumbel-softmax etc. \n* **Synthetic data**: The model is evaluated on synthetic data only. I would highly recommend exploring e.g. logical problems in natural language such as word problems, logical questions (e.g. LSAT), etc etc, to strengthen the paper.\n* **Suggestion: focusing on the reasoning modules**: I also recommend exploring the parts of the model related to parsing and reasoning independently of the perceptual module since that is the central part of the paper, so would be good to highlight that, and also would broaden the range of datasets that could be explored.\n* **Evaluating each component independently**: Providing more details on the performance of each component independently and performing ablation studies is critical for models with multiple components, rather than only having results on downstream task performance.", "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": {}}, {"review_id": "YtyNfWyl40H", "reviewer": "Reviewer_j25h", "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": "The paper proposes a new model -- Neural-Symbolic Recursive Machine (NSR), that uses a Grounded Symbol System as its core mechanism. The model includes three components: a perception module, a parsing module, and a program induction module. The three modules are trained in an end-to-end fashion without intermediate supervision. The system benefits from the inductive bias of equivariance and recursiveness. It shows a strong compositional generalization ability on several standard benchmarks, including SCAN, PCFG, and HINT. ", "summary_of_the_review": "Overall, the paper proposed an interesting new framework for achieving compositional generalization. Experiment results confirm the effectiveness of the model in synthetic tasks. However, the proposed method is fairly complicated, which shed doubt on whether the method can be generalized to real-world tasks. The author didn't provide any proof or discussion on this question.", "strength_and_weaknesses": "Strength:\n1. The proposed NSR achieve impressive generalization results on several datasets.\n2. The three-module design is intuitive and general enough to be applied to different tasks and modalities.\n3. Experiments on SCAN and PCFG show that NSR has good interpretability.\n\nWeaknesses\n1. The NSR is only tested on synthetic tasks. The limitation of applying NSR in real-world tasks is not discussed either.\n2. The paper is difficult to follow, important diagrams and figures are put in the appendix.", "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": "L9bG6fJdBn3", "reviewer": "Reviewer_kopJ", "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": "The paper proposes Neural-Symbolic Recursive Machine (NSR) as a means for neural networks to learn compositional rules through 3 modules, one for processing perception, syntactic parsing and semantic reasoning. These modules made up the Grounded Symbol System (GSS) and are jointly learned through a deduction-abduction algorithm. The authors also showed that the NSR modules confer equivariance and recursiveness to the network’s representations. The experiments showed that NSR outperforms baselines on semantic parsing, string manipulation and arithmetic reasoning tasks.", "summary_of_the_review": "Overall, the paper proposed a sound and intuitive approach for a model’s systemic generalization which is a timely contribution given how important generalization is for deep learning models. One area for improvement is more comparison against more recent baselines and prior work from the ‘data augmentation’ and ‘symbolic scaffolding’ categories. Though I am not an expert in this field, the contributions seem substantial enough for me to lean toward an accept.", "strength_and_weaknesses": "Strength:\nThe proposed idea is sound and shows superior performance vs some baselines.\nTheoretical analysis is done to show proposed NSR confers equivariance and recursiveness.\n\nWeaknesses:\nLack of comparison versus more recent baselines such as Ontanón et al. (2022) \n", "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": "1wEp-gEJOeL", "reviewer": "Reviewer_oDdz", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper introduces a ‘neural-symbolic recursive machine’ (NSR) to learn compositional rules from limited data that can be applied to unseen combinations in various domains. SotA is reported to be achieved on SCAN, PCFG, and HINT, which suggests at good domain-generalizability.", "summary_of_the_review": "\n- This is a valuable extension of other work in this area, although it is only somewhat hampered by some vagueness, and potential strawmen of baselines, as opposed to direct comparisons with specific work.", "strength_and_weaknesses": "Strengths\n\n- NSR is evaluated on three benchmarks from different domains, which demonstrates a good degree of generalization, and appears to achieve SotA on all three.\n- The related work of Sec 4 is fairly comprehensive in topic, and clarity.\n- The visualization of Fig 3 is fairly convincing\n\nWeaknesses\n\n- Although this is relatively minor, there are more recent alternatives to Chen & Manning (2014) for dependency parsing, including Mrini et al (2020) and a few based on deep biaffine attention.\n- Also relatively minor, but it would be preferable to explore the space of program induction to a greater degree than in Sec 2.2, as this is a fairly active area of research.\n- The baselines are adequate, but other more recent permutations of some of these exist (and it it probably not necessary to include seq2seq at this point). For example, is it possible to compare NSR against the approach in Ontañón et al (2022; arXiv:2108.04378v2), whom are cited?\n\nMinor\n\n- The forced correspondence to neuroscience always seems a bit naive, and may be removed? E.g., it’s easy to find studies that show that syntax and semantics are linked anatomically in a way that may counter Miller et al (2001), and connectionism vs symbolism is somewhat of a forced dichotomy.\n- Please do another round of editing, as some grammatical errors exist throughout (e.g., “… and are thus difficult to transfer such capability …”)\n- There should be a citation on the “have been shown” claim in Sec 2.3\n- Additional detail should be added to the lemmas of Sec 2.4. E.g., the broad claim of the existence of a neural network in Lemma 1 is not in doubt but either a citation should be added to ‘provably’ or the abstracted proof should be added, as there is already a precedent for repeating previously established facts or approaches, from Sec 2.3\n- It seems that ‘Theorem 3’ is meant to be ‘Lemma 3’ but, regardless, further explanation is advised.\n", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject