Think Big, Teach Small: Do Language Models Distil Occam’s Razor?
Authors: Gonzalo Jaimovitch-Lopez
David Castellano Falcón
Cesar Ferri
Jose Hernandez-Orallo
Venue: NeurIPS 2021 Poster (2021)
Keywords: Humans and AI
Cognitive Systems
Explainability
Language Models
Inductive Programming
Occam's razor
Machine Teaching

Abstract: Large language models have recently shown a remarkable ability for few-shot learning, including patterns of algorithmic nature. However, it is still an open question to determine what kind of patterns these models can capture and how many examples they need in their prompts. We frame this question as a teaching problem with strong priors, and study whether language models can identify simple algorithmic concepts from small witness sets. In particular, we explore how several GPT architectures, program induction systems and humans perform in terms of the complexity of the concept and the number of additional examples, and how much their behaviour differs. This first joint analysis of language models and machine teaching can address key questions for artificial intelligence and machine learning, such as whether some strong priors, and Occam’s razor in particular, can be distilled from data, making learning from a few examples possible.

Think Big, Teach Small: Do Language Models Distil Occam's Razor?
Gonzalo Jaimovitch-Lóperz
David Castellano-Falcón'
Cèsar Ferri!
José Hernández-Orallo--
VRAIN Universitat Politècnica de València
2 Leverhulme Centre for the Future of Intelligence University of Cambridge
(genzale jaipziitcciim dcast @gmail. com, eferri@dsic.uui es, jorallorooooooo sarallo@upv.e.
Abstract
Large language models have recently shown a remarkable ability for few-shot learning, including patterns of algorithmic nature. However, it is still open question to determine what kind patterns these models can capture and how many examples they need in their prompts. We frame this question problem with strong priors, and study whether language models can identify simple algorithmic concepts from small witness sets. In particular, GPT architectures, program induction systems and humans perform terms the complexity of the concept and the number of additional examples, and how much their behaviour differs. This first joint analysis of language models and machine teaching can address key questions for artificial intelligence and machine learning, such as whether some strong priors, and Occam's razor in particular, can be distilled from data, making learning from few examples possible.
teaching
explore how several
Introduction
An effective and reliable interaction between humans and machines depends proper understanding of their priors. The alignment between these priors, in the form of knowledge and other predispositions used bias, is especially critical for communication and learning (Sun et al. (020). For instance, after a human utters the prompt "on off on off on", another human would expect "off" to be a more likely continuation than "on"". In contrast, after the prompt "twinkle twinkle little" would expect "star" to be more likely. The former depends on an abstract pattern intrinsic to the sequence (a simple algorithmic sequence alternating "on" and "off"), while the latter depends some language pattern extrinsic to the sequence (common use in the English language because of popular song).
Language models are kind of AI systems extrapolating sequences of symbols, and are very good at exploiting the extrinsic patterns that are borrowed from humans after training over massive natural language corpora. However, it is only recently, with systems such as BERT (Devlin al. 2018). GPT-2 (Radford et al., (219)) and GPT-3 (Brown et al.) 2220), that we see how these models can also discover some intrinsic patterns provided in the prompts. This kind of inference is called 'few-shot learning', even if there is no further training or fine-tum fine-tuning of the model. Many of these language models are based on transformers and other attention- based architectures (Vaswani et al. 2017). which do not feature recursion or loops, unlike some approaches based on recurrent neural networks. Some particularly well-chosen and optimised prompts have shown remarkable extrapolations (Xu et al. 20200 Izacard and Grave 2020) Hendrycks et al. [2021), illustrating this new kind of abstraction on the go. However, it is unclear how elaborate or algorithmic these abstractions can be. More studies are needed to determine the optimal prompts and example order that make the model capture
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

a range of different patterns (Zhao et al. 2021 Lu et al. 2021 Liu et al. 2021| Webson and Pavlick 2021; Kirstain et al. 2021). Even when the prompt template fixed, it is an open question what the minimal set of examples should be for learning a concept, how this minimality is evaluated and what priors pretrained models incarnate for few-shot learning to work.
Precisely, machine teaching is the area of artificial intelligence that looks for the optimal examples or curriculum that teacher should use to make a learner capture a concept (Zuu 2015). This is of enormous importance today in applications such as digital assistants, where we would like to teach
them new concepts or routines with few examples, in the same way humans teach or communicate with other humans (Cakmak and Thomaz, 2014; Goodman and Frank] 2016) Degen et al. 2020).
is also fundamental for explainable AI. as the dual problem appears: how a machine can teach (explain) concept to a human in an efficient way (Khan et al. 2011 Basu and Christensen 2013
Frrnnndez-Oraloo and Ferri (02T). When dealing with rich representation languages (e.g., regular languages or
languages), closer or similar to human language in expressive power, it has recently been shown that strong simplicity priors can make effective teaching possible with very few examples: the overall size of the example set is usually shorter than the algorithmic expression of the concept itself (Telle et al. 2019). For instance, teaching the concept of what an odd number is becomes shorter by using few examples than by giving the full definition of what an odd number is.
Language models and machine teaching can now meet because of this new few-shot learning ability of language models. We can explore the question of how many examples are needed (or how long they have to be) to teach something to a language model. These examples and their template are seen as teaching prompts: we want the language model to continue the sequence as if it had captured the pattern that has been expressed in the prompt. From the machine teaching perspective, language models are general systems, as they have not been trained for simplicity or for any particular domain, other than a partial sample of human knowledge expressed as natural language.
With their conjunction, we can now ask key questions for AI such as the relevance of simplicity or acquired priors to make learning from few examples possible (Chater and Vitányi, 2003). In this paper, we examine how a machine teaching setting inspired by Occam's ' razor can help us understand how language models 'learn' and choose prompts more efficiently. We use the term 'prior distillation', overloading the notion of knowledge distillation within the field of machine learning, as we analyse whether a simplicity prior acquired as the result of training large language models such as GPT-2 or GPT-3. To complete the picture, we also compare them with some other Al systems (e.g., program induction systems) and humans on the same task, which are known to have this prior.
The key contributions of this paper are:
We analyse language models in the context of machine teaching, using minimal teaching sets for few-shot inference.
We compare the acquired priors of language models with humans and program induction systems (Gulwani et al. 2015), when facing patterns preferred by a simplicity prior.
We find that language models such GPT-3 have similar or better performance than humans. The performance negatively correlates with the complexity of the concept.
Language models and humans differ in their capability for producing explanations. The length of human explanations correlates with the complexity of the concept.
Having a better understanding of language models and its relation to the way other systems, including humans, make inferences fundamental research that can make the use of these systems safer and more effective, through more robust prompts to solve a variety of tasks. However, this better understanding can also be used maliciously to cunningly modify prompts that alter the results of some applications built on top of language models. A query may fail when using dates, numbers or other strings that have intrinsic patterns. For instance, GPT-3 usually continues "Mary's father has daughters, Lucy, Anne, Alice, Jane and" correctly, but fails on "Mary's 's father has 5 daughters, Ba, Baba, Bababa, Babababa and", systematically continued with 'Bababababa'.
The rest of the paper follows with related work in language models, the comparison of machine and human learning, as well as Occam's 's razor and machine teaching. Section Beontains the experimental design, and introduces the systems we consider for comparison. Section 4 presents and analyses the results. Finally, we close the paper with discussion of the implications of this work. The supplementary material includes additional experiments, plots, tables and specific analyses.

---

2 Related Work
It is only recently that deep language models are starting to show some minimal capabilities for few-shot learning. Systems such as GPT-3 solve "tasks which require to perform simple on-the-fly computational reasoning, recognize a novel pattern that is unlikely to have occurred in training, or adapt quickly to an unusual task" (Brown et al., 2020). Examples of these tasks are simple arithmetic operations and the induction of symbolic manipulations such as anagrams or reversed words. Hendrycks et al. (202I) compare the performance of a text model with humans on 57 tasks including elementary mathematics, US history, law, and more. (Sinha et al. (2019) show that language models obtain poor robustness and generalisation capabilities when compared to graph neural networks that work with symbolic inputs. The experiments also show that humans (with limited time) performed well in simple problems but the performance decreases with complex examples. There are also important limitations of language models on simple generalisation tasks (Bender and Koller 2020 Marcus and Davis 2020). On the one hand, recurrent neural networks, such as long-short-term-meenee memory (LSTM) architectures, have shown the capacity of capturing syntax-sensitive generalisations such as long distance number agreement (Lakretz et al. 2019), or language modelling for the game of chess (Toshniwal et al. [02T]. The abstract reasoning capacity of transformers and other deep learning architectures has been studied by Hupkes et al. (2020). In sum, as language models based on transformers are not recursive, it is an open debate whether they are just memorising a huge corpus, or they really have the capacity of learning abstract concepts from data.
The comparison between humans and AI systems has usually been performed with systems that are trained for task, but not for variety of tasks that are introduced with few words or examples. For instance, Kühl et al. (2020) present an experiment that compares the performance of several machine learning algorithms and 44 human participants recognising patterns in 3x3 matrices. The results in this case show that humans, as expected, tend to achieve better performance than the AI systems when few examples are provided. This work suggests that many Al systems may not be competitive with humans when limited examples are given for range of tasks. Further insight can be obtained when we try to look into the extracted models through explanations, and analyse them in the context of concept complexity. For instance, the relation between complexity of concepts and explanations is discussed by Ai et al. (22TT.
2.1 Occam's 's Razor
Occam's 's razor, the a priori preference for simple hypotheses over more complex ones, has pervaded philosophy of science, inductive inference, and human communication, and it is ubiquitous in statistics and machine learning, explicitly- -through criteria such as the MML/MDL principles (Wallace and Boulton| 1968 Rissanen 1983) and the use of regularisation terms- implicitly
the optimisation algorithms or parameter-function maps in many methods, including deep learning (Valle-Perez et al., [201 Shah et al. 2020). Occam's 's razor backed by strong theoretical and empirical reasons (Solomonofi] 1964] Dingle et al.) 2018).. which oppose the idea that all hypotheses should be equally likely priori, an assumption that would lead to the no free lunch theorems results (Wolpert 1996), making learning impossible. While simplicity is always relative to reference language, the invariance theorem (see, e.g., Li and Vitányi 2008) ensures that the use of different (optimal) languages gives at most a constant difference that only depends on these two languages. While these constants may be very large, some level of agreement in what simplicity is can happen even for very different representations, we explore in this paper.
A prior for simplicity is hard to understand in large language models, kind of architecture that is usually overparametrised, compared to the size of the evidence. While the model is not necessarily the most compressed representation of the data, leads to continuations with low perplexity, which can be used to compress future data, as language models were introduced for communication (Shannon 1949p. It is this interpretation that sheds light on the role of priors, compression and simplicity in human communication and understanding (Chater and Vitányil 2003 Dowe et al. 2011). It precisely in the context of few-shot inference, once the model has been trained, that we can reformulate the question as whether these models make inferences based on preference for simpler hypotheses. We use the term 'distillation', in a somewhat related way to 'knowledge distillation' (Gou) et al. 2021), to represent that the simplicity prior has emerged or have been distilled in the trained model, and used as 'learning' bias in few-shot inference. For further discussion about Occam's 's razor, compression and inference, see Section 15 in the supplementary material.
3

---

2.2
Machine Teaching and Priors
Machine teaching has analysed leaming from minimal set of examples for different concept classes, with the representational power of the class being a major factor to determine when this is possible. Machine teaching has also been used to understand how humans teach machines, comparing a machine teaching setting with a curriculum learning setting (Khan et al., 2011 [asu and Christensen 2013). Many of these studies use feature vector concepts instead of rich representations (Turing- complete) such as natural language. Only recently has machine teaching focused on universal languages, and how relevant simplicity priors become when teaching concepts with very few -or very short- examples (Telle et al. 2019 Hernández-Oralll and Telle. 2020; Garcia-Piqueett and Heraández-Orallo 2021 Hernández-Orall and Ferri] 2021).
More specifically, machine teaching is often understood as an inverse problem to machine learning (Zhu 2015), discovering the best set of examples or curricula for class of concepts and learners. Most of the early research in machine teaching was based on the idea of the teaching dimension, the minimum number of examples the learner needs to identify a concept. However, the teaching dimension approach is too narrow. For instance, in the case of teaching concepts from richer languages, it has been demonstrated that even if the teaching dimension is small (low cardinality), the examples might be enormously large. [Telle et al. (2019) propose machine teaching framework that is based on the size of examples instead of the dimension of the witness set. While the teaching dimension is related to algorithmic learning theory, the teaching size is more appropriate for language models and constructive examples. For instance, considering two witness sets of the same teaching dimension, the input-output example (010101, 1) contains more information than (0, 1).
Examples are defined as pairs (i. of elements (e.g., binary strings) and concepts as functions mapping inputs to outputs. An example set S = {(1,, o1)...., (ix. 0x)} is just a finite set of input- output pairs, used as witness for the teaching process. Considering a representational language L for programs, learner & can be seen as a function mapping sets of examples to programs. A simplicity- -baed learner on L just chooses the shortest L program that is compatible with the witness set. As a result, witness set only needs to distinguish the shortest satisfying program from earlier, shorter ones. Finally, if a teacher wants to teach a concept e it will look for the shortest witness set S (in bit size) such that (S)) returns program in L that is compatible with c. For more formal definition of the teaching size, the reader is referred to section [4 in the supplementary material.
In this work, we build on the increasing relevance of the alignment of priors between learner and teacher (Goodman and Frank 2016; Yang and Shafto 2017 Melo al., (2088) to investigate how long witness sets have to be for different learners (language models, program induction systems and humans), when devising the minimal teaching example set using simplicity (Occam's 's razor) as the learner's ' prior. This is well-founded controlled experiment setting to analyse the alignment of priors (learning bias) between the source of the concepts (what we call the teacher) and the learner.
3 Experimental Setting
The following questions will be explored experimentally (and on average terms):
Q1 Abstraction capability: Is a language model such as GPT able to capture algorithmic patterns from very few examples selected with simplicity prior?
Q2 - Learning curves: Does accuracy increase from the thcoretically minimal witness sets needed for teaching the concept with additional examples?
Q3 Characteristic curves: How do language models, program induction approaches and humans behave in terms of the complexity of the patterns?
Q4- Similarity: How similar are the errors of language models compared humans and program induction approaches?
Q5 Architecture: Apart from being more capable, which has already been shown before, do larger models have a stronger preference for simple concepts than smaller models?
Q6 - Explanations: Can we get explanations from GPT for these algorithmic patterns? Is the accuracy of human explanations related to performance, and their size related to complexity?
We now present the language, the machine teaching algorithm and the learners.

---

3.1 The Machine Teaching Setting
The language L we will use to express programs will be the simple but Turine-complete programming language P3, a variation of p" (Böhm 1964) with only instructions. We employ P3 as concept language because it is very different from the representational languages used by the learners we will use (natural language for humans and functional or logical languages for program induction), and especially different from the internal representation of a language model (transformers). This is also a way to see the invariance theorem in action, as all representational languages are different.
P3 programs operate on an input tape and a write-only output tape, with cells containing one of the three characters in the alphabet: Σ = f'O', '1', '... The pointer is moved using the instructions or operators '<' (left) and '>' (right). The instructions '4' and '-' are used to respectively increase or decrease the value of the pointed cell, in the (eyclic) order they are defined in E. The instructions '[' and 'J' represent the start and the end of a loop respectively, exiting the loop when the pointer is on :. Finally, the instruction "o" is used to output the value of pointed cell.
We follow Telle et al. (2019) to generate 'the teaching book': all P3 concepts and the associated witness sets (assuming simplicity-basee learner). The examples restricted to binary strings, with used as delimiter, padding cells before and after the string. We use a maximum teaching size of 7 (total number of bits in all the inputs and outputs in the witness set). Removing repeated sets and contradictory examples, the example set space is hence comprised of 17,252 example sets.
3.2 Choice of Concepts and Examples
We extract eight different concepts Ci....,, Cg. each e being randomly selected from all programs in the teaching book with i instructions. We bin the concepts into four levels: the programs with 1-2 operators (very low complexity, VL-C), those with 3-4 operators (low complexity. L-C), those with 5-6 operators (high complexity, H-C) and those with 7-8 operators (very high complexity, VH-C).
The minimal witness sets for these concepts are all between 1 and 3 examples. This will be the first batch (the witness set, WS) used as training set. This would lead to perfect identification if the learner were using the same simplicity prior over the same language. But, as the learner's prior might differ from the teacher's, s. we also want to analyse how learning improves as more examples are provided. Therefore, we will examples (additional set one, AS I) and a second batch with 3 extra examples (additional set two, AS II). These two additional sets cannot follow the machine teaching protocol (as they are redundant for perfect alignment). Instead of measuring their size, but to keep it in a similar distribution as the rest, we extract new examples from the example sets for the same program the teaching book. For the test examples, we generate 5 new examples per concept, using random sampling for the inputs i (avoiding repeated strings in WS, AS and AS II) with probability 2- 2-((())+), In total, we have 8 x 3 x 5 = 120 predictions. This number of concepts, batches and test examples aims to find trade-off for a minimally robust evaluation and the limitations of conducting the experiments with humans.
additional examples in two different batches, first batch with 2 extra
Table 1: Experimental setting for the learning of concepts Ci and
Id
P3 Description (not used)
WS
ASI
AS II
Test
Print the first character (CO,0)) of string
(C111001:1),
(C100110;1),
(C000000,0), ('11000,'), (00111100), (11010,1).
(110101:11)
(01010.0))
(111100;1T)
(0010; '0))
C4 0+00
If input print 'QO'; (CO0011)) (C10',T), else input starts with 'O', print '011;, else print '1'
(CO1OLT,0111), (0101,011)), (00100001)), (0000,011).
(000,001))
(001;001))
(000/011))
(1100,1), (T,T))
Table [ shows two concepts, C1 and Ca. their code P3, an intuitive description, and the several sets (WS, AS I, AS II and Test). The Tables I 2 and in the supplementary material contain all used concepts. With all this, the proposed teaching protocol for each 'concept lesson' is divided into three phases: (1) we ask to predict the test examples after only seeing WS, (2) we ask to predict the same 5 test examples after seeing WS AS and (3) we ask to predict the same 5 test examples after seeing WS + AS I + AS III
5

---

3.3 Learners
The following learner families have been considered.
Humans: 30 volunteering (umpaid) human participants with ages between 18 and 54, Apart from the answers to each test example, humans had to write an explanation in natural language for each of the 8 concepts after the third phase. All data collected in the experiments were anonymised, informing the participants of the data treatment and their rights, following data protection laws. The form can be found in the GitHub repository (link at the end of the next section).
MagicHaskeller (MH): A general-purpose inductive functional programming system based on systematic exhaustive search (Katayama (01T). It infers programs expressed Haskell from input- output examples. A strong simplicity prior and library of primitives allow MH to solve many problems using only one example. When MH returns more than one hypothesis, we take the first one.
Louise: An inductive logic programming system based on Top program construction (Patsantzis and Muggleton| 202T). It learns Prolog programs from finite examples, with the capability of learning recursive programs in polynomial time. Two different approaches are considered: Louise-ens, where the most frequent result returned by the totality of the Top program will be used as the final answer, with ties are broken randomly, and Louise-exp, where the expected score is calculated considering all the possible solutions returned by the Top program.
GPT-2: A transformer-based language model trained on a dataset of million web pages (Radford al. 2019). J The model returns the next predicted word or token considering the previous tokens as the given context. We use the 774M- 774M-parameter version of GPT-2. The default hyperparameters of the model are preserved, with the exception of the 'length' of the output returned, which is modified to return 3 tokens. By doing so, the experiment execution performance is improved, without asking GPT-2 for more information than what we require for our analysis. Deterministic results can be obtained by setting the 'top-k' parameter to 1, but we can get better performance if we use several continuations. Accordingly we will use the default 'top-k' value, which With this, two different approaches will be considered by running the model extrapolations n=40 times for the same query: GPT-2-ens, where the most frequent result (out of the n results obtained for the same query) will be used as the final answer, with ties are broken randomly (this approach can be understood majority ensemble setting), and GPT-2-exp. where the n results for the same query are averaged (this approach can be understood the expected value for GPT-2).
GPT-3: Another series from the GPT family (Brown al. 2020). We used different available models, with an increasing number of parameters (Ada, Babbage, Curie and Da Vinci), as recent work (Bender al., 2021) demonstrates that larger models outperform smaller ones. We want to show whether this trend holds for abstract concepts too, with Occam's 's razor emerging more strongly for larger models. We will employ acronyms GPT-3A, GPT-3B, GPT-3C, GPT-3D correspondingly. We performed the experiment considering two different settings: the hyperparameter temperature set to 0 and to 1. When the temperature is set to I, the results are non-deterministic, and the same approach used in GPT-2-ens is applied. We will use TO or T1 as shortcuts depending on the value of this parameter. For instance, GPT-3 Da Vinci with temperature 0 will be denoted by GPT-3D-TO Finally, we also asked GPT-3 to provide an explanation of the concepts, just after each batch (8 x explanations).
We explored very different kinds of prompts for both GPT-2 and GPT-3. A complete account of all the prompts we tried can be found in Table 9 in the supplementary material. Table 2 here shows the prompts that gave the best results, consequently being used in the experiments.
Table 2: Final prompts used in the experiments with GPT-2 and GPT-3.
System
Prompt
Observations
GPT-2
Inputl: O. Outputl: O; Input2:
The numbering aims to logically connect and dis- tinguish the different input-output pairs.
00000, 0utput2:
GPT-3
Input: 0
The separator is the line break with no numbering, following the prompt style guidelines from OpenAl API.
Output: 0
Input: 00000
Output:

---

100-
GPENIATO GPTNIRTI
GPT-3000
Averaage Accuracies (9)
Average Accuraciss (%)
GPT-MTII GPT-IC-T
GPT-ID-TI
GPT-3B-TO GPT-ICTI
50-
30-
GPT-M--O
GPT-IB-TI
GPT-3D-TO
25-
GPT-A T1 T0
TI
GPT-38-T GPT-3C-I
AS
u
VL-
VB-C
(a) Mean GPT-3 accuracy by teaching batch.
(b) Mean GPT-3 accuracy by concept complexity level.
Figure 1: Results for eight GPT-3 configurations. Figure (a) shows the learning curves: average accuracies when aggregated for the eight concepts (1-8 instructions) and split by the three teaching batches. WS refers the first (optimal) teaching set, AS I refers to these plus two additional examples and AS II refers to all these plus the final three additional examples. Figure (b) shows the characteristic curves: the average accuracies when aggregated for the three teaching set batches and split by the four concept complexity levels. VL-C, L-C, H-C and VH-C refer to programs with 1-2, 3-4, 5-6 and 7-8 instructions, respectively. A less crowded version of this figure, ablated by temperature and model size can be found in Figures 1 and 2 in the supplementary material.
4 Results
We first report the results of the main experimental setting that compares humans, language models and other systems, restricted to 8 concepts (lest examples with the empty string as output not included in the means). More extensive results with a larger number of concepts at the end of section.
4.1 Comparison against Humans using Concepts
We take the results of each of the learners in the previous section. For humans, we aggregate the results into a single value per concept, batch and test example, by calculating the average of the 30 human subjects. Performance is represented using learning curves and characteristic curves. A learning curve depicts the variation of accuracy according to the number of examples, which in our case is grouped into the batches WS, AS I and AS II. Characteristic curves depict the variation of accuracy in terms of the complexity level of the concepts: VL-C. L-C. H-C and VH-C. Accuracies always reported as percentage of the test examples that are correctly predicted.
We start with the analysis for the eight GPT-3 parameter configurations. The learning curves in Figure Ia are clearly increasing in general. The first observation is that the systems with the temperature set to obtain better performance than those with the temperature set to 1. There is no clear evidence that larger models in terms of the number of parameters present better performance for this kind of patterns, which are solely based on simplicity and not other priors. Regarding the characteristic curves in Figure 1b the GPT-3 systems show a decreasing trend in performance as the complexity increases. Once again, there is no clear pattern in terms of the number of the parameters. Nevertheless, GPT-3D-TO is the best method, and both GPT-3D versions (the largest models) show their advantage in the very few shot case (WS) and low complexity (VL-C). In other words, more parameters seem to make a difference for easier concepts with fewer examples.
Figure shows the learning curves for humans, MH, the two variations for Louise and a selection of GPT methods. GPT-3D-TO turns out to be the system with the highest average performance for every teaching batch. Louise's variants follow, with a similar performance between them. Humans and GPT-2-ens go next, with similar general performance in the experiment. GPT-2-exp remains slightly under the average performance of the ensemble (majority) approach. Finally, MH is the poorest system, especially for WS, the case with very few examples. For all systems, the accuracy increases as additional examples are provided (AS and AS II).
Figure 26 shows the characteristic curves. We see curves cross more often, but overall the order of the learners terms of performance is similar to the learning curves. The evolution of performance in terms of complexity is generally decreasing, with the best results clearly being for concepts of
7

---

Average Accuracies (96)
Average Accuracies (96)
40-
20-
WS
AS
VLU
LG
BLU
VB6C
(a) Mean accuracy by teaching batch.
(b) Mean accuracy by concept complexity level.
Figure 2: Figure (a) presents the average accuracies for seven learning agents shown for the three teaching set batches. Interpretation as in Figure Figure (b) presents the average accuracies for seven learning agents shown for the four complexity levels. Interpretation in Figure
Explatations (96)
Explenation Lengths
80-
60-
(Avg
25-
0-
VLC
L-
B1CC
VIL.C
VLC
VIL.C
Incomplete
Incomplate
(a) Types of human explanations.
(b) Size of human explanations.
Figure 3: Figure (a) shows breakout of the quality of human explanations after batch AS II. Correct answers are those that explain the whole concept correctly, incomplete answers explain part of the concept correctly and incorrect answers explain any part of the concept incorrectly. Figure (b) shows the average lengths of the different explanations provided by the human participants after batch AS II.
very low complexity (VL-C). Looking into the results more detail (see supplementary material), we find different reasons for the small increase in the last group (VH-C), but it is mostly explained because the chosen test examples have short outputs for these two concepts. This increase for VH-C disappears when experiments are performed with large number of concepts,
discuss below.
Explanations for the given predictions may be a good way of better understanding whether alignment has taken place, beyond accuracy. When looking for explanations, we tried many kinds of prompts for the GPT systems, as discussed the supplementary material. However, we did not manage get good explanations. For Louise, despite being interpretable, the solutions usually had too many clauses to serve as explanations. Only for MH the solution programs are easily interpretable by humans, assuming some knowledge of functional programming. but MH was seldom correct. Because of all this, we will pay more attention the explanations given by humans in the questionnaire.
We consider a correct explanation if, after inspection by us, the whole behaviour of the concept is well explained and is totally correct. We consider incomplete if it is partial account of the concept. We consider it incorrect if any part of it does not correspond to the concept. Note that the explanation might be wrong and the inferences correct, and the other way round. As observed in Figure 3a the percentage of correct natural language explanations decreases as the complexity of the concepts increases. On the other hand, Figure 3b) shows how the average size of the correct explanations increases with the complexity of the concepts (size is measured as the number of characters in the natural language explanation given by humans). Remarkably, the average size of the different types of explanations present the opposite behaviour to performance considering the concept complexity bins in Figure 26 Even for incorrect explanations, the perceived complexity terms of the size of the explanation inversely corresponds to the accuracy results.

---

Louise exp
0:25
0.29
0.34
0.34
0.3
0.06
Louise exp
0.60
0:47
0.35
0.43
0.47
0.96
1
Lonise ens
0.3
0.31
0.29
0.29
0.29
0.06
Lonise cas
0.6
0.39
0.41
0.47
0.45
0.96
MII
0.32
0.37
0.38
0.32
0.29
0.3
1.00
MII
0.34
0.37
0.16
0.43
0.45
0.47
0.75
cxp
0.21
0.36
0.25
0.32
0.37
0.36
GIT 2 cxp
0.62
0.6
0.83
0.43
0.47
0.43
0.50
0.0
CPT-2-cm cms
0.34
0.22
0.25
0.38
0.20
0.34
GPT--2ccms
0.45
0.6
0.83
0.16
0.41
0.35
0.00
1.0
GPT-3D-TO
0.29
0.22
0.36
0.37
0.31
0.29
CPT-3D-TD TO
0.06
0.6
0.6
0.37
0.39
0.47
Tumanss
0.29
0.34
0.21
0.32
0.3
0.25
Homanss
0.06
0.45
0.62
0.54
0.6
0.00
Hanans
GPTT-g GPTT-D--1
Mi
Lattasee
Bunane
GPT 3D--3
GPT
Mf
Latten
Latis-ep
op
GPT
(a) Error disagreement matrix.
(b) Phi coefficient matrix.
Figure 4: (a) Error disagreement matrix for performance and (b) Phi coefficient matrix for the
behaviour of seven learning agents.
In the previous plots, we have compared learners by batches of examples or complexity of the concepts, However, if want to have more fine-grained metric of how much similar the systems are, we can analyse if they succeed on the same examples. This is what we see in Figure 4 showing the error disagreement (proportion of cases where one method is right and the other is wrong, or vice versa) (Figure (a)) and the Phi coefficient (Figure44h taking all the examples individually. The matrix for error disagreement strongly depends on performance, the results for Phi coefficient (Pearson correlation) are more informative. We see that approaches of the same family usually have high correlations. When compared with humans, GPT-3D-TO and Louise-exp are the most similar ones.
Results for Language Models for Larger Concept Samples
The supplementary material includes more details of the comparison between humans, language models and the program induction systems. While comparison against humans is limited by the number of concepts that humans could attempt single form, we do not have these limitations when using language models. In particular, the supplementary material includes concepts with and without loops. We see that GPT-3 is better for concepts without loops, especially when sufficient examples are given in phase three (WS + ASI+ AS II).
Here just report the results for much larger samples. Table includes the results considering 300 concepts (shown also in the supplementary material with other parameter sizes in Tables [5 16 17 T8). What through the three batches, and also a decrease performance as the concepts are more complex.
is much more gradual increase of performance
information given
Table 3: Average GPT-3D-TO accuracy for 300 concepts.
GPT-3D-TO
Batch
VL-C (%)
L-C (%)
H-C (%)
VH-C (%)
Row Mean
WS
37.00
20.05
6.71
10.02
18.44
AS (I)
47.00
38.56
18.76
19.16
30.87
AS (II)
75.00
46.70
29.55
22.35
43.40
Column Mean
53.00
35.10
18.34
17.18
The supplementary material also includes results for the majority and random baselines (discarding
spurious effects) and experiments not using machine teaching. All the code and experimental data can be found at lattp:: thub. com ctwp://o..a...aaaiiitoottt//////
www.aaattoiiaaaiiaaaaaia big- teach sma 11

---

5 Discussion
We can now answer the questions we formulated in Section 3 We see that only for easy concepts (VL--C,, the simplicity prior leads to example sets that humans, Louise and some GPT models can identify consistently (Q1, Q3). For more complex concepts the behaviour is more erratic, and may depend on spurious factors, as the explanations are incorrect for those very hard cases having some accuracy. The learning curves are increasing for all systems, as more examples are given (Q2). The minimal set is rarely sufficient, which means that no system prior is perfectly aligned with the simplicity prior that derives from P3 program size. This is expected as the internal representations of these systems are different. Both humans and GPT have priors to capture both extrinsic and intrinsic patterns, as language models have been trained using natural language texts created by humans. This seems consistent with large language models having comparable performance to humans. However, this would not explain cases in which GPT-3 outperforms humans, unless (1) our population behaves differently (worse) than the population behind the training corpora used for learning them, and/or (2) GPT-3 has generalised some very abstract latent concepts that are applicable for simple intrinsic patterns, where GPT-3 seems excel (VL-C). Finally, MH is the system that behaves most like an ideal learner in our setting, but with very limited capability. The difference in the performance between MH and Louise might be due to the differences in their background knowledge.
Considering both matrices in Figure GPT-3D-TO shows a similar pattern of behaviour (cor- rect/incorrect results) with respect to humans in comparison with the rest of the analysed systems (Q4). This means the extra performance is not explained by being more deviated from human priors, but perhaps because of higher robustness. When we look at architecture size, we do not see monotonic relation between results and number of parameters (Q5), but GPT-3D, for the two variants that we have studied, achieves the best results for simple concepts. This may suggest that larger models can be better at capturing patterns that depend on simplicity priors, distilling some kind of Occam's 's razor for few-shot inference. However, some other experiments in the supplementary material, especially those concepts including loops, suggest that larger models in the future may not be able to solve complex algorithmic concepts, with this distillation being limited to sequential (if-then-else) algorithmic patterns. New paradigms beyond transformers may be needed in the future.
Explanations should give us more insight about what these systems are doing. Unfortunately, we were not able to find a working prompt so that GPT-3 could generate good explanations for the learnt concepts (Q6). Regarding the explanations provided by humans, the results suggest that the higher the complexity, the higher the size of the correct explanations to cover the learnt concepts. Furthermore, as complexity increases, the percentage of correct explanations decreases.
There are some limitations in this work. First, while we use MH as a system that would only be dominated by the simplicity priors, it is not very capable, and it is only useful to disentangle the behaviour for very easy concepts. Louise adds robustness to this analysis but has more dependency on background knowledge. More inductive programming systems could help in this analysis. Second, the use of humans for comparison limits the number of concepts and test examples that we can do for reasonable questionnaire. This has been partially mitigated by more concepts being explored for GPT-3 (section 4.2 and supplementary material), but the analysis of different samples according to other characteristics (not only loops but the frequencies of symbols or the lengths of the strings) could further characterise the performance. Third, the machine teaching setting we have used assumes perfect alignment and perfect identification, and this does not help in the understanding of how to provide further examples (AS I and AS II). Similarly, for compatibility with the original teaching book, in case of equal ties were broken lexicographically, which adds more dependence on P3. Fortunately, the machine teaching setting can be extended probabilistically for the teaching dimension FHernández-Orallo and Telle, 2020) (with more evidence increasing the confidence of correct identification), and a similar extension for the teaching size could be used for this analysis.
The main take-away of this paper is new approach, based on machine teaching, to analyse the power of language models under shw-shot inference. Because of the complexity of transformer architectures, the diversity of the training data used for language models, and their as pre-trained models through very different kinds of prompts, we require empirical yet well-founded ways to analyse how much evidence is needed for these systems make the right extrapolations This analysis boils down to determining the priors that pretrained models have distilled and the bias they represent. Overall, machine teaching can bring very important insights about what language models can do, what their acquired priors are, and the number -or the size- of examples they need.
10

---

Acknowledgments
We thank OpenAl for giving us early access to GPT-3 through their API. We thank support by the EU (FEDER) and Spanish grant CTI2018-0944D0 B-CC-B funded by MCIN/AEI/10. 1t..E//.....31//0000 and by "ERDF A way of making Europe", Generalitat Valenciana under grant PROMETE0/2019099 and INNEST/2021/217 (Project cofunded by the European Union with the "Programa Operativo del Fondo Europeo de Desarrollo Regional (FEDER) de Comunitat Valenciana 2014-2020"), EU's Horizon 2020 research and innovation programme under grant agreement No. 952215 (TAILOR), the FLJI under grant RFP2-152, and US DARPA HR001 12120007 (RECoG-AI). We thank the anonymous reviewers for their comments and interaction during the discussion process. We grateful to Dan Hendricks, Fernando Martínez-Plumee and Richard Evans for useful discussions, Carlos Monserrat for some assistance with the plots, Lidia Centreras-Ochandee for her help with MagicHaskeller and María José Ramirez-Quintana for their help with questions about visualisation, inductive programming and Louise. We also thank Stephen Muggleton and Stassa Patsantzis for their help with Louise. Finally, we thank the participants who completed the questionnaire.
13039/501 10001 1033
Funding Transparency Statement
All sources of funding have been included in the acknowledgments, None of the authors have financial relationships with entities that could potentially be perceived to influence the objectivity the paper.
References
Ai, L., Muggleton, S. H., Hocquette, C., Gromowski, M., and Schmid, U. (2021). Beneficial and harmful explanatory machine learning. Machine Learning, 110(4):695-221
Basu, and Christensen, J. (2013). Teaching classification boundaries to humans. In AAAI.
Bender, E. M., Gebru, T., MeMillan-Major, A., and Shmitchell, S. (2021). On the dangers of stochastic parrots: Can language models be too big? In Proceedings of the 2021 ACM Conference Fairness, Accountability, and Transparency, FAccT "21, page 610 6233.
Bender, E. M. and Koller, A. (2020). Climbing towards NLU: On meaning, form, and understanding in the age of data. In ACL, pages 5185-5195
Böhm, C. (1964). On family of Turing machines and the related programming language. ICC Bulletin, 387)1177-194
Brown, T. B., Mann, B., Ryder, N., al. (2020). Language models are few-shot learners. arXiv preprint arXiv:2005. 14165.
Cakmak, M. and Thomaz, A. L. (2014). Eliciting good teaching from humans for machine learners. Artificial Intelligence, 217:198-211 215.
Chater, N. and Vitányi, P. (2003). Simplicity: A unifying principle in cognitive science? Trends in Cognitive Sciences, 7(1):19-22.
Degen, J., Hawkins, R. D., Graf, C., Kreiss, E., and Goodman, N. D. (2020). When redundancy is useful: bayesian approach to "overinformative" referring expressions. Psychological Review.
Devlin, J., Chang. M.-W., Lee, K., and Toutanova, (2018). Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.044
Dingle, K., Camargo, C. Q., and Louis, A. A. (2018). Input-output maps are strongly biased towards simple outputs. Nature communications, 9(1):1-7.
Dowe, D. L., Hernández-Orallo, J., and Das, P. K. (2011). Compression and intelligence: social environments and communication. International Conference on Artificial General Intelligence, pages 204-211. Springer.

---

Carcia-Piqueras M. and Hemández-Oralloe J. (2021). Optimal teaching curricula with compositional simplicity priors. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 705-721. Springer.
Goodman, N. D. and Frank, M. C. (2016). Pragmatic language interpretation as probabilistic inference. Trends in Cognitive Sciences, 20(1 1):818-82)
Gou, J., Yu, B., Maybank, J. and Tao, D. (2021). Knowledge distillation: A survey. International Journal of Computer Vision, 129(6):1789-188) 1819.
Gulwani, S., Hernández-Orallo, J., Kitzelmann, E., Muggleton, S. H., Schmid, U., and Zom, B. (2015). Inductive programming meets the real world. Communications of the ACM, 58(1 1):90-99.
Hendrycks, D., Burns, C.. Basart, S.. Zou, A., Mazeika, M.. Song, D., and Steinhardt, J. (2021).
Mcasuring massive multitask language understanding, ICLR.
Hernández-Oralle J. and Ferri, C. (2021). Teaching and explanations: aligning priors between machines and humans. In Muggleton, S. and Chater, N., editors, Human-Like Machine Intelligence, chapter 9, pages 171-198. Oxford University Press.
Hernández-Orallo, J. and Telle, J. A. (2020). Finite and confident teaching expectation: Sampling from infinite concept classes. In ECAL, pages 1 1182-1189, IOS Press.
Hupkes, D., Dankers, V., Mul, M., and Bruni, E. (2020). Compositionality decomposed: How do neural networks generalise? Journal of Artificial Intelligence Research, 67:757-795.
Izacard, G. and Grave, F. (2020). Leveraging passage retrieval with generative models for open domain question answering. arXiv preprint arXiv:200..0122..
Katayama, (2011). Magichaskeller: System demonstration. AAIP 2011, pages 63-70.
Khan, F., Mutlu, B., and Zhu, (2011). How do humans teach: On curriculum learning and teaching dimension. In NIPS, pages 1457.
Kirstain, Y., Lewis, P., Riedel, S., and Levy, O. (2021). A few more examples may be worth billions of parameters. arXiv preprint arXiv:2110.04374
Kühl, N., Goutier, M., Baier, L., Wolff, C., and Martin, D. (2020). Human vs. supervised machine learning: Who learns patterns faster? arXiv preprint arXiv:2012.03661.
Lakretz, Y.. Kruszewski, G., al. (2019). The emergence of number and syntax units in LSTM language models. In NAACL 2019, pages 11-20.
Li, M. and Vitányi, P. (2008). An introduction to Kolmogorov complexity and its applications (3rd ed.). Springer-Verlag Verlag.
Liu, P., Yuan, W., Fu, J., Jiang, 7., Hayashi, H., and Neubig, G. (2021). Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing. arXiv preprint arXiv:2107.13586
Lu, Y., Bartolo, M., Moore, A., Riedel, S., and Stenetorp. P. (2021). Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity, arXiv preprint MxXiv:2104.08766
Marcus, G. and Davis, E. (2020). GPT-3, bloviator: OpenAl's language generator has no idea what it's talking about. Technology Review.
Melo, F. S., Guerra, C., and Lopes, M. (2018). Interactive optimal teaching with unknown learners. In 27th International Joint Conference on Artificial Intelligence, pages 2567-2573
Patsantzis, S. and Muggleton, S. (2021). Top program construction for polynomial meta- interinteerreetive learning. Machine Learning.
Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, I. (2019). Language models are unsupervised multitask learners. OpenAl blog, 1(8):9.
12

---

Rissanen, J. (1983). A universal prior for integers and estimation by minimum description length. Annals of Statistics, 11(2):416431.
Shah, H., Tamuly, K., Raghunathan. A., Jain, P., and Netrapalli, P. (2020). The pitfalls simplicity bias in neural networks. arXiv preprint vrXiv:2006.07710
Shannon, C. E. (1949). Communication theory of secreey systems. The Bell system technical journal, 2864)6656
Sinha, k. Sodhani, S., Dong, J., Pineau, J., and Hamilton, W. L.. (2019). CLUTRR: A diagnostic
benchmark for inductive reasoning from text. arXiv preprint vrXXiv1908.000
Solomonoff. R. (1964). A formal theory of inductive inference. Part Information and Control, 7(1):1-22.
Sun, W. Nasraoui, O., and Shafto, P. (2020). Evolution and impact of bias in human and machine learning algorithm interaction. Plas one, 1523550225
Telle, J. A., Hernández-Orallo, J., and Ferri, C. (2019). The teaching size: computable teachers and learners for universal languages. Machine Learning, (08(8-9):1653-161
Toshniwal, S., Wiseman, S., Livescu, K., and Gimpel, K. (2021). Learning chess blindfolded. https:://penneeview.. http://wwwww..eee/pp/////dddoooo
Valle-Perez, G., Camargo, C. Q., and Louis, A. A. (2019). Deep learning generalizes because the farameterrfuuction map biased towards simple functions. ICLR.
Vaswani, A., Shazeer, N., et al. (2017), Attention is you need. In Advances in neural information processing systems, pages 5998-6008.
Wallace, C. S. and Boulton, D. M. (1968). An information measure for classification. Computer Journal, 112)):185-194
Webson, A. and Pavlick, E. (2021). Do prompt-based models really understand the meaning of their prompts? arXiv preprint arX1v:2109.01247.
Wolpert, D. H. (1996). The lack of priori distinctions between learning algorithms. Neural computation, 8(7):134.
Xu, S., Semnani, S. J., Campagna, G., and Lam, M. S. (2020). AutoQA: From databases to QA semantic parsers with only synthetic training data. EMNLP.
Yang, S. C.-H. and Shafto, (2017). Explainable artificial intelligence via Bayesian teaching. In Workshop Teaching Machines, Robots, and Humans.
Zhao, T. Z., Wallace, E., Feng, S., Klein, D., and Singh, S. (2021). Calibrate before use: Improving few-shot performance of language models. arXiv preprint arXiv:2102. 09690..
Zhu, X. (2015). Machine teaching: An inverse problem to machine learning and an approach toward optimal education. In AAAL, pages 4083-4087.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Discussion,
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Introduction
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]] See Introduction and Learners
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] See Learners links and Supplementary Material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Supplementary Material.
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] We calculated the error bars for those systems that present variability on results (GPT-3) or that represent a population (differently parameterised GPT-2 or humans), but not for the rest of the cases as the systems are deterministic or there are very few instances. See Supplementary Material.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Supplementary Material.
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Learners
(b) Did you mention the license of the assets? [Yes] See Supplementary Material.
(c) Did you include any assets either in the supplemental material URL? [Yes]
See Learners links.
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're using/curating? [Yes] See Learnerss experiment form link.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes] See Learners
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [Yes] See Learners experiment form link.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [No] There were no potential participant risks identified.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [Ye]] See Learners experiment form link.
14


