1. Introduction

Hiking through the Bavarian Alps, you come upon a large bird gliding over a meadow. You pull out your European bird guidebook to identify it. From the shape of its body, you assume that this is a bird of prey, so you turn to the section on raptors in the guide. To determine the exact species, you next use size to narrow down your search to a few kinds of hawks; then you use color to eliminate a couple more species; and finally with one last cue - tail length - you can make a unique classification. Using only four cues (or features), you correctly identify this bird as a sparrow hawk. You could take out your binoculars and check more cues to support this identification, but for a rapid decision these few cues are enough.
How would this categorization process proceed if a rabbit rather than a human were watching the bird? The rabbit would not be interested in knowing the exact species of bird flying overhead, but rather would want to categorize it as predator or not, as quickly as possible - the Rabbit’s Guide to Birds has only two short sections. While the rabbit could also use several cues to make its category assignment, as soon as it finds enough cues to decide "predator" - for instance, that this bird is gliding - it will not bother gathering any more information, and instead will head for shelter. Obviously, in the case of the rabbit, speed is of the essence when categorizing birds as predators or nonpredators. Humans face similar circumstances where rapid categorization is called for, making use of only whatever information is immediately available. Being able to categorize rapidly the intention of another approaching person as either hostile or courting, for instance, will enable the proper reactions to ensure the most desirable outcome.
In this paper, we consider the case for a "fast and frugal" (ý la Gigerenzer & Goldstein, 1996) model of categorization, akin to the lexicographic process of bird identification described in the first paragraph. This model, which we call Categorization by Elimination (CBE), uses only as many of the available cues or features as are necessary to first make a specific categorization. As a consequence, it often uses far fewer cues in categorizing a given stimulus than do the standard cue-combination models, yielding its fast frugality. This information-processing advantage can be crucial in a variety of categorization contexts where speed is called for, as in identifying threats. On the other hand, the accuracy of this approach typically rivals that of more computationally extensive algorithms, as we will show. We therefore propose Categorization by Elimination as a parsimonious psychological model, as well as a potentially useful candidate for applied machine-learning categorization tasks.
Categorization by Elimination is closely related to Tversky’s Elimination by Aspects (EBA) model of choice (Tversky, 1972). After describing competing psychological and machine-learning models of categorization in the next section, we discuss the background of elimination models in section 3. We present the Categorization by Elimination model in section 4. Most other recent models of human categorization focus on the use of two or three cues, situations in which CBE can show little advantage. Therefore, we have experimentally investigated a multiple-cue categorization task in which we can compare our model with others in accounting for human performance with seven cue dimensions. We describe this study, which involves categorizing animate motion trajectories into different behavioral intentions, in section 5. CBE does as well as linear categorization methods, and does not overfit the data as neural networks seem to. Next, in section 6 we look at how well our algorithm does alongside some of the multiple-attribute categorization methods developed in psychology and machine learning on standard data sets from the latter field. This comparison shows that Categorization by Elimination can often compete in accuracy with more complex methods. Further, if minimizing the number of cues used is sought to maximize computational speed, CBE usually emerges as the clear winner. Finally in section 7 we consider some of the challenges still ahead, including how to test CBE against human learning data.

2. Existing Categorization Models

