<p>Related to this is several works on the integration or non-integration of computational models in general to cognitive science.  For instance, the Tractable Cognition Thesis basically says that we can improve cognitive modeling if we limit cognitive models to those tractably implementable on a Turing machine.</p>

<p>Van Rooij, I.  2008.  The Tractable Cognition Thesis.  Cognitive Science 32:939-984.  <a href="http://staff.science.uva.nl/~szymanik/papers/TractableCognition.pdf" rel="nofollow">http://staff.science.uva.nl/~szymanik/papers/TractableCognition.pdf</a></p>

<p>Personally, I disagree with the Tractable Cognition Thesis, and think, similar to Copeland, that a better model would be of an Oracle machine:</p>

<p>Copeland, J.  1998.  Turing's O-Machines, Searle, Penrose, and the Brain.  Analysis 58(2):128-138.</p>

<p>My own work goes ahead in this regard, and proposes how O-machines can be specifically integrated into cognitive psychology.  I give a presentation on it here and the proceedings will be published next year, but message me and I can provide a draft copy if you would like.</p>

<p><a href="http://www.youtube.com/watch?v=chQvZrkznbg&amp;feature=plcp" rel="nofollow">http://www.youtube.com/watch?v=chQvZrkznbg&amp;feature=plcp</a></p>

