A Generative Theory of Similarity

A Generative Theory of Similarity Charles Kemp, Aaron Bernstein & Joshua B. Tenenbaum {ckemp, aaronber, jbt}@mit.edu Department of Brain and Cognitive Sciences Massachusetts Institute of Technology Abstract We propose that similarity judgments are inferences about generative processes, and that two objects appear similar when they are likely to have been generated by the same process. We present a formal model based on this idea, and suggest that it may be particularly useful for explaining high-level judgments of similarity. We compare our model to featural and transformational accounts, and describe an experiment where it outper- forms a transformational model.  similarity; generative processes; computational theory Every object is the outcome of a generative process. An animal grows from a fertilized egg into an adult, a city develops from a settlement into a metropolis, and an artifact is assembled from a pile of raw materials ac- cording to the plan of its designer. Observations like these motivate the generative approach, which proposes that an object may be understood by thinking about the process that generated it. The promise of the approach is that apparently complex objects may be produced by simple processes, an insight that has proved productive across disciplines including biology (Thompson, 1961), physics (Wolfram, 2002), and architecture (Alexander, 1979). To give two celebrated examples from biology, the shape of a pinecone and the markings on a cheetah’s tail can be generated by remarkably simple processes of growth. These patterns can be characterized much more compactly by describing their causal history than by at- tempting to describe them directly. Leyton has argued that the generative approach pro- vides a general framework for understanding cognition. Applications of the approach can be found in generative theories of memory (Leyton, 1992), categorization (An- derson, 1991; Feldman, 1997; Rehder, 2003), visual perception (Leyton, 1992), speech perception (Liber- man et al., 1967), syntax (Chomsky, 1965) 1 , and mu- sic (Lehrdahl and Jackendoff, 1996). This paper offers a generative theory of similarity, a notion often invoked by models of high-level cognition. We argue that two objects are similar to the extent that they seem to have been generated by the same underlying process. The literature on similarity covers settings that ex- tend from the comparison of simple stimuli like tones and colored patches to the comparison of highly-structured objects like narratives. The generative approach is rele- vant to the entire spectrum of applications, but we are particularly interested in high-level similarity. In par- ticular, we are interested in how similarity judgments draw on intuitive theories, or systems of rich conceptual knowledge (Murphy and Medin, 1985). Intuitive theories and generative processes are intimately linked: Murphy (1993), for example, defines a theory as “a set of causal relations that collectively generate or explain the phe- nomena in a domain.” Our generative framework should therefore help to explain how similarity judgments are guided by intuitive theories. Others have recognized the importance of this issue: Murphy and Medin (1985) sug- gest, for example, that “the notion of similarity must be extended to include theoretical knowledge.” We develop a formal theory of similarity and compare it to two existing theories. The featural account (Tver- sky, 1977) suggests that the similarity of two objects is a function of their common and distinctive features, and the transformation account suggests that similarity de- pends on the number of operations required to transform one object into the other (Hahn et al., 2003). We show that versions of both approaches emerge as special cases of our model, and present an experiment that directly compares our model with the transformation account. Generative processes and similarity Before introducing our formal model, we describe several cases where the assessment of similarity relies on infer- ences about generative processes. Suppose we are shown The approach we have described should be distinguished from two usages of “generative” that are found in the linguis- tics literature. Generativity sometimes refers to the infinite use of finite means: for us, a generative process need not meet this criterion, although many interesting processes will. The second (and more central) usage refers to a grammar’s abil- ity to generate the set of grammatical sentences: Chomsky (1965) defines a generative grammar as “a system of rules that in some explicit and well-defined way assigns structural descriptions to sentences.” A system of this sort need not be generative in our sense — in particular, it need not as- sume that structural descriptions have derivational histories. Generative grammars, however, are typically expressed us- ing formalisms that do assign derivational histories to struc- tural descriptions, and theories that assume the psychological reality of these histories are instances of the generative ap- proach. Chomsky (1995) has rejected theories of this sort: “the ordering of operations [in grammatical theory] is ab- stract, expressing postulated properties of the language fac- ulty of the brain, with no temporal interpretation implied.” Others, however, argue for linguistic theories that are gener- ative in our sense (Marantz,