Many different models of categorization have been proposed in both the psychological and machine learning literature. Psychologists are primarily concerned with developing a model that best describes human categorization performance, while in machine learning the goal is to develop an optimally-performing model - that is, one with the highest accuracy of categorization. These two goals are not necessarily mutually exclusive; indeed, one of the main findings so far in the field of human categorization is that people are often able to achieve near optimal performance (that is, categorize a stimulus set with minimal errors - see Ashby & Maddox, 1992). As a consequence, some models, including neural networks and SCA (Miller & Laird, 1996) are often aimed at filling both roles.
However, the majority of psychological studies of categorization have used simple stimuli that vary on only a few (2-4) dimensions, unlike the typical high-dimensional machine learning applications. It remains to be seen whether humans can also be optimal at categorizing multi-dimensional objects. In addition, the predominant psychological models of categorization have not addressed the issue of constraints, such as limited time and information. What might the categorization process be when there are both time and information constraints, either because there is an overwhelming number of possible cues to use or only a subset of cues available? Here we briefly review some of the currently popular categorization models for human categorization and machine learning with these questions in mind. Throughout the remainder of the paper we use the terms cues, aspects, dimensions, and features, as appropriate, to all mean roughly the same thing.
The predominant theories of categorization in the psychology literature include exemplar models (Nosofsky, 1986), decision bound models (Ashby & Gott, 1988), and neural network models (e.g. ALCOVE - see Kruschke, 1992). Each of these categorization models assumes that the stimuli may be represented as points in a multidimensional space. Furthermore, these models all assume that humans integrate features - that is, combine multiple cues to come to a final judgment - and that we usually use all of the cues that are present - that is, do not discard any available information.
Exemplar models (Brooks, 1978; Estes, 1986; Medin & Schaffer, 1978; Nosofsky, 1986) assume that when presented with a novel object, humans compute the similarity between that object and all the possible categories in which the novel object could be placed. Similarity is a function of the sum of the distances between the object and all the exemplars in the particular category. The object is placed into the category with which it is most similar.
Nosofsky’s (1986) generalized context model (GCM) allows for variation in the amount of attention given to different features during categorization (see also Medin & Schaffer, 1978). Therefore, it is possible that different cues will be used in different tasks. However, this attention weight remains the same for the entire stimulus set for each particular categorization task, rather than varying across different objects belonging to the same category (in contrast to our new method, as we will see).
Decision Bound Theory (or DBT - see Ashby & Gott, 1988) assumes that there is a multidimensional region associated with each category, and therefore that categories are separated by bounds. An object is categorized according to the region of perceptual space in which it lies. Similarly, neural network models (e.g., Kruschke, 1992) learn hyperplane boundaries between categories, capturing this knowledge in their trainable weights. In both cases, all of the cues available in a particular stimulus are used to determine the region of multidimensional space, and hence the associated category, in which that stimulus falls.
These psychological models all categorize by integrating cues and using all the cues available (except in GCM if a cue has an attention weight of 0). In addition, training these models to learn new categories is a relatively simple process. But the memory requirements assumed by these models do differ: for example, GCM assumes that all exemplars ever encountered are stored and used when categorizing a novel object, while DBT does not need to store any exemplars. In comparison, our CBE algorithm does not integrate all available cues, is similarly easy to train, and typically requires little memory.
Another approach to psychological modeling is captured in the discrete symbol-processing framework of Miller and Laird’s (1996) Symbolic Concept Acquisition (SCA) model. Here rules are built up incrementally for classifying stimuli according to specific features, beginning with very general rules that test a single feature and progressing to more detailed rules that must match the stimuli on many features. While there are similarities between this approach and CBE (in particular, the order in which features are processed can be related to our cue validity measure), one major difference is that new stimuli are first checked against rules using all available cues, and only when this fails are fewer cues tested against the more general rules. In contrast, CBE begins with a single cue, and only adds new ones if necessary, thereby minimizing computation. The earlier EPAM symbolic discrimination-net model (Feigenbaum & Simon, 1984) tests rules in the efficient general-to-specific method we advocate, but the rest of our approach is distinct.
In machine learning, predominant categorization theories include neural networks, Classification and Regression Trees (or CART - see Breiman, Friedman, Olshen, & Stone, 1984), and decision trees (e.g., ID3 - see Quinlan, 1993). The goal of these machine learning models is usually to maximize categorization accuracy on a given useful data set. Algorithm complexity and speed are not typically the most important factors in developing machine learning models, so that many are not psychologically plausible.
One model that does attempt psychological plausibility by applying selective attention to unsupervised concept formation is Gennari’s (1991) CLASSIT. This system classifies objects initially using a subset of the available cues determined by their attentional salience. However, all cues must still be considered before a final decision is reached, due to a "worst case" stopping rule.
Thus, even though many of the machine learning models (e.g., CART and CLASSIT) use only a few cues during a given categorization, the process of setting up the algorithm’s decision mechanisms beforehand, including determining which cues to use, can be very complex. In contrast, our CBE algorithm has a simple learning phase, and still maintains comparable accuracy using few cues.

3. Elimination Models

