3
$\begingroup$

I am trying to understand the basic definition of realizable PAC learning from Shai Shalev-Shwartz's "understanding machine learning". They define a hypothesis class H to be PAC learnable if for every distribution D over the instances, and for any labeling function f, an approximately correct hypothesis can be learned with high probability over the random choice of a training set.

An issue that is not entirely clear ot me: they define PAC learnability as a property of an hypothesis class, i.e., of a solution. Intuitively I'd expect that learnability would be a property of the problem, as some problems are harder than others. What role do the properties of the problem play in the definition?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

The problem is generally to find a hypothesis for which the generalization bound is small.

For example, if you want to find the best SVM to classify your data, your hypothesis class is given exactly by a set of weights $w$ and biases $b$. The fact that you try to maximize the margin is reflected only in the fact that this will give you a good generalization bound later on. But this works only because SVMs are a relatively simple class.

However, if you take a very complex class, all NNs of all sizes with appropriate nonlinearities, say, you have a problem. Now your hypothesis class is so large that you can fit arbitrary training data without actually learning anything useful from the data.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thanks for the explanation, but I still don't understand how come the properties of the problem to be learned serve no function in the definition? For instance, isn't the task of digit recognition using a SVM inherently easier than the task of face recognition using a SVM? $\endgroup$
    – user1767774
    Commented Jul 1, 2018 at 13:53
  • 2
    $\begingroup$ PAC is basically about learning a hypothesis which is not much worse than the best hypothesis in your set. If your problem is harder (face recognition) then this will simply make all your hypotheses worse. The difficulty of the problem would then be reflected in the fact that you would select a larger hypothesis class in the first place (some NN architecture, say) for which the generalization bounds are worse than those for the smaller class. $\endgroup$
    – qeschaton
    Commented Jul 1, 2018 at 14:29
1
$\begingroup$

I would just add to the previous (excellent) answer, that Shai Shalev-Shwartz define the statistical learning framework already in chapter 2, previous to the PAC model, and their Definition 3.1 of PAC learning is actually a refinement of what they already explained in the previous chapter. "(...) a learning algorithm receives as input a training set S, sampled from an unknown distribution D and labeled by some target function f , and should output a predictor hS : X → Y (the subscript S emphasizes the fact that the output predictor depends on S). The goal of the algorithm is to find hS that minimizes the error with respect to the unknown D and f" (page 15). Then they explain that in order to avoid overfitting, one should restrict the empirical risk minimization to a chosen hypothesis class H (introducing therefore some bias). The 'complexity' of this class will then determine the size of he training data that is needed to achieve a given accuracy.

Improve this answer
$\endgroup$

Your Answer

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

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