Program induction is an appealing model for human concept learning, but faces scaling challenges in searching the massive space of programs. We propose a computational model capturing two key aspects of human concept learning – our ability to judge how promising a vague, partial hypothesis is, and our ability to gradually refine these vague explanations of observations to precise ones. We represent hypotheses as probabilistic programs with randomness in place of unresolved programmatic structure. To model the evaluation of partial hypotheses, we implement a novel algorithm for efficiently computing the likelihood that a probabilistic program produces the observations. With this, we guide a search process whereby high-entropy, coarse programs are iteratively refined to introduce deterministic structure. Preliminary results on list tasks show orders of magnitude improvement in sample efficiency when augmenting a sampling-based search with likelihood guidance, and intermediate hypotheses were similar to those considered by humans verbalizing their thought processes.

Authors:

Maddy L Bowers: MIT; Alexander Lew: MIT; Wenhao Qi: University of California, San Diego; Joshua S Rule: UC Berkeley; Vikash Mansinghka: MIT; Josh Tenenbaum: MIT; Armando Solar-Lezama: Massachusetts Institute of Technology