Motivated by the concerns raised in section 1, we wanted to develop a fast and frugal categorization method that combines the best aspects of both the psychological and machine learning models. From the psychological models we used the concepts of simple training and decision processes and a small memory load. From the machine learning models we took the notion of categorizing stimuli without using all available cues. This combination led us to look into elimination models.
Classical elimination models were conceived of for choice tasks (Restle, 1961; Tversky, 1972) In a sequential elimination choice model, an object is chosen by repeatedly eliminating subsets of objects from further consideration, thereby whittling down the set of remaining possibilities. First a particular subset of the original set is chosen with some probability, using a particular feature to determine the subset members. Subsequent subsets are chosen in the same manner, with successive features, until only one object remains.
The most widely known elimination model in psychology is Tversky’s (1972) Elimination by Aspects (EBA) model of probabilistic choice. One of the motivating factors in developing EBA as a normative model of choice was that there are often many relevant cues that may be used in choosing among complex alternatives (Tversky, 1972). Therefore, part of any reasonable psychological model of choice should be a procedure to select and order the cues to use from among many alternatives. In EBA, the cues, or aspects, to use are selected according to their utility for some decision (for instance, to choose a restaurant from those nearby, what they serve and how much they charge might be the most important aspects). Possible remaining choices that do not possess the current aspect being used for evaluation (for instance, restaurants that do not serve seafood) are eliminated from the choice set. Furthermore, only aspects that are present in the most recent choice set are considered (for instance, if all nearby seafood restaurants are cheap, then expense will not be used as an aspect to distinguish further among them). Additional aspects are used only until a single choice can be made, which is different from the categorization models described above that use all cues.

4. Categorization by Elimination

Our new Categorization by Elimination algorithm is a noncompensatory lexicographic model of categorization, in that it uses cues in a particular order, and categorization decisions made by earlier cues cannot be altered (or compensated for) by later cues. In CBE, cues are ordered and used according to their validity. For our present purposes we define validity as a measure of how accurately a single cue categorizes some set of stimuli (i.e., percent correct). This is calculated by running CBE only using the single cue in question, and seeing how many correct categorizations the algorithm is able to make. (If using the single cue results in CBE being unable to decide between multiple categories for a particular stimulus, as will often be the case, the algorithm chooses one of those categories at random - in this case, cue validity will be related to a cue’s discriminatory power.) Thus if size alone is more accurate in categorizing birds (or more successful at narrowing down the possible categories) than shape alone, size would have a higher cue validity than shape. (There are other ways that cues can be ordered besides by validity, such as randomly or in order of salience, which we are currently exploring.)
CBE assumes that cue values are divided up into bins (either nominal or continuous) which correspond to certain categories. These bins form the knowledge base that CBE uses to map cue values onto the possible corresponding categories. As an example, the size cue dimension for birds could be divided into three bins: a large size bin (which could be specified numerically, e.g. "over 50 cm") corresponding to the categories of eagles, geese, and swans; a medium size bin corresponding to crows, jays, and hawks; and a small size bin corresponding to sparrows and finches.
To build up the appropriate bin structures, the relevant cue dimensions to use must be determined ahead of time. At present we construct a complete bin structure before testing CBE’s categorization performance, but learning and testing could also be done incrementally. In either case, bins can be constructed in a variety of ways from the training examples - in the next two sections, we present two possibilities.
A flowchart of CBE is shown in Figure 1. Given a particular stimulus to categorize, an initial set of possible categories is assumed, along with the ordered list of cue dimensions to be used. The categorization process begins by using the cue dimension C with the highest validity. Next a subset S of the possible categories is created containing just those categories that correspond to the first cue C’s value for the current stimulus object (this subset is determined through the binning map described earlier). If only one category corresponds to that cue value, the categorization process ends with this single category. If more than one category corresponds to the current cue value, that set of possible categories S is kept, and the cue with the next highest validity, C*, is checked. The set of categories S corresponding to the previous cue C’s value is intersected with the set, S*, of categories corresponding to the present cue C*’s value. This is CBE’s elimination step.
If only one category remains in the new set intersection, the algorithm terminates at this point with that one category. If more than one category remains, this intersection becomes the new set S of remaining possibilities, the next cue is checked, and the process is repeated. If the intersection is empty, then the present cue is ignored, the prior set S of categories is retained, and the next cue is evaluated. This process of checking cues and using them to reduce the remaining set of possible categories continues until a single category remains, or until all the cues have been checked, in which case a category is chosen from the remaining set at random.
This algorithm has several interesting features. It is frugal in information, using only those cues necessary to reach a decision. It is non-compensatory, with earlier cues