A Rational Analysis of Rule-based Concept Learning
Noah D. Goodman and Joshua B. Tenenbaum
Massachusetts Institute of Technology

Jacob Feldman

Thomas L. Griffiths

Rutgers University

University of California, Berkeley

Revision Submitted October, 2007
Address correspondence to ndg@mit.edu
We propose a new model of human concept learning that provides a rational analysis of learning feature-based concepts. This model is built upon Bayesian inference for a grammaticallystructured hypothesis space—a concept language of logical rules. We compare the model predictions to human generalization judgments in several well-known category learning experiments, and find good agreement for both average and individual participants generalizations.
We further investigate judgments for a broad set of seven-feature concepts—a more natural
setting in several ways—and again find that the model explains human performance.

But what are concepts save formulations andcreations of thought, which, instead of giving
us the true form of objects, show us rather theforms of thought itself?
—Cassirer (1946, p. 7)
The study of concepts—what they are, how they are usedand how they are acquired—has provided one of the mostenduring and compelling windows into the structure of thehuman mind. What we look for in a theory of concepts, andwhat kinds of concepts we look at, depend on the functionsof concepts that interest us. Three intuitions weave throughout the cognitive science literature (see, e.g. Fodor, 1998;
Murphy, 2002):
1. Concepts are mental representations that are used todiscriminate between objects, events, relations, or otherstates of affairs. Cognitive psychologists have paid particularattention to concepts that identify kinds of things—those thatclassify or categorize objects—and such concepts will also
be our focus here. It is clear how an ability to separate objects according to kind could be critical to survival. To take aclassic example, a decision about whether it is appropriate topursue or to flee an intruder depends on a judgment of kind
(prey or predator), and an error in this judgment could havedisastrous consequences.
2. Concepts are learned inductively from the sparse andnoisy data of an uncertain world. Animals make some in-

A preliminary version of this work was presented at the 29th
Annual Meeting of the Cognitive Science Society. We wish to
thank Thomas Palmeri and two anonymous reviewers for very helpful comments. This work was supported by the J. S. McDonnell
Foundation causal learning collaborative initiative (NDG and JBT),
grants from the Air Force Office of Scientific Research (TLG and
JBT), and NSF grant SBE-0339062 (JF).

stinctive discriminations among objects on the basis of kind,but cognition in humans (and probably other species) goesbeyond an innate endowment of conceptual discriminations.
New kind-concepts can be learned, often effortlessly despite
great uncertainty. Even very sparse and noisy evidence, suchas a few randomly encountered examples, can be sufficient
for a young child to accurately grasp a new concept.
3. Many concepts are formed by combining simpler concepts, and the meanings of complex concepts are derived
in systematic ways from the meanings of their constituents.
Concepts are the constituents of thought, and thought isin principle unbounded, though human thinkers are clearlybounded. The “infinite use of finite means” (Humboldt,
1863) can be explained if concepts are constructed, as linguistic structures are constructed, from simpler elements: forexample, morphemes are combined into words, words into
phrases, phrases into more complex phrases and then sentences.
In our view, all of these intuitions about concepts are central and fundamentally correct, yet previous accounts haverarely attempted to (or been able to) do justice to all three.
Early work in cognitive psychology focused on the first
theme, concepts as rules for discriminating among categories
of objects (Bruner, Goodnow, & Austin, 1956). Themes twoand three were also present, but only in limited ways. Researchers examined the processes of learning concepts fromexamples, but in a deductive, puzzle-solving mode more thanan inductive or statistical mode. The discrimination rules
considered were constructed compositionally from simpler
concepts or perceptual features. For instance, one might
study how people learn a concept for picking out objects as“large and red and round”. An important goal of this research
program was to characterize which kinds of concepts were
harder or easier to learn in terms of syntactic measures of aconcept’s complexity, when that concept was expressed as a
combination of simple perceptual features. This approach

2

NOAH D. GOODMAN, JOSHUA B. TENENBAUM, JACOB FELDMAN, THOMAS L. GRIFFITHS

reached its apogee in the work of Shepard, Hovland, andJenkins (1961) and Feldman (2000), who organized possible Boolean concepts (those that discriminate among objects
representable by binary features) into syntactically equivalent families and studied how the syntax was reflected inlearnability.
A second wave of research on concept learning, often
known as the “statistical view” or “similarity-based approach”, emphasized the integration of themes one and twoin the form of inductive learning of statistical distributions or
statistical discrimination functions. These accounts include
prototype theories (Posner & Keele, 1968; Medin & Schaffer,1978), exemplar theories (Shepard & Chang, 1963; Nosofsky, 1986; Kruschke, 1992), and some theories in between(Anderson, 1990; Love, Gureckis, & Medin, 2004). These
theories do not rest on a compositional language for concepts
and so have nothing to say about theme three—how simple
concepts are combined to form more complex structures (Osherson & Smith, 1981).
An important recent development in the statistical tradition has been the rational analysis of concept learningin terms of Bayesian inference (Shepard, 1987; Anderson,
1990; Tenenbaum & Griffiths, 2001). These analyses show
how important aspects of concept learning—such as the
exponential-decay gradient of generalization from exemplars(Shepard, 1987) or the transitions between exemplar and prototype behavior (Anderson, 1990)—can be explained as approximately optimal statistical inference given limited examples. However, these rational analyses have typically been
limited by the need to assume a fixed hypothesis space ofsimple candidate concepts—such as Shepard’s (1987) “consequential regions”: connected regions in a low-dimensional
continuous representation of stimuli. The standard Bayesianframework shows how to do rational inductive learning givensuch a hypothesis space, but not where this hypothesis spacecomes from nor how learners can go beyond the simple concepts it contains when required to do so by the complex patterns of their experience.
The last decade has also seen renewed interest in theidea that concepts are constructed by combination, as a wayof explaining apparently unbounded human conceptual resources. This is especially apparent in accounts of concepts
and concept learning that place compositionality at center
stage (Fodor, 1998; Murphy, 2002). Logical or rule-based
representations are often invoked. Most relevant to our work
here is the rules-plus-exceptions (RULEX) model of Nosofsky, Palmeri, and McKinley (1994), which is based on a setof simple heuristics for constructing classification rules, inthe form of a conjunction of features that identify the concept plus a conjunction of features which identify exceptions.
The RULEX model has achieved strikingly good fits to classic human concept-learning data, including some of the data
sets that motivated statistical accounts, but it too has limitations. Fitting RULEX typically involves adjusting a numberof free parameters, and the model has no clear interpretationin terms of rational statistical approaches to inductive learning. Perhaps most importantly, it is unclear how to extend
the rule-learning heuristics of RULEX to more complex rep-resentations. Therefore, while RULEX uses a compositional
representation, it is unable to fully leverage compositionality.
Our goal here is a model that integrates all three of thesemajor themes from the literature on concepts and concept
learning. Our Rational Rules model combines the inferential power of Bayesian induction with the representational
power of mathematical logic and generative grammar; theformer accounts for how concepts are learned under uncertainty while the latter provides a compositional hypothesis
space of candidate concepts. This paper is only a first step
towards an admittedly ambitious goal, so we restrict our attention to some of the simplest and best-studied cases of concept learning from the cognitive psychology literature. We
hope readers will judge our contribution not by these limits,
but by the insights we develop for how to build a theory that
captures several deep functions of concepts that are rarely
integrated and often held to be incompatible. We think these
insights have considerable generality.
Our approach can best be understood in the tradition ofrational modeling (Anderson, 1990; Oaksford & Chater,
1998), and specifically rational models of generalization(Shepard, 1987; Tenenbaum & Griffiths, 2001). The maindifference with earlier work is the adoption of a qualitatively
richer and more interesting form for the learner’s hypothesis
space. Instead of defining a hypothesis space directly as a setof subsets of objects, with no intrinsic structure or constructive relations between more complex hypotheses and simpler
ones, we work with a compositional hypothesis space generated by a probabilistic grammar. The grammar yields a “concept langauge” which describes a range of concepts varying
greatly in complexity, all generated from a small basis set offeatures or atomic concepts. Hypotheses range from the simplest, single-feature, rules to complex combinations of rules
needed to describe an arbitrary discrimination boundary. The
prior probability of each hypothesis is not specified directly,
by hand, but rather is generated automatically by the grammar in a way that naturally favors the simpler hypotheses. By
performing Bayesian inference over this concept language, alearner can make rational decisions about how to generalize
a novel concept to unseen objects given only a few, potentially noisy, examples of that concept. The resulting model
is successful at predicting human judgments in a range ofconcept learning tasks at both the group and individual level,using a minimum of free parameters and arbitrary processing
assumptions.
This analysis is an advance for several viewpoints on concepts and concept learning. From the vantage of rule-basedmodels of categorization (e.g. RULEX) the Rational Rules
model provides a rational inductive logic explaining why certain rules should be extracted. This naturally complements
the insights of existing process-level accounts by tying therule-learning competency to general principles of learningand representation. To rational statistical accounts of concept learning, the grammar-based approach of the Rational
Rules model contributes a more satisfying account of the
hypothesis space and prior: from simple components thegrammar compactly specifies an infinite, flexible hypothesis
space of structured rules and a prior that controls complexity.

A RATIONAL ANALYSIS OF RULE-BASED CONCEPT LEARNING

For compositionality advocates, we provide a way to use the“language of thought” (Fodor, 1975) (reified in the concept
language of logical rules) to do categorization under uncertainty. That is, the grammar-based induction approach suggests a compelling way to quantitatively relate the languageof thought, already an elegant and rational view of the mind,
to human behavior, even at the level of predicting individual
participants. Finally, by showing that the rational statistical
approach to concepts is compatible with the rule-based, combinatorial, approach, and that the union can accurately predict human behavior, we hope to cut one of the gordian knots
of of modern psychology: the supposed dichotomy between
rules and statistics.

Preliminary Sketch
In this section we will sketch out a notion of concepts, andconcept learning, using the three intuitions above; in the next
section we formalize this discussion.
Concepts are mental representations, that is they are things“in the head” which have some structure that reflects theworld. Since we are concerned with concepts that are used
to discriminate between objects, a natural hypothesis is thatconcepts are simply rules for classifying objects based on
their features. This hypothesis is bolstered by the common
reports of participants in concept learning experiments thatthey “feel as if” they are using a rule (e.g. Armstrong, Gleitman, & Gleitman, 1983). How can we specify the structureof concepts, if we accept as a working hypothesis that they
are rules? Since many concepts are formed by combining
simpler concepts, many of the corresponding rules should bebuilt by combining other rules.
The classic examples of such combinatory syntax comefrom generative grammar, and particularly context-freegrammars (CFGs) (see e.g. Manning & Schütze, 1999; Russell & Norvig, 2002). A CFG is a collection of terminal
symbols, non-terminal symbols, and production rules. For
instance, we could have a CFG with single non-terminalA, two terminals a, b, and two productions A→Aa andA→b. Beginning with A this grammar generates strings
by applying the productions until no non-terminal remains:
A→Aa→Aaa→baa, etc. The strings of terminal symbols
formed by applying production rules are the language specified by the CFG—for the example all strings of the formba...a. Note that production rules specify possible expansions of single symbols, and can be seen as combination operations “in reverse” (for instance reversing the production
A→Aa allows the combination of an A-constituent with theprimitive a to get another A-constituent). We adopt CFGs
to provide the combinatory syntax for our concepts, thus
we have a concept language describing the representationsof rules. However, a CFG describes only the structure of
representations, if this structure is to influence the use ofconcepts it must be mirrored in the meaning we assign toa representation—each syntactic combination of rules must
give us a new rule able to discriminate among objects in theworld. Fortunately, if we think of rules as functions fromobjects to truth values (where T rue is arbitrarily assigned to3“in the concept”), then there is a natural set of combination
operations: the logical connectives. Indeed, classical logic
is a paradigmatic example of a language with CFG syntax,
a semantics of discriminative rules, and combination operations that work on both levels. If we supplement with a set ofprimitive concepts (which are features or, perhaps, other preexisting concepts), mathematical logic appears to provide a
simple and intuitive framework for concepts.
Before we embrace this framework for concepts, weshould reflect on the reasons why rule-based representations
have had such a troubled past in psychology. Since an underlying commitment of rule-based accounts (at least as classically interpreted) is that concepts have deterministic definitions, there seems to be no room for one object which satisfies the definition to be a “better” example than another.
Rosch and colleagues showed that people are very willingto assign graded typicality to concepts, and that this gradation is reflected in many aspects of concept use (e.g. Mervis& Rosch, 1981). Combined with the difficulty of identifying definitions for common concepts (Wittgenstein, 1953),
these results led many authors to suggest that the organizing
principle of concepts is similarity—for example via “family resemblance” among exemplars—not rules. The conventional wisdom regarding the virtues of rule-based versus
similarity-based models of cognition is that “rules provide
precision, expressiveness, and generativity, and similarity
provides flexibility and the means to deal with uncertainty”(Sloman, Love, & Ahn, 1998). Modern cognitive psychology has been especially concerned with the “fuzzy edges”—
capturing the ways that people deal with uncertainty—so it isnatural that similarity-based models of concept learning havecome to dominate. Is it true, however, that proper treatmentof uncertainty is antithetical to rule-based representation? In
concept learning uncertainty arises primarily in two ways:
examples are unreliable, and available evidence is sparse. We
believe that these can be addressed in ways that are agnostic
to representation: allow that some experiences are outliers,
and employ a strong inductive bias, respectively. Both ofthese responses to uncertainty can be realized by viewing
concept learning as an inductive inference problem.
A general approach to the analysis of inductive learning problems has emerged in recent years (Anderson, 1990;
Tenenbaum, 1999b; Chater & Oaksford, 1999). Under thisapproach a set of hypotheses is posited, and degrees of belief
are assigned using Bayesian statistics. This assignment relies
on: a description of the data space from which input is drawn,
a space of hypotheses, a prior probability function over thesehypotheses, and a likelihood function relating each hypothesis to the data. The prior probability, P(h), describes thebelief in hypothesis h before any data is seen, and hence captures prior knowledge. The likelihood, P(d|h), describes thedata one would expect to observe if hypothesis h were correct. With these components, inductive learning can be described very simply: we wish to find the appropriate degreeof belief in each hypothesis given some observed data—theposterior probability P(h|d). Bayes’ theorem tells us how to

4

NOAH D. GOODMAN, JOSHUA B. TENENBAUM, JACOB FELDMAN, THOMAS L. GRIFFITHS

compute this probability,
P(h|d) ∝ P(h)P(d|h),(1)

