Theory Acquisition as Stochastic SearchTomer D. Ullman, Noah D. Goodman, Joshua B. Tenenbaum{tomeru, ndg, jbt}@mit.edu
Department of Brain and Cognitive Sciences
Massachusetts Institute of Technology
Cambridge, MA 02139
Abstract
We present an algorithmic model for the development of children’s intuitive theories within a hierarchical Bayesian framework, where theories are described as sets of logical laws
generated by a probabilistic context-free grammar. Our algorithm performs stochastic search at two levels of abstraction– an outer loop in the space of theories, and an inner loop in
the space of explanations or models generated by each theory given a particular dataset – in order to discover the theory
that best explains the observed data. We show that this modelis capable of learning correct theories in several everyday domains, and discuss the dynamics of learning in the context ofchildren’s cognitive development.

Introduction
As children learn about the world, they learn more than justa large stock of specific facts. They organize their knowledge into abstract coherent frameworks, or intuitive theories, that guide inference and learning within particular domains (Carey, 1985; Wellman & Gelman, 1992). Much recent work in computational cognitive modeling has attempted
to formalize how intuitive theories are structured, used andacquired from experience (Tenenbaum, Griffiths, & Kemp,
2006), working broadly within a hierarchical Bayesian framework shown in Figure 1 (and explained in more detail below).
While this program has made progress in certain respects, it
has treated the problem of theory acquisition only in a very
ideal sense. The child is assumed to have a hypothesis spaceof possible theories constrained by some “Universal Theory”,
and to be able to consider all possible theories in that space, inlight of a given body of evidence. Given sufficient evidence,
and a suitably constrained hypothesis space of theories, it has
been shown that an ideal Bayesian learner can identify thecorrect theory underlying core domains of knowledge such as
causality (Goodman, Ullman, & Tenenbaum, 2009), kinshipand other social structures (Kemp, Goodman, & Tenenbaum,2008). These Bayesian computational analyses have not todate been complemented by working algorithmic models of
the search process by which a child can build up an abstract
theory, piece by piece, generalizing from experience. Here
we describe such an algorithmic model for Bayesian theory
acquisition. We show that our algorithm is capable of constructing correct if highly simplified theories for several everyday domains, and we explore the dynamics of its behavior– how theories can change as the learner’s search process unfolds as well as in response to the quantity and quality of thelearner’s observations.
At first glance, the dynamics of theory acquisition in childhood look nothing like the ideal learning analsyes of hierarchical Bayesian models – and may not even look particularly

rational or algorithmic. Different children see different random fragments of evidence and make their way to adult-likeintuitive theories at different paces and along different paths.
It seems unlikely that children can simultaneously evaluate
many candidate theories at once; on the contrary, they appear
to hold just one theory in mind at any time. Transitions between theories appear to be local, myopic, and semi-random,rather than systematic explorations of the hypothesis space.
They are prone to backtracking or “two steps forward, one
step back”. We suggest that these dynamics are indicativeof a stochastic search process, much like the Markov chain
Monte Carlo (MCMC) methods that have been proposed for
performing approximate probabilistic inference in complex
generative models. We show how a search-based learning algorithm can begin with little or no knowledge of a domain,and discover the underlying structure that best organizes it
by generating new hypotheses and checking them against its
current conceptions of the world using a hiearchical Bayesianframework. New hypotheses are accepted probabilistically ifthey can better account for the observed data, or if they compress it in some way. Such a search-based learning algorithm
is capable of exploring a potentially infinite space of theories,
but given enough time and sufficient data it tends to converge
on the correct theory – or at least some approximation thereof,
corresponding to a small set of abstract predicates and laws.
The plan of the paper is as follows. We first introduce ourframework for representing and evaluating theories, basedon first-order logic and Bayesian inference in a hierarchical probabilistic model that specifies how the theory’s logicalstructure constrains the data observed by a learner. We thendescribe our algorithmic approach to theory learning basedon MCMC search, using simulated annealing to aid convergence. Finally we study the search algorithm’s behavior on
two case studies of theory learning in everyday cognitive domains: the taxonomic organization of object categories andproperties, and a simplified version of magnetism.

