Top

Gepubliceerd in:

01-03-2008 | Original Article

Response times seen as decompression times in Boolean concept use

Auteurs: Joël Bradmetz, Fabien Mathy

Gepubliceerd in: Psychological Research | Uitgave 2/2008

Abstract

This paper reports a study of a multi-agent model of working memory (WM) in the context of Boolean concept learning. The model aims to assess the compressibility of information processed in WM. Concept complexity is described as a function of communication resources (i.e., the number of agents and the structure of communication between agents) required in WM to learn a target concept. This model has been successfully applied in measuring learning times for three-dimensional (3D) concepts (Mathy and Bradmetz in Curr Psychol Cognit 22(1):41–82, 2004). In this previous study, learning time was found to be a function of compression time. To assess the effect of decompression time, this paper presents an extended intra-conceptual study of response times for two- and 3D concepts. Response times are measured in recognition phases. The model explains why the time required to compress a sample of examples into a rule is directly linked to the time to decompress this rule when categorizing examples. Three experiments were conducted with 65, 49, and 84 undergraduate students who were given Boolean concept learning tasks in two and three dimensions (also called rule-based classification tasks). The results corroborate the metric of decompression given by the multi-agent model, especially when the model is parameterized following static serial processing of information. Also, this static serial model better fits the patterns of response times than an exemplar-based model.

vorige artikel Action–effect anticipation in infant action control

Alleen toegankelijk voor geautoriseerde gebruikers

Rule creation is the motor of conceptual progress in many domains. Before Descartes, there was a procedure for each equation, depending on the terms to the right and the left of the equal symbol. Descartes came up with a considerably more economical system of calculations by putting the terms on the left and a zero on the right. This discovery brought him up against the reticence of people to accept that “something” could be equal to “nothing”. Here, we see that all scientific revolutions take time. Similarly, it took a couple of decades for Kepler to admit that planetary orbits were not circular, even though elliptical orbits actually simplified the calculus.

In artificial intelligence, a theoretical analysis of inductive reasoning has been introduced by Gold (1967). Gold developed the notion of convergence (identification in the limit) by understanding that the most accurate hypotheses are reached faster when beginning to test the smallest ones (see also Osherson, Stob, & Weinstein, 1986, for a development of Gold theories). This principle, which consists of choosing the simplest rules is known as Occam’s razor, which guarantees both fast learning and accurate generalizations (see a study of the simplicity principle in unsupervised categorization in Pothos & Chater, 2002; a study of learning based on the principle of minimum description length (MDL) in Fass & Feldman, 2002; Feldman, 2003b for a short introduction to simplicity principles in concept learning and Feldman, 2004, for a study of the statistical distribution of simplicity). Recently, computational learning theories have achieved success with the probably approximately correct (PAC) learning theory of Valiant (1984) (Anthony & Biggs, 1992; Hanson, Drastal, & Rivest, 1994a, b; Hanson, Petsche, Kearns, & Rivest; Kearns & Vazirani, 1994). This approach is a general framework (e.g., sample complexity, Vapnik–Chernovenkis dimension, etc.) for a lot of inductive learning models like neural networks or inductive logic programming (De Raedt, 1997). A second approach, which we will follow in this paper, aims to develop symbolic learning algorithms based on decision trees, and is very well suited to the non-fuzzy Boolean concepts studied here (Quinlan, 1986; see Mitchell, 1997, for a general presentation or Shavlik & Dietterich, 1990, for readings in machine learning).

This progressive adaptation recalls “in the spirit” the procedure of identification in the limit (Gold, 1967), the cascade correlation algorithm for neural networks (Fahlman & Lebiere, 1990), the RULEX model that begins with the simplest rules and adds exceptions if necessary (Nosofsky, Palmeri, & McKinley, 1994b), and the SUSTAIN model of category learning in which clusters are recruited progressively (Love, Medin, & Gureckis, 2004b).

We will not present the method for obtaining communication protocols, as it is already explained in Mathy and Bradmetz (2004). The method is based on computing the information gain for each piece of information given by agents until there is no more uncertainty about the class. The knowledge of an agent is computed by the conditional entropy quantifying the remaining uncertainty about the class once the agent’s knowledge is made public.

The numbering of stimuli used in Table 2 (ex ₁, ex ₂, ex ₃, and ex ₄) is shown in Fig. 3.

Let us make an analogy: when memorizing before dialing a phone number, it takes less time to dial a number after its entire memorization (let us imagine 6 s to memorize the entire number plus 3 s to dial, for a total of 9 s), than to quickly look up and memorize the numbers and dial them group by group (e.g., four groups, and 3 s per group, for a total of 12 s). Nevertheless, a lot of people choose the second solution because starting to memorize an entire number takes more time (i.e., 6 s in our example) than directly memorizing the first group and then dialing it (i.e., 3 s). Of course, this analogy should be experimentally examined.

