Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper attempts to ask whether language models have a bias that allows them to learn from fewer examples in cases where a rule is simpler. They compare exploitation of rule simplicity in a variety of models, including human participants. This prior towards simplicity is most strongly observed in larger models, but the minimal example set is rarely enough to train any system, so with the exploitation of simplicity is not a perfect prior.

The paper also provides an analysis of the capability of these systems to provide explanations of the rule, but only humans and the algorithm that they specifically select for this purpose were capable of providing such explanations.
main_review: My main complaint with this paper is that it describes what's happening as a simplicity prior, or Occam's razor, but a more in-depth analysis of the pattern they observe might reveal that these systems have a prior towards specific types of rules or methods of compression, such as those that exploit hierarchical patterns or memorized chunks. Because there was a lack of analysis of the rule type, focusing only on an abstract idea of simplicity based on a particular method of compression, I found this unconvincing as a study of a general simplicity prior.

I was most impressed by the fact that there was a human study. This allows us to compare the priors of an artificial language model with the ability of a human to learn rules. I would like to see more papers like this, in that respect.

Minor issues / clarity:
- I wasn't satisfied with the attempt to explain what a concept was. Within the paper, this is left very vague. 
- What does it mean to say that an explanation is "minimally acceptable"?
- "A more systematic analysis is needed to determine the optimal prompts that make the model capture a range of different patterns." This sentence seems to indicate that this will be the focus of the paper, but it isn't my understanding of the purpose of the paper. 
- "most representative AI systems" - This is a really unclear claim
-  I found the example about "go stop go" pretty confusing. I wonder if you could come up with a better example that doesn't involve iffy phrases like "go stop go stop" or even obscure English idioms like "ready steady go".
- I was confused as to the purpose of the paragraph on liens 114-123. It didn't seem to particularly relate to the rest of the paper.
- "GPT-3D-T0 is one of the most similar systems to humans" -  What does this mean?

 Grammar:
- line 163 "being w"
limitations_and_societal_impact: Because this paper has such a broad prior it is investigating, the results may be misleading if the true priors are more constrained than "simplicity". Otherwise, this seems to have a limited impact outside of understanding of the inductive bias of neural networks.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors compare the few-shot learning abilities of humans and GPT* language models (and inductive programming systems) from a machine teaching point of view. Models (and humans) are given a minimal witness set (examples using as few bits of information as possible) that should be sufficient to uniquely determine a program (function from a sequence of bits to another) under a pretty strict simplicity prior. The authors also examine whether additional examples (on top of the minimal witness set) help performance. They consider 8 different P3 programs of increasing complexity based on the number of operators. Examples are presented as English prompts.

The minimal witness set is often not sufficient for humans and LMs to generalize correctly. Nevertheless, there is some evidence that GPT models favor simplicity to some degree. Overall, larger GPT models generally perform better than smaller ones, but the correlation is not perfect. GPT-3 models often generalize better than the human candidates based on the few provided examples. However, humans sometimes provide acceptable explanations (for the shorter programs), but the authors could not get GPT models to explain their reasoning.

main_review: The paper mostly explores LM few-shot learning [1] under the machine teaching setup in [2].

Experiments appear to be designed carefully. Multiple models are compared, both in terms of program complexity and number of examples given. The number of programs is low (only 8), which the authors justify as balancing between obtaining robust results and limiting the human effort needed. I would suggest keeping the current setup for the human comparisons, but greatly expanding the number of programs for the automated systems (much more than in the supplementary material).

Most of the paper is pretty clear, although I had trouble understanding section 3. In addition to the mathematical definitions, I would appreciate if the authors could explain more thoroughly in plain text.

The findings appear reasonably significant for researchers involved in language modelling and machine teaching. As language models are commonly used, understanding their behavior, limitations and how they compare to humans seems important.

Other remarks and questions for the authors:

L83: Is it really a failure?

Figure 1 is arguably overcrowded. It includes changes to both temperature and model size. For additional clarity, I think these should be presented separately.

In Figure 1b, what is the data condition (WS, WS +AS I, WS + AS I + AS II)?

You group 2 programs under each complexity category. Do you think that the paper would be more informative if the results of each program were presented on their own, or would it make the paper harder to read?

Does the order of examples matter?

The matrices in Figure 4 are symmetric (along the bottom-left to top-right diagonal), so most information is duplicated.

Why is the size of the additional examples not expressed in bits, as for the minimal witness sets?

Even with additional examples over the minimum witness set, performance of all systems and humans is still far from perfect. I would be interested in knowing how many examples (or bits) are needed to reach certain performance thresholds (if they are at all reachable).