Formal framework
We work with the hierarchical probabilistic model shown in
Figure 1, based on those in (Katz, Goodman, Kersting, Kemp,& Tenenbaum, 2008; Kemp et al., 2008). We assume that adomain of cognition is given, comprised of one or more systems, each of which gives rise to some observed data. The
learner’s task is to build a theory of the domain: a set of
abstract concepts and explanatory laws that together generate a hypothesis space and prior probability distribution overcandidate models for systems in that domain. The laws andUniversal
TheoryProbabilistic Horn Clause Grammar
Magnetism

TheoryCore Predicates: p(X), q(X)Surface Predicates: interacts(X,Y)
Laws:
interacts(X,Y)p(X) p(Y)interacts(X,Y)p(X) q(Y)interacts(X,Y)
interacts(Y,X)

p(X): “magnets”

Taxonomy
Core Predicates: f(X,Y), g(X,Y)
Surface Predicates: has_a(X,Y), is_a(X,Y)
Laws:
is_a(X,Y)
g(X,Y)
has_a(X,Y)
f(X,Y)
has_a(X,Y)
is_a(X,Z) has_a(Z,Y)
is_a(X,Y)
is_a(X,Z) is_a(Z,Y)
breathes“non-magnetic objects”
can_ﬂy

Model

bird

q(X): “magnetic objects”

Dataanimalg(X,Y): “is_a”
f(X,Y): “has_a”

can_swimﬁshcanary

eagle

shark

salmoncan_sing

has_claws

can_bite

is_pink“a shark is a ﬁsh”
“a bird can ﬂy”“a canary can ﬂy”“a salmon can breathe”..
.

Figure 1: A hierarchical Bayesian framework for theory acquisition

concepts are written in logical form, a “language of thought”,
typically a subset of first-order logic. The learner’s model of asystem specifies what is true of that system, and thereby generates a probability distribution over possible observations
that can be made for that system.
For example, consider a child learning about the domainof magnetism. She might begin by playing with a few piecesof metal and notice that some of the objects interact, exerting
strange pulling or pushing forces on each other. She could
describe the data directly, as “Object i interacts with objectf”, “Object i interacts with object j”, and so on. Or she could
form a simple theory, in terms of abstract concepts such as
magnet, magnetic object and non-magnetic object, and laws
such as “Magnets interact with other magnets”, “Magnets
interact with magnetic objects”, and “Interactions are symmetric” (but no other interactions take place). Systems in thisdomain correspond to specific subsets of objects, such as theset of objects {a, . . . , i} in Figure 1. A model of a system specifies the minimal facts needed to apply the abstract theory to
the system, in this case which objects are magnetic, which aremagnets, and which are non-magnetic. From these core facts
the laws of the theory determine all other true facts – in our
example, this means all the pairwise interactions between theobjects: e.g., objects i and j, being magnets, should interact,
but i and e should not, because e is non-magnetic. Finally, thetrue facts generate the actual data observed by the learner via
a noisy observation process.
While the abstract concepts in this simplified magnetism
theory are attributes of objects, more complex relations are
possible. Consider for example a domain of taxonomy, as
in Collins and Quillian’s classic model of semantic memory
as an inheritance hierarchy (Collins & Quillian, 1969). Herethe abstract concepts are is a relations between categories andhas a relations between categories and properties. The theory
underlying taxonomy has two basic laws: “The has a relation

