Complexity minimization in rule-based category learning: Revising the catalog of Boolean concepts and evidence for non-minimal rules

Abstract Feldman [(2000). Minimization of Boolean complexity in human concept learning. Nature, 407, 630–633] has provided evidence that the complexity (subjective difficulty) of a Boolean concept is related to the length of its minimum algebraic description. The catalog of Boolean concepts [Feldman, J. (2003a). A catalog of Boolean concepts. Journal of Mathematical Psychology, 47, 98–112] provides an extensive list of basic categorization problems along with their minimal algebraic descriptions and complexity levels. In the present study, we demonstrated that the minimum algebraic description is very useful for describing the most economical categorization rule that can be used, but does not always correspond to the category definition used by a participant in a concept-learning task. We developed a new minimization procedure, reanalyzed Feldman's catalog and revised the complexity of 148 out of 253 basic concept types. Among these cases, two new solutions that correspond to concept types used in the classic study on categorization by Shepard, Hovland, and Jenkins [(1961). Learning and memorization of classifications. Psychological Monographs: General and Applied, 75, 1–42] predicted a new difficulty rank ordering (for Types I–VI) that did not agree with experimental results reported in the literature. New experimental results reported here show that participants used similar non-minimal classification rules that can be explained by the hypothesis-testing sequence in the RULEX model [Nosofsky, R. M., Palmeri, T. J., & McKinley, S. C. (1994). Rule-plus-exception model of classification learning. Psychological Review, 101, 53–79].