3
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ 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: cis.upenn.edu/~mkearns/papers/lower.ps $\endgroup$ – Lev Reyzin♦ Mar 10 '14 at 18:23
  • 1
    $\begingroup$ 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. $\endgroup$ – Aaron Roth Mar 11 '14 at 21:36
2
$\begingroup$

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: http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=705570&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel4%2F18%2F15247%2F00705570.pdf%3Farnumber%3D705570

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks. Is this similar to what is known as maximal classes? $\endgroup$ – seteropere Dec 20 '14 at 0:26

Your Answer

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

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