Improving Neural Program Induction by Reflecting on Failures

We thank the reviewer for the detailed review and comments. Please see the following for our response!

1. I find Section 2.2 very hard to understand. I have some background in logic programming, but none in neural logic machines. "First, given a set of objects U f size m “ it is not clear what an object is, or what it means for an object to have a size "the NLM model first grounds p on U, which derives a tensor representation of p_U..." -- I'm not sure what it means to ground p in this context.

Object refers to an entity or element within a domain of discourse, which is a fundamental and broadly accepted concept of first-order logic [1]. “a set of objects $U$ of size $m$ ” means there is a set $U$, and $U$ contains m objects: $|U|=m$. Grounding is a frequently used concept in first-order logic which refers to the process of creating a variable-free first-order formula equivalent to a first-order sentence [2][3]. Thus, “ grounds p on $U$” denotes the process of instantiating the variables ($\alpha_1, \dots, \alpha_n$) of atom p($\alpha_1, \dots, \alpha_n$) with the corresponding truth values of the attributes/relations of the object set $U$ (of size $m$) which results in m truth values for the m respective objects. For instance, for the predicate IsFather( $X$, $Y$), and a family of three family members: $U={A, B, C}$. Grounding IsFather on $U$ results in a set of truth values of the ground atoms: IsFather($A$, $B$), IsFather($A$, $C$), IsFather($B$, $C$).

2. Algorithm 1, line 4/5: what is the difference between $f$ and $f_\theta$ ?" $b$ and $d$ denote the number of depth and breadth of the NLM model architecture respectively" -- is this backwards, or does refer to depth and refer to breadth?

$f$ and $f_\theta$ denotes the same neural model, \theta denotes the the model $f$ is parameterized with the parameters set $\theta$. $b$ denotes that model breadth and $d$ denotes the model depth. We will update these in our paper.

3. However, I don't see why this should necessarily lead to a better solution than standard gradient descent: if the set of predicates learned by the NLM is the same as in past iterations, then standard gradient descent should penalize incorrect large-magnitude weights; if the set of predicates is different than in past iterations, then this is penalizing using predicates that may not be incorrect.

Our approach is inspired by the success of provenance information for SAT-based program synthesis, in which previous error information is leveraged to reduce future search space. We empirically demonstrate that the vanilla training loss is not effective enough to capture model's erroneous behavior pattern and thus results in a ungeneralizable solution as well as low training efficiency. We further conduct a post hoc interpretation analysis to demonstrate the effectiveness of FRGR in refraining model from repeating erroneous behavior. We present an error pattern which FRGR manages to mitigate. Concretely, for the IsMGUncle and IsUncle tasks, their ground-truth programs only involve using binary predicates. The ground-truth programs are shown as follows:

IsUncle:

IsMGUncle:

Therefore, it is considered a erroneous behavior if the model strongly attributes its induction based on unary predicates. We calculate the ratio of all output binary predicates whose most attributed input predicate is unary during the training process. We evenly sample 5 epochs from the training process till nlm w/ FRGR converge to a optimal solution. The results are shown in Table 1. It is obvious that with the use of FRGR, the ratio of unary predicates are rapidly decreased compared with the vanilla NLM. The results indicate the FRGR is effectively in recognizing repetitious error pattern during the training process and actively regularizing the model based on it, which results in higher training efficiency and better generalization.

[Table 1: interpretation analysis.]

This process is similar to that of the provenance information used in the SAT-based synthesis, in which the solver's error is actively summarized based on previous derivation trees and is used to reduce future search space.

4. Hyperparameters: as mentioned above, one of the effects of the additional term in the loss function is increasing the effective learning rate. The paper does not provide evidence that the proposed approach outperforms a baseline with a well tuned learning rate. The paper also does not justify (or state) other hyperparameter choices. The paper does not state how hyperparameters are selected. In particular, hyperparameters are (as best I can tell) identical between the training methods, which may be an unfair comparison. I also cannot find the value of the hyperparameter coefficient for the regularization, the value of the history size or how these values were tuned.

