TY - GEN

T1 - Bootstrap learning via modular concept discovery

AU - Dechter, Eyal

AU - Malmaud, Jon

AU - Adams, Ryan P.

AU - Tenenbaum, Joshua B.

PY - 2013

Y1 - 2013

N2 - Suppose a learner is faced with a domain of problems 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 effectively. How can such a learner ever get off the ground? A common intuition is that if the solutions 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 components from these solutions and, by composing them, explore the solution space more efficiently. Here, we formalize this intuition, where the solution 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 grammar; 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 concepts 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 knowledge of the structure of the solution space.

AB - Suppose a learner is faced with a domain of problems 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 effectively. How can such a learner ever get off the ground? A common intuition is that if the solutions 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 components from these solutions and, by composing them, explore the solution space more efficiently. Here, we formalize this intuition, where the solution 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 grammar; 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 concepts 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 knowledge of the structure of the solution space.

UR - http://www.scopus.com/inward/record.url?scp=84896061120&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84896061120&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84896061120

SN - 9781577356332

T3 - IJCAI International Joint Conference on Artificial Intelligence

SP - 1302

EP - 1309

BT - IJCAI 2013 - Proceedings of the 23rd International Joint Conference on Artificial Intelligence

T2 - 23rd International Joint Conference on Artificial Intelligence, IJCAI 2013

Y2 - 3 August 2013 through 9 August 2013

ER -