identifying the posterior probability as proportional to the
product of the prior and the likelihood. This Bayesian posterior provides a rational analysis of inductive learning: acoherent integration of evidence and a priori knowledge into
posterior beliefs (optimal within the specified learning context).
By viewing concept acquisition as an inductive problem,
we may employ this Bayesian framework to describe thelearning of a concept from examples. As described earlier,
our hypothesis space is the collection of all phrases in agrammatically-generated concept language. Since each concept of this language is a classification rule, a natural likelihood is given by simply evaluating this rule on the examples:the data have zero probability if they disagree with the classification rule, and constant probability otherwise. However,to account for the unreliability of examples, we will allow
non-zero probability for a data set, even if some examples
are misclassified. That is, we assume that there is a small
probability that any example is an outlier, which should be
ignored. We will see in the next section that this outlier
assumption combines with rule-evaluation to give a simple
likelihood function, which decreases exponentially with thenumber of “misclassifications” of the examples.
In Bayesian models the prior, P(h), provides the inductive
bias needed to solve under-constrained learning problems.
Hence, equipping the concept language with an appropriate prior can address the uncertainty engendered by sparseevidence. A natural prior follows by extending the grammar into a probabilistic context free grammar. By viewing
the generative process for phrases, which is specified by thegrammar, as a probabilistic process, we get a probability distribution on phrases of the concept language. We will seethat this prior has a syntactic complexity bias: the prior probability of a combined rule is less than the prior probabilityof either component. In fact, the prior probability of a ruledecreases, roughly exponentially, in the number of symbols
used to express it. There is some empirical evidence thatthe number of primitive feature symbols in a rule, called its
Boolean complexity, is relevant to the inductive bias of human concept learning. Indeed, Feldman (2000) found thatthe Boolean complexity is a good predictor of the difficultyof remembering a wide variety of binary concepts. Feldman(2006) showed that other aspects of the algebraic complexityof concepts predict further facets of human learning and use.
This suggests that the natural inductive bias provided by thegrammar of our concept language may be sufficient to describe human learning, and particularly the ways that humanlearning copes with the uncertainty of sparse examples.
Using this formulation of concept learning as a Bayesian
induction problem, we can address, within a rule-based
framework, the uncertainty inherent in concept learning.
How does this overcome the determinism of rule-based representations, which was such a stumbling block to early theories? It has been noted before (Shepard, 1987; Tenenbaum,2000) that graded effects can arise out of mixtures of deterministic representations, and that such mixtures result fromrational Bayesian use of deterministic representations under
uncertainty. Though our ideal Bayesian learner is committed
to there being a correct definition for each concept, there israrely enough information to determine this correct definition completely. Instead, the posterior belief function willbe spread over many different definitions. This spread canresult in graded, similarity-like effects in the classification
behavior of the ideal agent, or in more deterministic rule-likeclassification, depending on the pattern of examples the agent
observes and the shape of the posterior distribution they giverise to.

An Analysis of Concept Learning
In light of the above discussion, we wish to formulate
a concept language of rules, and analyze the behavior of arational agent learning concepts expressed in this language.
This analysis will describe an ideal concept learner that satisfies the three intuitions with which we began this paper. In
later sections we will explore the relationship between human concept acquisition and this ideal learning model.
The learning problem can be phrased, using the Bayesian
induction formalism, as that of determining the posterior
probability P(F|E, `(E)), where F ranges over formulae inthe concept language, E is the set of observed example objects (possibly with repeats) and `(E) are the observed labels.
Thus concept learning will roughly amount to “probabilistic
parsing” of labeled examples into representations of the concept language. (We consider a single labeled concept, thus`(x) ∈ {1, 0} indicates whether x is an example or a nonexample of the concept. An example is given in Table 1,
which we will use throughout this section.) The posterior
may be expressed (through Bayes’ formula) as:
P(F|E, `(E)) ∝ P(F)P(E, `(E)|F)(2)

To use this relationship we will need our concept language(which describes the hypothesis space), the prior probability,
P(F), and a likelihood function, P(E, `(E)|F).

Concept Representation
The concept language in which we will represent rules isa fragment of first-order logic. This will later allow us to
use the standard truth-evaluation procedure of mathematical
logic in defining our likelihood. The terminal symbols of
the language (those which can appear in finished rules) arelogical connectives (∧, ∨, ⇔), grouping symbols, a quantifier over objects (∀ x) with quantified variable x, and a setof feature predicates. The feature predicates can be thoughtof as simple preexisting concepts, or as perceptual primitives. (Thus each concept, once learned, potentially becomesa “feature” for future concepts; for a related view see Schyns,
Goldstone, and Thibaut (1998).) We will focus on simple
feature predicates formed from functions fi (x), which reportthe value of a physical feature, and operators =c, <c, and >c,which represents comparison with constant c. Initially eachA RATIONAL ANALYSIS OF RULE-BASED CONCEPT LEARNING

Table 1
A set of labeled examples E={A1,...,A5,B1,...,B4} (fromMedin & Schaffer (1978)). This example set admits, for example, the simple definition D1 : f1 (x)=0, by assuming A5
and B1 are outliers, and the more complex definition D2 :( f1 (x)=0 ∧ f3 (x)=0) ∨ ( f2 (x)=0 ∧ f4 (x)=0), with no outliers.
ObjectLabel `
Feature Values
A1
1
0001
A2
1
0101
A3
1
0100
A4
1
0010
A5
1
1000
B1
0
0011
B2
0
1001
B3
0
1110
B4
0
1111

th

feature predicate is of the form fi (x)=c (read “the i featureof object x has value c”), with Boolean values (c ∈ {0, 1}).
The extension to continuous-valued features by using the inequality comparison operators is straightforward, and will be
used later in the paper.
(S1)
(D1)
(D2)
(C1)
(C2)
(P1)

S → ∀x `(x)⇔(D)
D → (C) ∨ D
D → False
C → P∧C
C → T rue
P → F1..
.

(PN)(F1 1)(F1 2)

P → FNF1 → f1 (x) = 1
F1 → f1 (x) = 0..
.

(FN 1)(FN 2)F N → fN (x) = 1
F N → fN (x) = 0

Figure 1. Production rules of the DNF grammar. S is the startsymbol, and D, C, P, Fi the other non-terminals. Productions (Fi 1)
and (Fi 2) can be naturally extended to “decision boundary” predicates, e.g., F1 → f1 (x) < 2.

The set of formulae in our language is generated by thecontext-free “disjunctive normal form”, or DNF, grammar,
Fig. 1. Informally, each formula provides a “definition” andasserts that that definition must hold anytime the label istrue1 : ∀x `(x)⇔D. Each definition has the form of a standard dictionary entry: a set of alternative “senses”, each ofwhich is a list of necessary and sufficient conditions on thefeatures. For example, the labeled examples in Table 1 admit
an imperfect definition with a single sense ( f1 (x)=0) and acomplex definition with two senses ( f1 (x)=0 ∧ f3 (x)=0) and( f2 (x)=0 ∧ f4 (x)=0). More formally, each D non-terminal
becomes, by productions (D1) and (D2), a disjunction of C

5

non-terminals (the “senses”); each C-term becomes a conjunction of predicate P-terms, and each P-term becomes a
specific feature predicate. Let us illustrate the generative process of the DNF grammar by considering the two examples
from Table 1.
S1 :
D1 :

S
∀x !(x)⇔(D)D2 :∀x !(x)⇔((C) ∨ D)

C1 :∀x !(x)⇔((C) ∨ False)C2 :∀x !(x)⇔((P ∧ C) ∨ False)

P1 :∀x !(x)⇔((P ∧ True) ∨ False)

F1 2 :∀x !(x)⇔((F1 ∧ True) ∨ False)∀x !(x)⇔(((f1 (x)=0) ∧ True) ∨ False)

Figure 2. Derivation of a formula from the DNF grammar.

First consider the derivation illustrated in Fig. 2. Beginning with the start symbol, S , the first step is to use production (S1) to derive ∀x `(x)⇔D. Next we expand the symbol
D by applying production (D1), then production (D2). This
leads to a single conjunct term:∀x `(x)⇔((C) ∨ False)
We continue by expanding the C-term using productions(C1) then (C2):∀x `(x)⇔((P ∧ T rue) ∨ False)
Using production (P1), the P-term is replaced with F1 , andusing production (F1 2) this becomes an assertion of the value
for the first feature2 :∀x `(x)⇔( f1 (x)=0)
We have thus derived a simple formula incorporating definition D1 for the concept of Table 1.
More complex derivations are also possible from thisgrammar. For example, let us consider the derivation of
the complex definition D2 from Table 1. Beginning with∀x `(x)⇔D, we expand the symbol D by applying production (D1) twice (instead of once), then production (D2). This1
In later sections we often write only the definition part of theformulae, for clarity.
2
The terminal symbols T rue and False stand for logical Trueand False—they are used to conveniently terminate a string of conjunctions or disjunctions, respectively, and can be ignored. We now
drop them, and unnecessary parentheses, for clarity.

6

NOAH D. GOODMAN, JOSHUA B. TENENBAUM, JACOB FELDMAN, THOMAS L. GRIFFITHS

leads to a disjunction of two conjunct terms (the two “senses”
of the definition). We now have the rule:∀x `(x)⇔(C ∨ C)
Recall that C is a non-terminal, so each of these C-terms
can ultimately result in a distinct substring (and similarly forthe other non-terminals). Each non-terminal symbol C leads,
by productions (C1) and (C2), to a conjunction of predicate
terms:∀x `(x)⇔((P ∧ P) ∨ (P ∧ P))
Using production(s) (Pi), each predicate term becomes a feature predicate Fi , for one of the N features:∀x `(x)⇔( F1 ∧ F3 ) ∨ (F2 ∧ F4 ))Finally, with productions (Fi 1) and (Fi 2), each feature predicate becomes an assertion that the ith feature has a particularvalue ( f1 (x)=0, etc.):∀x `(x)⇔( f1 (x)=0 ∧ f3 (x)=0) ∨ ( f2 (x)=0 ∧ f4 (x)=0))
Informally, this means that the label holds when: f1 and f3
are zero, or f2 and f4 are zero—this accurately classifies all
the examples of Table 1.
Thus far we have used the generative nature of the DNF
grammar only to specify which sequences of symbols aresyntactically well formed (that is, those which represent valid
concepts). However, generative processes can also be used
to induce probability distributions: we can induce a probability distribution over the formulae of the concept language
by providing a probability for each choice in the derivation
process. Thus, the simple generative process that allows us tobuild syntactic formulae will also provide a prior over theseformulae.

A Syntactic Prior
As illustrated above, each formula is generated from thestart symbol S by a derivation: a sequence of productions,each replacing a single non-terminal, that ends when there
are no non-terminals left to replace. At each step of a derivation we choose from among the productions which could be
used to expand the next non-terminal symbol3 —and if weassign a probability to each such choice we will have a probability for the complete derivation. Hence, by supplementing
the context-free grammar with probabilities for the productions we get a prior over the formulae of the language: eachproduction choice in a derivation is assigned a probability,
and the probability of the complete derivation is the productof the probabilities for these choices. Of course, the set of
production probabilities, τ, must sum to one for each nonterminal symbol. The probability of a derivation DerivF forformula F is:Y
P(DerivF |G, τ) =
τ(s),
(3)
s∈DerivF

where s∈DerivF are the productions in the derivation, τ(s)the probability of each, and G denotes the grammar. The

DNF grammar is unambiguous—there is a single derivationfor each well-formed formula4 —so Eq. 3 gives the probability of the formula itself: P(F|G, τ) = P(DerivF |G, τ). Fora generic context-free grammar, P(F|G, τ) would instead bethe sum of the probabilities of its derivations. This would
complicate our analysis, but not in any critical way.
Note that the prior in Eq. 3 captures a syntactic simplicity
bias: smaller formulae have shorter derivations, thus higher
prior probability. However, the precise values of the production probabilities may affect the inductive bias in importantways. For instance, if production (D2) (of the DNF grammar,
Fig. 1) is much more likely that production (D1), but productions (C1) and (C2) are about equally likely, then complexity
as measured by the number of disjunctions will be penalized
more heavily than complexity as measured by the number ofconjunctions. Given this sensitivity, how should a rational
agent choose production probabilities? Any specific choice
would be ad-hoc, and would preclude learning correct values from experience. Rather than committing to a specificchoice, we can maintain uncertainty over τ. Since we haveno a priori reason to prefer one set of values for τ to another
we assume a uniform prior over the possible values—that is,
we apply the principle of indifference (Jaynes, 2003). Now
the prior probability is over both the formula and the production probabilities: P(F, τ|G). However, since we are primarily concerned with learning formulae F, we marginalize outτ (see Appendix A). After some simplification this leads tothe expression:
P(F|G) =β(CY (F) + 1).
β(1)Y∈ non-terminals of GY

(4)Here β(c) is the multinomial beta function (or normalizing constant of the Dirichlet distribution, see Appendix A).
The vector CY (F) counts the uses of productions for nonterminal Y: it has an entry for each production s of Y,
equal to the number of times s was used in DerivF to replace Y. For instance, in the above derivation of the formula ∀x `(x)⇔( f1 (x)=0), the non-terminal D was expanded
once with derivation (2) and once with derivation (3). Thus
CD (F)=(1, 1), and D contributes β(2,2)β(1,1) = 0.1667 to the product in Eq. 4. In contrast, the non-terminal F2 is neverused in this derivation, so CF2 (F)=(0, 0), and F2 contributes
β(1,1)β(1,1) = 1 (i.e. nothing) to the product.
This prior probability has several important properties,
which we now illustrate with examples. First, because themultinomial beta function is monotonically decreasing ineach argument (over the domain which concerns us), thisprior will again have a complexity bias penalizing longer
3
There are multiple orders for any derivation, but this freedom
can be eliminated by always expanding the right-most non-terminal
first. We thus treat derivations as uniquely ordered, without loss ofgenerality.
4
To see this, note that it would change nothing to add additional
parentheses in productions (D1) and (C1), making the formulae
fully-parenthesized. The derivation of a formula could then be read
off the structure of its parentheses.

A RATIONAL ANALYSIS OF RULE-BASED CONCEPT LEARNING

derivations (hence longer formulae). For instance, we seein Fig. 2 that the formula ∀x `(x)⇔( f1 (x)=0) is derived byapplying productions S1, D1, D2, C1, C2, P1, and F1 2. The
prior probability of this formula is computed by applying
Eq. 4, which leads to the product:
S

D

C

F1

P

