Hostname: page-component-7c8c6479df-5xszh Total loading time: 0 Render date: 2024-03-28T15:10:52.345Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  29 July 2008

Todd Wareham
Affiliation:
Department of Computer Science, Memorial University of Newfoundland, St. John's, NL, A1B 3X5, Canada
Iris van Rooij
Affiliation:
Nijmegen Institute for Cognition and Information, Radboud University Nijmegen, 6525HR Nijmegen, The Netherlands
Moritz Müller
Affiliation:
Department of Mathematics, Albert-Ludwigs-Universität Freiburg, 79098 Freiburg, Germanyharold@cs.mun.cahttp://www.cs.mun.ca/~haroldi.vanrooij@nici.ru.nlhttp://www.nici.ru.nl/~irisvr/moritz.mueller@math.uni-freiburg.dehttp://home.mathematik.uni-freiburg.de/mueller/home.html

Abstract

Leech et al. 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.

Type
Open Peer Commentary
Copyright
Copyright © Cambridge University Press 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bruck, J. & Goodman, J. (1990) On the power of neural networks for solving hard problems. Journal of Complexity 6:129–35.CrossRefGoogle Scholar
Cummins, R. (1995) Connectionism and the rationale constraint on cognitive explanation. Philosophical Perspectives: AI, Connectionism and Philosophical Psychology 9:105–25.CrossRefGoogle Scholar
Cummins, R. (2000) “How does it work?” vs. “What are the laws?”: Two conceptions of psychological explanation. In: Explanation and cognition, ed. Keil, F. & Wilson, R., pp. 117–44. MIT Press.CrossRefGoogle Scholar
Gentner, D. (1983) Structure-mapping: A theoretical framework for analogy. Cognitive Science 7:155–70.Google Scholar
Green, C. (2001) Scientific models, connectionist networks, and cognitive science. Theory and Psychology 11:97117.CrossRefGoogle Scholar
Judd, J. S. (1990) Neural network design and the complexity of learning. MIT Press.CrossRefGoogle Scholar
Mareschal, D. & Thomas, M. S. C. (2007) Computational modeling in developmental psychology. IEEE Transactions on Evolutionary Computation (Special Issue on Autonomous Mental Development) 11(2):137–50.Google Scholar
Marr, D. (1982) Vision: A computational investigation into the human representation and processing of visual information. W. H. Freeman.Google Scholar
Parberry, I. (1994) Circuit complexity and neural networks. MIT Press.CrossRefGoogle Scholar
Thagard, P. (2000) Coherence in thought and action. MIT Press.CrossRefGoogle Scholar
Tsotsos, J. K. (1990) Analyzing vision at the complexity level. Behavioral and Brain Sciences 13(3):423–69.CrossRefGoogle Scholar
van Rooij, I. (2003) Tractable cognition: Complexity theory in cognitive psychology. Unpublished doctoral dissertation, Department of Psychology, University of Victoria, Canada.Google Scholar
van Rooij, I. (in press) The tractable cognition thesis. Cognitive Science.Google Scholar
van Rooij, I., Stege, S., & Kadlec, H. (2005) Sources of complexity in subset choice. Journal of Mathematical Psychology 49:160–87.CrossRefGoogle Scholar
van Rooij, I. & Wareham, T. (in press) Parameterized complexity in cognitive modeling: Foundations, applications and opportunities. Computer Journal. [DOI: 10.1093/comjnl/bxm034]Google Scholar
Veale, T. & Keane, M. T. (1997) The competence of sub-optimal theories of structure mapping on hard analogies. In: Proceedings of the 1997 International Joint Conference on Artificial Intelligence (IJCAI'97), vol. 1, pp. 232–37. Morgan Kaufmann.Google Scholar
Wareham, T. (1999) Systematic parameterized complexity analysis in computational phonology. Unpublished doctoral dissertation, Department of Computer Science, University of Victoria, Canada.Google Scholar