The goal of this experiment is to empirically establish a significant subset of the primitives that our subjects use to solve list transformation tasks.
The basic idea is to:
- grammatically generate a large set of functions, (~1,000-2,000)
We’ll start with a grammar containing a large set of primitives, many of whose behavior is unlikely to be primitive. We’ll construct all programs of depth 0 (i.e. just primitives), and sample additional programs according to their probability under the grammar. For any program containing a constant parameterization (e.g. `map (x. (* 2 (+ 3 x))) xs`), we’ll also include at least one reparameterization per parameter (e.g. `map (x. (* 3 (+ 5))) xs` and `map (x. (* 8 (+ 1))) xs`). All numbers will be between 0 and 99, inclusive, with a bias toward the first 10 numbers. We’ll stop when we collect 1,000 concepts. For each concept, we’ll also generate 100 input/output pairs to select from during the experiment.
- measure people’s ability to learn these functions
Using the Martha’s Machines paradigm, we’ll collect learning curves from 30 subjects for each of our concepts on Mechanical Turk. As per the original experiment, we’ll pay participants $1 for 10 trials for each of 5 concepts. We can stick with 10 here because our goal is to identify primitives, which should be quickly learned. Concepts and input/output pairs will be randomly sampled for each participant.
- automatically identify the primitives
The basic idea I have for this part of the experiment is to run some automated analysis that uses the learning curves to separate primitive concepts from non-primitive concepts. I had initially thought some sort of clustering analysis would work, but given that we want to consider higher-order functions, the problem is more difficult. I would appreciate suggestions for appropriate analyses.
- Report our findings
- What are the primitives? any borderline cases?
- We may want to use a clustering technique within each concept, or at least a sample of concepts, to show that mean learning curves are a good description of the data (no averaging effects). This could used alongside visually plotting distributions (and not just confidence intervals) around the curves.
- What technique do we use to decide what’s primitive?
I would appreciate suggestions here.
- How do we deal with higher-order functions like map, fold, filter, any, all, iterate, take_while, drop_while, unfold, find, repeat, …?
Consider the case of map. The difficulty here is that map cannot be used by itself. It is parameterized not by constants but by other functions. Moreover, map can be defined in terms of other higher-order functions (e.g. a map is a kind of fold). This seems like it might require some sort of hierarchical reasoning to resolve.
- What if functions which humans learn in the experiment cannot be built from the concepts our analysis reveals as primitives?
Perhaps we extend the set of tested concepts in a targeted way, collect additional data, and repeat the analysis with the extended dataset until we get a consistent grammar. This gives us an iterative, convergent approach rather than a single, monolithic experiment. We could also design the analysis algorithm to always explain all the given concepts, making this a non-issue.
- Do we sample complete reparameterizations or vary them systematically?
I suggest we sample to keep each concept independent of the others.
- How do we analyze the data for averaging effects?
Simply plotting the distribution should give us some good visual indicators. Running some sort of clustering technique on data from one or more individual concepts might also help us see if people tend to fall into multiple groups or behave similarly to one another.
- What DSL should we use to generate concepts?
Here’s a partial list:
// list functions [ ] append prepend concatenate repeat range enumerate (list of indices for input list) map filter fold find (returns indices where function is true) length is_empty count unique first pop-first last pop-last index drop take slice insert remove reverse sort == max min contains all any // numerical functions 0, 1, 2,... 99 +, *, -, /, mod, ^ <, >, == // boolean functions true, false ==, not, and, or if-then-else
The goal of this experiment is to empirically establish variance in the difficulty of learning various list transformation concepts and explain a significant portion that variance using program induction: learning in a space of TRSs.
The basic idea is to:
- generate concepts from the DSL discovered in Experiment 0.
To explore the space, we will construct many concepts from the DSL. We will provide an example of each primitive, while the rest will be sampled from the distribution suggested by the grammar. Let’s say we construct on the order of 1,000-2,000 distinct concepts. As in Experiment 0, for any concept parameterized by n constants, at least additional parameterizations will be included in the set.
- measure the difficulty of learning these concepts for humans
We will use the Martha’s Machines paradigm to recruit 30 subjects on Mechanical Turk to learn each of the concepts constructed above. As per the original experiment, participants will be asked to learn five list routines from examples. Because we want to test a wider variety of concepts across a wider variety of difficulties than the original experiment, participants will submit predicted outputs for 25 given inputs, and compensation will be increased slightly to $1.50. All the numbers in our inputs and correct outputs will be between 0 and 99.
- measure the difficulty of learning these concepts for our model
We will use our TRS-based model to run 30 simulated learners for each of the concepts constructed above. We will use the same primitive basis as was used to generate the concepts.
- analyze the collected data
We’ll perform similar analyses to those reported in the CogSci paper:
- show that learning occurs
- t-test first 5 trials vs. last 5 trials
- correlate performance and round number
- correlate performance and trial number
- correlate the mean performance of models and humans across concepts
- correlate mean human performance and description quality across concepts
- t-test showing benefit of getting hard concepts later in the experiment
- correlate the learning curves of models and humans per concept
We will also:
- analyze the distribution of learning curves in each concept to ensure our effects are not merely the result of averaging. This can be done simply by visual inspection of the distributions as well as by an automated clustering analysis.
- analyze the baseline performance against a linearly improving learner and a learner sensitive to just the complexity of the rules to be learned (i.e. sampling from the prior given by the grammar)
- analyze the actual learned systems of rules
- report distribution over likelihoods to show how good they are at explaining the data, perhaps a scatterplot of ideal vs. learned?
- report distribution over priors to show how good are they at being concise. Again, a scatter plot of the human solution vs. the learned solution.
- Show the rules for some example problems
- show that learning occurs
- Do we want to use the non-independent curriculum learning approach of the models in Experiment 2 during Experiment 1. If not, do we want to change the explanation of the human experiment to say that each machine is independent of the others?
The goal of this experiment is to empirically establish that certain types of curricula can make otherwise difficult concepts much easier to learn and explain that change in difficulty using program induction, specifically learning in a space of TRSs.
The basic idea is to:
- generate several curricula
This will likely be the trickiest part of the experiment to setup. We will handpick 5 target concepts (i.e. count-head-in-tail, and 4 others), and for each construct the following curricula:
- Relevant Parts
- this curriculum will teach each named concept that appears in the definition of the target but will not combine them in any way. For example, if C(xs) = A(B(C(xs)), D(E(xs), F(xs))), then A, B, C, D, E, and F would form the curriculum. The order of the curriculum will be randomized.
- Building Up
- this curriculum will successively teach not only each named concept but also any combinations of these parts that might appear in the definition of the target concept. For example if C(xs) = A(B(C(xs)), D(E(xs), F(xs))), then A, B, C, D, E, F, x. B(C(x)), and x. D(E(x), F(x)) would form the curriculum. This is a longer and more gradual curriculum, and not all the components may seem like useful concepts on their own. Complex parts wouldn’t be taught until their components had been learned, but the order would otherwise be random.
- Sampling
- this curriculum will randomly sample a fixed number of subparts of the target concept and teach them. For example if C(xs) = A(B(C(xs)), D(E(xs), F(xs))), then B, x,y. D(E(x), y), F, x. B(C(x)), and C might form the curriculum. The order of the curriculum would be randomized.
- Distractor
- this curriculum will consist of the relevant parts curriculum interleaved with randomly selected distractor concepts. The order of the curriculum will be randomized.
- no curriculum
- participants simply get extra trials on the target concept
- Random
- this curriculum will not incorporate the components of the target concept and will instead use randomly selected concepts of equivalent description length.
- Adversarial
- this curriculum will consist of a relevant parts curriculum for a different target concept.
- measure the difficulty of human learning in each curriculum
We will use the Martha’s Machines paradigm to recruit 30 subjects on Mechanical Turk to learn each of the concepts constructed above. Participants will be asked to learn N list routines from examples, where N is dictated by the curriculum and target concept. Because we want to test a wider variety of concepts across a wider variety of difficulties than the original experiment, participants will submit predicted outputs for 25 given inputs, and compensation will be increased slightly to $1.50. All the numbers in our inputs and correct outputs will be between 0 and 99.
- measure the difficulty of model learning in each curriculum
We will use our TRS-based model to run 30 simulated learners for each of the concepts constructed above. We will use the same primitive basis as was used to generate the concepts. The major hiccup here is that, unlike experiment 1, we will not treat the concepts independently. The best hypotheses at the end of the first concept will be used as the initial hypotheses when learning the second concept, and so on through the target concept. Moreover, the data from all concepts will accumulate, providing incentive to maintain and/or improve previously learned concepts while also learning the current concept.
- analyze the collected data
- test for differences in performance of the various conditions
- correlate human and model performance on the various curricula
- mean performance
- learning curve performance
- regression predicting target performance using curriculum performance
- look at changes in solution quality distributions across conditions in the models, for prior, likelihood, and posterior.
- report some of the learned systems of rules
- Are these the right curricula to consider?
- What will our four other target concepts be?
- What other analyses would we like to run?
- We need to pay special attention to making predicted outputs fast and easy to enter. Making predictions should be as easy as typing a list of digits, perhaps separated by space or tab.
- Before beginning the experiments, we may want to conduct some sort of power analysis to better justify exactly how many subjects we need.