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

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

<p>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 <span class="math-container">$C$</span> but yet not too large. I lack intuition on what's going on here.</p>

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

CC BY-SA 4.0
2019-08-29T15:14:52.283Z
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.
CC BY-SA 4.0
2019-08-29T15:16:56.460Z
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.
CC BY-SA 4.0
2019-08-29T23:55:20.603Z
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
CC BY-SA 4.0
2019-08-30T00:45:54.353Z
@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
CC BY-SA 4.0
2019-08-30T00:46:01.757Z
If $C \subseteq H$, what can you say about VC(H) and VC(C)? (Edit: Ah, Or, beat me to it)
Clement C.
CC BY-SA 4.0
2019-08-30T00:54:29.473Z
I totally agree with both of you wrote. So, essentially does one have to "optimize" over the set of hypotheses space, in order find a $H$ satisfying $C\subseteq H$ and also, $VC(H)$ is small, so that one need not make too many queries to PAC learn?
Annonymous
CC BY-SA 4.0
2019-08-30T02:28:04.927Z
You can see it that way, yes.
Clement C.
<machine-learning><lg.learning><vc-dimension><sample-complexity><pac-learning>
representation of concept classes and pac learning
Annonymous
# representation of concept classes and pac learning

(Asked by: username_0 on 2019-08-29)

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?

**Tags:** machine-learning, lg.learning, vc-dimension, sample-complexity, pac-learning
> **Comments:**
> **username_1**: 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.  
> **username_1**: 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.  
> **username_0**: 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?  
> **username_2**: @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).  
> **username_1**: If $C \subseteq H$, what can you say about VC(H) and VC(C)? (Edit: Ah, Or, beat me to it)  
> **username_0**: I totally agree with both of you wrote. So, essentially does one have to "optimize" over the set of hypotheses space, in order find a $H$ satisfying $C\subseteq H$ and also, $VC(H)$ is small, so that one need not make too many queries to PAC learn?  
> **username_1**: You can see it that way, yes.  

---

## 0 answers