CC BY-SA 3.0
2012-10-09T15:05:19.693Z
thanks, but this has very little to do with CoLT, and the first part of your answer is already taken care of by [this answer](http://cstheory.stackexchange.com/a/5388/1037) in the links I provide in the question.
Artem Kaznatcheev
CC BY-SA 3.0
2012-10-09T14:43:53.603Z
2012-10-09T14:43:53.603Z
Jonathan Bartlett
<p>Recently Bayesian models of cognitive development have been very successful in at least formulating working hypotheses as to how abstract knowledge "regularizes" and guides learning and reasoning from sparse data. I was thinking for instance of the following paper:</p>

<ul>
<li>Tenenbaum, J. B., Kemp, C., Griffiths, T. L., and Goodman, N. D. (2011). <a href="http://web.mit.edu/cocosci/Papers/tkgg-science11-reprint.pdf" rel="nofollow">How to Grow a Mind: Statistics, Structure, and Abstraction</a>. Science 331 (6022), 1279-1285.</li>
</ul>

CC BY-SA 3.0
2012-06-28T17:46:13.460Z
Bayesian models are not traditionally part of CoLT. Can you expand your answer to explain why you think the above work is a rigorous use of CoLT for building a psychological theory? I can see how it is a hand-wavy approach, or a modeling framework, but I don't see rigor as required by the question.
Artem Kaznatcheev
CC BY-SA 3.0
2012-06-28T14:58:29.837Z
2012-06-28T14:58:29.837Z
mrig
<p><a href="http://en.wikipedia.org/wiki/Computational_learning_theory" rel="noreferrer">Computational learning theory</a> (CoLT) is a branch of theoretical computer science associated with the mathematical analysis of machine learning. A lot of the early ideas of the field take inspiration from human learning. The field has developed into a very rigorous, mathematical, and precise science, but I have not seen it used much in the cognitive sciences directly. There is some indirect use through CoLT's interaction with statistics and machine learning algorithms (say, <a href="https://cogsci.stackexchange.com/a/253/29">analyzing neural networks through VC-dimension</a>).</p>
<p><strong>Are there examples of rigorous uses/applications of CoLT to build theories in psychology, neuroscience, and/or cognitive science?</strong></p>
<hr />
<h3>Notes:</h3>
<p>The only two examples I am familiar with are:</p>
<ol>
<li><p><a href="http://www.lps.uci.edu/%7Ejohnsonk/Publications/Johnson.GoldsTheorem.pdf" rel="noreferrer">Gold's theorem</a> on the unlearnability in the limit of certain sets of languages, among them context-free ones.</p>
</li>
<li><p><a href="http://homepages.cwi.nl/%7Erdewolf/publ/philosophy/phthesis.pdf" rel="noreferrer">Ronald de Wolf's master's thesis</a> on the <a href="https://linguistics.stackexchange.com/a/2023/33">impossibility to PAC-learn context-free languages</a>.</p>
</li>
</ol>
<p>The first made quiet a stir in the <a href="http://en.wikipedia.org/wiki/Poverty_of_the_stimulus" rel="noreferrer">poverty-of-the-stimulus debate</a>, and the second has been unnoticed by cognitive science.</p>
<p>I am interested in approaches of this flavor. I am relatively comfortable with CoLT as it is studied in mathematics, and am only interested (for this question) in approaches that have direct bearing on theories of human/animal cognition/learning, and not classic machine learning results. I am <strong>looking for general mathematical and asymptotic approaches</strong>, not the running of specific types of algorithms (be it neural-nets, bayesian, or otherwise) to simulate human performance as is typical in computational modeling in cogsci (which I am relatively familiar with).</p>
<p>I am <strong>not interested</strong> in arguments that try to trivially undercut the whole approach, even if they have empirical validity. For instance, the whole approach can be derailed by asserting that human brains are finite and thus asymptotic arguments are useless. This is the same as arguing that all of computational complexity theory is pointless because computers (and the whole universe, for that matter) are finite. It is a valid empirical argument, but boring from the point of view of theory building.</p>
<h3>Related questions:</h3>
<ul>
<li><a href="https://linguistics.stackexchange.com/q/1066/33">General mathematical frameworks of language acquisition since Gold</a> on ling.SE</li>
<li><a href="https://cstheory.stackexchange.com/q/5379/1037">What is the complexity class most closely associated with what the human mind can accomplish quickly?</a> on cstheory.SE</li>
</ul>

<learning><computational-modeling><mathematical-psychology><theoretical-neuroscience>
Applications of computational learning theory in the cognitive sciences
Artem Kaznatcheev
# Applications of computational learning theory in the cognitive sciences

(Asked by: username_0 on 2012-06-01)

[Computational learning theory](http://en.wikipedia.org/wiki/Computational_learning_theory) (CoLT) is a branch of theoretical computer science associated with the mathematical analysis of machine learning. A lot of the early ideas of the field take inspiration from human learning. The field has developed into a very rigorous, mathematical, and precise science, but I have not seen it used much in the cognitive sciences directly. There is some indirect use through CoLT's interaction with statistics and machine learning algorithms (say, [analyzing neural networks through VC-dimension](https://cogsci.stackexchange.com/a/253/29)).

**Are there examples of rigorous uses/applications of CoLT to build theories in psychology, neuroscience, and/or cognitive science?**

---

### Notes:

The only two examples I am familiar with are:

1. [Gold's theorem](http://www.lps.uci.edu/%7Ejohnsonk/Publications/Johnson.GoldsTheorem.pdf) on the unlearnability in the limit of certain sets of languages, among them context-free ones.
2. [Ronald de Wolf's master's thesis](http://homepages.cwi.nl/%7Erdewolf/publ/philosophy/phthesis.pdf) on the [impossibility to PAC-learn context-free languages](https://linguistics.stackexchange.com/a/2023/33).

The first made quiet a stir in the [poverty-of-the-stimulus debate](http://en.wikipedia.org/wiki/Poverty_of_the_stimulus), and the second has been unnoticed by cognitive science.

I am interested in approaches of this flavor. I am relatively comfortable with CoLT as it is studied in mathematics, and am only interested (for this question) in approaches that have direct bearing on theories of human/animal cognition/learning, and not classic machine learning results. I am **looking for general mathematical and asymptotic approaches**, not the running of specific types of algorithms (be it neural-nets, bayesian, or otherwise) to simulate human performance as is typical in computational modeling in cogsci (which I am relatively familiar with).

I am **not interested** in arguments that try to trivially undercut the whole approach, even if they have empirical validity. For instance, the whole approach can be derailed by asserting that human brains are finite and thus asymptotic arguments are useless. This is the same as arguing that all of computational complexity theory is pointless because computers (and the whole universe, for that matter) are finite. It is a valid empirical argument, but boring from the point of view of theory building.

### Related questions:

* [General mathematical frameworks of language acquisition since Gold](https://linguistics.stackexchange.com/q/1066/33) on ling.SE
* [What is the complexity class most closely associated with what the human mind can accomplish quickly?](https://cstheory.stackexchange.com/q/5379/1037) on cstheory.SE

**Tags:** learning, computational-modeling, mathematical-psychology, theoretical-neuroscience


---

## 2 answers

### Answer by username_1 on 2012-10-09. Score: 4

Related to this is several works on the integration or non-integration of computational models in general to cognitive science. For instance, the Tractable Cognition Thesis basically says that we can improve cognitive modeling if we limit cognitive models to those tractably implementable on a Turing machine.

Van Rooij, I. 2008. The Tractable Cognition Thesis. Cognitive Science 32:939-984. <http://staff.science.uva.nl/~szymanik/papers/TractableCognition.pdf>

Personally, I disagree with the Tractable Cognition Thesis, and think, similar to Copeland, that a better model would be of an Oracle machine:

Copeland, J. 1998. Turing's O-Machines, Searle, Penrose, and the Brain. Analysis 58(2):128-138.

My own work goes ahead in this regard, and proposes how O-machines can be specifically integrated into cognitive psychology. I give a presentation on it here and the proceedings will be published next year, but message me and I can provide a draft copy if you would like.

<http://www.youtube.com/watch?v=chQvZrkznbg&feature=plcp>

> **Comments:**
> **username_0**: thanks, but this has very little to do with CoLT, and the first part of your answer is already taken care of by [this answer](http://cstheory.stackexchange.com/a/5388/1037) in the links I provide in the question.  

---

### Answer by username_2 on 2012-06-28. Score: 2

Recently Bayesian models of cognitive development have been very successful in at least formulating working hypotheses as to how abstract knowledge "regularizes" and guides learning and reasoning from sparse data. I was thinking for instance of the following paper:

* Tenenbaum, J. B., Kemp, C., Griffiths, T. L., and Goodman, N. D. (2011). [How to Grow a Mind: Statistics, Structure, and Abstraction](http://web.mit.edu/cocosci/Papers/tkgg-science11-reprint.pdf). Science 331 (6022), 1279-1285.

> **Comments:**
> **username_0**: Bayesian models are not traditionally part of CoLT. Can you expand your answer to explain why you think the above work is a rigorous use of CoLT for building a psychological theory? I can see how it is a hand-wavy approach, or a modeling framework, but I don't see rigor as required by the question.  

---