If I understood correctly, the minimal witness set should allow to uniquely identify a program, under the assumption that shorter programs are preferred. On line 160, you mention "In case of equal l, ties are broken lexicographically." Does that mean that if a witness set is compatible with 2 programs of the same length, one program would be chosen arbitrarily? If that is the case, I would argue that the witness set is inappropriate to explain the chosen concept/program. Does this phenomenon occur in practice?

[1] Brown et al. (2020). Language models are few-shot learners. NeurIPS.
[2] Telle et al. (2019). The teaching size: computable teachers and learners for universal languages. Machine Learning.
limitations_and_societal_impact: Mostly yes. Limitations and societal impacts are discussed, albeit briefly, in the introduction and at the end of the paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes to empirically investigate to what extent large language models like GPT-3 learn (or "distill") a simplicity prior, i.e., a prior that favors concepts with shorter description length. The authors investigate this by randomly choosing 8 concepts/programs in the P3 language whose total number of P3 instructions number from 1 to 8, respectively. Using the framework of Telle et al. (2019), the authors are able to determine the "witness set," the minimal number of examples necessary for a learner with the correct simplicity prior to distinguish the intended concept from others. This witness set is fed to a learner, which is then evaluated on 5 randomly selected test examples of the concept. The authors also consider feeding additional sets of 2 and then 3 examples to the learner, each with its own random test set. The authors evaluate the accuracy of GPT learners, human learners, and 2 inductive program learners on these 3 test sets. They also elicit explanations from the learners.
main_review: This is a very interesting paper, which has undertaken the difficult work of comparing GPT with both human learners and inductive programming learners in a systematic way. Furthermore, the paper contains some interesting findings, namely, that the advantage of larger GPT models is most pronounced when it comes to smaller, simple concepts, and that GPT models largely outperform humans on the tasks considered.

In terms of presentation, I found the paper difficult to understand at points. Even after reading section 3 it was unclear to me how witness sets could be so small and what exactly the authors meant by priors being aligned between learner and teacher, and I was only able to understand what the authors intended by reading the Telle et al. paper. In particular, I think what I was missing was that witness sets only need to distinguish the shortest satisfying program from earlier, shorter ones. Since much of section 3 is not used subsequently anyway, I would suggest that the authors instead use the space to emphasize this and how this leads to the experimental setup. I would also recommend the authors put their GPT prompts and the way they attempted to elicit explanations from GPT in the main text, since it's very hard to interpret any of the results otherwise.

Methodologically, I'm a little concerned that the experiments don't fully address what the authors are after. In particular, it seems like what we'd really like to know is what concepts the learner has learned, but instead we measure accuracy. This seems potentially problematic in situations where programs/concepts can have very similar outputs but differ drastically in their complexity, which is presumably the case here. (For instance, do we have any way of telling from the experiments that GPT hasn't learned the exact desired program except on a list of 10,000 exception inputs where it behaves differently?) Furthermore, even if we were satisfied with just accuracy, why not get the accuracy on a much larger sample size than 15 per concept (at least for the non-human learners)? I think if we were able to get reliable explanations from the models we could resolve these questions to some extent, but as the authors note this is difficult to do. 

I also wonder whether the machine teaching dimension of the paper changes the story/experiments much. For instance, if instead of feeding the learners the optimal witness sets the learners just received random examples, would the plots change? (This experiment might be worth doing!) If not, these experiments may tell us more about the priors/biases of these learners in general rather than about how these learners perform when being taught, with ramifications for questions Q1 and Q2 in section 4.

Update after new experimental results: thanks for the new results; very interesting (especially for the VL experiments)! I increased my score.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the type of patterns learned by large pre-trained language models (LMs) in a few-show setting. The authors differentiate between external patterns (e.g., common-sense or world-knowledge), and internal patterns, such as ABAB, and focus on the latter. They frame this as a teaching problem with strong priors, and study the size of the example set (number of shots in the few-shot setting) compared to the length of explanation that can be provided to the model in order to teach it the given pattern. The authors focus on the simplicity prior, and study whether it is implicitly encoded in such large models.
Experiment that compare LMs, program induction systems and humans are performed. The main findings are that LMs perform as well as humans in few-shot settings, but the two populations differ in their ability to generate explanations.

I would say upfront that I am not an expert in this topic, and have found many points in the paper unclear, perhaps due to this. However, I wasn't fully convinced by the setup used by the authors. I am looking forward to the author response that might clarify some of these points.

main_review: 
The main concern I have with this paper is that I am not sure how the concept of witness set as used in this paper is learnable by a machine or a human. Looking at the examples in Table 1, there are numerous ways of generalizing the first WS, some of them of similar simplicity (e.g., copy the first character, copy the last character, copy the entire sequence, etc.). Moreover, it is impossible to learn C4 from the single WS example. In fact, none of the examples contain the first rule (if input is '', print '00'), so how can any system be expected to learn this?
This makes me unsure of the interpretation of the results in this paper.


