0
$\begingroup$

I was reading the book of Kearns and Vazirani and I didn't completely understand the following:

Let C be a concept class and suppose we want to PAC learn C, they say first consider a larger hypothesis set $H$ such that $C\subset H$, where the output of the learner lies in $H$. Then, they go on to show that suppose the VC(H)=d, then it suffices to take $O(d)$ many labelled examples $(x,c(x))$ in order to PAC learn $C$ by outputting a hypothesis in H.

My questions: 1) why do we need this H? In particular, isn't there a second layer of optimization going on; I could possibly pick a H which is the set of all functions, for which the VC(H) would be super large and that doesn't seem to tell us a good upper bound at all, so we need to find a H that includes $C$ but yet not too large. I lack intuition on what's going on here.

2) Is there a nice way to just talk about VC(C) and say, VC(C) many samples suffice to learn C?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Sometimes, you need $\mathcal{C} \subsetneq \mathcal{H}$ to avoid intractability (see Chapter 1.4 of the book, "Intractability of learning 3-term DNF formulae"). Sometimes, it is also just more convenient: an algorithm, simple or nice, will naturally output some hypothesis which is, say, a low-degree polynomial, or a threshold function. Bending backwards to make it output something specificaly in your concept class $\mathcal{C}$ may be difficult, or add a computationally intensive step afterwards. $\endgroup$ – Clement C. Aug 29 '19 at 15:14
  • $\begingroup$ You can say what you desire about using VC$(\mathcal{C})$ for inefficient learning, but recall -- the very definition of PAC learner requires poly-time. $\endgroup$ – Clement C. Aug 29 '19 at 15:16
  • $\begingroup$ But, what confuses me is then: if we want to learn C, we seem to be saying it suffices to obtain VC(H) many samples (so that the algorithm outputs a function in H). Somehow the complexity seems independent of C and that seems slightly strange to me. Could you clarify? $\endgroup$ – Annonymous Aug 29 '19 at 23:55
  • 2
    $\begingroup$ @Annonymous: Since $C \subseteq H$, it means that $VC(H) \ge VC(C)$. Thus, the complexity is not independent of $C$ - it must be at least $VC(C)$. It may be larger than $VC(C)$ if $H$ is richer than $C$, but this is the price we pay for using a richer hypothesis set (for the gain of computational tractability). $\endgroup$ – Or Meir Aug 30 '19 at 0:45
  • 1
    $\begingroup$ If $C \subseteq H$, what can you say about VC(H) and VC(C)? (Edit: Ah, Or, beat me to it) $\endgroup$ – Clement C. Aug 30 '19 at 0:46

Your Answer

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

Browse other questions tagged or ask your own question.