Commentary on Leech, Mareschal, & Cooper (2007)

Word Counts:
Abstract: 60 words
Main Text: 996 words
References: 278 words
Total Text: 1374 words

Computational complexity analysis can help, but first we need a theory

Todd Wareham
Department of Computer Science
Memorial University of Newfoundland
St. John's, NL, A1B 3X5
1 (709) 737-4601

Iris van Rooij
Nijmegen Institute for Cognition and Information
Radboud University Nijmegen
Montessorilaan 3, 6525HR Nijmegen,
The Netherlands

Moritz Müller
Abteilung für Mathematishe Logik
Albert-Ludwigs-Universität Freiburg
Eckerstrasse 1, 79098 Freiburg
0049 203 5605

Abstract: Leech, Mareschal, & Cooper present a connectionist algorithm as a model of (the development) of analogizing, but they do not specify the algorithm's associated computational-level theory, nor its computational complexity. We argue that doing so may be essential for connectionist cognitive models to have full explanatory power and transparency, as well as for assessing their scalability to real-world input domains.

Leech et al. describe a connectionist algorithm that reproduces several known effects in the development of analogy-making. The authors claim that this algorithm models how children develop the ability to make analogies in a manner not yet captured by previous (primarily non-connectionist) models of analogy like Structure Mapping Theory (SMT) (Gentner, 1983). The current version of the algorithm does not account for (the development of) the complex analogies made by adults. Moreover, Leech et al.'s target article is silent on two issues prominent in previous work on analogy, namely (1) a computational-level theory in the sense of (Marr, 1982), i.e., a precise formulation of a cognitive ability as an input-output function, of which the presented connectionist model supposedly provides an algorithmic-level implementation; and (2) the computational complexity of the proposed algorithm and/or its associated computational-level theory. In this commentary, we discuss why consideration of (1) and (2) may be essential for making progress in research programs such as Leech et al.'s.

To start, we find it useful to re-cast the problem of deriving models of cognitive development (be they algorithmic- or computational-level) in terms of satisfying various constraints. The most basic of these is the Empirical Constraint, i.e., the model must mimic / predict observed cognitive behavior. Though this is often construed only in terms of adult cognitive behavior, the model should be able to fit performance across the different stages of development (e.g., in infancy, childhood, and adulthood) and account for any apparent discontinuities between different stages (e.g., relational shift in the case of analogy). This constraint holds for any model of natural phenomena. In the case of cognitive abilities, which develop over time, Leech et al. point out the need for a Developmental Constraint, i.e., "all proposed mechanisms [of the model] must have a developmental origin" (p. 55). That is, the model should incorporate mechanisms which allow the ability to mature consistent with the Empirical Constraint. Overlooked or ignored so far is a third and equally important constraint, the Computational Constraint, i.e., a cognitive model must satisfy both the Empirical Constraint and the Developmental Constraint while operating within the computational resource-limits imposed by the human body and its environment.

Computational complexity analysis is the tool of choice for assessing whether or not a cognitive model can satisfy the Computational Constraint, thus placing such analysis at the heart of cognitive modeling. This is not to say that such analysis is easy: Though well-developed measures like worst-case asymptotic time complexity are applicable to algorithms operating on digital computational architectures, it is not obvious which measures are most appropriate for connectionist algorithms. Potential measures include the time it takes for the network to settle, the number of training-cycles required to develop a given level of performance, and the number of nodes and layers in a network required for computing a given input-output mapping. Once defined, such measures can be used in conjunction with a suitable criterion for computational tractability (see e.g. van Rooij, 2003, in press). Doing so would enable cognitive modelers such as Leech et al. to evaluate how their models' computational resource requirements scale for the larger inputs that are characteristic of real-world domains of analogizing, and show if modifications are necessary to accommodate adult-level analogizing.