One of the two players chooses a word and the other must guess it after having asked as few yes–no questions as possible.

There is an analogy with variable typing in computer science. Static-typed variables are defined at compile-time and remain unchanged throughout program execution, whereas dynamic variables are defined at run-time.

Anthony, M., & Biggs, N. (1992). Computational learning theory. Cambridge, MA: Cambridge University Press.

Arnauld, A., & Nicole, P. (1996). Logic or the art of thinking. Cambridge, UK: Cambridge university press (Original work published 1662).

Ashby, F. G., Alfonso-Reese, L. A., Turken, A. U., & Waldron, E. M. (1998). A neuropsychological theory of multiple systems in category learning. Psychological Review, 105, 442–481.PubMedCrossRef

Ashby, F. G., Boyton, G., & Lee, W. W. (1994). Categorization response time with multidimensional stimuli. Perception and Psychophysics, 55, 11–27.PubMed

Axelrod, R. (1997). The complexity of cooperation: Agent-based models of competition and collaboration. Princeton, NJ: Princeton University Press.

Bennett, C. H. (1986). On the nature and origin of complexity in discrete, homogeneous, locally-interacting systems. Foundations of Physics, 16(6), 585–592.CrossRef

Bourne, L. E. Jr. (1970). Knowing and using concepts. Psychological Review, 77, 546–556.CrossRef

Bruner, J. S., Goodnow, J. J., & Austin, G. A. (1956). A study of thinking. New York: Wiley.

Bryant, R. E. (1986). Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Compilers, 35(8), 677–691.CrossRef

Chaitin, G. J. (1974). Information-theoretic computational complexity. IEEE Transactions on Information Theory, 20(1), 1015.CrossRef

Chaitin, G. J. (1987). Information, randomness and incompleteness: papers on algorithmic information theory. New York: World Scientific.

Chaitin, G. J. (1990). Algorithmic information theory. Cambridge, MA: Cambridge University Press.

Chater, N., Vitányi, P. (2003). Simplicity: A unifying principle in cognitive science? Trends in Cognitive Science, 7(1), 19–22.CrossRef

Davies, P. C. W. (1989). Why is the physical world so comprehensible? In W. H. Zurek (Ed.), Complexity, entropy, and the physics of information, pp. 61–70. New York: Addison-Wesley.

De Raedt, L. (1997). Logical settings for concept-learning. Artificial Intelligence, 95, 187–201.CrossRef

Delahaye, J. P. (1993). Complexités. In J. P. Delahaye (Ed.), Logique, informatique et paradoxe. Paris: Pour la science.

Delahaye, J. P. (1994). Information, complexité et hasard. Paris: Hermès.

Duda, R. O., Hart, E., & Stork, D. G. (2001). Pattern classification (2nd ed.). New York: Wiley.

Estes, W. K. (1994). Classification and cognition. Oxford: Oxford University Press.

Fahlman, S. E., & Lebiere, C. (1990). The cascade-correlation learning architecture. Technical report. CMU-CS-90–100. Canergy-Mellon University.

Fass, D., & Feldman, J. (2002). Categorization under complexity: A unified MDL account of human learning of regular and irregular categories. In S. Becker, S. Thrun, & K. Obermayer (Eds.), Advances in neural information processing systems, Proceedings of the 2002 conference (Vol. 15). Cambridge, MA: MIT Press.

Feldman, J. (2000). Minimization of Boolean complexity in human concept learning. Nature, 407, 630–633.PubMedCrossRef

Feldman, J. (2003a). A catalog of Boolean concepts. Journal of Mathematical Psychology, 47, 75–89.CrossRef

Feldman, J. (2003b). The simplicity principle in human concept learning. Cognition, 93, 199–224.CrossRef

Feldman, J. (2004). How surprising is a simple pattern? Quantifying “Eureka!”. Current Directions in Psychological Science, 12(6), 227–232.CrossRef

Ferber, J. (1999). Multi-agent systems, an introduction to distributed artificial intelligence. Harlow: Addison-Wesley.

Gell-Mann, M. (1994). The quark and the jaguar: Adventures in the simple and the complex. New York: Freeman and Company.

Gluck, M. A., & Bower, G. H. (1988a). Evaluating an adaptive network model of human learning. Journal of Memory and Language, 27, 166–195.CrossRef

Gluck, M. A., & Bower, G. H. (1988b). From conditioning to category learning: an adaptive network model. Journal of Experimental Psychology: General, 117, 227–247.CrossRef

Gold, E. M. (1967). Language identification in the limit. Information and Control, 10, 447–474.CrossRef

Gosselin, F., & Schyns, P. G. (2001). Why do we SLIP to the basic level? Computational constraints and their implementation. Psychological Review, 108(4), 735–758.PubMedCrossRef

