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.
3
-
2$\begingroup$ this is a rather open ended question. Not sure if it's appropriate. $\endgroup$– Suresh VenkatApr 8, 2011 at 21:52
-
$\begingroup$ 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? $\endgroup$– amitlanApr 9, 2011 at 5:45
-
1$\begingroup$ 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. $\endgroup$– Suresh VenkatApr 10, 2011 at 2:06
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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 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...