Other questions and comments:

1. Can you provide a formal definition of a concept? The authors discuss it rather informally in the intro and related work (e.g., the concept of an odd number), but then treat it as a function in #150 and onwards.
2. Q1 asks "Is a language model such as GPT able to capture algorithmic patterns from very few examples selected with a simplicity prior?", but then Q2 asks "Does accuracy increase from the theoretically minimal witness sets needed for teaching the concept with additional examples?" From the definition of "capturing a concept" in #154 we have "iff for every S we have that p 􏰑 S iff c 􏰑 S.". In what sense does accuracy improve once you've captured a concept?
3. #193: in which sense can a language relate to "the way language models work internally (transformers)"?
4. Please add random/majority baselines to the figures.


Minor:
#41 story -> history?

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper empirically compares humans, language models, and inductive programming systems through the framework of machine teaching. Concepts and example sets are selected using a simplicity prior with reference to the P3 language. The main experiments present the example sets to the humans or machines and ask them to infer the corresponding concept. This setup leads to several experimental questions regarding the alignment between humans and the computational approaches and the extent to which language models like GPT have distilled a simplicity prior.
main_review: Note: I am not an NLP researcher so I cannot comment on this work’s significance to that community.


Positive comments:
* The basic premise of this paper, to study the intersection of machine teaching and language models, is very interesting, and as far as I know, novel, and I expect there will be follow up work that continues this line of inquiry. I would therefore give this paper high marks in terms of originality and significance.
* The paper is extremely well written at both a sentence level and a high level. I found the whole paper very enjoyable to read and would give high marks in terms of clarity.
* The experiments are clear and thorough and the supplemental results are extensive.
* The overall contribution of the paper is large, clearly requiring an extensive effort, making it well suited for NeurIPS in terms of scope.
* I commend the authors for reporting the experimental question Q6 even though they were not able to answer it affirmatively. (As an aside, the teacher-student conversation in supplementary materials 8, while a “failure”, is remarkably coherent.)


Concerns and questions:
* My biggest concern is that nearly all of the results in the paper are based on the same 8 concepts. It is very possible that some of the empirical findings are specific to quirks in these 8 concepts. It makes sense that the human experiments needed a limited set, but it would greatly strengthen the paper if additional machine-only results were added with results averaged over hundreds or thousands of concepts.
* I am also concerned about the relative mismatch between the average accuracies of humans (e.g. Figure 2b) versus their ability to provide correct explanations (Figure 3a). Should we conclude that humans are sometimes guessing correctly? Or that there are some quirks in the concepts, where the examples are suggestive of some other concept that is wrong, but happens to align with the test examples? Also, the relatively low rate of explanation correctness across the board suggests that this task may just be too difficult for humans (it is certainly difficult for me, looking at the examples).
* For the “accuracy” results, if I were to guess 2 out of 5 tests correctly for a single concept, would that contribute 0.4 or 0.0 to the accuracy? Please clarify in the text.
* There are a lot of interesting results and points raised in this paper, which is mostly a strength, but there are parts where the narrative feels unfocused and the main takeaways feel unclear.
* I am wondering if the inclusion of the inductive programming methods (Louise and MH) are more distracting than informative, at least in the way that they are presented now, as first-class citizens alongside the GPT and human results. My understanding is that the behavior of these methods is much less mysterious than that of GPT or humans -- if the background knowledge given to the inductive programming methods were perfectly aligned with P3, then we would see perfect agreement in the results. So really the results for these methods are just a function of the background knowledge. I’m not sure what we are meant to take away from these results in particular.
* The link in footnote 1 (https://bit.ly/Code3357) cannot be accessed (permission error)
* For both humans and GPT, I would be curious to see if the results are robust to changes in the syntax. For example, instead of 0 and 1, what about a and b, or apple and banana, # and %, etc.
* When presenting the non-human approaches with WS, then WS + AS I, then WS + AS I + AS II, are the methods “reset” after each phase? For example, with GPT-3, does it see the full history of phases, or is just given each phase independently? I am guessing the latter. If so, is it possible that the humans have an inherent advantage over the machines? Intuitively, from the sequence, the humans could infer the relative complexity of the examples in each set, giving some additional hints about the target concept.
limitations_and_societal_impact: See “concerns” above.
review_title: null

Meta-review: This paper seeks to provide more insight into the few-shot learning capabilities of language models by pitting them against humans on a set of algorithmic tasks under the framework of machine teaching. Specifically, the goal of the paper is to identify whether language models learn to prefer simple explanations for algorithmic rules. Reviewers appreciated the thorough experimental design, in particular the inclusion of a high-quality human study. There were some concerns raised about clarity, claims, and fit for NeurIPS, but I think these can be improved for the camera-ready version based on the author's rebuttal.
Decision: Accept (Poster)