Hahn, U., & Chater, N. (1997). Concepts and similarity. In K. Lamberts & D. Shanks (Eds.), Knowledge, concepts and categories (pp. 43–92). Cambridge, MA: MIT Press.

Hanson, S. J., Drastal, G. A., & Rivest, R. L. (1994a). Computational learning theory and natural learning systems (Vol. 1). Cambridge, MA: MIT Press.

Hanson, S. J., Petsche, T., Kearns, M., & Rivest, R. L. (1994b). Computational learning theory and natural learning systems (Vol. 2). Cambridge, MA: MIT Press.

Hovland, C. L. (1966). A communication analysis of concept learning. Psychological Review, 59, 461–472.CrossRef

Hromkovič, J. (1997). Communication complexity and parallel computing. New York: Springer.

Huber, L. (2001). Visual categorization in pigeons. In R. G. Cook (Ed.), Avian visual cognition [On-line]. Available: www.pigeon.psy.tufts.edu/avc/huber/.

Hunt, E. B., Marin, J., & Stone, P. J. (1966). Experiments in induction. New York: Academic.

Huth, M., & Ryan, M. (2000). Logic in computer science: Modeling and reasoning about systems. London: Cambridge University Press.

Keanrs, M. J., Vazirani, U. V. (1994). An introduction to computational learning theory. Cambridge, MA: MIT Press.

Kolmogorov, A. N. (1965). Three approaches for defining the concept of information quantity. Information Transmission, 1, 3–11.

Kruschke, J. K. (1992). ALCOVE: An exemplar-based connectionist model of category learning. Psychological Review, 99, 22–44.PubMedCrossRef

Lamberts, K. (1997). Process models of categorization. In K. Lamberts & D. Shanks (Eds.), Knowledge, concepts and categories (pp. 43–92). Cambridge, MA: MIT Press.

Lamberts, K. (2000). Information-accumulation theory of speeded categorization. Psychological Review, 107, 227–260.PubMedCrossRef

Levine, M. (1966). Hypothesis behavior by humans during discrimination learning. Journal of Experimental Psychology, 71, 331–338.PubMedCrossRef

Li, M., & Vitányi, P. (1997). An introduction to Kolmogorov complexity and its applications. New York: Springer Verlag.

Lockhead, G., & Pomerantz, J. R. (Eds.). (1991). The perception of structure. Washington: American Psychological Association.

Love, B. C., & Markman, A. B. (2003). The nonindependence of stimulus properties in human concept learning. Memory and Cognition, 31(5), 790–799.

Love, B. C., Medin, D. L., & Gureckis, T. M. (2004a). SUSTAIN: A network model of category learning. Psychological Review, 111, 309–332.CrossRef

Love, B. C., Medin, D. L., & Gureckis, T. M. (2004b). SUSTAIN: A network model of category learning. Psychological Review, 111(2), 309–332.CrossRef

Luce, R. D. (1963). Detection and recognition. In R. D. Luce, R. R. Bush, E. Galanter (Eds.), Handbook of mathematical psychology (pp. 103–189). New York: Wiley.

Mathy, F. (2002). L’apprenabilité des concepts évaluée au moyen d’un modèle multi-agent de la complexité des communications en mémoire de travail. Unpublished Doctoral Dissertation. Université de Reims, France.

Mathy, F., Bradmetz, J. (1999). Un modèle multi-agent de la complexité conceptuelle. In M. P. Gleizes, P. Marcenac (Eds.), Ingénierie des systèmes multi-agents: acte des 7e Journées Francophones d’Intelligence Artificielle et Systèmes Multi-Agents. Paris: Hermès. (pp. 343–345).

Mathy, F., & Bradmetz, J. (2004). A theory of the graceful complexification of concepts and their learnability. Current Psychology of Cognition, 22(1), 41–82.

Medin, D. L., & Schaffer, M. M. (1978). A context theory of classification learning, Psychological Review, 85, 207–238.CrossRef

Minsky, M. L. (1985). The society of mind. New York, NY: Simon and Schuster (French translation: La société de l’esprit. Paris: Inter Editions, 1988).

Mitchell, T. (1997). Machine learning. New York, NY: McGraw-Hill.

Myung, I. J. (1994). Maximum entropy interpretation of decision bound and context models of categorization. Journal of Mathematical Psychology, 38, 335–365.CrossRef

Nosofsky, R. M. (1986). Attention, similarity, and the identification-categorization relationship. Journal of Experimental Psychology: General, 115, 39–57.CrossRef

Nosofsky, R. M., & Alfonso-Reese, L. A. (1999). Effects of similarity and practice on speeded classification response times and accuracies: Further tests of an exemplar-retrieval model. Memory and Cognition, 27, 78–93.

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

