A Rational Analysis of Rule-based Concept LearningNoah D. Goodman and Joshua B. TenenbaumMassachusetts Institute of TechnologyJacob FeldmanRutgers UniversityThomas L. GriffithsUniversity of California, BerkeleyRevision Submitted October, 2007Address correspondence to [email protected] propose a new model of human concept learning that provides a rational analysis of learn-ing 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 pre-dictions to human generalization judgments in several well-known category learning experi-ments, 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 naturalsetting in several ways—and again find that the model explains human performance.But what are concepts save formulations andcreations of thought, which, instead of givingus 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 through-out 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 alsobe our focus here. It is clear how an ability to separate ob-jects 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 29thAnnual Meeting of the Cognitive Science Society. We wish tothank Thomas Palmeri and two anonymous reviewers for very help-ful comments. This work was supported by the J. S. McDonnellFoundation causal learning collaborative initiative (NDG and JBT),grants from the Air Force Office of Scientific Research (TLG andJBT), 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 despitegreat uncertainty. Even very sparse and noisy evidence, suchas a few randomly encountered examples, can be sufficientfor a young child to accurately grasp a new concept.3. Many concepts are formed by combining simpler con-cepts, and the meanings of complex concepts are derivedin 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 lin-guistic structures are constructed, from simpler elements: forexample, morphemes are combined into words, words intophrases, phrases into more complex phrases and then sen-tences.In our view, all of these intuitions about concepts are cen-tral 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 firsttheme, concepts as rules for discriminating among categoriesof objects (Bruner, Goodnow, & Austin, 1956). Themes twoand three were also present, but only in limited ways. Re-searchers examined the processes of learning concepts fromexamples, but in a deductive, puzzle-solving mode more thanan inductive or statistical mode. The discrimination rulesconsidered were constructed compositionally from simplerconcepts or perceptual features. For instance, one mightstudy how people learn a concept for picking out objects as“large and red and round”. An important goal of this researchprogram was to characterize which kinds of concepts wereharder or easier to learn in terms of syntactic measures of aconcept’s complexity, when that concept was expressed as acombination of simple perceptual features. This approach2 NOAH D. GOODMAN, JOSHUA B. TENENBAUM, JACOB FELDMAN, THOMAS L. GRIFFITHSreached its apogee in the work of Shepard, Hovland, andJenkins (1961) and Feldman (2000), who organized possi-ble Boolean concepts (those that discriminate among objectsrepresentable by binary features) into syntactically equiva-lent families and studied how the syntax was reflected inlearnability.A second wave of research on concept learning, oftenknown as the “statistical view” or “similarity-based ap-proach”, emphasized the integration of themes one and twoin the form of inductive learning of statistical distributions orstatistical discrimination functions. These accounts includeprototype theories (Posner & Keele, 1968; Medin & Schaffer,1978), exemplar theories (Shepard & Chang, 1963; Nosof-sky, 1986; Kruschke, 1992), and some theories in between(Anderson, 1990; Love, Gureckis, & Medin, 2004). Thesetheories do not rest on a compositional language for conceptsand so have nothing to say about theme three—how simpleconcepts are combined to form more complex structures (Os-herson & Smith, 1981).An important recent development in the statistical tra-dition has been the rational analysis of concept learningin terms of Bayesian inference (Shepard, 1987; Anderson,1990; Tenenbaum & Griffiths, 2001). These analyses showhow important aspects of concept learning—such as theexponential-decay gradient of generalization from exemplars(Shepard, 1987) or the transitions between exemplar and pro-totype behavior (Anderson, 1990)—can be explained as ap-proximately optimal statistical inference given limited exam-ples. However, these rational analyses have typically beenlimited by the need to assume a fixed hypothesis space ofsimple candidate concepts—such as Shepard’s (1987) “con-sequential