The details of the training settings and hyperparameter choices are delivered in Appendix B&C with clear reference on page 6&7 of the paper. We state that all the training settings and hyperparameter choices for the NLM model strictly follow previous work [3] instead of being cherry-picked by ourselves. We have to state that it is inappropriate for the reviewer to state that: “hyperparameters are (as best I can tell) identical between the training methods, which may be an unfair comparison.” as it is an extremely common practice to set hyperparameters (such as learning rate) the same for the evaluated baseline models. Please feel free to refer to the cited literature for details [4][5]. Nevertheless, we conduct the hyperparameter analysis of the learning rate, the results are shown in Table 2: We conduct hyperparameter analysis for the IsGrandparent task from the family tree benchmark and 2-outdegree from the graph reasoning benchmark. Specifically, we experiment with the following learning rates: 0.005 (default of NLM), 0.01, 0.05, 0.1 for both NLM and NLM w/ FRGR. For IsGrandparent, the results are shown in the table below. Concretely, for the original NLM model, it performs the best under the default setting (0.005 learning rate) while for NLM w/ FRGR, it performs even better under the 0.1 learning rate. Specifically, the learning iterations can be decreased by +49.82% (from 55.80 to 28.00).

[Table 2: learning rate analysis.]

For 2-Outdegree, the best results for both the NLM and NLM w/ FRGR are achieved under the default learning rate (0.005), which are the same results shown in Table 1 of our paper. Therefore, with the same budget of hyperparameter tuning, NLM w/ FRGR steadily outperforms the original NLM.

5. Regularization: as mentioned above, another effect of the additional term in the loss function is weight decay. The paper does not provide evidence that the proposed approach outperforms a baseline with weight decay (or other regularization).

The weight decay mechanism is already implemented in the original NLM model, which further demonstrates the effectiveness of FRGR’s effectiveness over this regularization approach. Besides, we further conduct an ablation study by comparing our approach with a random regularization baseline (i.e., randomly penalizing the same percentage of the model’s weights as that of FRGR), denoted as NLM w/ random. The results are shown in Table 3:

[Table 3: regularization comparisons.]

The results illustrate that by adding random regularization, the model's performance decreases compared to that of the original NLM. Specifically, compared to the original NLM model, the grad-ratio decreases by +10.00%, and the performance decreases by -14.42%. While with FRGR, it is effective in improving grad-ratio, performance, generalization, and training efficiency. The results demonstrate that the vanilla training loss, random regularization as well as weight decay regularization are not sufficient enough to capture the repetitious error pattern during training thus incapable of improving the NLM model.

6. How are hyperparameters for the evaluation tuned? What are $\gamma$ and $\tau$ set to?

We haven’t conducted specific hyperparameter tuning for our method. And we directly adopt the hyperparameter settings from the original NLM paper and used them for all evaluated methods. $\gamma$ is set to be 0.99 and $\tau$ is set to be 100 for all tasks.

[1] https://www.cs.rice.edu/~vardi/comp409/lec14.pdf

[2] Migimatsu, Toki, and Jeannette Bohg. "Grounding predicates through actions." 2022 International Conference on Robotics and Automation (ICRA). IEEE, 2022.

[3] Dong, Honghua, et al. "Neural Logic Machines." International Conference on Learning Representations. 2018.

[4] Kim, Donggyun, et al. "Universal Few-shot Learning of Dense Prediction Tasks with Visual Token Matching." The Eleventh International Conference on Learning Representations. 2022. (Outstanding Paper)

[5] Riad, Rachid, et al. "Learning Strides in Convolutional Neural Networks." International Conference on Learning Representations. 2021. (Outstanding Paper)

We would appreciate it if the reviewer can be more involved in the discussion (Nov 10-22) and let us know whether the response has clarified the corresponding questions.

We would appreciate it if the reviewer could let us know whether the response has clarified the corresponding questions as it is approaching the Author/Reviewer Discussion period deadline (Nov 22) and it has already been 5 days since we posted our response (Nov 16).

We thank the reviewer for the detailed review and comments. Please see the following for our response!

1. The paper is written for a specialist audience, with little context or background given about NLP, about what the challenges in it are, about how ML methods can help solve it, or even just about what the tasks look like. In general, a formulation of the problem as a task that can be used to train a neural network on a certain experience and with a certain performance metric is omitted completely and taken for granted. As a result, most readers (as well as this referee) will not be able to get much from this paper.

Our work is unrelated to NLP and the term “NLP” or “natural language processing” never exists throughout our paper. The focus of our work is on relational reasoning and decision-making tasks which is clearly stated many times in our paper as well as supplementary materials. Furthermore, it is a factual error to state that the description of the tasks and evaluation metrics are omitted. The corresponding details are all clearly delivered in section 4.1 and Appendix C with clear reference in the footnote of page 6. We sincerely recommend the reviewer carefully reread the paper and provide a more objective assessment.

2. My main recommendation would be for the authors to provide context on NLP, NLMs, and on how their task can be solved via ML methods to begin with, and how one would train a neural net to do so. Without such context, it's for me impossible to do justice to the content of this paper, but it is also going to be impossible for a mainstream ML reader (such as most of those attending ICLR) to profit from the paper, to begin with.

