%0 Conference Paper %B Advances in Neural Information Processing Systems 33 pre-proceedings (NeurIPS 2020) %D 2020 %T Learning abstract structure for drawing by efficient motor program induction %A Lucas Tian %A Kevin Ellis %A Marta Kryven %A Joshua B. Tenenbaum %X

Humans flexibly solve new problems that differ from those previously practiced. This ability to flexibly generalize is supported by learned concepts that represent useful structure common across different problems. Here we develop a naturalistic drawing task to study how humans rapidly acquire structured prior knowledge. The task requires drawing visual figures that share underlying structure, based on a set of composable geometric rules and simple objects. We show that people spontaneously learn abstract drawing procedures that support generalization, and propose a model of how learners can discover these reusable drawing procedures. Trained in the same setting as humans, and constrained to produce efficient motor actions, this model discovers new drawing program subroutines that generalize to test figures and resemble learned features of human behavior. These results suggest that two principles guiding motor program induction in the model - abstraction (programs can reflect high-level structure that ignores figure-specific details) and compositionality (new programs are discovered by recombining previously learned programs) - are key for explaining how humans learn structured internal representations that guide flexible reasoning and learning.

%B Advances in Neural Information Processing Systems 33 pre-proceedings (NeurIPS 2020) %8 12/2020 %G eng %U https://papers.nips.cc/paper/2020/hash/1c104b9c0accfca52ef21728eaf01453-Abstract.html %0 Conference Proceedings %B Neural Information Processing Systems (NeurIPS 2019) %D 2019 %T Write, Execute, Assess: Program Synthesis with a REPL %A Kevin Ellis %A Maxwell Nye %A Yewen Pu %A Felix Sosa %A Joshua B. Tenenbaum %A Armando Solar-Lezama %X

We present a neural program synthesis approach integrating components which write, execute, and assess code to navigate the search space of possible programs. We equip the search process with an interpreter or a read-eval-print-loop (REPL), which immediately executes partially written programs, exposing their semantics. The REPL addresses a basic challenge of program synthesis: tiny changes in syntax can lead to huge changes in semantics. We train a pair of models, a policy that proposes the new piece of code to write, and a value function that assesses the prospects of the code written so-far. At test time we can combine these models with a Sequential Monte Carlo algorithm. We apply our approach to two domains: synthesizing text editing programs and inferring 2D and 3D graphics programs.

%B Neural Information Processing Systems (NeurIPS 2019) %C Vancouver, Canada %8 11/2019 %G eng %0 Conference Paper %B NIPS Workshop | Bounded Optimality and Rational Metareasoning %D 2015 %T Metareasoning in Symbolic Domains %A Kevin Ellis %A Owen Lewis %X

Many AI problems, such as planning, grammar learning, program induction, and theory discovery, require searching in symbolic domains. Most models perform this search by evaluating a sequence of candidate solutions, generated in order by some heuristic. Human reasoning, though, is not limited to sequential trial and error.  In particular, humans are able to reason about what the solution to a particular problem should look like, before comparing candidates against the data. In a program synthesis task, for instance, a human might first determine that the task at hand should be solved by a tail-recursive algorithm, before filling in the  algorithm’s details.

Reasoning in this way about solution structure confers at least two computational advantages. First, a given structure subsumes a potentially large collection of primitive solutions, and exploiting the constraints present in the structure’s definition makes it possible to eval- uate the collection in substantially less time than it would take to evaluate each in turn. For example, a programmer might quickly conclude that a given algorithm cannot be implemented without recursion, without having to consider all possible non-recursive solutions. Second, it is often possible to estimate ahead of time the cost of evaluating different structures, making it possible to prioritize those that can be treated cheaply. In planning a route through an unfamiliar city, for example, one might first consider possibilities which use the subway exclusively, excluding for the moment ones that involve bus trips as well: if a successfully subway-only solution can be found, one then avoids the (potentially) exponentially more difficult bus-and-subway search problem.

Here, we consider a family of toy problems [1], in which an agent is given a balance scale, and is required to find a lighter counterfeit coin in a collection of genuine coins using at most some prescribed number of weighings. We develop a language for expressing solution structure  that places restrictions on a set of programs,  and use recent program synthesis techniques to search for a solution, encoded as a program, subject to hypothesized constraints on the program  structure.

%B NIPS Workshop | Bounded Optimality and Rational Metareasoning %8 12/2015 %G eng %U https://sites.google.com/site/boundedoptimalityworkshop/