Though algorithmic-level models can be evaluated against the three constraints mentioned above, there are additional benefits in specifying the computational problems that these algorithms are supposed to be solving, i.e., formulating computational-level theories. The first benefit is explanatory transparency: A computational-level theory provides a precise input-output characterization of the cognitive capacity that is to be explained, which is the primary explanandum.[1] In the absence of such a characterization, it is hard to tell if the proposed algorithmic-level theory is explaining anything at all (Cummins, 2000). The second benefit is explanatory power: Computational-level theories postulate organizing principles that govern cognitive abilities, which in turn give insight into the rationale of cognitive computations. This is not obviously supported by algorithmic-level theories, especially when we are dealing with connectionist algorithms (Cummins, 1995). The third benefit is analytical power: Computational-level complexity analyses can demonstrate that no algorithm (let alone a given algorithm) meets the Computational Constraint for a particular computational-level theory (see also Tsotsos, 1990). Moreover, the same analyses can highlight aspects of one's theory that are responsible for excessive resource demands, and as such can guide the formulation of new theories that meet the Computational Constraint (see van Rooij & Wareham, in press, van Rooij et al., 2005; Wareham, 1999).

Formulating computational-level theories of cognitive capacities is not easy, and seems particularly hard for connectionist architectures. Yet, such theories can be formulated (see Thagard, 2000, for an example), and given the benefits we have identified, it may well be worth the effort. Such theories may counteract the acknowledged temptation to focus on getting connectionist algorithms to work rather than focusing on why they work (Mareschal & Thomas, 2007, p. 148), and enable them to actually count as explanations (Green, 2001). Such theories may also enable the exploitation of known connectionist-oriented complexity results (Bruck & Goodman, 1990; Judd, 1990; Parberry, 1994) which, given the computational intractability of theories of analogy such as SMT (Veale & Keane, 1997), may be crucial in helping approaches such as Leech et al.'s scale to adult-level performance. Finally, computational-level connectionist theories may more clearly expose relationships to non-connectionist theories. For example, reading the target article, we wonder to what extent connectionist algorithms could be trained to map analogies according to the criteria set forth by SMT, and hence to what degree these approaches are complementary rather than competing. Lacking a characterization of the problem that the connectionist network is supposed to be solving, we are so far unable to tell.


1. Following Cummins (2000), we consider cognitive capacities to be the primary explananda of cognitive science. The effects considered by Leech et al., on the other hand, are secondary explananda in that they help constrain (via the Empirical Constraint) theoretical accounts of the cognitive capacity for forming analogies.


Bruck, J. & Goodman, J. (1990). On the power of neural networks for solving hard problems. Journal of Complexity, 6, 129-135.

Cummins, R. (1995). Connectionism and the rationale constraint on cognitive explanation. Philosophical Perspectives: AI, Connectionism and Philosophical Psychology, 9, 105-125.

Cummins, R. (2000). "How does it work?" vs. "What are the laws?": Two conceptions of psychological explanation. In Keil, F. and Wilson, R. (eds), Explanation and cognition. Cambridge, MA: MIT Press.

Gentner, D. (1983). Structure-mapping: A theoretical framework for analogy. Cognitive Science, 7, 155-170.

Green, C. (2001). Scientific models, connectionist networks, and cognitive science. Theory & Psychology, 11, 97-117.

Judd, J. S. (1990). Neural network design and the complexity of learning. Cambridge, MA: MIT Press.

Marr, D. (1982). Vision: A computational investigation into the human representation and processing visual information. W. H. Freeman: San Francisco.

Thagard, P. (2000). Coherence in thought and action. MIT Press, Cambridge, MA.

Tsotsos, J. K. (1990). Analyzing vision at the complexity level. Behavioral and Brain Sciences, 13 (3), 423-469.

van Rooij, I. (in press). The tractable cognition thesis. Cognitive Science.

van Rooij, I. (2003). Tractable cognition: Complexity theory in cognitive psychology. PhD thesis, University of Victoria, Canada.

van Rooij, I., Stege, S., & Kadlec, H. (2005). Sources of complexity in subset choice. Journal of Mathematical Psychology, 49, 160-187.

van Rooij, I. & Wareham, T. (in press). Parameterized complexity in cognitive modeling: Foundations, applications and opportunities. Computer Journal.

Veale, T. & Keane, M.T. (1997). The competence of sub-optimal theories of structure mapping on hard analogies. Proceedings of the 1997 International Joint Conference on Artificial Intelligence (IJCAI'97).

Wareham, T. (1999). Systematic parameterized complexity analysis in computational phonology. PhD thesis, University of Victoria, Canada.