inherits down is a relations” and “The is a relation is transitive” (laws 3 and 4 on the right side of Figure 1). A system
consists of a specific set of categories and properties, such as
salmon, eagle, breathes, can fly, and so on. A model specifies
the minimal is a and has a relations, typically corresponding
to a tree of is a relations between categories with properties
attached by has a relations at the broadest category they holdfor: e.g., “A canary is a bird”, “A bird is an animal”, “An animal can breathe”, and so on. The laws then determine thatproperties inherit down chains of is a relations to generatemany other true facts that can potentially be observed, e.g.,“A canary can breathe”.
Equipped with this hierarchical generative model, a learnercan work backwards from observed data to multiple levels oflatent structure. Given the correct theory, the learner can infer
the most likely model underlying a set of noisy, sparse observations and predict facts that have not been directly observed(Katz et al., 2008; Kemp et al., 2008). If the true theory is
unknown, the learner can consider a hypothesis space of candidate theories, generated by higher-level “Universal Theory(UT )” knowledge. UT defines a distribution over the spaceof possible theories, P(T |UT ), which can then be used by alearner to infer the correct theory describing a domain, according to the standard Bayesian formulation:
P(T |D,UT ) ∝ P(D|T )P(T |UT )(1)

Bayes’ rule here captures the intuition of Occam’s razor. The
theory that best explains the data, or has highest posterior
probability P(T |D,UT ), should be based on two considerations: how well the theory fits the data, as measured by the
likelihood P(D|T ), and how simple or short is the theory, as
measured by the prior P(T |UT ). We now define these hypothesis spaces and probabilities more formally, and then describe a learning algorithm that searches the space of theories
by proposing small random changes to the current theory andaccepting changes stochastically based on whether they arelikely to lead to higher overall probability.
A language for theories. Following (Katz et al., 2008) we
represent the laws in a theory as Horn clauses: logical expressions of the form t ← (p ∧ q ∧ ... ∧ r). Horn clauses express
logical implications – a set of conjunctive conditions underwhich t holds – but can also capture intuitive causal relations
under the assumption that any propositions not generated by
the theory are assumed to be false. In our formulation, theclauses contain two kinds of predicates: “core” and “surface”.
Core predicates are a minimal set of predicates that determine
all other predicates when combined with the theory’s laws.
Surface predicates are derived from other predicates, either
surface or core, via the laws. Predicates may or may not bedirectly observable in the data. The core predicates can beseen as compressing the full model into just the minimal bits
necessary to specify all true facts. In the magnetism example
above, the core could be expressed in terms of two predicatesp(X) and q(X). Based on an assignment of truth values tothese core predicates, theTop level theory
(S1)
(S2)
(S3)

S
S
S

⇒
⇒
⇒

(Law) ∧ S
(Tem) ∧ S
Stop

Random law generation(Law)(Add1)(Add2)

Law
A
A

⇒
⇒
⇒

(Ple f t ← Pright ∧ Add)
P ∧ Add
Stop

P(X,Y) ← P(X,Z)∧P(Z,Y)
P(X,Y) ← P(Z,X)∧P(Z,Y)
P(X,Y) ← P(X,Z)∧P(Y,Z)
P(X,Y) ← P(Z,X)∧P(Y,Z)
P(X,Y) ← P(X,Y)∧P(X)
P(X,Y) ← P(Y,X)∧P(X)
P(X,Y) ← P(X,Y)∧P(Y)P(X,Y) ← P(Y,X)∧P(Y)P(X,Y) ← P(X)∧P(Y)P(X,Y) ← P(Y,X)
P(X,Y) ← P(X,Y)P(X)← P(X)P(X)← P(X,Y)∧P(X)
P(X)← P(Y,X)∧P(X)
P(X)← P(X,Y)∧P(Y)P(X)← P(Y,X)∧P(Y)Figure 3: The list of templates available to in the PHCG.
Predicate generation(Ple f t 1)..
.
(Ple f t α)(Pright 1)..
.
(Pright α)(Pright (α + 1))..
.
(Pright (α + β))
Law templates(Tem1)..
.
(Temγ)

Ple f t⇒sur f ace1()

