Neural-Symbolic Recursive Machine for Systematic Generalization

We sincerely thank you for the constructive comments and the acknowledgment of the significance of our work. Below, we provide detailed replies to your comments and questions.

I would suggest the authors provide at least 1 other neuro-symbolic method to compare against to make the results more significant. The work from Minervini et. al. on Greedy Theorem Provers, or other variants could potentially be used as a baseline for some of these tasks.

Thank you for the suggestion! We appreciate your concern and will check Minervini et. al.'s work on Greedy Theorem Provers and other neural-symbolic methods to add more neural-symbolic baselines.

The ambiguous explanation of how the search for a GSS tree is terminated.

The search for a GSS tree stops when one of the following conditions is satisfied:

1. the found GSS can generate the given ground truth y, i.e., the root node's value is equal to y;
2. the search steps exceed the pre-defined maximum searching steps.

It would be beneficial to explain why the three modules of NSR exhibit equivariance and recursiveness.

Equations 1, 2, and 3 demonstrate that in all three modules of the NSR system, the joint distribution is factorized into a product of several independent terms. This factorization process makes the modules naturally adhere to the principles of equivariance and recursiveness, as outlined in Definitions 3.1 and 3.2.

Suggestions: In Table 3, for the task of compositional translation, it would be interesting to also evaluate the performance of a vanilla transformer like in the previous tables. Discuss previous neuro-symbolic works such as Neural Theorem Provers (NTPs) and Greedy NTPs.

Thank you for the suggestions! We will incorporate them in the revision.

What is the vocabulary size of the primitives considered? Did you try more complex sets of logical primitives? What do you think the effect would be on time and performance?

The total number of primitives is 15. Whether adding more primitives is beneficial or detrimental depends on their relevance to the task at hand. Including primitives that aren't relevant can lead to longer search time, or could even cause the search to fail if it exceeds the maximum number of search steps allowed. On the other hand, if the new primitives are relevant and useful, they can shorten the length of the program and accelerate the search process.

Do you have any hints of how to start thinking about representing probabilistic semantics like mentioned in the Limitation section?

Probabilistic programming languages (PPL) or frameworks might be useful for representing probabilistic semantics. PPLs are designed to handle uncertainty in a structured and systematic manner. They integrate probabilistic models with traditional programming concepts, enabling users to represent and manipulate uncertainty explicitly in their models.

How general is this approach: it would be good to have an extended discussion on what the symbols and programs look like for more natural data distributions, like GeoQuery.

To discuss how our approach can generalize to natural language semantic parsing tasks, we construct the following example of how our model might work for GeoQuery.

Question: How many rivers are in California?

SQL query: SELECT count(*) FROM rivers WHERE state = 'California'

Here's how our framework might model this example:

1. The Perception module simplifies the question by removing unnecessary grammatical details:

how-many rivers be in California

2. The Parsing module breaks down the simplified sentence into a parse tree.
3. The Semantic module then generates the query step-by-step in a bottom-up manner. Here's the parse tree with intermediate results:

(be => [SELECT count(*) FROM rivers WHERE state = 'California']
    (rivers => [SELECT count(*) FROM rivers]
        how-many => [SELECT count(*)]
    )
    (in => [state = 'California']
        California => ['California']
    )
)

As discussed in Limitations of Section 5, training the entire framework from scratch on natural language datasets can be challenging. However, we have observed that the parse tree is quite similar to standard dependency structures. As a result, we can leverage existing parsers to initialize the modules in our framework, which could accelerate the training process.

We hope the above clarifications address your concerns and thank you again for your valuable suggestions. Please let us know if there is any further question.

We sincerely thank you for reviewing our paper and providing constructive feedback. Below, we provide detailed replies to your comments and hope these replies can resolve your major concerns.

Presentation is unclear: few details about the actual approach in Section-3 (and Figure-1), highly suggest moving simple definitions and statements to the Appendix and spending more space on explaining the approach.

Thank you for your feedback! We appreciate your suggestions and will incorporate them into the revision. Below, we provide detailed clarifications to your questions regarding our proposed approach.

• What exactly are the symbols in T for each of the datasets?

Figure-1 shows the examples of T = <(x,s,v), e> for each dataset.

For SCAN, x is the input word, e.g., left; s is the symbol id, e.g., 5; v is the output actions, e.g., [LTURN,JUMP]. (x,s,v) forms a node, e.g., left 5 [LTURN,JUMP] in the first example of Figure-1. The edge e is the arrow, e.g., left 5 [LTURN,JUMP] -> jump 4 [JUMP], which means the value of the node jump 4 [JUMP], i.e., [JUMP], is an input to the node left 5 [LTURN,JUMP].

