How to deal with concept classes with exponential value of VC dimension

Question

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.

Answer 1

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