Ple f tPright⇒⇒sur f aceα()
sur f ace1()

PrightPright⇒⇒sur f aceα()
core1()

Pright⇒coreβ()

Tem⇒

template1()Tem⇒

templateγ()

Figure 2: Production rules of the Probabilistic Horn Clause Grammar. S is the start symbol and Law, Add, P and Tem are nonterminals. α, β, and γ are the numbers of surface predicates, core
predicates, and law templates, respectively.

learner can use the theory’s laws such as
interacts(X, Y) ← p(X) ∧ q(Y) to derive values for theobservable surface predicate interacts(X, Y). Notice thatp(X) and q(X) are abstract predicates, which acquire their
meaning as concepts picking out magnets or magnetic objects
respectively in virtue of the role they play in the theory’s
laws. In constructing such a theory the learner essentiallycreates new concepts (Carey, 1985). Entities may be typed
and predicates restricted based on type constraints: e.g., intaxonomy, has a(X, Y) requires that X be a category and Y
be a property, while is a(X, Y) requires that X and Y both be
categories. Forcing candidate models and theories to respectthese type constraints provides the learner with a valuable
and cognitively natural inductive bias.
The theory prior P(T |UT ). We posit UT knowledge inthe form of a probabilistic context-free Horn clause grammar(PHCG) that generates the hypothesis space of possible Hornclause theories, and a prior P(T |UT ) over this space (Figure2). This grammar and the Monte Carlo algorithms we use tosample or search over the theory posterior P(T |D,UT ) arebased heavily on Goodman, Tenenbaum, Feldman, and Griffiths (2008), who introduced the approach for learning single
rule-based concepts rather than the larger theory structures weconsider here. We refer readers to Goodman et al. (2008) for
many technical details. Given a set of possible predicates inthe domain, the PHCG draws laws from a random construction process (Law) or from law templates (Tem; explained
in detail below) until the Stop symbol is reached, and thengrounds out these laws as horn clauses. The prior p(T |UT ) is

the product of the probabilities of choices made at each pointin this derivation. All these probabilities are less than one, so
overall the prior favors simpler theories with shorter derivations. The precise probabilities of different rules in the grammar are treated as latent variables and integrated out, favoring
re-use of the same predicates and law components within atheory (Goodman et al., 2008).
Law templates. We make the grammar more likely to generate useful laws by equipping it with templates, or canonicalforms of laws that capture structure likely to be shared across
many domains. While it is possible for the PHCG to reacheach of these law forms without the use of templates, their
inclusion allows the most useful laws to be invented more
readily. They can also serve as the basis for transfer learning across domains. For instance, instead of having to reinvent transitivity anew in every domain with some specifictransitive predicates, a learner could recognize that the sametransitivity template applies in several domains. It may be
costly to invent transitivity for the first time, but once found– and appreciated! – its abstract form can be readily reused. The specific law templates used are described in Figure
3. Each “P(·)” symbol stands for a non-terminal representing a predicate of a certain -arity. This non-terminal is later
instantiated by a specific predicate. For example, the template P(X, Y) ← P(X, Z) ∧ P(Z, Y) might be instantiated as
is a(X, Y) ← is a(X, Z) ∧ is a(Z, Y) (a familiar transitive law)or as has a(X, Y) ← is a(X, Z) ∧ has a(Z, Y) (the other key
law of taxonomy, stating that “has a is transitive over is a”).
The theory likelihood P(D|T ). An abstract theory makes
predictions about the observed data in a domain only indirectly, via the models it generates. A theory typically generates many possible models: even if a child has the correct
theory and abstract concepts of magnetism, she could categorize a specific set of metal bars in many different ways, eachof which would predict different interactions that could beobserved as data. Expanding the theory likelihood,
P(D|T ) = ∑ P(D|M)P(M|T )(2)

M

