# Questions tagged [vc-dimension]

For questions related to the Vapnik–Chervonenkis (VC) dimension, originally defined by Vladimir Vapnik and Alexey Chervonenkis, which is a measure of the capacity (complexity, expressive power, richness, or flexibility) of a space of functions that can be learned by a statistical classification algorithm.

13 questions
Filter by
Sorted by
Tagged with
63 views

### VC Dimension of Reinforcement Learning (RL)

Is the VC dimension meaningful for the reinforcement learning (RL) as a machine learning (ML) method? How?
57 views

### What do we mean by saying “VC dimension gives a LOOSE, not TIGHT bound”?

From what I understand VC dimension is what establishes the feasibility of learning for infinite hypothesis sets, the only kind we would use in practice. But, the literature (i.e. Learning from Data)...
409 views

### How does size of the dataset depend on VC dimension?

This might be a little broad question, but I have been watching Caltech youtube videos on Machine Learning, and in this video prof. is trying to explain how we should interpret VC dimension in terms ...
53 views

### An infinite VC dimensional space vs using hierarchical subspaces of finite but growing VC dimensions

I have the following scenario. I have a binary classification problem, whose underlying function is a step function. The probability distribution of feature vectors is a uniform over the domain. Case ...
58 views

### Understanding relation between VC Symmetrization Lemma and Generalization Bounds

I am new in the field of Machine Learning so I wanted to start of by reading more about mathematics and history behind it. I am currently reading, in my opinion, a very good and descriptive paper on ...
49 views

### Why does the growth function need to be polynomial in order for the learning algorithm to be consistent?

Could someone please explain to me why in VC theory, specifically, when calculating the VC dimension, the growth function needs to be polynomial in order for the learning algorithm to be consistent? ...
### How can neural networks approximate any continuous function but have $\mathcal{VC}$ dimension only proportional to their number of parameters?
Neural networks typically have $\mathcal{VC}$ dimension that is proportional to their number of parameters and inputs. For example, see the papers Vapnik-Chervonenkis dimension of recurrent neural ...