Skip to main content

Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

  • Letter
  • Published:

Minimization of Boolean complexity in human concept learning

Nature volume 407, pages 630–633 (2000)Cite this article

Abstract

One of the unsolved problems in the field of human concept learning concerns the factors that determine the subjective difficulty of concepts: why are some concepts psychologically simple and easy to learn, while others seem difficult, complex or incoherent? This question was much studied in the 1960s1 but was never answered, and more recent characterizations of concepts as prototypes rather than logical rules2,3 leave it unsolved4,5,6. Here I investigate this question in the domain of Boolean concepts (categories defined by logical rules). A series of experiments measured the subjective difficulty of a wide range of logical varieties of concepts (41 mathematically distinct types in six families—a far wider range than has been tested previously). The data reveal a surprisingly simple empirical ‘law’: the subjective difficulty of a concept is directly proportional to its Boolean complexity (the length of the shortest logically equivalent propositional formula)—that is, to its logical incompressibility.

This is a preview of subscription content, access via your institution

Access options

Buy this article

  • Purchase on SpringerLink
  • Instant access to full article PDF
Buy now

Prices may be subject to local taxes which are calculated during checkout

Figure 1: The D[P] hierarchy, showing the number of cases ( D [P]) in each family.
Figure 2: Results, showing log proportion correct as a function of Boolean complexity for each family (collapsing over parity).
Figure 3: Results by parity, collapsing over family.

Similar content being viewed by others

References

  1. Bourne, L. E. Knowing and using concepts. Psychol. Rev. 77, 546–556 (1970).

    Article  Google Scholar 

  2. Posner, M. I. & Keele, S. W. On the genesis of abstract ideas. J. Exp. Psychol. 77, 353– 363 (1968).

    Article  CAS  Google Scholar 

  3. Rosch, E. H. Natural categories. Cogn. Psychol. 4, 328 –350 (1973).

    Article  Google Scholar 

  4. Osherson, D. N. & Smith, E. E. On the adequacy of prototype theory as a theory of concepts. Cognition 9, 35–58 (1981).

    Article  CAS  Google Scholar 

  5. Medin, D. L. & Smith, E. E. Concepts and concept formation. Annu. Rev. Psychol. 35, 113– 138 (1984).

    Article  CAS  Google Scholar 

  6. Komatsu, L. K. Recent views of conceptual structure. Psychol. Bull. 112, 500–526 (1992).

    Article  Google Scholar 

  7. Medin, D. L., Wattenmaker, W. D. & Hampson, S. E. Family resemblance, conceptual cohesiveness, and category construction. Cogn. Psychol. 19, 242–279 (1987).

    Article  CAS  Google Scholar 

  8. Nosofsky, R. M., Palmeri, T. J. & McKinley, S. C. Rule-plus-exception model of classification learning. Psychol. Rev. 101, 53– 79 (1994).

    Article  CAS  Google Scholar 

  9. Pinker, S. Rules of language. Science 253, 530– 535 (1991).

    Article  ADS  CAS  Google Scholar 

  10. Smith, E. E., Patalano, A. L. & Jonides, J. Alternative strategies of categorization. Cognition 65, 167–196 ( 1998).

    Article  CAS  Google Scholar 

  11. Neisser, U. & Weene, P. Hierarchies in concept attainment. J. Exp. Psychol. 64, 640– 645 (1962).

    Article  CAS  Google Scholar 

  12. Bourne, L. E., Ekstrand, B. R. & Montgomery, B. Concept learning as a function of the conceptual rule and the availability of positive and negative instances. J. Exp. Psychol. 82, 538–544 ( 1969).

    Article  Google Scholar 

  13. Medin, D. L., Wattenmaker, W. D. & Michalski, R. S. Constraints and preferences in inductive learning: an experimental study of human and machine performance. Cogn. Sci. 11, 299–339 ( 1987).

    Article  Google Scholar 

  14. Shepard, R., Hovland, C. L. & Jenkins, H. M. Learning and memorization of classifications. Psychol. Monogr. Gen. Appl. 75, 1– 42 (1961).

    Article  Google Scholar 

  15. Nosofsky, R. M., Gluck, M. A., Palmeri, T. J., McKinley, S. C. & Glauthier, P. Comparing models of rule-based classification learning: a replication and extension of Shepard, Hovland and Jenkins (1961). Mem. Cogn. 22, 352– 369 (1994).

    Article  CAS  Google Scholar 

  16. Wegener, I. The Complexity of Boolean Functions (Wiley, Chichester, 1987).

    MATH  Google Scholar 

  17. Givone, D. D. Introduction to Switching Circuit Theory (McGraw Hill, New York, 1970).

    MATH  Google Scholar 

  18. Chaitin, G. J. On the length of programs for computing finite binary sequences. J. Assoc. Comput. Machin. 13, 547– 569 (1966).

    Article  MathSciNet  Google Scholar 

  19. Kolmogorov, A. N. Three approaches to the quantitative definition of information. Problems Inf. Transm. 1, 1–7 (1965).

    Google Scholar 

  20. Solomonoff, R. J. A formal theory of inductive inference. Part I. Inf. Control. 7, 1–22 (1964).

    Article  MathSciNet  Google Scholar 

  21. Li, M. & Vitányi, P. An Introduction to Kolmogorov Complexity and its Applications (Springer, New York, 1997).

    Book  Google Scholar 

  22. Garey, M. R. & Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-completeness (Freeman, New York, 1979).

    MATH  Google Scholar 

  23. Hovland, C. I. & Weiss, W. Transmission of information concerning concepts through positive and negative instances. J. Exp. Psychol. 45, 175–182 (1953).

    Article  CAS  Google Scholar 

  24. Haygood, R. C. & Devine, J. V. Effects of composition of the positive category on concept learning. J. Exp. Psychol. 74, 230–235 ( 1967).

    Article  CAS  Google Scholar 

  25. Nahinsky, I. D. & Slaymaker, F. L. Use of negative instances in conjunctive concept identification. J. Exp. Psychol. 84, 64–68 ( 1970).

    Article  Google Scholar 

  26. Rissanen, J. Modeling by shortest data description. Automatica 14 , 465–471 (1978).

    Article  Google Scholar 

  27. Chater, N. Reconciling simplicity and likelihood principles in perceptual organization. Psychol. Rev. 103, 566– 581 (1996).

    Article  Google Scholar 

Download references

Acknowledgements

Supported in part by a grant from the National Science Foundation. I thank S. J. Hanson, W. A. Richards, J. Tenenbaum and P. Tremoulet for helpful comments, and M. Balaban, E. Barenholtz, D. Berse, N. Folsom-Kovarik, J. Sutton and P. Tremoulet for assistance in data collection.

Author information

Authors and Affiliations

  1. Department of Psychology, Center for Cognitive Science, Rutgers University, New Brunswick, 08903 , New Jersey, USA

    Jacob Feldman

Authors
  1. Jacob Feldman
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jacob Feldman.

Supplementary information

Rights and permissions

Reprints and permissions

About this article

Cite this article

Feldman, J. Minimization of Boolean complexity in human concept learning. Nature 407, 630–633 (2000). https://doi.org/10.1038/35036586

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1038/35036586

Search

Advanced search

Quick links

Nature Briefing

Sign up for the Nature Briefing newsletter — what matters in science, free to your inbox daily.

Get the most important science stories of the day, free in your inbox. Sign up for Nature Briefing