Data-Efficient Learning with Neural Programs

Summary

This paper looks at optimizing "neural programs", which are composites of a deep neural network (DNN) followed by a program written in a traditional programming language or an API call to a large language model (LLM). This paper proposes ISED (Infer-Sample-Estimate-Descend) for learning neural programs that only rely on input-output samples of black-box components. ISED is evaluated on benchmarks involving calls to GPT-4 and prior work from neurosymbolic learning literature, showing comparable performance to state-of-the-art neurosymbolic frameworks and achieving more data- and sample-efficient results.

Strengths

* From comprehensive evaluations, ISED significantly outperforms prior work regarding accuracy and data efficiency. * The proposed ISED approach is novel by estimating gradients of black-box programs from inductive samples.

Weaknesses

* Clarity: While Section 1 and 2 is nicely written and can be understood by readers new to this field, it is challenging to read Section 3 due to over-formalism and the lack of end-to-end running examples. * Clarity: The symbolism is a bit inconsistent. $x$ and $y$ in Section 2 presents the input to $M_\theta$ and output from $P$, while in Section 3.1 $x$ and $y$ denotes the "input-output samples" of $P$. Other minor editorial suggestions: * L3 and L20: double quotation can be done via `` and '' in LaTeX.

Questions

* What are the choice reasons for the types of defined structural mapping? * What does "interpretation" mean here in L145? How is that related? * Besides scalability, what other future directions do the authors see as promising for the development and improvement of neural programs?

Rating

6

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

As is acknowledged by the authors, ISED struggles with scaling to high-dimensional input spaces, limiting its applicability in complex scenarios.

Summary

This paper proposes an algorithm ISED for learning a composition between a neural model (e.g., using DNN to classify objects in an image) and traditional programming (e.g., calling GPT-4 to identify room type). ISED is based on reinforcement learning, which summarizes the input-output samples of the traditional black-box program as if-then logic programming. Evaluation of several benchmark tasks, such as leaf classification and scene recognition, shows the effectiveness and generalizability of the ISED.

Strengths

+ Proposing a data-efficient learning framework ISED. + Evaluating the effectiveness of ISED on three types of benchmark tasks. + Analyzing the efficiency of data sampling and used data for ISED.

Weaknesses

- The motivation could be made stronger. - The advantages of ISED over individual programming are not investigated. - Lack of investigation on the impact of the capability of traditional programming on the ISED’s performance. More specifically: . (Introduction) The motivation of this work is not very strong. If the two models work well, why composite them with a neural program? For the scene recognition example, DNN plus GPT-4 can identify objects in the image and classify the scene. What is the goal of the composed program? . (Method) ISED considers traditional programming as a black-box program. It is assumed that ISED can learn from any program. In the evaluation, GPT-4 is a powerful LLM that can generate good outputs. Thus, for a powerful black-box program, ISED works better. It is suggested to analyze how the capability of a black-box program affects the performance of neural symbolic learning. . (Evaluation) This study presents two new neural program learning benchmarks which both contain a program component that can make a call to GPT-4. A neural model can only learn limited capability of LLM. The composite program may not replace individual programming? .(RQ1: Accuracy) The results indicate that ISED can achieve higher performance than other neurosymbolic methods. It is suggested to analyze the differences between the composite program and the individual programming. . (RQs) The three investigated RQs only focused on the performance and efficiency of ISED. Generally, the composite neural program aims to build a more explainable logic programming. The explainability is not verified. . The acronyms need to be defined in the first place, such as ISED and LLM.

Questions

- What is the motivation of the composition? - What are the advantages of ISED over individual programming ? - What is the impact of the capability of traditional programming on the ISED’s performance?

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors adequately addressed the limitations of this work.

Summary

