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.

Filter by
Sorted by
Tagged with
1
vote
1answer
47 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)...
5
votes
4answers
375 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 ...
2
votes
1answer
47 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 ...
1
vote
1answer
47 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 ...
1
vote
0answers
43 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? ...
2
votes
1answer
84 views

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 ...
2
votes
1answer
72 views

How to prove $\mathcal H$ with VC dimension $d$ shatter all subsets with size less than $d-1$?

I was wondering that if a certain hypothesis class $H$ has a VC dimension $d$ over domain $X$ how to prove that $H$ will shatter all subsets of $X$ with size less than $d$ i.e $H$ will shatter $A \...
4
votes
2answers
222 views

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?
2
votes
0answers
28 views

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 ...
5
votes
1answer
108 views

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 ...
3
votes
1answer
86 views

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 ...
3
votes
1answer
55 views

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 |\...