Bootstrap Learning via Modular Concept Discovery
Eyal Dechter, Jon Malmaud, Ryan Prescott Adams, Joshua B. Tenenbaum · 2014
Suppose a learner is faced with a domain of prob-lems about which it knows nearly nothing. It does not know the distribution of problems, the space of solutions is not smooth, and the reward signal is uninformative, providing perhaps a few bits of information but not enough to steer the learner ef-fectively. How can such a learner ever get off the ground? A common intuition is that if the solu-tions to these problems share a common structure, and the learner can solve some simple problems by brute force, it should be able to extract useful com-ponents from these solutions and, by composing them, explore the solution space more efficiently. Here, we formalize this intuition, where the so-lution space is that of typed functional programs and the gained information is stored as a stochastic grammar over programs. We propose an iterative procedure for exploring such spaces: in the first step of each iteration, the learner explores a finite subset of the domain, guided by a stochastic gram-mar; in the second step, the learner compresses the successful solutions from the first step to estimate a new stochastic grammar. We test this procedure on symbolic regression and Boolean circuit learning and show that the learner discovers modular con-cepts for these domains. Whereas the learner is able to solve almost none of the posed problems in the procedure’s first iteration, it rapidly becomes able to solve a large number by gaining abstract knowl-edge of the structure of the solution space. 1