we see that theory T predicts data D well if it assigns highprior P(M|T ) to models M that make the data probable under
the observation process P(D|M).
The model prior P(M|T ) reflects the intuition that a theory T explains some data well if T requires few additional
degrees of freedom beyond its abstract concepts and laws
to make its predictions. That is, few specific and contingent facts about the system under observation are required

in addition to the theory’s general prescriptions. This intuition is captured by a prior that encourages the core predicates to be as sparse as possible, penalizing theories that can
only fit well by “overfitting” with many extra degrees of freedom. Formally, following (Katz et al., 2008), we model all
values of the core predicates as independent Bernoulli random variables with conjugate beta priors encouraging mostvariables to have the same value (on or off). We assume thatany proposition potentially in the model M is false unless it isa core predicate turned on by this Bernoulli process or is derived from the core predicates through the theory’s laws (theminimal model assumption of logic programming).
Finally, the model likelihood P(D|M, T ) comes from assuming that we are observing randomly sampled true facts(sampled with replacement, so the same fact could observedon multiple occasions), which also encourages the model extension to be as small as possible.
Stochastic search in theory space: a grammar-basedMonte-Carlo algorithm. Following Goodman et al. (2008),
we use a grammar-based Metropolis-Hastings (MH) algorithm to sample theories from the posterior distribution
over theories conditioned on data, P(T |D,UT ). This algorithm is applicable to any grammatically structured theory
space, such as the one generated by our PHCG. The MH
algorithm proceeds by randomly proposing changes to thecurrent theory, and accepting or rejecting these changes.
Each proposed change to the current theory corresponds
to choosing a grammatical constituent of the theory thenregenerating it from the PHCG. For example, if our theory ofmagnetism includes the law interacts(X, Y) ← p(X) ∧ q(Y),the MH procedure might propose to add or delete a
predicate(e.g.,
interacts(X, Y) ← p(X) ∧ q(Y) ∧ p(Y)or interacts(X, Y) ← p(X)), to change one predicate to an alternative of the same form (e.g.,interacts(X, Y) ← p(X) ∧ p(Y)) or a different form
if available (e.g.,interacts(X, Y) ← p(X) ∧ r(X, Y));
to resample the law from a template (e.g.,interacts(X, Y) ← r(X, Z) ∧ r(Z, Y)); or to add or delete
a whole law.
These proposals are accepted with probability equal to theminimum of 1 and the MH acceptance ratio,
P(T 0 |D,UT ) Q(T |T 0 )·P(T |D,UT ) Q(T 0 |T )(3)

where T is the current theory, T 0 is the new proposed theory, and Q(·|·) is the transition probability from one theory
to the other, derived from the PHCG (Goodman et al., 2008).
To aid convergence we raise the posterior ratio to a power
greater than 1, which we increase very slightly after each MH
step in a form of simulated annealing. The learner initiallyexplores alternative theories freely, but with time becomes increasingly likely to reject theory changes unless they lead toan improved posterior probability.
While this MH algorithm could be viewed merely as a way
to approximate the calculations necessary for a hierarchical

Bayesian analysis, we suggest that it could also capture in aschematic form the dynamic processes of theory acquisitionand change in young children. Stochastic proposals to add a
new law or change a predicate within an existing law are consistent with some previous characterizations of children’s theory learning dynamics (Siegler & Chen, 1998). These dynamics were previously proposed on purely descriptive grounds,
but here they emerge as a consequence of a rational learningalgorithm for effectively searching an infinite space of logicaltheories.
Approximating the theory score. Computing the theory
likelihood P(D|T ), necessary to compare alternative theories
in Equation 3, requires a summation over all possible models consistent with the current theory (Equation 2). Because
this sum is typically very hard to evaluate exactly, we approximate P(D|T ) with P(D|M ∗ )P(M ∗ |T ), where M ∗ is an
estimate of the maximum a-posteriori (MAP) model inferredfrom the data: the most likely values of the core predicates.
The MAP estimate M* is obtained by running a Gibbs sampler over the values of the core predicates, as in (Katz et al.,2008), annealing slightly on each Gibbs sweep to speed convergence and lock in the best solution. The Gibbs sampler
over models generated by a given theory is thus an “innerloop” of sampling in our learning algorithm, operating withineach step of an “outer loop” sampling at a higher level of abstract knowledge, the MH sampler over theories generated by
UT knowledge.