Our work is unrelated to NLP. The concrete details of the NLM model are delivered in section 2.2 and Appendix D with clear reference in the footnote of page 4. The training details can be found in section 4.1 and Appendix B with clear reference on page 7. Again, We sincerely recommend the reviewer to carefully reread the paper and provide a more objective judgment.

3. On the contribution side, the authors should prove that their regularisation scheme does have any general applicability beyond NLP tasks carried out with NLMs.

Our work is unrelated to NLP. The benchmarks evaluated in our work range from relational reasoning tasks and decision making tasks, which are all broadly used by many domains such as LLMs [1], program induction [2], SAT-based program synthesis [3], etc.

4. The authors' method appears to work as intended, but also to be quite narrow in applicability: it only presumably works on NLMs (since it requires direct control of the weights) and only for the particular task considered by the authors. At first sight, the scope of the contribution appears very limited. [1/2]

It is a disparagement to regard our method as "work as intended" and "presumably works on NLMs and only for the particular task considered by the authors". First, we state that the domain of neural program induction is not narrow and limited and the NLM is an influential sota baseline: It manages to outperform previous enlighting methods such as DILP and MemNN. We also show that it also manages to outperform the sota gpt-4 model on the relation reasoning tasks. The results are shown in Table 1, where n denotes the number of family (graph) members.

[Table 1: LLMs evaluation.]

Specifically, all models are given samples with n=20 for few-shot learning, and tested with n=20 samples for performance and n=30 for generalization evaluation for the Family tasks. And for the graph reasoning tasks, all models are given samples with n=10 for few-shot learning, and tested with n=10 samples for performance and n=20 for generalization evaluation. The results indicate that the NLM outperforms the gpt-4 model as well as the gpt-4 with chain-of-shot mechanism [1] under few-shot learning setting with much smaller model size. It is also demonstrated in previous work that the LLM methods perform poorly on the blocksworld decision making benchmark [2] while NLM manages to excel it.

4.The authors' method appears to work as intended, but also to be quite narrow in applicability: it only presumably works on NLMs (since it requires direct control of the weights) and only for the particular task considered by the authors. At first sight, the scope of the contribution appears very limited. [2/2]

To demonstrate the fact that FRGR is general, we also evaluated our method on more recent DLM model [3]. The results are shown in Table 2 & 3. The results indicate that FRGR is also effective in improving the DLM model under both the data-rich and data-scarce settings.

[Table 2: Results under data-rich scenario with DLM and DLM-FRGR]

[Table 3: Results under data-scarce scenario with DLM and DLM-FRGR]

Second, in terms of the tasks used for evaluation in our work, it is inappropriate to state the "...only for the particular task considered by the authors" as we did not cherry-pick the evaluation tasks. All the benchmarks we used are directly adopted from the NLM and DLM papers. All these tasks are also broadly used for the reasoning ability evaluation of LLMs [2] as well as SAT-based program synthesis [4]. In summary, all the above-mentioned evidence suggests that FRGR is not "intended" and "limited in contribution" by significantly improving over the state-of-the-art neural program induction models (which are sota in terms of relational reasoning ability) on previously adopted and broadly used benchmarks.

[1] Wei, Jason, et al. "Chain-of-thought prompting elicits reasoning in large language models." Advances in Neural Information Processing Systems 35 (2022): 24824-24837.

[2] Valmeekam, Karthik, et al. "Large Language Models Still Can't Plan (A Benchmark for LLMs on Planning and Reasoning about Change)." NeurIPS 2022 Foundation Models for Decision Making Workshop. 2022.

[3] Matthieu Zimmer, et al. "Differentiable Logic Machines". Transactions on Machine Learning Research. (2023).

[4] Raghothaman, Mukund, et al. "Provenance-guided synthesis of datalog programs." Proceedings of the ACM on Programming Languages 4.POPL (2019): 1-27.

We would appreciate it if the reviewer can be more involved in the discussion (Nov 10-22) and let us know whether the response has clarified the corresponding questions.

We would appreciate it if the reviewer could let us know whether the response has clarified the corresponding questions as it is approaching the Author/Reviewer Discussion period deadline (Nov 22) and it has already been 5 days since we posted our response (Nov 16).

Thanks for the response. We have not submitted the revised version of the paper before as we think the reviewer has not carefully read the paper due to the misleading use of "NLP" as well as the previous unfair claims. We have now submitted the revised version of the main paper as well as the supplementary materials which explain NLM model design more plainly in the preliminary and we use a concrete case to explain the rationale of FRGR in the methodology section. Besides, we have revised all the mentioned details by all the reviewers as well. The revised parts are highlighted in blue. We hope the reviewer to inspect our revised version and take it into consideration for the rating.