z}|{ z }| { z }| { z }| { z }| {β(2)β(2, 2) β(2, 2) β(2, 1, 1, 1) β(2, 1)
×
×
×
×
β(1)
β(1, 1) β(1, 1) β(1, 1, 1, 1) β(1, 1)= 1.7 × 10−3 .
(Each term of this product comes from the non-terminal
written over it; the remaining non-terminals are not used
for this formula.) In contrast the more complex formula∀x `(x)⇔(( f1 (x)=0 ∧ f3 (x)=0) ∨ ( f2 (x)=0 ∧ f4 (x)=0)) uses anumber of the productions repeatedly (as illustrated above),and has prior probability:
S

C

D

P

z}|{ z }| { z }| { z }| {β(2)β(3, 2) β(5, 3) β(2, 2, 2, 2)
×
×
×
×
β(1)
β(1, 1) β(1, 1) β(1, 1, 1, 1)
F3

F2

F1

F4

z }| { z }| { z }| { z }| {β(2, 1) β(2, 1) β(2, 1) β(2, 1)×××β(1, 1) β(1, 1) β(1, 1) β(1, 1)= 5.9 × 10−8 .
Again, this complexity bias follows from the monotonicityof the beta functions, and is the dominant contribution to theprior.
Another, subtler, contribution to the behavior of the priorcomes from the property: β(i, j, ...) < β(i + 1, j − 1, ...) if
i ≥ j. This means, in particular, that the prior favors reuseof features over use of multiple features. For instance, if wealter the above formula into ∀x `(x)⇔(( f1 (x)=0 ∧ f3 (x)=0) ∨( f1 (x)=0 ∧ f4 (x)=0)) (so that we use feature f1 twice, and f2
never), the formula receives a slightly higher prior probability:
S

C

D

P

z}|{ z }| { z }| { z }| {β(3, 2) β(5, 3) β(3, 1, 2, 2)
β(2)
×
×
×
×
β(1)
β(1, 1) β(1, 1) β(1, 1, 1, 1)
F1

F3

F4

z }| { z }| { z }| {β(3, 1) β(2, 1) β(2, 1)××β(1, 1) β(1, 1) β(1, 1)= 1.6 × 10−7 .
We will show below that this property of the prior allows us
to naturally capture certain “selective attention” effects exhibited by human learners.

Likelihood: Evaluation and Outliers
We have given an informal description of the meaning of
formulae in our concept language—they are definitions in
disjunctive normal form. This meaning is captured formallyby the likelihood function P(E, `(E)|F), which specifies the7

probability of a “world” of labeled examples, given a formula. Here we present the likelihood function, with intuitive
justification; in Appendix B we provide a formal derivationof this likelihood.
Our informal description above suggests that examples
should be labeled consistently with the classification rule,
so we might constrain P(E, `(E)|F) to be uniform on worlds
where the formula is true5 , and zero otherwise. If we knewthat the observed labels were correct, and we required an explanation for each observation, this constraint would determine the likelihood. However, we wish to allow concepts
that explain only some of the observations. For instance, it
seems unreasonable to ignore the definition D1 of Table 1,
which is quite simple and correctly predicts seven of the nine
examples (though it misses A5 and B1). Hence we assume
that there is a small probability that any given example is an
outlier (ie. an unexplainable observation which should be excluded from induction). For a given partition of the examples
into outliers and in-liers the likelihood will still be a simple
step function, but we must sum over outlier sets. This sum
produces an exponential gradient6 (see Appendix B), and thelikelihood becomes:
P(`(E), E|F) ∝ e−bQ` (F) ,(5)where Q` (F) is the number of example objects which do notsatisfy the definition asserted by F. Note that this likelihood
decreases exponentially with the number of mislabeled examples, since they must be treated as outliers, but is neverzero. The probability that any given example is an outlier is
e−b —thus the parameter b is a measure of the a prior probability that an example is an outlier. (As we will see below,
multiple exposures to an example will effectively decrease
the probability that it is an outlier.)
Returning to the examples of Table 1, the simpler definition D1 incorrectly classifies examples A5 and B1, hence
P(`(E), E|F D1 ) ∝ e−2b . The complex definition D2 correctlyclassifies all examples, hence P(`(E), E|F D2 ) ∝ 1.

The Rational Rules Model
The above likelihood and prior, combined using Bayes’rule, constitute a model of concept learning, which we callthe Rational Rules model (RRDNF , to indicate the grammar). The posterior probability of formula F according tothis model is:


Y



P(F|E, `(E)) ∝ β(CY (F) + 1) e−bQ` (F) .
Y∈ non-terminals of G

(6)
In Table 2 we show the highest posterior formulae given theexamples in Table 1, according to the RRDNF model.
5
The concept language generates formulae of predicate logic.
Hence we inherit from the standard truth-functional semantics ofmathematical logic a procedure allowing us to decide whether theformula is true.
6
This is similar to the derivation of Shepard’s Law of Generalization (Shepard, 1987) by a sum over consequential regions.

8

NOAH D. GOODMAN, JOSHUA B. TENENBAUM, JACOB FELDMAN, THOMAS L. GRIFFITHS

The generalization probability that a test object t has label`(t)=1 is given by:
X
P(`(t)=1|E, `(E)) =P(`(t)=1|F)P(F|E, `(E)) (7)F

where P(`(t)=1|F) reflects the classification predicted by formula F (assuming t is not an outlier).
Let us summarize the ingredients of the Rational Rules
model. At the most general level, we have assumed (i) thatconcepts are expressed in a grammatically defined concept
language; (ii) that the generative process of this grammar
leads to a prior over formulae in the language; and, (iii) that
there is a likelihood which captures evaluation of concepts
and allows that some examples may be outliers. These ingredients are combined by the standard techniques of Bayesian
induction, and, all together, give a general framework for“grammar-based induction” (N. D. Goodman, Tenenbaum,
Griffiths, & Feldman, In Press). The particular grammar wehave used, the DNF grammar, describes concepts as classification rules: disjunctive normal form “definitions” for a concept label. This grammar incorporates some structural priorknowledge: labels are very special features (Love, 2002),
which apply to an object exactly when the definition is satisfied, and conjunctions of feature values are useful “entries”
in the definition. The final ingredient of the model is one
free parameter, the outlier probability, which describes theprior probability that an example is an outlier which shouldbe ignored.
Each of the three intuitions about concepts and concept
learning that initially seeded our discussion is captured in theposterior belief function of the Rational Rules model, Eq. 6.
First, each concept described in the concept language is aclassification rule that determines when its label can be applied. Since the posterior is seldom degenerate, there willusually remain uncertainty about which rule corresponds toa given concept label. Second, this posterior deals gracefully
with uncertainty by including a strong inductive bias, andthe possibility of treating some examples as outliers; these
two factors imply a trade-off between explanatory completeness and conceptual parsimony. Finally, concepts which canbe expressed in the concept language are built by combining
primitive concepts (the feature predicates); and these combinations are mirrored in the meaning of the concepts, throughthe likelihood.

Bridging to Empirical Studies
In this section we present a few additional assumptions
and tools that we will need in order to bridge from the rational model to experimental results.
Individuals and choice rules. The posterior and generalization probabilities, Eqs. 6 and 7, capture the inferencesof an ideal learner. However, to make experimental predictions, we will require an auxiliary hypothesis—a choicerule—describing the judgments made by individual learners on classification questions. One possibility, probability
matching, is to assume that individuals maintain (in somesense) the full posterior over formulae, and match the expected probability of labels when it comes time to make achoice. The expected portion of participants judging that atest object “t is an `”, would then be equal to the generalization probability, Eq. 7. The probability matching assumption is implicit in much of the literature on Bayesian learning(e.g. Tenenbaum & Griffiths, 2001), and also prevalent in the
broader literature on decision making, via the Luce choicerule (Luce, 1959).
A second possibility, hypothesis sampling, is that each inidividual has one (or a few) hypotheses drawn from the posterior over formulae. (That is, by the end of learning eachindividual has acquired such a hypothesis—we may remain
agnostic about the process by which this is achieved.) Eachindividual then gives the most likely response to any query,given their hypothesis. The expected probability of generalization responses, averaged over a large enough population,is again given by Eq. 7. Thus the prediction for the population average of responses is identical between the probability
matching and hypothesis sampling assumptions.
We favor the hypothesis sampling assumption for threereasons. First, it seems intuitively very plausible that individuals maintain only one, or a few, hypotheses rather thanan entire distribution. This allows for the possibility that theprocess of learning resembles hypothesis testing, while sequentially sampling from the Bayesian posterior (as in Sanborn, Griffiths, & Navarro, 2006). Second, maintaining asmall number of hypotheses is an efficient use of bounded
computational resources. Indeed, memory constraints werea primary motivating consideration for the RULEX model.
Finally, there is some experimental evidence that supports
the idea that individuals in standard laboratory tasks learn asmall number of rules. For instance, the classification behavior exhibited by individuals in the experiments of Nosofsky et al. (1994); Nosofsky and Palmeri (1998); Johansen
and Palmeri (2002) are suggestive of hypothesis sampling(and the idea of idiosyncratic rule formation discussed bythese authors is similar to the hypothesis sampling assumption). Lamberts (2000), has shown that over a large number of transfer blocks individual participants respond with
far lower variance than expected based on the group average.
This is consistent with the idea that individuals learn a nearly
deterministic representation of concepts, such as a small setof alternative rules.
Where it is useful to be explicit, we phrase our discussion
below in terms of the hypothesis sampling assumption. (Thewider implications of this assumption will be considered in
the General Discussion.) We further assume that each participant gives slightly noisy responses: there is a probability η ofgiving the subjectively wrong answer. This captures simple
decision noise and a host of pragmatic effects (motor noise,
inattention, boredom, etc.), and is a common assumption inmodels of concept learning (cf. Nosofsky et al., 1994; Smith& Minda, 1998). The effect of this response noise on thepredicted (aggregate) response probability, Eq. 7, is a simple
linear transformation—this parameter is thus absorbed into
the correlation when R2 values are used to compare with human data. Below we explicitly fit η only when discussing the

A RATIONAL ANALYSIS OF RULE-BASED CONCEPT LEARNING

9Table 2The best formulae according to the RRDNF model (with posterior probabilities) for the examples of Table 1, at two different
values of the parameter b. (Only the “definition” part of the formulae are shown.) For small b the model favors single-featurerules, weighted by their predictiveness; for larger b the model begins to favor complex formulae.
b=6
b=1
0.234 f3 (x)=00.059 (( f1 (x)=0) ∧ ( f3 (x)=0)) ∨ (( f2 (x)=0) ∧ ( f4 (x)=0))
0.234 f1 (x)=00.027 f1 (x)=00.086 f4 (x)=00.027 f3 (x)=00.031 f2 (x)=00.005 (( f1 (x)=0) ∧ ( f4 (x)=0)) ∨ ( f3 (x)=0)

performance of individual participants.
Parameter fitting. The Rational Rules model describedabove has two free parameters: the outlier parameter b,
and the response noise parameter η. In the results reported
below we have simulated the model for outlier parameter b∈{1, . . . , 8} (these values were chosen for convenienceonly). When only a single fit is reported it is the bestfrom among these eight parameter values. It is likely that
this rough optimization does not provide the best possible
fits of the RRDNF model to human data, but it is sufficient
to demonstrate the ability of the model predict human responses. Where η is explicitly fit, it is fit by grid search.
The model predictions were approximated by Monte
Carlo simulation (30,000 samples for each run, with five runs
averaged for most reported results). Details of the Monte
Carlo algorithm and simulation procedure can be found in
Appendix C.
Blocked-learning experiments. In many of the experiments considered below participants were trained on the category using a blocked-learning paradigm: each example in
the training set was presented once per block, and blocks
were presented until the training set could be classified accurately (relative to a predetermined threshold). It is often
the case that different effects occur as training proceeds, andthese effects can be tricky to capture in a rational model. One
advantage of the Rational Rules model is that the effect of
repeated examples on the posterior is related to the value ofthe outlier parameter b. Indeed, it is apparent from Eq. 6that the Rational Rules model with outlier parameter b presented with N identical blocks of examples is equivalent to
the model presented with only one block, but with parameterb0 = b·N. This makes intuitive sense: the more often an
example is seen, the less likely it is to be an outlier. Thus wemay roughly model the course of human learning by varying the b parameter—effectively assuming a constant outlier
probability while increasing the number of trials.
Two-category experiments. In several of the experiments
considered below participants were required to distinguishbetween two categories, A and B, which were mutually exclusive. (As opposed to distinguishing between a category
A and it’s complement “not A”.) For simplicity in fitting themodel we assume that the population is an even mixture ofpeople who take A to be the main category, and B the con-trast category, with vice versa. Since these experiments have
similar numbers of A and B examples, this is probably a reasonable initial assumption. (A more realistic treatment would
follow by treating these two categories as a system of interrelated concepts (Goldstone, 1996)—we leave this extension
to future work.)
Descriptive measures of the posterior. We will shortly try
to understand the behavior of the model in various concept
learning experiments. Since the posterior (Eq. 6) describes
what has been learned by the model, it will be useful to havea few descriptive measures of the posterior. In particular, we
would like to know the relative importance of formulae withvarious properties.
The Boolean complexity of a formula (Feldman, 2000),
written cplx(F), is the number of feature predicates in theformula: a good overall measure of syntactic complexity.
For example, ( f1 (x)=1) has complexity 1, while ( f2 (x)=0) ∧( f1 (x)=1) has complexity 2. The posterior weight of formulae with complexity C is the total probability under the posterior of such formulae:
X
P(F|E, `(E)).
(8)
F st. cplx(F)=Cfi ∈F)
Define the weight of feature i in formula F to be count(cplx(F) ,that is, the number of times this feature is used divided by
the complexity of the formula. The posterior feature weightis the posterior expectation of this weight:
X count( fi ∈F)
P(F|E, `(E)).
(9)
cplx(F)F

The posterior feature weights are a measure of the relative
importance of the features, as estimated by the model. Indeed, it can be shown that Eq. 9 is related in a simple (monotonic) way to the posterior expectation of the production
probability for production P → Fi (see Appendix D).

Comparison with Human
Category Learning
In the preceding sections we have presented a Bayesiananalysis of concept learning assuming that concepts are represented in a concept language of rules. In this section we
begin to explore the extent to which this analysis captures human learning by comparing the RRDNF model to human data

10

NOAH D. GOODMAN, JOSHUA B. TENENBAUM, JACOB FELDMAN, THOMAS L. GRIFFITHS

from several influential experiments. We consider four experiments from the Boolean concept learning literature thathave often been used as tests of modeling efforts (e.g. Nosofsky et al., 1994), and one concept based on non-Boolean features which has been used in a similar way (e.g. Nosofsky& Palmeri, 1998). We close this section by considering thewithin-participants pattern of generalization judgments – amore refined test of the model.
We use data from human experiments in which physicalfeatures were counter-balanced against logical features. So,
for instance, in an experiment with the two physical features
Length and Angle, half of participants would see Angle playing the role of logical feature f1 and for the other half Angle would be f2 . This counter-balancing allows us to focus
on foundational questions about concept formation, withoutworrying over the relative saliency of the physical properties
used to represent features. Except where otherwise notedphysical features in these experiments were along psychologically separable dimensions.

Prototype Enhancement and Typicality Effects
The second experiment of Medin and Schaffer (1978),among the first studies of ill-defined categories, used the “54” category structure shown in Table 3 (we consider the human data from the Nosofsky et al. (1994) replication of thisexperiment, which counter-balanced physical feature assignments). This experiment is a common first test of the abilityof a model to predict human generalizations on novel stimuli.
The overall fit of the Rational Rules model (Fig. 3) isgood: R2 =0.98. Other models of concept learning arealso able to fit this data quite well: for instance R2 =0.98
for RULEX, and R2 =0.96 for the context model (Medin &Schaffer, 1978). However, the Rational Rules model has
only a single parameter (the outlier parameter), while eachof these models has four or more free parameters; indeed,
the full RULEX model has nine free parameters.
The best (highest posterior probability) formulae according to the Rational Rules model are shown in Table 2. For
small values of b (those that are more permissive of outliers),
the best formulae are single dimension rules. Note that theposterior probabilities of these formulae reflect their predictiveness on the training examples, and in particular that formula f4 (x)=0, though not the best, has significantly greater
posterior probability than formula f2 (x)=0. In Fig. 4 we haveplotted the posterior complexity weights and the posteriorfeature weights of the Rational Rules model for b=1. We seethat this pattern is maintained when considering the entire
posterior: most of the weight is on simple formulae along
features 1 and 3, followed by feature 4, then feature 2.
The object T3=0000 is the prototype of category A, inthe sense that most of the examples of category A are similar to this object (differ in only one feature) while most of
the examples of category B are dissimilar. Though it neveroccurs in the training set, the importance of this prototype
is reflected in the human transfer judgments (Table 3 andFig. 3): T3 is, by far, the most likely transfer object to beclassified as category A. The Rational Rules model predicts

this “prototype enhancement effect” (Posner & Keele, 1968).
This prediction results because the highest posterior probability formulae (Table 2) all agree on the categorization ofT3, so combine (together with lower probability formulae)
to enhance the probability that T3 is in category A.
The degree of typicality, or recognition rate for training
examples, is often taken as a useful proxy for category centrality (Mervis & Rosch, 1981) because it correlates withmany of the same experimental measures (such as reactiontime). In Table 3 and Fig. 3, we see greater typicality forthe prototype of category B, the object B4=1111, than forother training examples: though presented equally often it isclassed into category B far more often. The Rational Rules
model also predicts this typicality effect, in a manner similar to prototype enhancement: most high probability formulae agree on the classification of B4, while fewer agree on
the classifications of the other training examples. However,note that the typicality gradient of training examples is notentirely determined by similarity to the prototypes. For instance, training example A2 and A1 are equally typical ofcategory A and more typical than examples A4 and A5 (according to both humans and the Rational Rules model), however A1, A3, and A4 are each more similar to the prototype,
T3, than is A2. This finding has often been taken as evidenceof exemplar memory (Medin & Schaffer, 1978). However,for the Rational Rules model the enhancement of A2 reflects
the greater reliance on rules involving features 1 and 3 (which
support the classification of A2, but not of A4 or A5) and therelative unimportance of feature 2 (the only feature on which
A1 and A2 differ).
In these model results graded typicality effects arise out of
deterministic rules by maintaining uncertainty over the rulethat defines the concept. Following the hypothesis samplingassumption outlined above, we might expect a single individual to learn a small set of rules, sampled from the posterior. Objects which satisfy all these rules would be considered more typical of the concept (after all, they are partof the concept under any of the competing definitions) thanobjects which satisfy only some. (This is similar to the proposal of Lakoff (1987), in which “idealized cognitive models” of a concept are composed of several “entries”; objects
which satisfy many entries are considered better examplesof the concept than those which satisfy few.) In this way
similar graded typicality judgments would be expected fromindividuals, as from group averages.
Prototype and typicality effects led to great interest among
the psychological community in prototype-based models ofconcept learning (e.g. Reed, 1972). Many such models
represent prototypes as points in a similarity space. Because the curve equidistant to two points in a metric space
is a line, these prototype models predict that linearly separable categories—those which admit a linear discriminantboundary—will be easier to learn than those that are not linearly separable. Medin and Schwanenflugel (1981) tested
this prediction in four experiments, finding that linearly separable concepts could be harder for human participants tolearn than closely matched concepts which were not linearly separable. As an example, consider Medin and Schwa-

11

A RATIONAL ANALYSIS OF RULE-BASED CONCEPT LEARNING

(b)

0.7

0.4

0.6

0.35
0.3

0.5

Posterior feature weight

Posterior complexity weight

(a)

0.4
0.3
0.2

0.2
0.15
0.1

0.1
0

0.25

0.05

1

2

3
Complexity

4

0

5

1

2

3

4

FeatureFigure 4. (a) Posterior complexity distribution of the RRDNF model (b=1) for the category structure of Medin & Schaffer (1978), see
Table 3. (b) Posterior feature weights for this category structure. Together these weight distributions indicate that the RRDNF model focuseson simple rules along features 1 and 3.

nenflugel (1981), Experiment 3, in which participants weretrained on the two concepts shown in Table 4, and tested onclassification accuracy for the training set. Concept LS islinearly separable, Concept NLS is not, and the two concepts
have matched single dimension strategies (that is, any single feature predicts category membership two thirds of thetime, in each concept). Throughout the experiment learners

1
A3
A2

0.8

T3
A1

A4

Human mean

Table 3The category structure of Medin & Schaffer (1978), with thehuman data of Nosofsky et al. (1994), and the predictions of
the Rational Rules model (b=1).
ObjectFeature Values
Human
RRDNF
A1
0001
0.77
0.82
A2
0101
0.78
0.81
A3
0100
0.83
0.92
A4
0010
0.64
0.61
A5
1000
0.61
0.61
B1
0011
0.39
0.47
B2
1001
0.41
0.47
B3
1110
0.21
0.21
B4
1111
0.15
0.07
T1
0110
0.56
0.57
T2
0111
0.41
0.44
T3
0000
0.82
0.95
T4
1101
0.40
0.44
T5
1010
0.32
0.28
T6
1100
0.53
0.57
T7
1011
0.20
0.13

0.6

A5

T1
T6

0.4

T2

B2

T4

B1

T5

0.2

T7
B3
B4

0
0

0.2

0.4
0.6
RR predictions

0.8

Figure 3. Comparison of human judgments with RRDNF model
predictions: mean probability of category A judgments after training on the category structure of Medin & Schaffer (1978), see Table 3, for human and RRDNF model (b=1). The fit between modeland human data is R2 =0.98.

make fewer errors on Concept NLS (Fig. 5a). In Fig. 5b we
see that the Rational Rules model provides good qualitative
agreement with the human data, predicting more errors on
the linearly separable concept (and note that no parameters
were fit in these model results). The RULEX model also predicts the relative difficulty of Concept LS over Concept NLS(Nosofsky et al., 1994), which suggests that this is a rather

1

NOAH D. GOODMAN, JOSHUA B. TENENBAUM, JACOB FELDMAN, THOMAS L. GRIFFITHS

Table 4
The two concepts from Medin & Schwanenflugel (1981).
Concept LS is linearly separable, Concept NLS is not.
Concept LS
Category A
Category B
1000
0111
0001
1000
0110
1001
Concept NLS
Category A
0011
1100
0000

Category B
1111
1010
0101

0.7
Concept LS
Concept NLS
0.6
0.5
Posterior probability

12

0.4
0.3
0.2
0.1
0

general prediction of rule-based models.
To understand this result, note that, though the two concepts support equally informative complexity 1 rules (thatis single-feature strategies), Concept NLS supports more informative rules of complexity 2, 3, and 4 than does Concept LS. For example the complexity 4 formula ( f1 (x)=0 ∧f2 (x)=0) ∨ ( f3 (x)=0 ∧ f4 (x)=0) discriminates perfectly forConcept NLS, while there is no complexity 4 formula which
does so for Concept LS. The RRDNF model relies more heavily on these rules of complexity 2, 3, and 4 for Concept NLS
than for Concept LS, see the plots of posterior complexity in
Fig. 6, which results in a difference in accuracy. The model
does not, however, simply use the most informative rules(after all there are always perfectly predictive rules of very
high complexity), but balances predictive accuracy against
simplicity—it places weight on highly informative and moderately complex rules for Concept NLS, but, finding no suchrules for Concept LS, places the majority of the weight onvery simple rules.

Selective Attention Effects
It is important to be able to ignore uninformative featuresin a world, such as ours, in which every object has many
features, any of which may be useful for classification. This
motivates the long standing interest in selective attention inhuman concept learning (Kruschke, 1992): the tendency toconsider as few features as possible to achieve acceptableclassification accuracy. We have seen a simple case of thisalready predicted by the Rational Rules model: single feature
concepts were preferred to more complex concepts for the 54 category structure (Fig. 4(a)). Indeed, each of the descriptive measures described above (the complexity and feature
weights) is a measure of selective attention exhibited by themodel: the posterior complexity weights describe the extent
to which the model favors simpler formulae (which will havefewer features), while the posterior feature weights directly
describe the informativeness of each feature, as estimated by
the model. It has been noted before (Navarro, 2006) that selective attention effects emerge naturally from the Bayesian123Complexity

4

5

Figure 6. Posterior complexity distribution of the RRDNF model(b=3) on the two category structures from Medin & Schwanenflugel(1981), see Table 4. The model shows greater dependence on simple
rules for Concept LS than Concept NLS.

framework. In our setting selective attention can be understood as the effect of updating the uncertainty over production probabilities as evidence accumulates. Indeed, as theprior over τ—initially uniform—is updated, it will often concentrate, becoming tightly peaked on a subset of productions.
For instance, if only the first of three features is informative, the posterior distribution on production P → F1 will
become larger, while the posteriors on P → F2 and P → F3
will be small (and these values will be reflected in the posterior feature weights, see Appendix D). The changing importance of the productions τ have been marginalized awayin the summary prior Eq. 4, but the effects will still be felt inmodel predictions. As a result the inferences of the Rational
Rules model will depend most sensitively on the informative
features—this is the manner in which Bayesian models implement selective attention.
Shepard et al. (1961), in one of the first studies to demonstrate selective attention effects, compared difficulty in learning the six concepts in Table 5 (these are the six concepts
with three Boolean features, four positive and four negative
examples). These concepts differ in the number of dimensions which must be attended to, in the complexity of theirsimplest perfect rule, and in the number of imperfect, but
useful, simple rules. To learn Concept I it is only necessary
to consider the first feature, that is, the rule ( f1 (x)=0) perfectly predicts category membership, and the remaining features are uninformative. For Concept II the first two features
are informative; for example the complexity 4 formula(( f1 (x)=1) ∧ ( f2 (x)=1)) ∨ (( f1 (x)=0) ∧ ( f2 (x)=0))
is the simplest perfect rule for this concept. In contrast, allthree features are informative for Concepts III, IV, V, and VI.

13

A RATIONAL ANALYSIS OF RULE-BASED CONCEPT LEARNING

(a)

(b)

0.5

0.4
Concept LS
Concept NLS

0.45

Concept LS
Concept NLS

0.35

0.4
0.3
Error probability

Error rate

0.35
0.3
0.25
0.2

0.25
0.2
0.15

0.15
0.1
0.1
0.05

0.05
0
0

1

2

3

4

5

6

Block

7

0
0

1

2

3

4

5

6

7

8

b

Figure 5. (a) The human data from Medin & Schwanenflugel (1981) for the category structures in Table 4, showing that linearly separable
Concept LS was more difficult to learn than Concept NLS, which is not linearly separable. (b) Predictions of the RRDNF model: theprobability of an incorrect response vs. the outlier parameter b.

Concept III admits the relatively simple formula(( f1 (x)=0) ∧ ( f3 (x)=0)) ∨ (( f2 (x)=0) ∧ ( f3 (x)=1)),
while Concepts IV, V, and VI don’t admit any perfect rules oflow complexity. However, IV, and V both admit imperfect,
but useful, rules of low complexity, while VI has no usefulsimple rules at all.
A well replicated finding concerning human errors (Shepard et al., 1961) is that these concepts vary reliably in difficulty, reflecting the above complexity and informativenessconsiderations: I<II<III=IV=V<VI (ordered from least to
most difficulty, where “=” indicates no reliable difference indifficulty). The RRDNF model predicts these qualitative findings: error rates (via posterior probability, when b=3) of 0%,17%, 24%, 24%, 25%, 48% for concepts I, II, III, IV, V, andVI, respectively. This ordering is predicted for a fairly wide
range of parameter values, though an inversion is predicted
at b=1: concept II is then more difficult than concepts III, IV,
and V. It is intriguing that this inversion has been experimentally observed in humans when the stimulus dimensions are
non-separable (Nosofsky & Palmeri, 1996), but further work
will be needed to determine whether this is an illuminatingor accidental prediction of the model. (This inversion, whichis also seen in rhesus monkeys (Smith, Minda, & Washburn,2004), is predicted by the ALCOVE model when attention
learning is disabled.)
However, people are not bound to attend to the smallest set of informative features—indeed, selective attention
is particularly interesting in light of the implied tradeoff between accuracy and number of features attended. Medin, Altom, Edelson, and Freko (1982) demonstrated this balance bystudying the category structure shown in Table 6. This structure affords two strategies: each of the first two features are

Table 5The six concepts with three features, four positive and four
negative examples, studied first in Shepard et al. (1961).
I
II
III
IV
V
VI
+000 +000 +000 +000 +000 +000
+001 +001 +001 +001 +001 -001
+010 -010 +010 +010 +010 -010
+011 -011-011-011-011 +011-100-100-100 +100 -100
-100
-101
-101 +101 -101
-101 +101-110 +110 -110
-110
-110 +110-111 +111 -111
-111 +111 -111

individually diagnostic of category membership, but not perfectly so, while the correlation between the third and fourthfeatures is perfectly diagnostic. It was found that humanlearners relied on the perfectly diagnostic, but more complicated, correlated features. McKinley and Nosofsky (1993)
replicated this result, studying both early and late learning byeliciting transfer judgments after both initial and final training blocks. They found that human participants relied primarily on the individually diagnostic dimensions in the initial stage of learning, and confirmed human reliance on thecorrelated features later in learning. The RRDNF model explains most of the variance in human judgments in the final
stage of learning, R2 =0.95 when b=7; see Fig. 7. Correlation
with human judgments after one training block is also respectable: R2 =0.69 when b=1. By comparison RULEX has
R2 =0.99 for final, and R2 =0.67 for initial learning. We have

9

14

NOAH D. GOODMAN, JOSHUA B. TENENBAUM, JACOB FELDMAN, THOMAS L. GRIFFITHS

0.5

plotted the posterior complexity of the RRDNF model against
b in Fig. 8, and the posterior feature weights in Fig. 9. Whenb is small the Rational Rules model relies on simple rules, but
gradually switches as b increases to rely on more complex,
but more accurate, rules.

Posterior feature weight

0.4

1
0.9
0.8

Final block.
Initial block.

0.7

b=1
b=4
b=7

0.45

0.35
0.3
0.25
0.2
0.15
0.1

R2

0.6

0.05
0.5
0
0.4

1

2

3

4

5

6

7

8

4

9

b

Figure 7. Fit of the RRDNF model to human data (R2 ), for data frominitial and final learning blocks of McKinley & Nosofsky (1993),
see Table 6. The fits are shown for eight values of the outlier parameter b. (Error bars represent standard error over five independent
simulation runs.)

0.7
b=1
b=4
b=7

0.6
Posterior complexity weight3

Figure 9. Posterior feature weights of the RRDNF model on the
category structure of Medin et al. (1982), see Table 6, for threevalues of the outlier parameter.

0.2

0.5
0.4
0.3
0.2
0.1
0

2
Feature

0.3

0.1
0

1

1

2

3

4
5
Complexity

6

7

8

Figure 8. Posterior complexity distribution of the RRDNF modelon the category structure of Medin et al. (1982), see Table 6, forthree values of the outlier parameter.

Concepts based on non-Boolean Features
We have focussed thus far on concepts with Boolean feature values, but the modular nature of the concept gram-mar makes it quite easy to extend the model to other concept learning settings. Indeed, when the features take values
on a continuous dimension we may, as described above, replace the simple boolean feature predicates with “decisionboundary” predicates, e.g. f1 (x) < 3. This is quite similar tothe strategy taken in Nosofsky and Palmeri (1998) to extend
RULEX to continuous feature values. Indeed, the Nosofsky
and Palmeri (1998) version of RULEX is in some ways mostsimilar to the Rational Rules model. However the complications of the continuous RULEX model result in an awkward
modeling process: a set of likely rules is chosen by hand,then the model is fit with several free parameters for eachrule. In contrast, the Rational Rules model is easily extended,
and acquires no additional free parameters or ad-hoc fitting
steps.
As an initial test we have compared the RRDNF model,using decision boundary predicates, with human data for theconcept with two continuous features that first appeared in
Nosofsky, Clark, and Shin (1989), using the human data fromthe Nosofsky and Palmeri (1998) replication. (The two experiments of this replication were identical except they used
the two different assignments of logical dimensions to physical dimensions—we have averaged the results from these two
experiments to counterbalance the data). The result suggeststhat the RRDNF model captures a significant amount of human learning also for concepts based on continuous feature
dimensions: R2 = 0.82 (for b=3).
All of the results discussed so far depend on the choiceof primitive feature predicates, but this is especially true ofpredictions for continuous-dimension stimuli. Indeed, there
seems to be no a priori reason to choose two continuousfeatures f1 and f2 rather than alternative “rotated” features
f10 = f1 + f2 and f20 = f1 − f2 . Yet the predictions of the Rational Rules model will differ significantly depending on the

A RATIONAL ANALYSIS OF RULE-BASED CONCEPT LEARNING

15

Table 6The category structure of Medin et al. (1982), with initial and final block mean human responses of McKinley & Nosofsky(1993), and the predictions of the Rational Rules model at b=1 and b=7.
ObjectFeature Values
Human, initial block
Human, final block
RRDNF , b=1
RRDNF , b=7
A1
1111
0.64
0.96
0.84
1
A2
0111
0.64
0.93
0.54
1
A3
1100
0.66
1
0.84
1
A4
1000
0.55
0.96
0.54
0.99
B1
1010
0.57
0.02
0.46
0
B2
0010
0.43
0
0.16
0
B3
0101
0.46
0.05
0.46
0.01
B4
0001
0.34
0
0.16
0
T1
0000
0.46
0.66
0.2
0.56
T2
0011
0.41
0.64
0.2
0.55
T3
0100
0.52
0.64
0.5
0.57
T4
1011
0.5
0.66
0.5
0.56
T5
1110
0.73
0.36
0.8
0.45
T6
1101
0.59
0.36
0.8
0.44
T7
0110
0.39
0.27
0.5
0.44
T8
1001
0.46
0.3
0.5
0.43

set of features: simple concepts in terms of decision bounds
along f1 and f2 may be quite complicated in terms of f10 and
f20 . (This parallels the “grue/green” thought experiment often
used to illustrate the “new riddle of induction” (N. Goodman,
1955).) The psychological reality and importance of basisfeatures has been shown a number of ways. For instance,
the “Filtration” concept of Kruschke (1993) may be simply
describe as a decision bound along one dimensions, whilethe “Condensation” concept cannot—though it is identical to
the Filtration concept but for a 45 degree rotation. Both human learners and the Rational Rules model find the Filtration
concept considerably easier to learn than the Condensation
concept.
It is likely that Rational Rules, viewed as a computationallevel model, can guide the resolution of some of the ad-hoc
assumptions in the existing process-level accounts of rulebased learning for continuous features. Conversely, the modeling assumptions used here to extend Rational Rules to continuous features can certainly be refined by incorporating
insights from the (extensive) literature on continuous categories. In particular, empirical evidence (e.g. Maddox &Ashby, 1993) suggests that feature predicates capturing general linear or quadratic decision boundaries may be appropriate in some situations.

Individual Generalization Patterns
Nosofsky et al. (1994) investigated the pattern of generalizations made by individual participants, that is, theyreported the proportion of participants giving each set ofanswers to the generalization questions. One may wonder
whether it is necessary to consider these generalization patterns in addition to group averages for each question. As
noted in Nosofsky and Palmeri (1998), even the best binomial model does very poorly at predicting individual gen-eralization patterns (R2 =0.24 in the case of Nosofsky et al.
(1994), Exp. 1), though, by construction, it perfectly predicts
the group average for each generalization question. Therefore the pattern of generalizations provides an additional,
more fine grained, probe for testing concept learning models.
To understand how the Rational Rules model can predictthese generalization patterns, recall the hypothesis samplingassumption discussed above: each individual has a single hypothesis which is drawn from the posterior over formulae.
The pattern of judgments made by each individual is then determined by this hypothesis, with additional response noise
η. If we assume a single value of the parameters (b and η)
for all participants, the best fit of the RRDNF model explains
R2 =0.85 of the variance in human generalization for the 36
generalization patterns reported in (Nosofsky et al., 1994).
The RULEX model also does well, R2 =0.86, but uses several
more free parameters. As with RULEX, the qualitative matchof the Rational Rules model to human judgments is good,
see Fig. 10. Also as with RULEX, the generalization pattern
ABABBAB is under-predicted by the model (cf. Johansen &Palmeri, 2002).

An Experiment
In the previous section we have discussed several important experiments from the concept learning literature, exploring human learning of concepts based on relatively few features. In each of these experiments participants were trainedon many, or all, of the objects in the feature space, leaving
only a few untrained objects available as transfer stimuli.
(In fact, none of these experiments had fewer than half ofpossible objects as training examples.) In contrast, humanlearners must often cope with both large feature spaces, andrelatively few labeled examples compared to the number of
unseen objects. In a more natural setting, one with many

16

NOAH D. GOODMAN, JOSHUA B. TENENBAUM, JACOB FELDMAN, THOMAS L. GRIFFITHS

0.2

Model
Human

0.15

0.1

0.05

AAAAAAA
AAAABABAAABAABAAABABBAAABBABAAABBBAAAABBBBAABBABAAABBBBBABAAAABABAABABABABAAAABABAABABABABAABABABBABABBABABABBBBABBABABABBBAABABBBBBABAAABABBAABBABBAABBBBBABBBBBBBAAAAABBAAAABBBAABABBBAABBBBBABAAABBABAABBBABABABBABABBBBABBABBBABBBABBABBBBBBBAABB

0

Figure 10. Individual generalization patterns: the probability of responding with the indicated categorizations for the seven transfer stimuli
of Table 3. Human data from Nosofsky et al. (1994), Experiment 1. The model values are for parameters b=4, η=0.09. Agreement of modelwith human data is good: R2 =0.85, rmsd=0.016.

features and sparse training examples, one might expect different aspects of concept learning to come to the fore. For
instance, when training examples are sparse, learning will beless constrained by available information and the inductive
bias of the learning mechanism will play a relatively larger
role. Further, when there are many features, the memory demands of remembering even a single exemplar become significant, so it is important to focus on informative rules basedon a subset of the features. Given these considerations, it isimportant to test models of concept learning against humanlearning in settings with many features and sparse examples.
In addition, there is a danger of selecting the concepts
to be tested in a way that biases the results. Historically,
many concept learning experiments have used the same
hand-picked concept structures, e.g. the Medin and Schaffer (1978) 5-4 concept, which has been used in dozens ofstudies. It is extremely plausible that some learning techniques work better on some types of concepts than others (seeBriscoe & Feldman, 2006; Feldman, 2003, 2004), leaving
doubt about whether performance on a small set of concepts
is a reliable indicator of success more generally. This was
one of the motivations for Shepard et al. (1961)’s famousconcept set, which constitutes an exhaustive (and thus inherently unbiased) survey of concepts with three dimensions
and four positive examples. When the number of features islarge, it is impossible to be similarly exhaustive, but we canachieve a similar end by choosing our concepts randomly, sothat we are at least guaranteed that our choices will be unbiased with respect to the performance of competing models—a level playing field. Thus in the experiment described below,
the training set is a randomly selected subset of the complete
set of objects.
The complexity of patterns formed by chance should varywith the number of examples: for example, with few examples there may be more “accidental” simple regularities. It

isn’t feasible to vary the number of examples systematicallyover a wide range, but it is possible to do so for small numbers of examples. Hence, in the experiment that follows we
use a large set of Boolean features (D=7), yielding 27 =128
objects total, of which a small randomly drawn set of 3 to
6 are presented as positive examples, and two are presented
as negative examples. (Some negative examples are necessary to give the participant a sense of the range of positive
examples; for simplicity we always used two negative examples.) This leaves the vast majority of the space (at least 122
objects) as “transfer” objects. After brief training with theexample objects, participants were asked to classify all 128
objects in random order. The goal is to apply the model topredict responses on the 128 generalization trials, as a function of the training set.

MethodParticipants. Participants were 47 undergraduate students
enrolled in a Psychology class, participating in the study inreturn for course credit. All were naive to the purposes of thestudy.
Materials and procedure. Objects were amoeba-likeforms, each consisting of an outer boundary and one or more
“nuclei” (smaller shapes in the interior). The amoebas varied
along seven Boolean dimensions (body shape = rectangle orellipse; boundary = solid or fuzzy; nucleus shape = triangle
or circle; nucleus size = large or small; nucleus color = filled
or unfilled; nucleus number = 1 or 2; fins present or absent).
These features were chosen simply to be plainly perceptible
and salient to participants.
Participants were told they were to play the role of a biologist studying a new species of “amoeba”-like organisms.
They were instructed that they were to study a small numberof known examples of each new species, and then attempt to17

A RATIONAL ANALYSIS OF RULE-BASED CONCEPT LEARNING

Results and Discussion
We consider several ways of analyzing the experimental
data, in order to address three main questions. First, to what
extent can the probabilistic rule-based approach describe human concept learning and generalization behavior in this relatively unconstrained setting? Second, can we infer the specific rules that learners adopted on particular runs, and canwe make any general conclusions about the kinds of rules
they tend to use in this setting? Third, how well can we
predict the graded generalization probabilities of individual
learners for individual test objects? The RRDNF model provides our basic tool for answering each of these questions.
To assess the first question we consider the overall abilityof the RRDNF model to predict participants’ patterns of judgments for the 128 test stimuli within each run. We measure
the fit of the model to human responses with the (natural)
log-likelihood of the pattern of responses in an individual run
according to the model:ln(PRRDNF (response1 , ..., response128 |training examples)).
This is a measure of how likely the model considers the response pattern given the training set (or, roughly, the amountof information in the human data that cannot be accounted
for by the model). It is always negative, and numbers withsmaller magnitude indicate better fit. Without fitting any parameters, simply fixing η=0.1 and b=1, mean log-likelihood
across runs is -54. That is, using the model the probability ofcorrectly predicting responses to all 128 questions of a given

run is 34 orders of magnitude better than chance (chance is1)= − 89). Moreover this predictive success is quiteln( 2128
broad: the response pattern of 85% of runs is predicted better
than chance, and the mean predictive success for runs in eachof the 43 unique training sets is above chance.
0
−10
−20
Log−likelihoodclassify unknown examples as members or non-members of
the species.
Each concept session began with a training screen, divided
into top and bottom halves by a horizontal line. The top halfof the screen contained the P = 3, 4, 5 or 6 positive example objects, drawn in a horizontal row in random order, andlabeled “Examples”; the bottom half contained the two negative examples, again drawn in a horizontal row in random
order, and labeled “NOT examples.” The training screen remained up for a fixed period of time, equal to 5P seconds(i.e. 15 – 30 seconds depending on the number of positives,
yielding a constant average learning time per positive object).
After the training screen disappeared, participants were
presented with a series of 128 individual classification trials
in random order. On each classification trial, a single object
was presented centrally, and participants were instructed toclassify it as a member of the species or a nonmember. No
feedback was given.
Each participant was run on several separate concepts, atdifferent values of P, in random order. It was emphasized toparticipants that each new species (concept) was unrelated tothe preceding ones. The entire sequence took about an hour
per participant. In some cases we intentionally ran multiple participants on the same concepts, to facilitate comparisons between participants on identical inputs, but this was
not pursued systematically. In total there were 140 participant/training set pairs, which we will refer to as individual
runs.

−30
−40
−50
−60
−70
−80
−90
0

0.1

0.2

η

0.3

0.4

0.5

Figure 11. Distribution of (natural) log-likelihood scores vs. bestfit η parameter for each individual run. (Chance log-likelihood is−89, since there are 128 binary choices in each run.)

In light of the results on individual generalization patterns
above, it makes sense to fit parameters η and b for each individual run, hoping to capture individual differences in learning in addition to the differences in what is learned. (Fitting
parameters per run can quickly lead to over-fitting; however,since we have 128 responses per run in this experiment, it is
not unreasonable to fit two parameters for each.) The mean
best log-likelihood for each run is -44. This log-likelihood
is significantly greater than that expected by a chance fit(p<0.001 by permutation test7 ). The distribution of loglikelihood scores against best-fit η values is shown in Fig. 11.
Note first that the majority of η values are relatively small,indicating that behavior on most runs is best explained primarily in terms of the rational rule-based inferences from theexamples participants saw rather than in terms of response
noise. Second, the tight correlation between log-likelihood
values and η values indicates that the amount of response
noise (as measured by the inferred value of η) is a primaryfactor explaining the differences in fit between individual
runs. If there was another factor that distinguished runs andexplained differences in model fit, we would expect that factor to produce independent variance observable in Fig. 11.
The fit between model predictions and human data indicates that participants’ performance may usefully be analyzed as probabilistic rule-based classification. Can we gain
7
For this test we randomly permuted the data within individual
runs. It is likely that the p-value is much smaller than 0.001: weestimated the permutation test by Monte Carlo simulation of 1500
random permutations of the data, and found no permutations withgreater log-likelihood than the actual data.

18

NOAH D. GOODMAN, JOSHUA B. TENENBAUM, JACOB FELDMAN, THOMAS L. GRIFFITHS

All runs (! < 0.1)
RunsAll
runswith(! <b<5
0.1)
Runs
with
b"
Runs with b<5 5Runs with b" 5

Number of runs
Number of runs

30
30
25
25
20
20
15
15
10
10
5
5
0
0

(f
(f))

(f)

(f
(f&
∧ff))∨(f(f & f) (f(f))∨(f| (f)) (f & f & f)
(f))∨(f| (f))∨(f| (f)()f & f) | (f(f)
| (f))∨(f| (f))(f ∧f )
(f ∧f ∧f)
(f ∧f )∨(f )Logicalform(f & f) (f) | (f) (f & f & f)(f) | (f) | (f)(f & f) | (f(f)& f) | (f) | (f)Logical form

Figure 12. The distribution of logical forms of best formulae for individual runs with η < 0.1. The logical forms are schematic: f stands
for any feature predicate (e.g., f1 =1). Runs with high b (less permissive outlier parameter) exhibit somewhat more complex classification
behavior.

Table 7
Two sample individual runs, showing the training examples,
best-fit parameters, and highest posterior formulae together
with their agreement with the participant’s responses (i.e. theportion of the 128 transfer questions on which participants’
responses satisfy the formula). Formulae are listed in descending order of posterior probability given the training examples.
label
+
+
+

feature values
0110101
01101101000101
10110101110011best-fit b=1, η=0.03
formula agreement( f1 =1)
50%( f2 =0)48%( f5 =0)97%( f6 =1)
53%

label
+
+
+
+

feature values
0000001
00001100001110001111010111101101000

best-fit b=8, η=0.07
formulaagreement( f1 =1) ∨ ( f5 =0)76%( f1 =1) ∨ ( f7 =1)
88%( f1 =1) ∨ ( f3 =0)84%( f1 =1) ∨ ( f6 =0)77%( f4 =1) ∨ ( f7 =1)
74%

further insight into which rules each participant used in eachrun? The rules that participants were using cannot be readoff directly from their generalization behavior, but we canuse the RRDNF model to infer which rules they were likely to
be using. Consider two sample runs shown in Table 7, where
we have given the training set, the highest posterior formulae
according to the model under best-fitting parameters, and theagreement between participants’ responses and the responses
predicted by these high posterior formulae. As exemplified
by the first run, some participants seem to pick a simple onefeature rule and use it consistently to classify the test stimuli.

The rule chosen may be somewhat arbitrary, not necessarily
fitting the training examples perfectly or fitting them better
than alternative rules of equivalent complexity. In the firstrun of Table 7, we see that a formula with high posterior
probability captures the vast majority of the participant’s responses but is not the formula with highest posterior probability; another simple rule exists ( f1 =1) that can perfectly explain the training data. The inferred response noise (η) is low,
because the participant’s judgments are highly predictable.
Other participants, as illustrated by the second run shownin Table 7, appear to be using slightly more complex ruleswith multiple features, but these more complex rules may be
used less consistently. Here the agreement between generalization behavior and any high-probability formula is lessstrong, which the model attributes to greater intrinsic noise(higher η). The agreement is also less tightly peaked, withmultiple formulae having similarlly high agreement levels(largely because agreement between formulae forces correlation in agreements with participants’ responses). Even inthese cases, however, responess may be still usefully captured by a single high-agreement formula.
To generalize this analysis beyond single case studies, wedefine the “best” rule for each individual run to be the rulewith maximum posterior probability given the participant’s
responses8 . In Fig. 12 we have plotted the distribution oflogical forms of the best formula for each of the individual
runs. Overall, participants focused primarily on rules thatuse only one or two of the available seven features. Thisfinding is similar in spirit to the classic finding of Medin,
Wattenmaker, and Hampson (1987), that participants in unsupervised classification tasks tend to classify based on a sin8
We may think of this as a Bayesian estimate of the rule used byan individual, in which the prior is given by the model’s posterior
over rules, and the likelihood is based on how well each rule predicts the noisy classification behavior of that individual. We obtain
similar results if we define the “best” rule to be simply the formulathat best agrees with a participant’s responses, chosen from among
those formulae with high posterior according to the model.

A RATIONAL ANALYSIS OF RULE-BASED CONCEPT LEARNING

gle feature, even if the features of objects could also be explained by a family-resemblance category structure. Here,
we see that participants in a “lightly supervised” conceptlearning setting—in which there are relatively few examples,and brief familiarization—classify mostly based on simple
one- or two-feature rules.
It is worth noting that runs which are best modeled witha permissive outlier parameter (b<5) rely mostly on one or
two features, while runs with stricter outlier parameter values (b≥5) begin to exhibit more complex classification rules.
Because the value of the outlier parameter is an estimate of
how accurately participants have learned a concept consistent with the training set, this provides an indication of thecourse of learning (without manipulating it directly). The
difference between small and large b runs is suggestive of a“representational shift” (Smith & Minda, 1998; Johansen &Palmeri, 2002; Briscoe & Feldman, 2006), from simple rules
to more complex rules (or exemplar-type representations) as
training is extended. In future work, it would be interesting
to test whether this pattern of variation in representational
complexity would result from more systematic variation of
exposure time and number of examples relative to size of the
training set.
Finally, we turn to the question of how well the
RRDNF model can predict the graded generalization probabilities of individual learners for individual test objects (asopposed to entire generalization patterns). This assessment
is complicated by the fact that the model makes different
predictions for each participant on each question, depending on the training set they saw—and because of the large
number of training sets in this experiment only a few participants saw each. Yet if the model accurately predicts individual responses, across participants and questions, then of
responses predicted with probability X% to be “yes”, roughly
X% should actually be answered “yes”. Thus, instead of doing an object-by-object correlation as we did above for otherdata sets, we first sort the responses according to predictedprobability of generalization—that is, we bin responses according to the prediction of the model, given the training set
and the best-fit b and η. In Fig. 13(a) we have plotted the frequency of “yes” responses against the predicted generalization probability. We see that response frequencies are highly
correlated with model generalization probability (R2 =0.97),
indicating that the model is a good predictor of individual
responses. Another way of interpreting Figs. 13(a) is that,across judgments, the model correctly predicts human responses in proportion to how confident it is in that prediction: when the model predicted a “yes” response with highprobability most people did say yes, and when the model
was unsure—assigning probability near 50%—people were
evenly split between “yes” and “no” responses.
To find out whether this trend holds at the level of individual runs we did a similar analysis for each run: webinned the 128 responses in a run according to model posterior, and computed the frequency of “yes” responses in eachbin. Fig. 13(b) shows the mean and standard error over runs,
demonstrating that the model is a good predictor of individual responses on individual runs. (Since each run is an indi-

19

vidual participant this indicates good fit for the responses ofindividuals.)
One of the responsibilities of models of concept learning
is to describe the inferences that people make across a broad
range of natural situations. Thus it is important to verify thata model fits human data not only on simple, well-controlled
concepts, but for more natural and generic circumstances.
We have found good agreement between the RRDNF modeland human judgments when the number of features is large,
the number of training examples small, and the specific training sets randomly generated. This is a necessary complement
to the results discussed above which show that the Rational Rules model captures a number of well-known, specificlearning effects.

General Discussion
We have suggested an approach for analyzing human concept learning: assume that concepts are represented in a concept language, propose a specific grammar and semantics forthis language, then describe rational inference from examples to phrases of the language. Carrying out this scheme forconcepts which identify kinds of things, by using a grammar
for DNF formulae, we derived the Rational Rules (RRDNF )model of concept learning. This model was shown to predict
human judgments in several key category learning experiments, and to do so with only one, readily interpretable, parameter (and an additional, decision-noise, parameter for fits
to individual subjects). Several phenomena characteristic of
human concept learning—prototype enhancement, typicality
gradients, and selective attention—were demonstrated. The
model was used to predict categorization judgments basedon continuous features, and the the pattern of generalization
responses of individual learners. In a new experiment, weinvestigated the ability of the model to predict human behavior in generic natural environments: natural in the sensethat there were many features and few training examples relative to the number of transfer stimuli, generic because thesetraining sets were randomly chosen. Human generalization
behavior was again well predicted by the model in this experiment.

Relation to Other Models of Concept Learning
For most fits of the Rational Rules model to human data
we have provided a comparison with RULEX model fits.
This comparison has shown that the RRDNF model fits human data as well as one of the most successful existing models of concept learning, but it also shows how fits of the
RRDNF model generally parallel fits of RULEX, both better
and worse. This reinforces the interpretation of the Rational
Rules model as a computational-level analysis of the same
species of rule-based inductive inferences that RULEX attempts to capture at the process level. Of course the RRDNF
model is not a rational analysis of RULEX per se, but rather
of a class of models for which RULEX is one prominent example.
Our DNF representations are in some ways more similar to the cluster-based representations of the SUSTAIN20NOAH D. GOODMAN, JOSHUA B. TENENBAUM, JACOB FELDMAN, THOMAS L. GRIFFITHS

(a)

(b)

1

1

0.9
Mean Human Response Frequency

Human Response Frequency

0.8
0.7
0.6
0.5
0.4
0.3
0.2

0.8

0.6

0.4

140

0.2

0.1
0
0

0.2
0.4
0.6
0.8
Posterior Generalization Probability

1

0
0

0.2
0.4
0.6
0.8
Posterior Generalization Probability

1

Figure 13. (a) Human categorization response frequency (proportion of “yes” judgments) against model posterior generalization probability, R2 =0.97; error bars represent standard error of frequency (assuming binomial distribution). (Frequencies are computed by first binningresponses according to model prediction.) (b) The mean of response frequencies (binned according to model prediction) computed for eachrun separately; error bars represents standard error of the mean over runs; bars below each data point indicate number of runs contributing
to that bin (scale on right).

model (Love et al., 2004) than they are to representations
in RULEX; conjunctive blocks of RRDNF formulae are analogous to the clusters that SUSTAIN learns, with features thatare ommitted from a conjunctive clause analogous to features that receive low attentional weights in SUSTAIN. All
three of these models—RULEX, SUSTAIN, and RRDNF —navigate similar issues of representational flexibility, tradeoffs between conceptual complexity and ease of learning, andgeneralization under uncertainty. The main advantages that
Rational Rules offers over the other two models come fromits focus on the computational-theory level of analysis andthe modeling power that we gain at that level: the ability
to work with a minimal number of free parameters and stillachieve strong quantitative data fits, the ability to separate
out the effects of representational commitments and inductive logic from the search and memory processes that implement inductive computations, and the ability to seamlessly
extend the model to work with different kinds of predicatebased representations, such as those appropriate for learning
concepts in continuous spaces, concepts defined by causal
implications (see N. D. Goodman et al., In Press), or concepts defined by relational predicates (see below).
A central theme of our work is the complementary natureof rule-based representations and statistical inference, andthe importance of integrating these two capacities in a modelof human concept learning. Other authors have written about
the need for both rule-based and statistical abilities—or of-ten rules and similarity—in concept learning, and cognition
more generally (Sloman, 1996; Pinker, 1997; Pothos, 2005).
The standard approach to combining these notions employs
a “separate-but-equal” hybrid approach: endowing a modelwith two modules or systems of representation, one specialized for rule-based representations and one for statistical orsimilarity-based representations, and then letting these twomodules compete or cooperate to solve some learning task.
The ATRIUM model of Erickson and Kruschke (1998) is agood example of this approach, where a rule module and asimilarity module are trained in parallel, and a gating module
arbitrates between their predictions at decision time.

We argue here for a different, more unified approach tointegrating rules and statistics. Rules expressed in a flexible concept language provide a single unitary representation;
statistics provides not a complementary form of representation, but the rational inductive mechanism that maps fromobserved data to the concept language. We thus build on theinsights of Shepard (1987) and Tenenbaum (2000) that theeffects of similarity and rules can both emerge from a single
model: one with a single representational system of rule-likehypotheses, learned via a single rational inductive mechanism that operates according to the principles of Bayesianstatistics.

A RATIONAL ANALYSIS OF RULE-BASED CONCEPT LEARNING

Effect of the Specific Concept Grammar
Although we focused on one concept language, based on
a DNF representation, other concept languages are possible
and the choice of language should affect the performance ofa grammar-based induction model. For instance, grammars
which are incomplete (lacking conjunction, say, hence unable to capture all extensions) fail to predict the flexibilityof human learning. We focused here on only the DNF grammar for simplicity of exposition, because our goal has been toshow the viability of a probabilistic grammar-based approachto concept learning, but this should not be taken to imply
an endorsement of the DNF grammar as the correct concept
grammar. Other possibilities capture aspects of other proposals about concepts and concept learning, which may beappropriate for different settings.
For instance, there is increasing evidence that causal relationships play an important role in concept use and formation(see e.g. Rehder, 2003; Sloman et al., 1998). We could attempt to capture causal regularities amongst features by generating sets of “causal laws”: conjunctions of implications
amongst features (this representation for concepts was suggested in Feldman (2006)). In Fig. 14(a) we indicate what agrammar for this language might look like; see N. D. Goodman et al. (In Press) for studies with this concept grammar.
Another possible grammar (Fig. 14(b)), inspired by the representation learned by the RULEX model (Nosofsky et al.,1994), represents concepts by a conjunctive rule plus a set of
exceptions. Finally, it is possible that context-free grammars
are not the best formalism in which to describe a concept
language: graph-grammars and categorial grammar, for instance, both have attractive properties.
(a)
S → ∀x `(x)⇔I
I → (C⇒P) ∧ I
I → T
C → P∧C
C → T
P → FiFi → fi (x) = 1
Fi → fi (x) = 0(b)
S → ∀x `(x)⇔((C) ∧ E)
E → ¬(C) ∧ E
E → T
C → P∧C
C → T
P → FiFi → fi (x) = 1
Fi → fi (x) = 0

Figure 14. (a) An Implication Normal Form grammar. (b) A ruleplus-exceptions grammar inspired by Nosofsky et al. (1994).

Rationality of Hypothesis Sampling
In the first part of this paper we gave a rational analysis
of rule-based concept learning, assuming that the output of
this learning was a posterior distribution on possible concept
meanings. In subsequent sections we showed that this rational analysis predicted human behavior at the group and individual level, at least when supplemented by the additional
assumption of hypothesis sampling (that each learner arrives
at one or a small set of rules distributed according to the posterior). What is the status of the supplemented analysis? We
may ask this along two dimensions: the level of analysis (in21the sense of Marr (1982)), and the claim of rationality. Thus
we have two questions: is hypothesis sampling a processlevel correction to the computational-level analysis, or an extension at the computational level of analysis? And, in either
case, is it a “rational” extension to the analysis?
There are at least two ways in which it is reasonable tothink of hypothesis sampling as a rational correction to theBayesian analysis. First, as the scale of the learning problem increases, exact evaluation of Bayesian analyses quickly
becomes intractable. This suggests that a rational analysis
should account for limited computational resources available to the organism by describing a rational process for approximating the Bayesian solution. Bounded-optimal algorithmic approximation of this sort was an important component of the rational model of Anderson (1991). In recent years, Bayesian models in AI and machine learning
have relied heavily on methods for efficiently computing
approximate probabilities from complex models (Russell &Norvig, 2002). The most general and straightforward approximation methods are based on Monte Carlo sampling—a randomized procedure for constructing a set of hypotheses that are drawn from the Bayesian posterior. The ubiquity of sampling-based approximation methods suggests thatthey could provide the basis for bounded-optimal analysis ofhuman learning (Sanborn et al., 2006)—an approach which
could be consistent with our findings that individual subjects’
behavior can be well explained as samples from the posterior.
One appealing version of this approach, explored by Sanborn
et al. (2006) for similarity-based representations, is basedon sequential Monte Carlo (or “particle filter”) algorithms(Doucet, De Freitas, & Gordon, 2001). These algorithms update a set of hypotheses in response to new evidence in a waythat looks very much like simple hypothesis testing, but thedetails of the “hypothesis update” procedure guarantee thatthe resulting hypotheses are samples from the full Bayesianposterior. (The results for several simulations reported in thispaper were verified by using such a sequential Monte Carloalgorithm, based on Chopin (2002), but we have not yet investigated the behavior of this algorithm in detail.) Thus, it ispossible that the hypothesis sampling assumption is rationalin the sense of being a rational process-level correction to thecomputational-level rational analysis.
There may also be a deeper sense in which the hypothesis
sampling assumption corrects the Bayesian analysis, at thecomputational level, by altering the competence that is being
described. If the output of the concept-learning competence
is a mental representation, not merely classification behavior,
then we must take care that the end result of a model of concept learning is a reasonable candidate for mental representation. In particular, because the full distribution on formulaein the Rational Rules model is infinite, the output representation can only be a summary of this distribution. The hypothesis sampling assumption then embodies the claim that thissummary takes the form of a small set of rules—and that thisapproximates the format of concepts in the mind.
Additional work will be required to establish either the
optimality of hypothesis sampling as a process-level approximation, or the plausibility of sets of rules as a mental rep-22

NOAH D. GOODMAN, JOSHUA B. TENENBAUM, JACOB FELDMAN, THOMAS L. GRIFFITHS

resentation formed by concept learning. In the mean time,
viewing hypothesis sampling as a useful and intriguing auxiliary hypothesis to the rational analysis may be the best
course.

Limitations, Extensions, and Future Directions
Learning tasks. In this paper we have only modeled supervised learning of a single concept. As pointed out in a
number of places (e.g. Love et al., 2004) it is important formodels of concept learning to account for human behavior
over a range of learning situations and a variety of inferencetasks.
It should be possible to extend the Rational Rules modelto unsupervised and semi-supervised learning tasks, by employing a “strong-sampling” likelihood (which assumes thatexamples are sampled from those with a given label), asin Tenenbaum and Griffiths (2001). Similar effects should
emerge as those found in other Bayesian models which use
strong-sampling (Tenenbaum, 1999a)—foremost a size principle, favoring more restrictive hypotheses over more general. This size principle also enables learning concepts fromonly positive examples (Tenenbaum & Xu, 2000; Xu &Tenenbaum, 2007).
We indicated earlier that the feature predicates used asprimitives throughout this paper should be thought of as just
one simple case of preexisting concepts that can be used
as atoms for new concepts. Indeed, compositionality suggests that once a concept has been learned it is available as abuilding block for future concepts—and this effect has been
demonstrated for human learning (Schyns & Rodet, 1997).
We may extend the Rational Rules model to systems of concepts in exactly this way: by adding each learned concept asa primitive predicate to the concept grammar used to learn
the next concept. This will predict certain synergies between
concepts which should be empirically testable. (For instance,
having learned that “daxes” are red squares, it might be easierto learn that a “blicket” is a fuzzy dax than it would have been
to learn the meaning of blicket alone—a fuzzy red square.)In such synergies we begin to see the real power of compositional representations for concepts.
Process-level description. While we have not attempted
here to predict processing measures of concept learning,
there are natural approaches to bridge between our analysis
and such measures. For instance, it is likely that response
times for individual categorization decisions can be modeledby making processing assumptions similar to those in Lamberts (2000). Specifically, we may assume that noisy perceptual observations of features are accumulated at a constantrate, that the log-likelihood of a particular response given the(set of) concept formulae and observations is accumulated
over time, and that a decision is made when this accumulating log-likelihood reaches a confidence threshold. This
would result in a diffusion process (Luce, 1986; Ratcliff,
Zandt, & McKoon, 1999) in which the diffusion rate depends
on properties of the stimulus with respect to the concept language. It is important to note that the speed-limiting stepin this process is perceptual information gathering, not evaluation of rules. Thus, contra Fodor (1998), we would not
expect that the representational complexity of concepts need
be reflected in response times.
Sequential effects in learning have been taken to be a particularly puzzling set of phenomena from the Bayesian pointof view (Kruschke, 2006). A parallel puzzle for our analysis, is how individuals are able to arrive at a set of samples
from the posterior. Both of these puzzles may be addressedby considering the process of learning over the course of anexperiment. Indeed, it is likely that rational process models, such as the sequential Monte Carlo models describedabove, will be able to give a more detailed treatment of thecourse of human learning. This includes refined learning
curves and explanations of sequential effects—such as thegreater weight of early examples in concept learning (Anderson, 1990)—which might otherwise be puzzling from theBayesian point of view. A proper investigation of these questions could become a whole research program on its own.
Representation. One of the primary advantages of the Rational Rules model is the ease with which it can be extended
to incorporate new, more powerful, representational abilities.
We have already seen a simple case of this flexibility, when
we extended the Rational Rules model to continuous feature
dimensions by simply adding decision-boundary predicates(e.g. f1 (x) < c). In N. D. Goodman et al. (In Press) we have
explored concepts defined by their role in a relational system(the importance of such concepts has been pointed out recently (Markman & Stilwell, 2001; Gentner & Kurtz, 2005)).
For instance, the concept “poison” can be represented∀x poison(x)⇔(∀y in(x, y)∧organism(y)⇒injured(y)),
or, “a poison is something that causes injury when introduced
into an organism”. To capture this rich set of concepts only asimple extension of the concept grammar is needed (including relational feature predicates and additional quantifiers).
One can imagine making similar alterations to the concept
language to include representations required, for instance, insocial cognition or naive physics.

Conclusion
Our work here can be seen as part of a broader theme
emerging in cognitive science, AI, and machine learning,where logical representations and statistical inference areseen as complementary rather than competing pararadigms.
In the context of concept learning, the integration of statistical learning and rule-based representations may help
us to understand how people can induce richly structured
concepts from sparse experience. This is crucial if concepts are to play a foundational role in our understanding of the mind: concepts must serve many purposes—
classification, theory building, planning, communication andcultural transmission—which require the inferential flexibility of statistics and the representational power of mathematical logic.

A RATIONAL ANALYSIS OF RULE-BASED CONCEPT LEARNING

The proposal that concepts are represented by phrases ina concept language is not new in cognitive science—indeed
this is a principal component of the language of thought hypothesis (Fodor, 1975). Nor is the idea of analyzing cognition by considering a rational Bayesian agent new: ideal
observers have been prominent in vision research (Geisler,
2003) and cognitive psychology (Shepard, 1987; Anderson,
1990; Chater & Oaksford, 1999). However, the combinationof these ideas leads to an exciting project not previously explored: Bayesian analysis of the language of thought. Although this paper represents only the first steps in such a
program, we have shown that rigorous results are possible
and that they can provide accurate models of basic cognitive
processes.

References
Anderson, J. R. (1990). The adaptive character of thought. Hillsdale, NJ: Erlbaum.
Anderson, J. R. (1991). The adaptive nature of human categorization. Psychological Review, 98(3), 409–429.
Armstrong, S. L., Gleitman, L. R., & Gleitman, H. (1983). Whatsome concepts might not be. Cognition, 13, 263–308.
Briscoe, E., & Feldman, J. (2006). Conceptual complexity and thebias-variance tradeoff. In Proceedings of the conference of thecognitive science society (pp. 1038–1043).
Bruner, J. S., Goodnow, J. J., & Austin, G. A. (1956). A study ofthinking. New York: Wiley.
Cassirer, E. (1946). Language and myth. Harper & Bros. (Translated by Suzanne K. Langer)
Chater, N., & Oaksford, M. (1999). Ten years of the rational analysis of cognition. Trends in Cognitive Science, 3(2), 57–65.
Chopin, N. (2002). A sequential particle filter method for static
models. Biometrika, 89(3), 539–552.
Doucet, A., De Freitas, N., & Gordon, N. (Eds.). (2001). Sequential
monte carlo methods in practice.
Enderton, H. B. (1972). A mathematical introduction to logic. New
York: Academic Press.
Erickson, M. A., & Kruschke, J. K. (1998, Jun). Rules and exemplars in category learning. J Exp Psychol Gen, 127(2), 107–140.
Feldman, J. (2000). Minimization of Boolean complexity in humanconcept learning. Nature, 407, 630-633.
Feldman, J. (2003). The simplicity principle in human concept
learning. Current Directions in Psychological Science, 12(6),227–232.
Feldman, J. (2004). How surprising is a simple pattern? Quantifying “Eureka!”. Cognition, 93, 199–224.
Feldman, J. (2006). An algebra of human concept learning. Journalof Mathematical Psychology, 50, 339–368.
Fodor, J. A. (1975). The language of thought. Harvard University
Press: Cambridge, MA.
Fodor, J. A. (1998). Concepts: Where cognitive science went
wrong. New York: Oxford University Press.
Geisler, W. S. (2003). Ideal observer analysis. In L. Chalupa &J. Werner (Eds.), The visual neurosciences (pp. 825–837). MITpress.
Gelman, A., Carlin, J. B., Stern, H. S., & Rubin, D. B. (1995).
Bayesian data analysis. New York: Chapman & Hall.
Gentner, D., & Kurtz, K. (2005). Categorization inside and outside the lab. In W. K. Ahn, R. L. Goldstone, B. C. Love, A. B.
Markman, & P. W. Wolff (Eds.), (pp. 151–175). APA.

23

Goldstone, R. (1996). Isolated and interrelated concepts. Mem
Cognit, 24(5), 608–28.
Goodman, N. (1955). Fact, fiction, and forecast. Cambridge: Harvard University Press.
Goodman, N. D., Tenenbaum, J. B., Griffiths, T. L., & Feldman, J. (In Press). Compositionality in rational analysis:
Grammar-based induction for concept learning. In M. Oaksford & N. Chater (Eds.), The probabilistic mind: Prospects forbayesian cognitive science. Oxford: Oxford University Press.
Griffiths, T. L., & Tenenbaum, J. B. (2005). Structure and strength
in causal induction. Cognitive Psychology, 51, 285–386.
Halpern, J. Y., & Pearl, J. (2001). Causes and explanations: astructural-model approach. Part II: Explanations. In Proceedings of the 17th International Joint Conference on Artificial Intelligence.
Humboldt, W. von. (1863). On language.
Jaynes, E. T. (2003). Probability theory: The logic of science.
Cambridge: Cambridge University Press.
Johansen, M., & Palmeri, T. (2002). Are there representational
shifts during category learning? Cognitive Psychology, 45(4),482–553.
Kruschke, J. K. (1992, Jan). ALCOVE: An exemplar-based connectionist model of category learning. Psychological Review,
99(1), 22–44.
Kruschke, J. K. (1993). Human category learning: implications forbackpropagation models. Connection Science, 5(1), 3–36.
Kruschke, J. K. (2006). Locally Bayesian Learning with Applications to Retrospective Revaluation and Highlighting. Psychological Review, 113, 677–699.
Lakoff, G. (1987). Women, fire, and dangerous things: What categories reveal about the mind. Chicago: University of Chicago
Press.
Lamberts, K. (2000). Information-accumulation theory of speededcategorization. Psychol Rev, 107(2), 227–260.
Love, B. C. (2002). Comparing supervised and unsupervised category learning. Psychonomic Bulletin & Review, 9(4), 829–835.
Love, B. C., Gureckis, T. M., & Medin, D. L. (2004). SUSTAIN:
A network model of category learning. Psychological Review,111(2), 309–332.
Luce, R. D. (1959). Individual choice behavior. New York: John
Wiley.
Luce, R. D. (1986). Response times: Their role in inferring elementary mental organization. Oxford, England: Oxford University
Press.
Maddox, W. T., & Ashby, F. G. (1993, Jan). Comparing decision bound and exemplar models of categorization. Percept Psychophys, 53(1), 49–70.
Manning, C., & Schütze, H. (1999). Foundations of statisticalnatural language processing. Cambridge, MA: MIT Press.
Markman, A. B., & Stilwell, C. H. (2001). Role-governed categories. Journal of Experimental and Theoretical Artificial Intelligence, 13(4), 329–358.
Marr, D. (1982). Vision. Freeman Publishers.
McKinley, S. C., & Nosofsky, R. M. (1993). Attention learning
in models of classification. ((Cited in Nosofsky, Palmeri, andMcKinley, 1994))
Medin, D. L., Altom, M. W., Edelson, S. M., & Freko, D.
(1982). Correlated symptoms and simulated medical classification. Journal of Experimental Psychology: Learning, Memory,
and Cognition, 8, 37–50.
Medin, D. L., & Schaffer, M. M. (1978). Context theory of classification learning. Psychological Review, 85, 207–238.
Medin, D. L., & Schwanenflugel, P. J. (1981). Linear separability

24

NOAH D. GOODMAN, JOSHUA B. TENENBAUM, JACOB FELDMAN, THOMAS L. GRIFFITHS

in classification learning. Journal of Experimental Psychology:
Human Learning and Memory, 7, 355–368.
Medin, D. L., Wattenmaker, W. D., & Hampson, S. E. (1987). Family resemblance, conceptual cohesiveness, and category construction. Cognitive Psychology, 19(2), 242–279.
Mervis, C. B., & Rosch, E. H. (1981). Categorization of naturalobjects. Annual Review of Psychology, 32, 89–115.
Metropolis, A. W., Rosenbluth, A. W., Rosenbluth, M. N., Teller,
A. H., & Teller, E. (1953). Equations of state calculations by fastcomputing machines. Journal of Chemical Physics, 21, 10871092.
Murphy, G. L. (2002). The big book of concepts. Cambridge, MA:
MIT Press.
Navarro, D. J. (2006). From natural kinds to complex categories.
In R. Sun & N. Miyake (Eds.), Proceedings of the 28th annual
conference of the cognitive science society (pp. 621–626).
Nosofsky, R. M. (1986, Mar). Attention, similarity, and theidentification-categorization relationship. J Exp Psychol Gen,
115(1), 39–61.
Nosofsky, R. M., Clark, S. E., & Shin, H. J. (1989, Mar). Rules
and exemplars in categorization, identification, and recognition.
J Exp Psychol Learn Mem Cogn, 15(2), 282–304.
Nosofsky, R. M., & Palmeri, T. J. (1996). Learning to classify
integral-dimension stimuli. Psychonomic Bulletin & Review,
3(2), 222–226.
Nosofsky, R. M., & Palmeri, T. J. (1998). A rule-plus-exception
model for classifying objects in continuous-dimension spaces.
Psychonomic Bulletin & Review, 5, 345–369.
Nosofsky, R. M., Palmeri, T. J., & McKinley, S. C. (1994). Ruleplus-exception model of classification learning. Psychological
Review, 101(1), 53–79.
Oaksford, M., & Chater, N. (Eds.). (1998). Rational models ofcognition. Oxford: Oxford University Press.
Osherson, D. N., & Smith, E. E. (1981, Feb). On the adequacyof prototype theory as a theory of concepts. Cognition, 9(1),35–58.
Pinker, S. (1997). How the mind works. W. W. Norton & Company.
Posner, M. I., & Keele, S. W. (1968). On the genesis of abstract
ideas. Journal of Experimental Psychology, 77(3), 353–363.
Pothos, E. M. (2005, Feb). The rules versus similarity distinction.
Behav Brain Sci, 28(1), 1–14; discussion 14-49.
Ratcliff, R., Zandt, T. V., & McKoon, G. (1999). Connectionist anddiffusion models of reaction time. Psychol Rev, 106(2), 261–
300.
Reed, S. K. (1972). Pattern recognition and categorization. Cognitive Psychology, 3, 393-407.
Rehder, B. (2003). A causal-model theory of conceptual representation and categorization. Journal of Experimental Psychology:
Learning, Memory, and Cognition, 29, 1141-1159.
Russell, S. J., & Norvig, P. (2002). Artificial intelligence: A modern
approach (2nd ed.). Englewood Cliffs, NJ: Prentice Hall.
Sanborn, A., Griffiths, T., & Navarro, D. (2006). A more rationalmodel of categorization. In Proceedings of the twenty-eighth
annual conference of the cognitive science society.
Schyns, P. G., Goldstone, R. L., & Thibaut, J.-P. (1998). The development of features in object concepts (with commentary). Behavioral and Brain Sciences, 21, 1–54.
Schyns, P. G., & Rodet, L. (1997). Categorization creates functional features. Journal of Experimental Psychology: Learning,
Memory & Cognition, 23, 681–696.
Shepard, R. N. (1987). Towards a universal law of generalization
for psychological science. Science, 237, 1317-1323.

Shepard, R. N., & Chang, J. J. (1963). Stimulus generalization in
the learning of classifications. J Exp Psychol, 65, 94–102.
Shepard, R. N., Hovland, C. L., & Jenkins, H. M. (1961). Learning and memorization of classifications. Psychological Monographs: General and Applied, 75(13), 1–42.
Sloman, S. A. (1996). The empirical case for two systems of reasoning. Psychological Bulletin, 119(1), 3–22.
Sloman, S. A., Love, B. C., & Ahn, W. kyoung. (1998). Feature
Centrality and Conceptual Coherence. Cognitive Science, 22,
189–228.
Smith, J. D., & Minda, J. P. (1998). Prototypes in the mist: The
early epochs of category learning. Journal of Experimental Psychology: Learning, Memory, and Cognition, 24, 1411–1436.
Smith, J. D., Minda, J. P., & Washburn, D. A. (2004, Sep). Category
learning in rhesus monkeys: a study of the shepard, hovland, andjenkins (1961) tasks. J Exp Psychol Gen, 133(3), 398–414.
Tenenbaum, J. B. (1999a). A Bayesian framework for concept
learning. Unpublished doctoral dissertation, Massachussets Institute of Technology, Cambridge, MA.
Tenenbaum, J. B. (1999b). Bayesian modeling of human concept
learning. In M. S. Kearns, S. A. Solla, & D. A. Cohn (Eds.), Advances in neural information processing systems 11 (p. 59-65).
Cambridge, MA: MIT Press.
Tenenbaum, J. B. (2000). Rules and similarity in concept learning.
In S. A. Solla, T. K. Leen, & K.-R. Muller (Eds.), Advances in
Neural Information Processing Systems 12. Cambridge, MA:
MIT Press.
Tenenbaum, J. B., & Griffiths, T. L. (2001). Generalization, similarity, and Bayesian inference. Behavioral and Brain Sciences,24, 629-641.
Tenenbaum, J. B., & Xu, F. (2000). Word learning as Bayesianinference. In Proceedings of the 22nd annual conference of thecognitive science society. Hillsdale, NJ: Erlbaum.
Wittgenstein, L. (1953). Philosophical investigations. New York,MacMillan.
Xu, F., & Tenenbaum, J. B. (2007). Word learning as bayesianinference. Psychological Review.

Appendix A
Derivation of the Prior
We begin with the expression for the prior probability ofa formula given production probabilities τ (Eq. 3):
Y
P(F|G, τ) =
τ(s),
(10)
s∈DerivF

However, we wish to allow uncertainty over the values of the
production probabilities, thus:Z
P(F|G) =P(F, τ|G)dτ
Z=
P(τ)P(F|τ, G)dτ
(11)


Z
 Y

=
P(τ) 
τ(s) dτ,s∈DerivF

where P(τ) is the prior probability for a given set of production probabilities. (Note that the integral of Eq. 11 is overall production probabilities—a product of simplices.) Since

25

A RATIONAL ANALYSIS OF RULE-BASED CONCEPT LEARNING

we have no a priori reason to prefer one set of values forτ to another, we apply the principle of indifference (Jaynes,
2003) to select the least informative prior: P(τ) = 1. The
probability of a formula becomes:Z  Yτ(s) dτ.
P(F|G) =(12)s∈DerivF

We may simplify this equation by recognizing the integral asa Multinomial-Dirichlet form (see Gelman, Carlin, Stern, &Rubin, 1995):
Yβ(CY (F) + 1)
P(F|G) =
.
(13)
β(1)
Y∈ non-terminals of G

Here the expression CY (F) is the vector of counts of the
productions for non-terminal symbol Y in DerivF (and 1
is the vector of ones of the same length). The function
β(c1 , c2 , ..., cn ) is the multinomial beta function (i.e. the normalizing constant of the Dirichlet distribution for pseudocounts c1 , c2 , ..., cn , see Gelman et al. (1995)), which may
be written in terms of the Gamma function:QnΓ(ci )Pnβ(c1 , c2 , ..., cn ) = i=1(14)
Γ( i=1 ci )Appendix B
Derivation of the Likelihood
In this appendix we will derive the likelihood function, Eq. 5. The DNF grammar generates a concept language of formulae, and it will be useful in what follows
to write the formulae in two parts, the “quantified” part∀x (`(x)⇔Def(x)), and the “definition” part Def(x), where
the definition part is a disjunction of conjunctions of predicate terms.
We wish to define the truth-value of Def(x) for a given object x. Following the usual approach in mathematical logic(Enderton, 1972) the evaluation of Def(x) is given recursively:
1. Def(x) is a term.
2. If a term is a feature predicate, such as f1 (x)=0, then it
can be evaluated directly (presuming that we know the feature values for the object x).
3. If a term is a conjunction of other terms, A(x) ∧ B(x),then it is True if and only if each of the other terms is True.
4. If a term is a disjunction of other terms, A(x) ∨ B(x),then it is True if and only if any of the other terms is True.
At first this definition may appear vacuous, but it provides
a concrete procedure for reducing evaluation of Def(x) toevaluation of (primitive) feature predicates. The steps of thisreduction exactly parallel the syntactic derivation from which
the formula was built, hence providing a compositional semantics. (For a more careful treatment of the general issueof compositionality in Bayesian models, see N. D. Goodman
et al. (In Press).) We now have an evaluation procedure thatassigns a truth value to the definition part of each formula foreach object; we write this truth value also as Def(x).

The natural reading of the “quantified” part of the formula
is “the formula is true if, for every example, the label is true if
and only if Def(x) is true”. Using this as the only constraint
on the likelihood, P(`(E), E|F) is nonzero only when F istrue, and otherwise uniform. (This is again an application of
the principle of indifference: we add no additional assumptions, and are thus indifferent among the worlds compatible
with the formula.) Thus, with logical True/False interpreted
as probability 1/0:^
P(`(E), E|F) ∝`(x)⇔Def(x).
(15)
x∈E

We needn’t worry about the constant of proportionality in
Eq. 15, because it is independent of the formula F (this holds
because there is exactly one labeling which makes the formula true for each set of examples).
If we knew that the observed labels were correct, and we
required an explanation for each observation, we could stopwith Eq. 15. However, we assume that there is a probability e−b that any given example is an outlier (ie. an unexplainable observation which should be excluded from induction)9 . Writing I for the set of examples which are notoutliers (which ranges over subsets of E), the likelihood becomes:
X
P(`(E), E|F) =P(I)P(`(I), I|F)
I⊆E

X
^
∝
(1 − e−b )|I| (e−b )|E|−|I|`(x)⇔Def(x)
x∈I

I⊆E

=

X

−b |I|(1 − e ) (e−b )|E|−|I|I⊆{x∈E|`(x)⇔Def(x)}= e−bQ` (F) ,(16)
where the last step follows from the Binomial Theorem. We
have used the abbreviation Q` (F) = |{x∈E|¬(`(x)⇔Def(x))}|(this is the number of example objects which do not satisfy
the definition asserted by F).

Appendix C
A Grammar-based Monte Carlo
Algorithm
The expected generalization probability of Eq. 7 cannot
be directly evaluated, since the set of formulae is infinite.
However, this expectation may be approximated by importance sampling from the posterior distribution (Eq. 6). We
now sketch a Markov chain Monte Carlo algorithm for sampling from the posterior distribution10 . This algorithm applies generally for inference over a grammatically structured
hypothesis space.
9
We have written the outlier probability as an exponential
merely for later convenience.
10
Software implementing this algorithm is available from the authors’ web site.

26

NOAH D. GOODMAN, JOSHUA B. TENENBAUM, JACOB FELDMAN, THOMAS L. GRIFFITHS

We wish to define a Markov chain on the space of parsetrees (the grammatical derivations, up to order), in which
each step is compatible (in some intuitive sense) with thestructure of the grammar, G. We do so by the MetropolisHastings procedure (Metropolis, Rosenbluth, Rosenbluth,
Teller, & Teller, 1953), using subtree-regeneration proposals which formalize the intuitive idea “generate a proposal
by changing a (syntactically coherent) part of the given formula.”First fix an auxiliary probabilistic CFG, to be used in proposal generation, by choosing a convenient set of production
probabilities, σ, for G. Now the subtree-regeneration proposal is generated from parse tree T as follows: select n ∈ T
uniformly at random from among the non-terminal nodes ofT , remove all nodes of T below n, now regenerate the tree
below n according to the stochastic rules of Gσ , to get proposal T 0 . (If T 0 = T , repeat the process.) Each proposal isaccepted with probability equal to the minimum of 1 and:P(E, `(E)|FT 0 ) P(T 0 |G) |T | P(T |G, σ)···.
P(E, `(E)|FT ) P(T |G) |T 0 | P(T 0 |G, σ)(17)

Where FT is the formula associated with parse T , and |T | isthe number of non-terminal symbols in T . For the Rational
Rules posterior each of the terms in Eq. 17 may be easily
evaluated: the likelihood by Eq. 5, the prior by Eq. 4, andP(T 0 |G, σ) by Eq. 3.
Detailed balance follows as usual in the MetropolisHastings prescription, supplemented with some graph andcounting arguments. Since we could amputate at the root,
generating a completely new parse tree from the start symbol, this proposal scheme is ergodic. From ergodicity anddetailed balance we may conclude that this Markov chain
converges to P(T |E, `(E), G) in distribution. By interpreting
each parse T as its formula FT we generate samples from the
Rational Rules posterior.
In the reported results the RRDNF model was approximated by using this Monte Carlo algorithm. Except whereotherwise noted 30,000 iterations were used to approximate
each reported value, and convergence of most approximations was verified by doing five independent simulations (reported results are the mean of these five runs—hence an aggregate of 150,000 samples—and error bars, where given,
are standard error over the five runs).

P → Fi . Because these production probabilities determine
the relative importance of the features in generating a concept, their posterior expectations capture the relative informativeness of the features.
The posterior probability of the production probabilities
τP for non-terminal P, given a formula, is:P(τP |F) = R=R

In the main text we have defined the posterior feature
weights by:P(F|τP )dτP
QN
(τP,i )count( fi ∈F)= R QNi=1
count( fi ∈F) dτP
i=1 (τP,i )QN
count( fi ∈F)
(τ
)
P,i
= i=1
.
β(count( fi ∈F) + 1)

cplx(F)

P(F|E, `(E)),(19)

Where 1 indicates the vector of all ones. The expected valueof production probability τPk (for production P → Fk ), given
formula F, is then:Z
E P(τP |F) (τPk ) =τPk P(τP |F)dτP
R
QN
τPk i=1(τP,i )count( fi ∈F) dτP(20)=β(count( fi ∈F) + 1)β(count( fi ∈F) + 1 + δk )=.
β(count( fi ∈F) + 1)
Where δk indicates the vector with a 1 in the k-place, andzeros elsewhere. If we expand the beta functions in terms of
gamma functions, most terms cancel giving us:PΓ(count( fk ∈F) + 2) · Γ(N + i count( fi ∈F))P
E P(τP |F) (τPk ) =Γ(count( fk ∈F) + 1) · Γ(N + 1 + i count( fi ∈F))
Γ(count( fk ∈F) + 2) · Γ(N + cplx(F))=Γ(count( fk ∈F) + 1) · Γ(N + 1 + cplx(F))
1 + count( fk ∈F)=
N + cplx(F)(21)

E P(τP |E,`(E)) (τPk ) =X 1 + count( fk ∈F)
F

F

P(τP )P(F|τP )dτP
P(F|τP )where the last simplification follows from the recursion
Γ(z + 1) = zΓ(z). Finally, the posterior expectation for production probability τPk is given by:Appendix D
Derivation of Feature Weights

X count( fi ∈F)

P(τP )P(F|τP )(18)

and used them as an intuitive measure of the importance ofeach feature, as estimated by the model. We will now showthat these weights are related in a simple way to the posterior
expectations of the production probabilities for productions

N + cplx(F)P(F|E, `(E)) (22)Thus the feature weights, Eq. 18, are monotonically related
to the posterior expectations of the production probabilities,
Eq. 22. The primary difference between the two, which is
unimportant for our purposes, is that features which are neverused will have non-zero posterior expectation, but zero posterior weight.