# representation of concept classes and pac learning

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?

• 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. – Clement C. Aug 29 at 15:14
• 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. – Clement C. Aug 29 at 15:16
• 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? – Annonymous Aug 29 at 23:55
• @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). – Or Meir Aug 30 at 0:45
• If $C \subseteq H$, what can you say about VC(H) and VC(C)? (Edit: Ah, Or, beat me to it) – Clement C. Aug 30 at 0:46