Analyzing the RULEX model of category learning
Introduction
Early research on human category learning (e.g., Bruner et al., 1956) stressed the importance of systematic rule search. The idea is that people solve a learning problem serially, by forming hypotheses about the structure of a category, and testing them against environmental feedback. Following influential studies such as those of Posner and Keele (1968) and Rosch and Mervis (1975), this notion of rule-based categories fell out of favor, and was largely replaced by prototype-based models and exemplar-based models (see Komatsu, 1992, for an overview). Nevertheless, interest in rule-based models has resurfaced in recent years, in part due to concerns with the psychological plausibility of the high-memory requirements of existing models, but also due to the ability of rule-based models to account for phenomena previously assumed to be inconsistent with them.
One of the more interesting rule-based models is Nosofsky, Palmeri et al., 1994, Nosofsky and Palmeri, 1995, Palmeri and Nosofsky, 1998) rule-plus-exception (RULEX) model, which has been shown to capture a number of important empirical findings with minimal memory requirements. However, work involving RULEX is hampered by the difficulty in extracting precise predictions from the model: extensive simulations are required in order to estimate the probability that RULEX makes a particular response on any given trial. The main purpose of this paper is to introduce an algorithmic method of quickly calculating response probabilities for RULEX without having to resort to stochastic methods. However, since the methods used are standard combinatorics, an ancillary goal is to illustrate the general idea of developing algorithms for computing discrete models in cognitive psychology. It should be emphasized at the outset that the notation used in this paper differs from that used in previous RULEX papers. This is unavoidable, since the mathematical approach adopted here necessarily requires the use of a large number of functions and variables, which rapidly become unwieldly in the original notation.
Section snippets
The RULEX model
The workings of RULEX during supervised learning tasks are as follows. When presented with a stimulus, a participant is generally assumed to have a candidate rule in mind which assigns the observed stimulus to one of the available categories, and responds accordingly. If no rule is available, or if the rule does not help in this case, then a response is made at random. After receiving some feedback the participant may either keep the rule, or discard it and try a new one. The next trial
Calculating the predictions of cognitive models
Calculating RULEX predictions is made difficult, not by any inherent problem with the model, but by the method of its construction. Nosofsky, Palmeri et al. (1994) began with an intuition about the process by which people might solve categorization problems, which became formalized as the RULEX model. The principal interest of those authors was to expound a theoretical idea, so the purpose of the model was to illustrate the theory, and not necessarily to provide a tractable statistical
On the survival of a rule
Suppose that rule r is adopted at some point during exact, inexact, or conjunctive search. According to the RULEX model, that rule will be maintained until it makes too many errors, or is judged to be good enough to adopt permanently. Furthermore, so long as rule r survives, the behavior of RULEX does not depend on the rules that were adopted previously. This suggests that a basic mathematical unit of RULEX is the length of time spent considering the rule. I will refer to this time as the
Learning good rules
The first source of learning in the RULEX model is the sequential search for good rules. In the previous section lifetime distributions were derived that precisely express the “goodness” of any particular rule. In this section, I use these lifetime distributions to find the probability that RULEX is considering any particular rule on any given trial.
Finding response probabilities
The final aspect of the derivations concerns the probability that RULEX makes the correct response on any given trial. Conceptually, this can be divided into the probability of making the correct response during rule search and the probability of making the correct response during exception learning.
Application: The Shepard, Hovland & Jenkins Task
As an initial illustration of the methods developed in this paper, this section reproduces and extends RULEX results pertaining to the classic “Shepard, Hovland and Jenkins” task. Shepard et al. (1961) studied human performance on a category learning task involving eight stimuli divided evenly between two categories. The stimuli were generated by varying exhaustively three binary dimensions such as (black, white), (small, large) and (square, triangle). They observed that, if these dimensions
General discussion
Formal models of psychological processes play an important role in understanding cognition, so it is useful to be able to calculate the predictions of these models in an efficient and precise manner. This paper has outlined a formalization of a version of the RULEX model using no more than basic probability theory and simple combinatorics. In doing so, not only do we obtain a faster method of calculating model predictions, but gain an insight into the internal workings of the model. The
Acknowledgments
Part of this work was undertaken while the author was employed at Ohio State University. The research was financially supported by NIH grant R01-MH57472, ARC grant DP-0451793, and by a grant from the Office of Research at OSU. The Matlab functions used in this paper are available from the author's website. I thank Rob Nosofsky, Rich Shiffrin and an anonymous reviewer for helpful comments.
References (14)
- et al.
Family resemblance studies in the internal structure of categories
Cognitive Psychology
(1975) - et al.
A study of thinking
(1956) Minimization of Boolean complexity in human concept learning
Nature
(2000)Recent views of conceptual structure
Psychological Bulletin
(1992)ALCOVE: An exemplar-based connectionist model of category learning
Psychological Review
(1992)- et al.
Extending the ALCOVE model of category learning to featural stimulus domains
Psychonomic Bulletin & Review
(2002) - Navarro, D. J., & Lee, M. D. (in press). An application of minimum description length clustering to partitioning...
Cited by (8)
Algorithms of adaptation in inductive inference
2022, Cognitive PsychologyCitation Excerpt :Our analysis of explicit rule changes suggested even greater degrees of anchoring than that found in Experiment 1 with participants making very few changes to their hypotheses on average when seeing their partners’ data despite this data being valuable from a normative perspective. Finally, we based our implementation of RULEX on Navarro (2005). Our RULEX* has several search phases: 1.
Mathematical Psychology
2015, International Encyclopedia of the Social & Behavioral Sciences: Second EditionComplexity minimization in rule-based category learning: Revising the catalog of Boolean concepts and evidence for non-minimal rules
2007, Journal of Mathematical PsychologyData compression in artificial category learning
2012, Annee PsychologiqueRipple-down rules with censored production rules
2012, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)