For PCFG, x is the input word, e.g., swap; s is the symbol id, e.g., 51; v is the output letters, e.g., [C,B,A]. (x,s,v) forms a node swap 51 [C,B,A] in the second example of Figure-1. The edge e is the arrow, e.g., swap 51 [C,B,A] -> A 0 [A], which means the value of the node A 0 [A], i.e., [A], is an input to the node swap 51 [C,B,A].

For HINT, x is the input image, e.g., the image of *; s is the symbol id, e.g., 12; v is the output number, e.g., 27. (x,s,v) forms a node * 12 27 in the third example of Figure 1. The edge e is the arrow, e.g., * 12 27 -> 3 3 3, which means the value of the node 3 3 3, i.e., 3, is an input to the node * 12 27.

• Is every raw input mapped to a single symbol or is there a consolidation step where multiple raw inputs can be associated with the same symbol?

Currently, every raw input is mapped to a single symbol.

• What models are used to parameterize all of the distributions in Eq~4? Are these neural networks?

\theta_p and \theta_s are parameterized by neural networks. \theta_l are functional programs, as illustrated by Figure 4(b).

• What is the overall parameter count?

For SCAN and PCFG, the parameter count is ~0.2M, mainly from the dependency parser. For HINT, the parameter count is ~11M, mainly from the image encoder ResNet-18.

• How does inference work for this model?

As illustrated in Figure 2, the neural perception module first maps the input x, e.g., a handwritten expression in Figure 1 (3) HINT, to a symbol sequence, 2 + 3 * 9. The dependency parsing module then parses the symbol sequence into a tree in the form of dependencies, e.g., + -> 2 *, * -> 3 9. Finally, the program induction module uses the learned programs for each symbol to calculate the values of the nodes in the tree in a bottom-up manner, e.g., 3 x 9 => 27, 2 + 27 => 29.

• How does this compare to other neuro-symbolic systems, for example, "Neuro-Symbolic Concept Learner" from Mao et al. 2019?

Mao et al. 2019's NS-CL model relies on a pre-established domain-specific language (DSL) tailored for CLEVR, which limits its flexibility, as the meanings of operations like Filter, Relate, and Query are predefined and unchangeable. Moreover, NS-CL uses GRU for question parsing, a model that prior research [1,2] has identified as less effective in generalizing to longer sequences. In contrast, our model operates with minimal domain-specific knowledge, learns the semantics of symbols directly from data, and demonstrates significantly improved generalization capabilities.

[1] Lake, et al. Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks. ICML (2018).

[2] Li, et al. A minimalist dataset for systematic generalization of perception, syntax, and semantics. ICLR (2023).

We are grateful for your review of our paper and your constructive feedback. Your questions are answered in detail below:

More explanation or analysis on why the symbolic components actually lead to better generalization.

We think the effectiveness of symbolic components in fostering systematic generalization in neural networks, such as the symbolic stack machine in NeSS and the Grounded Symbolic System (GSS) in NSR, stems from their ability to introduce structured, rule-based processing into otherwise fluid neural computations. These symbolic systems act as a framework within which neural networks can operate more predictably and consistently, thereby enhancing their generalization capabilities. Besides, symbolic components can mitigate overfitting by imposing rule-based constraints on the learning process. These constraints ensure that the model does not merely memorize the training data but learns the underlying rules and structures, thereby improving its ability to generalize to new, unseen data.

In equation (3), what is the p in the right-hand side?

p denotes the probability.

When you say that you "leverage" DreamCoder, do you mean that this module simply is DreamCoder?

The original DreamCoder does not support noisy examples, so we modified its search process to tolerate a ratio of noisy examples.

We kindly refer the reviewer to Appendix Section A for more details on the program induction module.

Figure 3: image is wrong?

Yes, thank you for pointing it out! We will correct it in the revision.

Section 3.3: How do you use the gradients? Is this SGD?

Yes, we use the Adam optimizer in practice.

Why is abduction called that?

Naturally, this is a process of abductive reasoning. Consider the input x and output y as observations. The goal is to identify the T that most likely explains these observed values of x and y. This suggests that the discovered T may not necessarily match the actual ground-truth value of T.

Def 3.2: Isn't "compositionality" a more usual word for this?

Thank you for pointing it out! The word "compositionality" is indeed a more appropriate choice for Def 3.2 and we will update it in the revision.

We sincerely thank you for reviewing our paper and acknowledging the novelty and effectiveness of the proposed method. Below, we provide a detailed response to your question.

Could it achieve better generalization performance than conventional seq2seq models on real machine translation tasks?

Our proposed model achieves much better performance on a compositional machine translation task, as described in Section 4.4. Table 3 shows the comparison: our model can achieve perfect generalization accuracy (100%), while the conventional seq2seq model performs badly (12%).