Symposium on Concept Formation

Symposium on Computational Approaches to Concept Formation

The Symposium on Computational Approaches to Concept Formation was held at Stanford University on January 6 and 7, 1990. Some 48 researchers attended the meeting, of which 16 presented talks on their recent results in the area. Two fields - artificial intelligence and cognitive psychology - were well represented, with the former focusing on computational characteristics of concept learning algorithms and the latter focusing on computational models of human learning.

However, all attendees shared a concern with the topic of the meeting - concept formation - the incremental and unsupervised acquisition of conceptual knowledge. A variety of approaches to this problem were also represented, including inductive learning methods, explanation-based techniques, and connectionist algorithms. In general, the meeting fostered cross-disciplinary interaction on many issues, as revealed in the following summary of presentations.

Principles of Object Concept Formation

Several presentations illustrated general principles of concept formation. In general, these talks assumed that the learner passively accepts observations, that these observations contain all information used in the description of training instances, and that the only knowledge used is that acquired by the learner from previous experience.

A rational analysis of human concept formation.
John R. Anderson and Michael Matessa (Carnegie Mellon University) discussed the need to bridge the gap between computational and psychological principles of concept formation. Their central premise was that humans are rational but resource-bounded decision makers, and they showed how a variety of psychological phenomena can stem from such a `rational' view of human concept formation. They also described an incremental algorithm that constructs a hierarchy of probabilistic concepts.
Representational specificity and concept formation.
Joel Martin and Dorrit Billman (Georgia Institute of Technology) described an alternative to the traditional hierarchical approach to concept formation, discussing a method which incrementally chunks informative features into classification rules that implicitly define a set of (possibly overlapping) clusters. They considered methods for focusing attention on features that are statistically informative, and reported experimental evidence for the computational advantages and disadvantages relative to hierarchical strategies.
Concepts as probabilities, chunks, and templates.
Howard Richman (Carnegie Mellon University) reviewed the psychological evidence for some basic representational schemes. He enumerated three main alternatives: discrimination networks like those constructed by Epam, connectionist representations like those used by competitive learning methods, and Bayesian descriptions that combine probabilistic evidence. He examined the ability of each framework to explain observed context effects in psychological experiments on letter perception.
Hierarchical concept formation in perceptual domains.
Richard Granger (University of California, Irvine) drew from research on the human olfactory system to develop a biologically-inspired theory of hierarchical concept formation. His model is closely related to agglomerative (bottom-up) clustering strategies studied in the field of numerical taxonomy. This presentation was novel in its integration of biological and computational perspectives.
An adaptive network model of basic-level concept learning.
James Corter (University of Columbia), Mark Gluck, and Gordon Bower (Stanford University) described a connectionist model of concept learning that accounts for psychological evidence that some categories are more `basic' than others in terms of retrieval time and other measures. Their configural cue model uses only a single layer network, but adds representational power by describing instances and concepts as conjunctions of observed features.
Concept formation in structured domains.
Kevin Thompson and Pat Langley (NASA Ames) focused on concept formation over experiences having structured representations, in which the values of attributes can themselves be component objects and in which relations between components can be represented as well. Their concept formation algorithm is recursive, in that acquired component concepts are used to describe and influence the acquisition of composite concepts. Thus, their research has implications for work on representation change.
Learning to recognize movements.
Wayne Iba and John Gennari (University of California, Irvine) described concept formation as a way of improving the recognition of motor behaviors. In particular, movements like throwing can be segmented and represented in a manner that supports their storage in and retrieval from memory. This talk also raised issues about the processes required to match complex knowledge structures, and provided one approach to this problem.

The Role of Background Knowledge in Concept Formation

A second set of speakers focused on the use of prior background knowledge in concept formation, which can be used to augment or redescribe observations. As in recent work on explanation-based learning, domain knowledge can lead to inferences from the observation that bias the process of concept formation.