We thank the reviewer for the detailed review and comments. Please see the following for our response!

1. No ablations or comparisons of design choices, or even motivation given for the design choices.

We conduct an ablation study by comparing our approach with a random regularization baseline (i.e., randomly penalizing same percentage of the model’s weights as that of FRGR), denoted as NLM w/ random. The results are shown in Table 1:

[Table 1: regularization comparisons.]

The results illustrate that by adding random regularization, the model's performance decreases compared to that of the original NLM. Specifically, compared to the original NLM model, the grad-ratio decreases by +10.00%, and the performance decreases by -14.42%. While with FRGR, it is effective in improving grad-ratio, performance, generalization, and training efficiency. The results demonstrate that the vanilla training loss, random regularization as well as weight decay regularization are not sufficient enough to capture the repetitious error pattern during training thus incapable of improving the NLM model.

2. The paper would be stronger with experiments (could be toy) or examples that show how the approach is working, or a discussion comparing the usefulness of provenance information for SAT-based synthesis with how the provenance information is helping the neural models

We present an error pattern that FRGR manages to mitigate. Concretely, for the IsMGUncle and IsUncle tasks, their ground-truth programs only involve using binary predicates. The ground-truth programs are shown as follows:

IsUncle:

IsMGUncle:

Therefore, it is considered an erroneous behavior if the model strongly attributes its induction based on unary predicates. We calculate the ratio of all output binary predicates whose most attributed input predicate is unary during the training process. We evenly sample 5 epochs from the training process till NLM w/ FRGR converges to an optimal solution. The results are shown in Table 2. It is obvious that with the use of FRGR, the ratio of unary predicates is rapidly decreased compared with the vanilla NLM. The results indicate the FRGR is effective in recognizing repetitious error patterns during the training process and actively regularizing the model based on it, which results in higher training efficiency and better generalization.

[Table 2: interpretation analysis.]

This process is similar to that of the provenance information used in the SAT-based synthesis, in which the solver's error is actively summarized based on previous derivation trees and is used to reduce future search space.

3. I think there should be more description in section 3 of why the technique works: I guess the model is a bunch of logical combinations simultaneously during training, and due to the logical nature of the NN activations, it's possible to get information about "incorrect search" happening just how the SAT solver generates erroneous formula.

We agree with the explanation of the reviewer that due to the similarity of the neuro-symbolic models' design and the SAT solving process, we can therefore effectively leverage the error pattern of the model's previous learning process (similar to the provenance information summarized from derivation tree which is used in SAT-based synthesis) to improve models' generalization and training efficiency. We will add the corresponding explanation of our method's effectiveness in the paper.

4. The description of the approach in section 3 is poor. it leaves out numerous details, or mentions them unsystematically. things like "what is an error?", eq 1 is challenging to understand, the error list updating is never described clearly outside of the pseudocode— based on the pseudocode, you store a list of the T most recent errors, and once T is found, you run the pattern mining algorithm. and then you start over with a new list, right? this could be quickly described with a sentence in the text.

An error simply denotes a wrong final conclusion (i.e., classification results for relational reasoning tasks, actions for decision-making tasks). The understanding of the reviewer in terms of the error list update process is mostly correct: we store a list of the T most recent erroneous behavior in the erroneous behavior list, and once T is found, we run the pattern mining algorithm. And we continuously update the list from the beginning of the erroneous behavior list. We will add more explanation of the update process in our paper.

5. What does the Apriori algorithm return? a single thing? based off elsewhere, it returns a set of weights, but this should be described when Apriori is brought up.

Apriori returns the position index of the frequently occurred weights of the error behavior representations stored in the erroneous behavior list, as described with a concrete example after Apriori brought up (last paragraph of section 3.1): “After the mining process, FRGR manages to identify the error pattern representation that stores the position index of the frequently intersected weights of all historical erroneous behavior representations, …”

6. How much of a correspondence is there between the form of the provenance information in this paper and RAGHOTHAMAN et al 2019?

FRGR is motivated by and similar to the provenance information used in SAT-based synthesis, which leverages error from model's previous derivation to reduce future search space. FRGR is the first to propose actively summarizing neural model's error pattern from previous mistakes and using it to boost the model's training efficiency and generalization. The corresponding details are illustrated in the analogy between derivation tree based provenance used in SAT-based synthesis and the neuro-symbolic model architectures shown in the Introduction (section 1).

