Questions tagged [vc-dimension]
The VC dimension (for Vapnik–Chervonenkis dimension) is a measure of the capacity (complexity, expressive power, richness, or flexibility) of a statistical classification algorithm, defined as the cardinality of the largest set of points that the algorithm can shatter.
25
questions
1
vote
1answer
41 views
How can the VC-dimension of Turing machine be finite?
The VC-dimension of a hypothesis class $\mathcal{H}$ is defined to be the size of the maximal set $C$ such that $\mathcal{H}$ cannot shutter. This paper shows that the VC-dimension of the set of all ...
1
vote
1answer
205 views
VC dimension of finite unions of one-sided intervals
What is the VC dimension of $k$ finite unions of one-sided intervals:
If we take 3 one-sided intervals like $(-\infty, a_1] $, $(-\infty, a_2] $ and $(-\infty, a_3] $, I think union of these ...
1
vote
0answers
181 views
VC Dimension of A Set of Hypothesis
I am confused about what does a VC dimension of a set of hypothesis means.
I have two hypothesis, say $H_1$ with VC dimension of $x$, and $H_2$ of VC dimension of $y$. Does this automatically mean ...
5
votes
1answer
90 views
VC dimensions: Let ${x_1, \ldots, x_N}$ be $N$ labelled points on $\mathbb{R}$, then there exists a sinusoid that separates these points
(Proposition, pg 26): Let ${x_1, \ldots, x_N}$ be $N$ points on $\mathbb{R}$, $N \in \mathbb{Z}$, labelled either $+1$ or $-1$ , then there exists a function from the set $\{t \mapsto \sin(\omega t)| \...
1
vote
1answer
191 views
Geometric intuition behind VC-dimension
Recently, I learnt about VC-dimension and how its boundedness assures PAC learnability on uncountable range spaces (let's assume that hypothesis class is the same as the family of concepts we want to ...
2
votes
3answers
2k views
VC Dimension of Origin-Centered Circle
Is the VC dimension of an origin-centered circle 1 or 2?
It seems to me that the VC dimension of an origin centered circle should be 1, because for two points with distances from the origin r1 <= ...
3
votes
1answer
379 views
Do I have the right definition of VC dimension?
I am having some trouble understanding the notion of the VC dimension. The definition I have is the following:
The VC dimension of a set of hypothesis functions $H$ is the cardinality of the ...
4
votes
2answers
807 views
Is it a problem that “successful” machine learning algorithms have large VC dimension?
In my limited exposure, it appears that "successful" machine learning algorithms tend to have very large VC dimension. For example, XGBoost is famous for being used to win the Higgs Boson Kaggle ...
83
votes
7answers
16k views
Why is deep learning hyped despite bad VC dimension?
The Vapnik–Chervonenkis (VC)-dimension formula for neural networks ranges from $O(E)$ to $O(E^2)$, with $O(E^2V^2)$ in the worst case, where $E$ is the number of edges and $V$ is the number of nodes. ...
4
votes
0answers
47 views
VC dimension and binary operations
There are two classes of binary functions, $F_1,F_2$. The VC-dimension of $F_i$ is $d_i$. Is there any simple formula for the VC-dimension of the following classes?
$F_\lor := \{ f_1(x) \lor f_2(x) |...
3
votes
1answer
352 views
The VC dimension when the samples are fixed
The VC dimension is usually used in the following way. There is a space of hypotheses. There is an unknown probability distribution. We sample some training-samples from this distribution. We find the ...
0
votes
1answer
281 views
VC dimension of monotone disjunctions of length k over n variables?
There are of course $n \choose k$ monotone disjunctions which bounds the VC dimension at $\log_2 {n \choose k}$. I'm wondering if this is bound at $k \log_2 n$? (Possibly follows from combinatorial ...
1
vote
0answers
143 views
Sample Complexity for Real-Valued PAC-Learnable Functions
Can anyone shed some light on how the VC Dimension affects the sample complexity bounds of infinite hypothesis classes with real-valued outputs in PAC learning, or how to calculate the sample ...
0
votes
1answer
2k views
VC Dimension Calculation for Intervals
As i See in ML Course a VC dimension calculation is very theoretical.
What is the VC-dimension of intervals in R?
The target function is specifieed by an interval, and labels any example positive ...
1
vote
0answers
105 views
If one hypothesis class is a proper subset of another, what is the relation of their VC dimensions?
Assume two hypotheses classes $H_A\subset H_B$ defined over the same instance space $\delta$. Assume also $VC(H_A)=d$, does this mean $VC(H_B)\geq d$ ? where $VC$ is the VC dimension.
We can use the ...
1
vote
1answer
466 views
Why is the VC dimension different on intervals and half intervals?
As I read this lecture for being familiar with VC dimension we find on p. 8:
VC(half intervals in $\mathbb{R}$ ) = 1 .... no subset of size 2 can be shattered
VC(intervals in $\mathbb{R}$ )...
1
vote
0answers
189 views
VC dimension of 1-NN classifier for discrete metric space?
We know VC dimension of 1-NN classifier is infinite for continuous metric space. Is there any proof of VC dimension of 1-NN classifier if the metric space is discrete?
2
votes
1answer
538 views
VC dimension of complement
Let $C\subseteq 2^X$ be a concept class over $X$ and let $\bar{C}:=\{X\setminus c\mid c\in C\}$ be the complement. Show that $VCdim(C)=VCdim(\bar{C})$.
Proof:
Let $d:=VC_{dim}(C)$, then there exists ...
6
votes
2answers
419 views
What is usually the next step after showing the VC dimension?
I am new to statistical learning. I have a structure $X$ where I showed its hypothesis class $H$ has VC dimension $d$. All I know now is that I can bound the number of examples by $m\geq \frac{1}{\...
2
votes
1answer
597 views
VC dimension and optimal mistake bound
I have a question regarding optimal mistake bound for learning algorithm
There is a famous fact that $VC(C) \leq Opt(C)$,
where $C$ - set of learning concepts,
VC(C) - VC dimension of C,
$Opt(C)$ ...
3
votes
2answers
254 views
How to determine the size of training data using VC dimension?
I want to determine the size of training data ($m$) when I know the parameters $VC(H)$, $δ$ and $e$. As I know the $VC$ bound satisfy this equation:
$$ \mathrm{error}_{\mathrm{true}}(h) \le \mathrm{...
3
votes
0answers
250 views
How to find the shattered set size for unknown hypothesis target
My aim is to prove a VC-dimension $d$ for different problems. All the problems I have do not have a target function (or concept) explicitly stated. This unlike most of the examples I came through. For ...
4
votes
2answers
2k views
VC dimension of linear separator in 3D
I am confused about the Vapnik-Chervonenkis dimension of a linear separator in 3 dimensions.
In three dimensions, a linear separator would be a plane, and the classification model would be "...
8
votes
1answer
463 views
Vapnik-Chervonenkis Dimension: why cannot four points on a line be shattered by rectangles?
So I'm reading "Introduction to Machine Learning" 2nd edition, by Bishop, et. all. On page 27 they discuss the Vapnik-Chervonenkis Dimension which is,
"The maximum number of points that can be ...
17
votes
1answer
753 views
Efficiently computing or approximating the VC-dimension of a neural network
My goal is to solve the following problem, which I have described by its input and output:
Input:
A directed acyclic graph $G$ with $m$ nodes, $n$ sources, and $1$ sink ($m > n \geq 1$).
Output:
...