Nosofsky, R. M., Kruschke, J. K., & McKinley, S. C. (1992). Combining exemplar-based category representations and connectionist learning rules. Journal of experimental Psychology: Learning, Memory, and Cognition, 18, 211–233.PubMedCrossRef

Nosofsky, R. M., Palmeri, T. J. (1997). An exemplar-based random walk model of speeded classification. Psychological Review, 104, 266–300.PubMedCrossRef

Nosofsky, R. M., Palmeri, T. J., & McKinley, S. C. (1994b). Rule-plus-exception model of classification learning. Psychological Review, 101(1), 53–79.CrossRef

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

Osherson, D. Stob, M., & Weistein, S. (1986). Systems that learn: an introduction to learning theory for cognitive and computer scientists. Cambridge, MA: MIT Press.

Pothos, E. M., & Chater, N. (2002). A simplicity principle in unsupervised human categorization. Cognitive Science, 26, 303–343.CrossRef

Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1, 81–106.

Richards, W., & Bobick, A. (1988). Playing twenty questions with nature. In Z. W. Pylyshyn (Ed.), Computational processes in human vision: an interdisciplinary perspective (pp. 3–26). Norwood, NJ: Ablex.

Richards, W., McKay, B. D., & Richards, D. (2002). The probability of collective choice with shared knowledge structures. Journal of Mathematical Psychology, 46, 338–351.CrossRef

Rips, L. J., Shoben, E. J., Smith, E. E. (1973). Semantic distance and the verification of semantic relations. Journal of Verbal Learning and Verbal Behavior, 12, 1–20.CrossRef

Roberts, S., & Pashler, H. (2000). How persuasive is a good fit? A comment on theory testing. Psychological Review, 107, 358–367.PubMedCrossRef

Rosch, E. (1973). Natural categories. Cognitive Psychology, 4, 328–350.CrossRef

Rosch, E., & Mervis, C. B. (1975). Family resemblances: studies in the internal structure of categories. Cognitive Psychology, 7, 573–605.CrossRef

Selfridge, O. (1959). Pandemonium: a paradigm for learning. In D. V. Blake, A. M. Uttley (Eds.), Proceedings of the symposium on mechanisation of thought processes (pp 511–529). London: H. M. Stationary Office.

Shavlik, J. W., & Dietterich, T. G. (Eds.). (1990). Readings in machine learning. San Mateo, CA: Morgan Kaufmann.

Shepard, R. N. (1987). Toward a universal law of generalization for psychological science. Science, 237, 1317–1323.PubMedCrossRef

Shepard, R. N., Hovland, C. L., & Jenkins, H. M. (1961). Learning and memorization of classifications. Psychological Monographs, 75 (13, whole No. 517).

Shin, H. J., & Nosofsky, R. M. (1992). Similarity-scaling studies of dot-pattern classification and recognition. Journal of Experimental Psychology: General, 121, 278–304.CrossRef

Siegler, R. S. (1977). The twenty questions game as a form of problem solving. Child Development, 48 (2), 395–403.CrossRef

Smith, E. E., & Medin, D. L. (1981). Categories and concepts. Cambridge, MA: Harvard University Press.

Townsend, J. T., & Wenger, M. J. (2004). The serial-parallel dilemma: A case study in a linkage of theory and method. Psychonomic Bulletin & Review, 11, 391–418.

Valiant, L. G. (1984). A theory of the learnable. Communication of the Association for Computing Machinery, 27, 1134–1142.

Wolfram, S. (2002). A new kind of science. Champaign, IL: Wolfram Media.

Yamauchi, T., Love, B. C., & Markman, A. B. (2002). Learning nonlinearly separable categories by inference and classification. Journal of Experimental Psychology: Learning, Memory and Cognition, 28, 585–593.CrossRef

Zucchini, W. (2000). An introduction to model selection. Journal of Mathematical Psychology, 44, 41–61.PubMedCrossRef

Titel: Response times seen as decompression times in Boolean concept use
Auteurs: Joël Bradmetz
Fabien Mathy
Publicatiedatum: 01-03-2008
Uitgeverij: Springer-Verlag
Gepubliceerd in: Psychological Research / Uitgave 2/2008
Print ISSN: 0340-0727
Elektronisch ISSN: 1430-2772
DOI: https://doi.org/10.1007/s00426-006-0098-7

Bohn Stafleu van Loghum

Deel dit onderdeel of sectie (kopieer de link)

Abstract

Log in om toegang te krijgen

Andere artikelen Uitgave 2/2008

Action–effect anticipation in infant action control

The influence of trial-to-trial recalibration on sequential effects in cross-modality matching

Laterally focused attention modulates asymmetric coupling in rhythmic interlimb coordination

Effector-related sequence learning in a bimanual-bisequential serial reaction time task

Attentional awakening: gradual modulation of temporal attention in rapid serial visual presentation

Objects do not aid inhibition of return in crossing the vertical meridian