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.

  • 2
    $\begingroup$ this is a rather open ended question. Not sure if it's appropriate. $\endgroup$ – Suresh Venkat Apr 8 '11 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$ – amitlan Apr 9 '11 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 Venkat Apr 10 '11 at 2:06

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...

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.