Reviews:
[{"review_id": "vFvShVEcLx7", "reviewer": "Reviewer_HcAt", "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.\n\nThe 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.", "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": "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.\n\nI 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.\n\nMinor issues / clarity:\n- I wasn't satisfied with the attempt to explain what a concept was. Within the paper, this is left very vague. \n- What does it mean to say that an explanation is \"minimally acceptable\"?\n- \"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. \n- \"most representative AI systems\" - This is a really unclear claim\n-  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\".\n- 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.\n- \"GPT-3D-T0 is one of the most similar systems to humans\" -  What does this mean?\n\n Grammar:\n- line 163 \"being w\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"ethical_concerns": "This paper seems to have followed reasonable procedures in their research with human subjects. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "cEEIpIGLa6e", "reviewer": "Reviewer_yfFz", "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.", "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": "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.\n\nIn 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.\n\nMethodologically, 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. \n\nI 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.\n\nUpdate after new experimental results: thanks for the new results; very interesting (especially for the VL experiments)! I increased my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "_4UJ47x_kba", "reviewer": "Reviewer_s6LA", "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.\nExperiment 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.\n\nI 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.\n", "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": "\nThe 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?\nThis makes me unsure of the interpretation of the results in this paper.\n\n\nOther questions and comments:\n\n1. 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.\n2. 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?\n3. #193: in which sense can a language relate to \"the way language models work internally (transformers)\"?\n4. Please add random/majority baselines to the figures.\n\n\nMinor:\n#41 story -> history?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "OPdS_TDL75J", "reviewer": "Reviewer_1G3n", "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.\n\nThe 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.\n", "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": "The paper mostly explores LM few-shot learning [1] under the machine teaching setup in [2].\n\nExperiments 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).\n\nMost 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.\n\nThe 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.\n\nOther remarks and questions for the authors:\n\nL83: Is it really a failure?\n\nFigure 1 is arguably overcrowded. It includes changes to both temperature and model size. For additional clarity, I think these should be presented separately.\n\nIn Figure 1b, what is the data condition (WS, WS +AS I, WS + AS I + AS II)?\n\nYou 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?\n\nDoes the order of examples matter?\n\nThe matrices in Figure 4 are symmetric (along the bottom-left to top-right diagonal), so most information is duplicated.\n\nWhy is the size of the additional examples not expressed in bits, as for the minimal witness sets?\n\nEven 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).\n\nIf 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?\n\n[1] Brown et al. (2020). Language models are few-shot learners. NeurIPS.\n[2] Telle et al. (2019). The teaching size: computable teachers and learners for universal languages. Machine Learning.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "JczOlOZKlaH", "reviewer": "Reviewer_HZ79", "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.", "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": "Note: I am not an NLP researcher so I cannot comment on this work’s significance to that community.\n\n\nPositive comments:\n* 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.\n* 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.\n* The experiments are clear and thorough and the supplemental results are extensive.\n* The overall contribution of the paper is large, clearly requiring an extensive effort, making it well suited for NeurIPS in terms of scope.\n* 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.)\n\n\nConcerns and questions:\n* 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.\n* 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).\n* 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.\n* 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.\n* 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.\n* The link in footnote 1 (https://bit.ly/Code3357) cannot be accessed (permission error)\n* 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.\n* 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See “concerns” above.\n", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

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)