Case Studies
We now explore the performance of this stochastic approachto theory learning in two case studies, using simulated datafrom the domains of taxonomy and magnetism introduced
above. We examine the learning dynamics in each domain
and make more explicit the possible parallels with human theory acquisition.

Taxonomy
Katz et al. (2008) defined a similar hierarchical Bayesianframework and showed that a theory of taxonomic reasoning about properties and categories in an inheritance hierarchy could be correctly selected from among several alternatives, on the basis of data. However, they did not address theharder challenge of constructing the theory from the groundup, or selecting it from an effectively infinite hypothesis spaceof theories (which could be used to describe many other domains). That is our goal here. Following Katz et al. (2008),
we take the correct theory to have two unobservable core
predicates, g(X, Y) and f(X, Y), and two observable surface
predicates, is a(X, Y) and has a(X, Y). There are four laws:
Law 1:
Law 2:

has a(X, Y) ← f(X, Y)
is a(X, Y) ← g(X, Y)

Law 3:

has a(X, Y) ← is a(X, Z) ∧ has a(Z, Y)

Law 4:

is a(X, Y) ← is a(X, Z) ∧ is a(Z, Y)

Laws 1 and 2 set up the core predicates to represent the mini-Log posterior

2

1

Simulation iterations

Figure 4: Log posterior score for representative runs of theory learning in Taxonomy. Dashed lines show different runs. Solid line is theaverage across all runs. Node 1 marks the acquisition of law 3, node
2 marks the acquisition of law 4.

