<p>Let's stick to the classical PAC (supervised learning) setting.
The short answer is that if computability is not an issue, then any class of functions with finite VC-dimension is PAC learnable via the Empirical Risk Minimization algorithm (just pick the hypothesis with the minimal sample error).</p>

<p>Of course, in many cases of interest ERM is computationally hard (e.g., if your class of functions is 3-term DNFs; see <a href="http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&amp;tid=7334" rel="nofollow">book</a> by Kearns and Vazirani.</p>

<p>As Suresh commented above, the question is too vague and open-ended to give a comprehensive answer, but hopefully the above is a start...</p>

CC BY-SA 3.0
2011-04-10T09:16:21.163Z
2011-04-10T09:16:21.163Z
Aryeh
<p>Could someone give a brief explanation of the computability &amp; learnability theory &amp; the correspondence betwwen them if any? (pointers to good sources of info. on this other than wikipedia are welcome) <strong>Thank You</strong>.</p>

CC BY-SA 3.0
2011-04-08T21:52:24.007Z
this is a rather open ended question. Not sure if it's appropriate.
Suresh Venkat
CC BY-SA 3.0
2011-04-09T05:45:58.737Z
actually, I couldn't understand the paper by Leslie Valiant "A Theory Of The Learnable' which tries to establish a theory of learnability of class of concepts (Boolean Expressions/functions) just as there exists a theory of computability of functions. So, with reference to this paper, could you guide me?
amitlan
CC BY-SA 3.0
2011-04-10T02:06:32.490Z
you need to formulate more specific questions along these lines. your current question is far too open ended. Ask a specific question about Valiant's paper, and then we can see.
Suresh Venkat
<computability><lg.learning>
Correspondence between Computability & Learnability Theory
amitlan
# Correspondence between Computability & Learnability Theory

(Asked by: username_0 on 2011-04-08)

Could someone give a brief explanation of the computability & learnability theory & the correspondence betwwen them if any? (pointers to good sources of info. on this other than wikipedia are welcome) **Thank You**.

**Tags:** computability, lg.learning

> **Comments:**
> **username_1**: this is a rather open ended question. Not sure if it's appropriate.  
> **username_0**: actually, I couldn't understand the paper by Leslie Valiant "A Theory Of The Learnable' which tries to establish a theory of learnability of class of concepts (Boolean Expressions/functions) just as there exists a theory of computability of functions. So, with reference to this paper, could you guide me?  
> **username_1**: you need to formulate more specific questions along these lines. your current question is far too open ended. Ask a specific question about Valiant's paper, and then we can see.  

---

## 1 answers

### Answer by username_2 on 2011-04-10. Score: 3

Let's stick to the classical PAC (supervised learning) setting.
The short answer is that if computability is not an issue, then any class of functions with finite VC-dimension is PAC learnable via the Empirical Risk Minimization algorithm (just pick the hypothesis with the minimal sample error).

Of course, in many cases of interest ERM is computationally hard (e.g., if your class of functions is 3-term DNFs; see [book](http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=7334) by Kearns and Vazirani.

As Suresh commented above, the question is too vague and open-ended to give a comprehensive answer, but hopefully the above is a start...


---

