<p>One approach would be to stratify your concept class by VC-complexity. For example, suppose that <span class="math-container">$C$</span> is the set of all functions <span class="math-container">$f:\{0,1\}^n\to\{0,1\}$</span>; its VC-dim is <span class="math-container">$2^n$</span>.
However, you can decompose <span class="math-container">$C$</span> in any number of ways. Say, <span class="math-container">$C_k$</span> is the collection of all functions whose (minimal) binary tree has depth <span class="math-container">$k$</span> or less. Or, <span class="math-container">$C_k$</span> is the set of all functions whose Fourier expansion puts no weight on XORs of more than <span class="math-container">$k$</span> bits.
Then <span class="math-container">$C_1\subset C_2 \subset \ldots \subset C_n$</span>, and selecting the appropriate <span class="math-container">$C_k$</span> is the problem of <i>model selection</i>. Machine learning theory offers a principled way of doings this via Structural Risk Minimization; here is a good start:
<a href="https://ieeexplore.ieee.org/document/705570" rel="nofollow noreferrer">Link</a></p>

CC BY-SA 3.0
2014-12-20T00:26:10.777Z
Thanks. Is this similar to what is known as maximal classes?
seteropere
CC BY-SA 4.0
2014-12-15T22:22:27.377Z
2022-07-06T15:23:36.193Z
2022-07-06T15:23:36.193Z
Aryeh
<p>Let $C$ be a concept class with VC dimension $d$ exponential to the input size (i.e number of variables represented in each concept $c\in C$). I am looking for papers/resources/suggestions of how computational learning community handle the learnability of $C$.  </p>

<p>One thing I am thinking about is investigating the learnability of $C$ in active learning. Hoping that I will end up with less number of examples required. </p>

<p>However, I prefer to stick with the passive learning for now and wondered what else I can do for this poor $C$? As I am new to the field, I also wish to have some examples of concept classes with exponential VC dimension. </p>

CC BY-SA 3.0
2014-03-10T18:23:45.087Z
You need your number of samples to scale *linearly* with VC dimension or you cannot even do supervised learning. This is a lower bound, see: http://www.cis.upenn.edu/~mkearns/papers/lower.ps
Lev Reyzin
CC BY-SA 3.0
2014-03-11T21:36:25.337Z
Its also confusing what you are asking for... Suppose each $c \in C$ can be described with d bits. Then trivially, $|C| \leq 2^d$, and hence $VCDIM(C) \leq d$ -- so the VC-Dimension of a class is never more than linear in the description length of one of the concepts in the class. I guess you must mean something different by "number of variables represented in each concept c", but I'm not sure what.
Aaron Roth
<machine-learning><lg.learning><vc-dimension>
How to deal with concept classes with exponential value of VC dimension
seteropere
# How to deal with concept classes with exponential value of VC dimension

(Asked by: username_0 on 2014-03-10)

Let $C$ be a concept class with VC dimension $d$ exponential to the input size (i.e number of variables represented in each concept $c\in C$). I am looking for papers/resources/suggestions of how computational learning community handle the learnability of $C$.

One thing I am thinking about is investigating the learnability of $C$ in active learning. Hoping that I will end up with less number of examples required.

However, I prefer to stick with the passive learning for now and wondered what else I can do for this poor $C$? As I am new to the field, I also wish to have some examples of concept classes with exponential VC dimension.

**Tags:** machine-learning, lg.learning, vc-dimension
> **Comments:**
> **username_1**: You need your number of samples to scale *linearly* with VC dimension or you cannot even do supervised learning. This is a lower bound, see: http://www.cis.upenn.edu/~mkearns/papers/lower.ps  
> **username_2**: Its also confusing what you are asking for... Suppose each $c \in C$ can be described with d bits. Then trivially, $|C| \leq 2^d$, and hence $VCDIM(C) \leq d$ -- so the VC-Dimension of a class is never more than linear in the description length of one of the concepts in the class. I guess you must mean something different by "number of variables represented in each concept c", but I'm not sure what.  

---

## 1 answers

### Answer by username_3 on 2014-12-15. Score: 3 | Accepted answer

One approach would be to stratify your concept class by VC-complexity. For example, suppose that $C$ is the set of all functions $f:\{0,1\}^n\to\{0,1\}$; its VC-dim is $2^n$.
However, you can decompose $C$ in any number of ways. Say, $C\_k$ is the collection of all functions whose (minimal) binary tree has depth $k$ or less. Or, $C\_k$ is the set of all functions whose Fourier expansion puts no weight on XORs of more than $k$ bits.
Then $C\_1\subset C\_2 \subset \ldots \subset C\_n$, and selecting the appropriate $C\_k$ is the problem of *model selection*. Machine learning theory offers a principled way of doings this via Structural Risk Minimization; here is a good start:
[Link](https://ieeexplore.ieee.org/document/705570)

> **Comments:**
> **username_0**: Thanks. Is this similar to what is known as maximal classes?  

---