mal is a and has a links, on top of which are defined the lawsof property inheritance (Law 3) and transitive category membership (Law 4). We take laws 1 and 2 as given, assuming
the structure and meaning of the core predicates as Katz et al.
did, and ask whether a learner can successfully construct laws
3 and 4. Following Katz et al., we consider a concrete domain
with 7 categories and 7 properties in a balanced taxonomy, as
shown in Figure 1. Observations include all positive facts asserting that a property is true of a category, as in “An eagle has
claws”. (The data used for this section and the following casestudy can be found at http://web.mit.edu/tomeru/www/tlss.)
We ran 10 simulations for 1300 iterations of the outer MH
loop. Learning curves for representative runs as well as theaverage over all runs are shown in Figure 4. Out of 10 simulations, 8 found the correct theory within the given number of
iterations, and 2 discovered a partial theory which included
only law 3 (property inheritance). Several observations areworth noting.
Abstract learning is possible. Using only stochastic local
search moves, a learner can navigate the space of potential
theories to discover the laws underlying the domain. Even a
relatively small dataset (with 7 categories and 7 properties) is
sufficient to learn the correct abstract domain theory.
Individual learning curves show sudden changes and highvariability in what is learned when, while on average learning is smooth and follows a characteristic timecourse. The
learning algorithm’s local dynamics are highly stochastic andvariable across runs, because of the randomness in what theory changes are proposed when, and the fact that a small theory change can make a big difference in predictive power. Yet
there is still a meaningful sense in which we can talk about“typical” learning behavior, even though any one learner may
not look much like this average. If stochastic local search isa key component in children’s theory construction, it could
explain why cognitive development shows this same dual
nature: systematic and graded progression at the population level, despite random, discontinuous and highly variable
learning rates in any one child.
Although proposals are random, there is a systematic andrational order to learning. While there are many routes

through theory space to a given endpoint, a sequence of random MH proposals may still prefer some orders of knowledge acquisition over others. Here, when law 4 is discovered(on 8/10 runs), it is always acquired after law 3. This is because law 4 (transitivity of category membership) provides
much more explanatory power – and hence is more stable
under our stochastic theory-learning dynamics – given law 3(property inheritance) and a reasonable domain model specifying which properties hold for which categories. This order is also consistent with the order of acquisition in humancognitive development (Wellman & Gelman, 1992): children
learn to generalize properties of biological categories to instances well before they learn that categories can be arranged
in a multilevel hierarchy supporting transitive inferences ofcategory membership.

Magnetism
After showing that stochastic search can learn the correct laws
in a domain theory, we now consider a second case study inwhich the acquisition of new laws corresponds to a shift inthe meaning of the core predicates, and new (i.e., previously
unassigned) core predicates are introduced during learning –akin to some of the conceptual changes described by Carey(1985). Our domain here is the simple version of magnetism described above, with two unobservable core predicates: p(X) and q(X), and one observable surface predicate:interacts(X, Y). There are three laws:
Law 1:

interacts(X, Y) ← p(X) ∧ p(Y)Law 2:

interacts(X, Y) ← p(X) ∧ q(Y)Law 3:

interacts(X, Y) ← interacts(Y, X)

We consider a concrete system with 3 magnets, 5 magnetic
objects and 2 non-magnetic objects. These concepts are initially unknown to the learner. The core predicates p(X) andq(X) are completely abstract and initially uninterpreted. They
will acquire their meaning as concepts picking out magnets
and magnetic objects respectively in virtue of the role theyplay in the theory’s laws, specifying that objects in one subset (the p’s) interact with each other and with objects in asecond set (the q’s), but q’s do not interact with each other.
In constructing a theory, the learner introduces these abstract
predicates via new laws, or new roles in existing laws, andthereby essentially creates these concepts where she did nothave them before (Carey, 1985).
We ran 10 simulations for 1600 iterations of the outer MH
loop. Representative runs are displayed in Figure 5, as well as
the average over all the runs. The results were similar to thetaxonomy case study in several respects, which we also expect to hold for a variety of other domains. The correct theory
was usually learned, with some variation: 9/10 simulations
found the correct theory or a variant of it, and one discovered a partial theory containing only law 1. Only some runs
learned the exact form of law 3, asserting that interactions
are symmetric. Others found variants that were extensionally equivalent to symmetry in this domain, but slightly moreLog posterior

1

Simulation iterations

Figure 5: Representative runs of theory learning in Magnetism.
Dashed lines show different runs. Solid line is the average acrossall runs. Node 1 marks the acquisition of law 1 and the confoundingof magnets with magnetic objects. Lower right panel zooms into theend of the simulation, showing acquisition of the final correct theory.

complex in their logical form. Individual runs of learning
showed discrete jumps with high variability, while averagecase behavior was smooth, with systematic order effects. Law
3 is never learned first, because alone it has no explanatory
power. Either law 1 or the combination of laws 2 and 3 tend
to be learned first, followed by the other, although sometimes
laws 1 and 2 are learned first, followed by law 3. Law 1 tends
to be learned first overall because it is most likely under theprior (which is also the proposal distribution for local searchmoves), and also because, as explained below, it represents areasonable first approximation to the domain’s structure.
The algorithm’s learning dynamics in this case study areparticularly interesting for how they parallel key transitions inchildrens’ cognitive development: restructuring or construction of new concepts, as when one concept differentiates into
two (Carey, 1985). When our simulations of learning aboutmagnetism construct law 1 first, without laws 2 and 3, theyfind a simpler theory capturing many of the observed facts
at the cost of over-generalizing. That is, under law 1 alone,
the optimal setting of the core predicates – the most probable model – equates magnets and magnetic objects, makingp(X) true for both. This is a good first approximation, evenas it collapses two categories of objects with fundamentallydifferent causal properties: the generators of magnetic force(the “magnets”) and the objects on which that force acts (the“magnetic objects”). Only once all three laws have been constructed does the learner come to distinguish between magnets and magnetic objects, reflected in the difference between
the roles played by the two core predicates p(X) and q(X).
Only once law 2 is available does the learner have reason to
restrict the extension of p(X) to just magnets, excluding othermagnetic objects.

Conclusion and Future Directions
We have presented an algorithmic model of theory acquisition
as stochastic search in a hierarchical Bayesian framework andexplored its dynamics in two case studies. We were encouraged by the general pattern of successes on these examples
and by several qualitative parallels with phenomena of hu-

man cognitive development. These results suggest that previous ideal learning analyses of Bayesian theory acquisition canbe realized approximately by algorithms that are cognitively
plausible for child learners, and indeed potentially descriptiveof the dynamics of development.
Previous hierarchical Bayesian analyses of learning abstract knowledge have focused on the role of accumulating
data in driving changes to the learner’s hypotheses (Kemp &Tenenbaum, 2008). In contrast, here we have focused on howchanges to the learner’s theories and abstract concepts are
driven by a different source, the stochastic dynamics of thelearning algorithm. Data-driven and algorithm-driven theorychange can have a similar character, first discovering simpler,rougher approximations to reality and then refining those to
more complex, accurate representations; sometimes changing by adjusting small details, but other times by making
large qualitative transitions or discoveries. In future work weplan to explore further the similarities, differences and interactions between these two drivers of learning dynamics, bothin computational analyses and experimental work. We hopeto establish tighter quantitative correspondences with humanlearning curves in development, as well as with controlledlaboratory studies of theory learning in adults, where some ofthe same mechanisms might be at work. We will also consider a broader range of algorithmic approaches, stochastic
as well as deterministic, evaluating them both as behavioral
models and as effective computational approximations to thetheory search problem for larger domains.
Acknowledgments. We thank Yarden Katz for valuable discussions. This work was funded in part by grants from the McDonnell
Causal Learning Collaborative, AFOSR (FA9550-07-1-0075), ONR(N00014-09-0124) and ARO MURI W911NF-08-1-0242.

References
Carey, S. (1985). Conceptual change in childhood. Cambridge,
MA: MIT Press/Bradford Books.
Collins, A., & Quillian, M. (1969). Retrieval time from semantic
memory. Journal of Verbal Learning and Verbal Behavior, 8,240–247.
Goodman, N. D., Tenenbaum, J. B., Feldman, J., & Griffiths, T. L.
(2008). A rational analysis of rule-based concept learning. Cognitive Science, 32(1), 108—154.
Goodman, N. D., Ullman, T. D., & Tenenbaum, J. B. (2009). Learning a theory of causality. In Proceedings of the 31st annual conference of the cognitive science society.
Katz, Y., Goodman, N. D., Kersting, K., Kemp, C., & Tenenbaum,
J. B. (2008). Modeling semantic cognition as logical dimensionality reduction. Proceedings of the Thirtieth Annual Conferenceof the Cognitive Science Society.
Kemp, C., Goodman, N. D., & Tenenbaum, J. B. (2008). Theory acquisition and the language of thought. In Proceedings of thirtiethannual meeting of the cognitive science society.
Kemp, C., & Tenenbaum, J. B. (2008). The discovery of structuralform. Proceedings of the National Academy of Sciences, 105(31),10687–10692.
Siegler, R. S., & Chen, Z. (1998). Developmental differences inrule learning: A microgenetic analysis. Cognitive Psychology,
36, 273-310.
Tenenbaum, J. B., Griffiths, T. L., & Kemp, C. (2006). Theory-based
bayesian models of inductive learning and reasoning. Trends in
Cognitive Sciences, 10, 309–318.
Wellman, H. M., & Gelman, S. A. (1992). Cognitive development:
Foundational theories of core domains. Annual Review of Psychology, 43, 337-375.