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.
48
questions
0
votes
0
answers
39
views
Infinite VC Dim not PAC learnable
This is usually shown by an application of the Statistical No Free Lunch Theorem.
But is this possible to show this by working simply with the definition of PAC learnability and the sample complexity ...
1
vote
1
answer
55
views
How can I understand the proof of the VC dimension of half-spaces in d-dimensions?
Statement : A half space is set of all points on one side of a linear separator, i.e., a set of the form $\{x \mid w^{T}x \ge t\}$. The VC-dimension of half spaces in $d$-dimensions is at least $d+1$.
...
- 35
2
votes
0
answers
53
views
Multi-class sample complexity for PAC learning using "VC dimension"
VC dimension covers the binary classification case, i.e. when we want to get a predictor $X \to \{0, 1\}$.
Using VC dimension, we can get the upper bound on the sample complexity for PAC-learning.
In ...
- 298
1
vote
0
answers
27
views
pseudo dimension of the minimum of functions
Suppose a real-valued function class $\mathcal{F}$ with pseudo dimension less than $d$, I am wondering what is the pseudo dimension of the following function class
\begin{equation}
\mathcal{F}_2 = \{\...
- 111
1
vote
0
answers
94
views
Hoeffding's inequality applicability for sample complexity
I am trying to determine some bounds for sample complexity. Suppose we have a bounded loss function $\ell$ and target function $f:\mathcal{X}\to\mathcal{Y}$. Hypothesis $h$ is learned, then the ...
- 11
0
votes
1
answer
107
views
Uniform convergence of union of hypothesis
Let $H_{1}$ and $H_{2}$ are two hypothesis classes over some domain $X$1.
If both $H_{1}$ and
$H_{2}$ have the uniform convergence property, then do $H_{1}$ U $H_{2}$ have uniform convergence?
- 9
0
votes
0
answers
38
views
Question about machine learning
Hello everyone I am new to the site, I have a question that was in the test and did not understand the parts that are in the question. This question from a test I failed to pass, in a machine learning ...
- 29
2
votes
1
answer
77
views
prove that 2 collection have the same VC-dimensions
I'm new here on the site, I'm a final year student in computer science.
In a machine learning course, there was a question on a test that I could not understand.
The question goes like this:
Suppose ...
- 29
1
vote
1
answer
121
views
Proof of Calculating VC-Dimensions
I still have some doubts for finding the VC-dimension. Suppose $\mathcal{H}$ has VC-dimension $n$. This is the process of how I think about it: (1) Show that there is a set of $n$ points that can be ...
- 21
1
vote
1
answer
198
views
VCdim of concentric circles
I have researched this topic in the last time, but no usefull results for me. So I'm here and I please you to help me with the following problem:
What is $VCdim$($\mathcal{H}$), where $\mathcal{H}$ is ...
- 11
1
vote
0
answers
87
views
VC Dimension of the class of $k$-dimensional cross-polytope (1-norm ($l_1$) ball)
What is the VC Dimension of the class of $k$-dimensional cross-polytope (1-norm ($l_1$) balls)?
A $k$-dimensional $l_1$ ball with radius $r\in \mathcal R$ and center $\mathbb v\in \mathcal R^k$ is
$\{\...
0
votes
1
answer
103
views
Pseudo-dimension of a subset of affine functions
Let's say there are two sets of affine functions.
$\mathcal{A} = \{ax +b \mid a,b \in \mathbb{R}\}$
$\mathcal{H} = \{2x + 1, x, 3x + 4, 4x\}$
I know that the $\mathrm{Pdim}(\mathcal{A}) = 2$. From ...
- 73
0
votes
0
answers
111
views
VC dimension of a combination of two hypothesis classes
I have found this exercise and I cannot solve it:
In $X=\mathbb R^2$, let's observe two models $H_1$ (rectangle with sides parallel to the coordinate axes) and $H_2$ (lines). We define a model $H_3$ ...
0
votes
0
answers
123
views
VC dimension of axis-aligned hyperplanes and their complements
This is a problem of VC that I've been trying to solve. Any help is appreciated.
Let's assume hypothesis classes $H_{\mathit{init}}$ of initial segments over domain $X = \mathbb R$ and $H_{\mathit{...
- 65
1
vote
1
answer
120
views
VC dimension of set of functions
Let $\chi$ be an instance space and $H \in \{0, 1\}^\chi$ a class with finite VC-dimension. For each $x \in X$ we consider $z_x\colon H \rightarrow \{0, 1\}$ s.t. $z_x(h) = h(x), \forall h \in H$.
Let ...
- 293
1
vote
1
answer
180
views
Understanding growth function of closed intervals in $\mathbb{R}$
I as studying VCdimensions and growth functions and found the following example on Wikipedia:
The domain is the real like $\mathbb{R}$. The set H contains all the real intervals, i.e., all sets of ...
- 293
0
votes
1
answer
360
views
What is the VC dimension of the hypothesis class $H=\left\{f_{\theta_{1}, \theta_{2}}: R^{2} \rightarrow\{0,1\} \mid 0<\theta_{1}<\theta_{2}\right\}$?
I would like to know what is the VC dimension of the following hypothesis class.
$$H=\left\{f_{\theta_{1}, \theta_{2}}: R^{2} \rightarrow\{0,1\} \mid 0<\theta_{1}<\theta_{2}\right\}$$
where $f_{\...
- 11
0
votes
1
answer
151
views
Classes of circle rims
The input space is a unit circle, $\mathcal{X} = \mathbb{S}^1 \subset \mathbb{R}^2$. There is class $\mathcal{F}$ of arcs on $\mathbb{S}^1$, where a point is labeled 1 if it is on the arc, and 0 ...
user120261
1
vote
1
answer
171
views
VC dimension of only the rim of a unit disk
Suppose we have an origin centered circle, ie $x^2 + y^2 =1$, so it's in $\mathbb{R}^2$ (2D). It will be classified as 1 if it lies only on this arc, and will be labeled 0 otherwise. What is the VC ...
user120261
3
votes
1
answer
171
views
PAC learning vs. learning on uniform distribution
The class of function $\mathcal{F}$ is PAC-learnable if there exists an algorithm $A$ such that for any distribution $D$, any unknown function $f$ and any $\epsilon, \delta$ it holds that there exists ...
- 53
0
votes
1
answer
50
views
Uniform Convergence and VC Theroy
I've started reading more about statistical learning theory, specifically this paper right here and I cannot understand the following part:
It turns out the conditions required to render empirical ...
- 105
1
vote
1
answer
272
views
Proof of uniform convergence if VC dimension is finite
In the book »Understanding Machine Learning: From Theory to Algorithms«, written by Ben-David and Shalev-Shwartz, there is a proof which I do not understand. The context is proving that if a ...
- 327
0
votes
2
answers
2k
views
VC dimension of the class of polynomial classifiers of degree $n$
I came across this statement on page 85 of the book "understanding machine learning: from theory to algorithms"
The general idea is as follows:
Consider a binary classification problem with the ...
- 41
1
vote
1
answer
94
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 ...
- 101
1
vote
1
answer
602
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
0
answers
268
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 ...
- 11
5
votes
1
answer
180
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)| \...
- 153
1
vote
1
answer
417
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 ...
- 142
3
votes
3
answers
7k
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 <= ...
- 133
3
votes
2
answers
602
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 ...
- 133
4
votes
2
answers
1k
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 ...
- 1,399
103
votes
7
answers
21k
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. ...
- 1,399
4
votes
0
answers
80
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) |...
- 5,798
3
votes
1
answer
489
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 ...
- 5,798
0
votes
1
answer
608
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 ...
- 487
1
vote
0
answers
198
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 ...
- 11
0
votes
1
answer
6k
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 ...
- 35
1
vote
0
answers
187
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 ...
- 677
1
vote
1
answer
949
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}$ )...
- 11
1
vote
0
answers
224
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?
- 131
3
votes
1
answer
864
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 ...
- 41
6
votes
2
answers
463
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}{\...
- 677
4
votes
1
answer
1k
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)$ ...
- 317
3
votes
2
answers
342
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{...
- 141
3
votes
0
answers
265
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 ...
- 677
8
votes
2
answers
3k
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 "...
- 81
8
votes
1
answer
844
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 ...
- 1,115
19
votes
1
answer
1k
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:
...
- 4,782