The paper introduces a sample-efficient algorithm called ISED (Iterative Sampling for Efficient Differentiable Programming) for learning neural programs i.e. programs that have a neural network component (that needs to be learned) and another fixed program. The fixed program could be a python program, a call to a black box LLM model, or a logic program. The task here is to train this neural program using only end-to-end input-output data. The challenge lies in propagating gradients through the fixed program, which could be complex, non-differentiable, and black-box. The paper proposes an alternative to REINFORCE-based methods by trying to approximate the fixed program as if input = u then output = v by sampling multiple u with the NN's predicted distribution and using neurosymbolic methods to compute gradients through this approximate program.

Strengths

- Combining neural networks with pre-trained LLMs is an interesting idea and very useful in many applications. - The paper addresses the challenging problem of propagating gradients through black-box LLMs with an interesting approach. - The proposed method offers an alternative to REINFORCE-based methods which require significantly more samples due to weak supervision. - The evaluation is comprehensive. The authors considered many variants of benchmarks and baselines. The results are promising, showing better performance and sample efficiency than REINFORCE-based methods and faster training than the A-NeSI baseline.

Weaknesses

One of the main limitations, as mentioned by the authors, is that the approach doesn't work effectively on high-dimensional intermediate inputs. The authors should definitely explore this limitation further. Also one minor comment: The paper should present results for all benchmarks in Table 3. It is misleading to show mostly positive benchmarks in the main paper and relegate the negative ones to the appendix.

Questions

Why do tests time out during test time? While it is understandable for Sudoku, why does sum_4 also time out for DPL?

Rating

7

Confidence

4

Soundness

4

Presentation

3

Contribution

3

Limitations

Limitations are addressed.

Summary

This paper is about learning the parameters for a neural network (or other differentiable structure) where its output is then provided to a different black-box procedure, and we can compute a loss for the (second) output from that procedure. The procedure consists of four parts: infer, sample (+ execute), and estimate, and descend. Given the input, we "infer" using the neural network, which produces a distribution over the inputs to the black-box program. We "sample" from this distribution multiple times to construct possible inputs to the black-box program, and we run the program on these inputs. We "estimate" by combining the outputs from the program to construct a distribution over the black-box program's output space, only using differentiable operations over the neural network's outputs. We "descend" by computing the loss using that distribution against the ground-truth label and computing the derivative with respect to the neural network's parameters. The authors consider several benchmark tasks: classifying leaf images to the correct plant species, scene recognition from images, arithmetic and sudoku solving using images of handwritten digits. The authors compare against two neuro-symbolic methods, A-NeSI which emulates the black-box program with a differentiable neural network, and three other methods for computing gradients through black-box programs. The authors show that their proposed method generally outperforms the comparison methods and demonstrates better data efficiency.

Strengths

### Originality In my view, the paper explores an interesting point in the design space that is an interesting variant some of the existing baselines, e.g. it is akin to a sampled version of DeepProbLog. Much of the value of the paper is in showing that this variant works well empirically on a variety of tasks. ### Quality The paper performs a thorough evaluation on a variety of different tasks involving different image recognition problems and compares against many baselines, which convincingly demonstrates the empirical gains of this approach. ### Clarity The paper is generally well-written and easy to understand. Some aspects of the algorithm description could have been clearer, but I found the worked example in Appendix A very useful for both understanding the proposed algorithm and also how it compares to the baselines studied.

Weaknesses

- The studied tasks all have a relatively small space of potential discrete outputs from the black-box program. The method seems to lack support for the case where outputs of the program can be real-valued. - If the combination of the initial neural network and black-box program produce the correct answer for an input with very low likelihood, or if the sampling is unlucky and fails to produce a black-box program input which gives the correct answer, it would seem that there is no learning signal at all. The method as stated is not adaptive to such cases, for example by sampling from the neural network more often until some suitable input is found. - The study of the proposed method is entirely empirical and there are no theoretical justifications provided for why it works (also as stated by the authors in item 3 of the paper checklist).

Questions

- What is the specific sampling strategy used in Algorithm 1? Are there restrictions on what this sampling strategy is allowed to be? - For computing the results in the paper, how did you sample from the neural network at test time?

Rating

7

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

The author's description of the limitations seems adequate.