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.
Questions tagged [vc-dimension]
19 questions
10
votes
3 answers
Are there any rules of thumb for having some idea of what capacity a neural network needs to have for a given problem?
To give an example. Let's just consider the MNIST dataset of handwritten digits. Here are some things which might have an impact on the optimum model capacity:
There are 10 output classes
The inputs are 28x28 grayscale pixels (I think this…
Alexander Soare
- 1,319
- 2
- 11
- 26
7
votes
2 answers
How to estimate the capacity of a neural network?
Is it possible to estimate the capacity of a neural network model? If so, what are the techniques involved?
jaeger6
- 308
- 1
- 7
7
votes
1 answer
Are PAC learning and VC dimension relevant to machine learning in practice?
Are PAC learning and VC dimension relevant to machine learning in practice? If yes, what is their practical value?
To my understanding, there are two hits against these theories. The first is that the results all are conditioned on knowing the…
FourierFlux
- 783
- 1
- 4
- 14
5
votes
4 answers
How does size of the dataset depend on VC dimension of the hypothesis class?
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 the VC dimension in terms of what it means in layman terms, and why do…
Stefan Radonjic
- 187
- 5
3
votes
3 answers
How would you intuitively but rigorously explain what the VC dimension is?
The VC dimension is a very important concept in computational/statistical learning theory. However, the first time you read its definition, you may not immediately understand what it really represents or means, as it involves other concepts, such as…
nbro
- 39,006
- 12
- 98
- 176
3
votes
1 answer
What is the maximum number of dichotomies in a square?
I am new to machine learning. I am reading this blog post on the VC dimension.
$\mathcal H$ consists of all hypotheses in two dimensions $h: R^2 → \{−1, +1 \}$, positive inside some square boxes and negative elsewhere.
An example.
My…
Rain
- 31
- 1
3
votes
0 answers
How to show Sauer's Lemma when the inequalities are strict or they are equalities?
I have the following homework.
We proved Sauer's lemma by proving that for every class $H$ of finite VC-dimension $d$, and every subset $A$ of the domain,
$$
\left|\mathcal{H}_{A}\right| \leq |\{B \subseteq A: \mathcal{H} \text { shatters } B\} |…
Ben
- 133
- 5
2
votes
0 answers
What is the effect of K in K-NN on the VC dimension?
What is the effect of K in K-NN on the VC dimension? When K increases, is the VC dimension decreased or increased, or we can't say anything about this? Is there a reference book that discusses this?
robot learning
- 21
- 2
2
votes
1 answer
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 1: I have a classifier which fits the training…
Rajesh D
- 121
- 3
2
votes
1 answer
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 networks (1998) by Pascal Koirana and Eduardo D.…
nbro
- 39,006
- 12
- 98
- 176
2
votes
1 answer
How do I prove that $\mathcal{H}$, with $\mathcal{VC}$ dimension $d$, shatters all subsets with size less than $d-1$?
If a certain hypothesis class $\mathcal{H}$ has a $\mathcal{VC}$ dimension $d$ over a domain $X$, how can I prove that $H$ will shatter all subsets of $X$ with size less than $d$, i.e. $\mathcal{H}$ will shatter $A \subset X$ where $|A| \leq d-1$?
user9947
2
votes
1 answer
How does the number of stacked LSTM layers or units in each layer affect the model complexity?
I playing around sequence modeling to forecast the weather using LSTM.
How does the number of layers or units in each layer exactly affect the model complexity (in an LSTM)? For example, if I increase the number of layers and decrease the number of…
Manojk07
- 121
- 2
2
votes
0 answers
How can I show that the VC dimension of the set of all closed balls in $\mathbb{R}^n$ is at most $n+3$?
How can I show that the VC dimension of the set of all closed balls in $\mathbb{R}^n$ is at most $n+3$?
For this problem, I only try the case $n=2$ for 1. When $n=2$, consider 4 points $A,B,C,D$ and if one point is inside the triangle formed by the…
j200932
- 181
- 1
- 2
1
vote
0 answers
Is the VC dimension of a MLP regressor a valid upper bound on how many points it can exactly fit?
I want to calculate an upper bound on how many training points an MLP regressor can fit with ~0 error. I don't care about the test error, I want to overfit as much as possible the (few) training points.
For example, for linear regression, it's…
Daniele
- 11
- 2
1
vote
2 answers
Why was the VC dimension not defined for all configurations of $d$ points?
Let's start with a typical definition of the VC dimension (as described in this book)
Definition $3.10$ (VC-dimension) The $V C$ -dimension of a hypothesis set $\mathcal{H}$ is the size of the largest set that can be shattered by $\mathcal{H}$…
nbro
- 39,006
- 12
- 98
- 176