Explanation-based learning as concept formation.
Ray Mooney (University of Texas at Austin) questioned the traditional formalization of explanation-based methods as a supervised form of learning. Rather, he described a body of explanation-based work that is best viewed as unsupervised. In this framework, the domain theory need not be oriented towards making inferences regarding a target concept, but can be flexibly structured to support inferences along a variety of dimensions.
The interaction of theory and similarity in induction.
Ed Wisniewski and Doug Medin (University of Michigan) focused on psychological experiments that demonstrate the relative roles of background knowledge and observations in concept learning. Their results suggested that expectations have a strong impact on the concepts that humans acquire, leading them to consider more abstract features than when background knowledge is absent. However, observations also affect the features considered during learning, as well as the reasons people give for category membership. They outlined a process model of concept learning that begins to account for these effects.
Some influences of instance comparisons in concept formation.
Brian Ross and Tom Spalding (University of Illinois) outlined a theory, backed by results from psychological experiments, that emphasizes the role of reminding in concept learning. Their studies examined the nature of the generalizations formed during learning, the focus of the generalization process, and the effects of knowledge on the operation of this mechanism. Their theory assumes a hybrid representation of concepts that incorporates both exemplars and abstractions, and assumes that the inference process directs the formation of useful concepts.
Internal supervision of unsupervised clustering algorithms.
Michael Pazzani, Kamal Ali, and Glenn Silverstein (University of California, Irvine) described work on a hierarchical approach to concept formation that takes advantage of knowledge about which features one wants to predict. Their generalization of Gluck and Corter's measure of category utility weights features according to the importance of predicting them. They argued that this approach should lead to better predictive accuracy than methods that weight all features equally, such as Fisher's Cobweb. One can view unsupervised and supervised learning as special cases of this framework.

Concept Formation in Problem Solving

A third set of speakers examined the utility of concept formation in a variety of `problem-solving' contexts, including planning, mathematical reasoning, and game playing. In each case, the utility of concept formation is that it organizes problem-solving experience for efficient reuse in similar situations. These talks highlighted the importance of complex, bidirectional interactions between the learner and the environment.

An architecture for exploratory learning and problem solving.
Paul Scott and Shaul Markovitch (University of Michigan) described an approach to unsupervised learning in problem-solving domains that involves interaction with the environment, prediction of outcomes, and the search for novelty. Their Dido system incorporates a number of interacting learning mechanisms that let it partition events and induce descriptions for them that are useful in prediction.
Concept formation over explanations, plans, and problem solutions.
Jungsoon Yoo, Hua Yang, and Doug Fisher (Vanderbilt University) described mechanisms for concept formation that perform induction over problem-solving experience and plans. Building on Fisher's Cobweb algorithm for the hierarchical formation of probabilistic concepts, they outlined an algorithm for learning to solve algebra story problems that incorporates aspects of both inductive and explanation-based learning. They also reported an algorithm for means-ends planning that improves its search efficiency using a variant on the Cobweb method.
Learning useful abstractions by aggregation.
Nicholas Flann (Oregon State University) argued for the importance of concept formation in problem-solving contexts, where useful concepts can let one reformulate a problem at a higher level of abstraction. He described an approach to such reformulation and reported runs from the domain of chess endgames indicating the savings in search that result.
Dynamic concepts and their acquisition.
Jeff Shrager (Xerox PARC) discussed psychological data on children's acquisition of complex procedural concepts, such as cooking skills, through interaction with an expert. He also proposed a computational framework that accounts for aspects of these learning phenomena as the interpretation, revision, and combination of sensori-motor structures in long-term memory.
A computational account of conservation learning and development.
Tony Simon (Carnegie Mellon University) reviewed results from developmental psychology on conservation and described a computational model that accounts for the transition between observed stages. The model is implemented within the Soar architecture, in which the basic learning mechanism involves chunking the results of solved problems. He showed how this framework can produce useful concepts in the domain of conservation tasks, and linked these to human behavior.

Progress Amidst Variety

Collectively, the presentations described a variety of approaches to the task of concept formation. These differed along many dimensions, including their assumptions about the representation and organization of knowledge, their mechanisms for performance and learning, their focus on the relative roles of experience and knowledge, and their emphasis on computational, psychological, or biological evaluation.

However, many common themes also emerged, and the discussion after each talk highlighted the relations among the various research efforts. One encouraging sign was the frequent use of hybrid methods that combine features of earlier systems. For instance, some models incorporate both exemplars and abstractions, others combine logical and probabilistic notions, and still others consider combinations of inductive and theory-driven learning. Together with the increasing communication between representatives of cognitive psychology, machine learning, and even neurobiology, such hybrids provide clear evidence of progress in the study of concept formation.

In short, the symposium revealed new results on both the psychological and computational fronts, and encouraged the interchange of knowledge between these traditionally separate disciplines. Informal discussions during the meeting also suggested promising directions for future research in this increasingly active area.