7. RAGHOTHAMAN et al 2019 provides guidance for both "why" an incorrect conclusion was derived and "why not" i.e. why a correct conclusion was not derived, but this work only provides guidance for "why". what about "why not" mistakes?

In this paper, we focus on the realization of the “why” provenance on the neural program induction model. This idea of further using “why not” for neural program induction is intriguing and would be explored in our future work.

8. To elaborate more, regularization of errors is never done with NN training in any other domain. Does this approach fail when applied to image classification? Both a yes or no answer would be quite illuminating...

Though in this work, we focus our scope on relational reasoning and decision-making tasks, we believe that our method is general and can be well adapted to other domains such as image classification, robotics, etc. We will strive to further apply our methods to other areas if our paper gets accepted.

9. Is there any related work of such types of techniques? (L1 penalty on negative examples, storing errors during training)

To the best of our knowledge, there are no similar techniques and we are the first to conduct pattern mining on neural model’s previous erroneous behavior and use it to improve training efficiency and generalization.

We would appreciate it if the reviewer can be more involved in the discussion (Nov 10-22) and let us know whether the response has clarified the corresponding questions.

We thank the reviewer for the detailed review and comments. Please see the following for our response!

1. I also could not find how # of iterations is defined in either the main paper or the appendix

The concept of iterations is defined in the Evaluation Metrics section of page 7. Training iteration measures the number of training epochs required to train the model till reaching optimal success rate on validation set. We use it to measure training efficiency.

2. the choice of the buffer size $\tau$

The default value of $\tau$ is set to 100. We conduct ablation studies to explore the effect of $\tau$. Specifically, we conduct experiments on the IsUncle task under three different values of $\tau$: 75, 100, 125, the results are shown in Table 1 & 2:

[Table 1: erroneous behavior list size analysis on IsUncle.]

[Table 2: erroneous behavior list size analysis on 6-connectivity.]

The results indicate that under all the evaluated settings of $\tau$, FRGR steadily improves over the original NLM model.

3. Second, the improvement in # of iterations appears not to be statistically significant, as the errors appear quite large.

The reason for the large errors (standard deviation) is that our model manages to converge to the optimal solution for most of the seeds, therefore a single timeout (reaching the maximum 500 epochs) would render the standard deviation of the results large. Whereas the original NLM model often fails to converge to an optimal solution and therefore frequently timeout. For example, Table 3 shows the results of all the evaluated seeds of the 6-Connectivity task (note that 500 training epochs is the timeout threshold):

[Table 3: detailed training epochs of 6-Connectivity.]

4. The improvements in Figure 4 appear quite marginal, again with overlapping error bars.

We state that the improvement is not marginal under the data-scare setting if the reviewer is referring to the curves of performance and generalization. Though the lines of the NLM and NLM w/ frgr could be close when the data volume grows larger (due to the scale of the image), we have to mention that it is critical and also difficult for the models to reach an optimal solution (100%) (i.e., inducing the perfect ground-truth program), and with the incorporation of FRGR, the model manages to achieve optimal performance with much fewer iterations. For instance, NLM w/ FRGR manages to achieve optimal solution with only 800 examples on the IsUncle task, whereas the original NLM never able to achieve that across multiple seeds (only ~98%) with even 1000 examples. The results is consistent with standard deviation = 0 across 10 random seeds. Similarly, for outdegree-2, NLM w/ FRGR achieves optimal performance and generalization with only 200 examples, while the original NLM takes 600 examples.

5. In Tables 1 and 2, what are units for the reported errors? Specifically, the entries are generally of the form x% +/- y, so is y a raw number or a percentage?

y is a raw number. We will add the description regarding this format in our paper.

6. How is $\theta_v$ defined?

$\theta_v$ denotes the the set of instersected weights of the error pattern set and the model’s current behavior representation, which is described in the last paragraph of section 3.2: “In this work, we consider matching by calculating the intersection between the error pattern set $\epsilon$ and the model’s current behavior representation $\omega$, as shown in line 13. This matching factor, denoted by $m$, measures the degree of repetitions (regarding the error pattern presented previously) performed by the model.”, “To calculate the behavioral regularization term, we obtain the intersected weights set m and apply the L1 norm to aggregate the weights …”

7. How did you determine when to stop training (for # of iterations)?

The training stops when the model achieves 100% success rate on the validation set. The maximum number of epochs is set as 500 for all models, which strictly follows the settings of the original NLM paper.

We would appreciate it if the reviewer can be more involved in the discussion (Nov 10-22) and let us know whether the response has clarified the corresponding questions.