1
$\begingroup$

Can anyone shed some light on how the VC Dimension affects the sample complexity bounds of infinite hypothesis classes with real-valued outputs in PAC learning, or how to calculate the sample complexity bounds of said classes with some other measure of the class's 'complexity'?

I'm studying machine learning theory, particularly the PAC model, and been having trouble finding some definitive upper and lower bounds on the sample complexity for real-valued hypothesis classes, like those given for binary classification classes with the 0-1 Loss. I know the PAC model and VC Dimension have been generalised to real-valued functions, but at this stage the actual work of Vapnik is a bit impenetrable to me. Still, the VC Dimension still seems like a very intuitive measure to use when determining number of samples you're likely to need to learn a given class; too few samples given the complexity and your learner can't have a clear enough picture of the underlying distribution, and too many and those extra samples aren't really going to improve the learner's capability to learn.

The literature that's out there seems very disjointed, I understand the field is constantly in motion so I'm trying to catch up, without necessarily knowing where 'up' is.

Improve this question
$\endgroup$
4
  • $\begingroup$ How is it possible to have real-valued learn-able functions? Did you actually mean functions that output real values but belong to a class of functions that can be represented by a countable set (such as the set of integer) $\endgroup$
    – InformedA
    Aug 9, 2014 at 9:20
  • $\begingroup$ Yes, sorry that is what I meant. I've updated the question $\endgroup$
    – Ashley
    Aug 9, 2014 at 12:16
  • $\begingroup$ You would have to do a case by case to determine the complexity for each member of the concerning class. Then, you would come to a generic formula for the entire class. I don't think the fact that the class outputs real-value makes any different. $\endgroup$
    – InformedA
    Aug 10, 2014 at 3:06
  • $\begingroup$ I thought it was different for real-valued outputs vs binary outputs because the VC Dimension can only be used to analyse the sample complexity of binary classification tasks $\endgroup$
    – Ashley
    Aug 10, 2014 at 7:54

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.