25
votes
Accepted
What is the exact definition of VC dimension?
The definition of VC dimension is: if there exists a set of n points that can be shattered by the classifier and there is no set of n+1 points that can be shattered by the classifier, then the VC ...
- 1,096
18
votes
Accepted
How to calculate VC-dimension?
The VC dimension is an estimate for the capability of a binary classifier. If you can find a set of $n$ points, so that it can be shattered by the classifier (i.e. classify all possible $2^n$ ...
oW_♦
- 6,254
6
votes
What is the exact definition of VC dimension?
The points should fulfil points in general condition before consider for VC dimension.
- 161
5
votes
How to calculate VC-dimension?
The VC dimension of a classifier is determined the following way:
...
- 18.7k
4
votes
With regards to VC-dimension, why can you shatter 3 points with circles but not 4 points?
Given $4$ points $A,B,C,D$. If they do not lie on the boundary of a convex hull, then it is impossible to shatter the inner point from the boundary.
So assume they lie on the boundary of the hull. ...
- 141
3
votes
Accepted
VC-dimension of the infinite set of convex bodies?
For a binary class of data and any number of instances, as you have an infinite number of convex bodies, you can put all instances of a class inside the body and leave others. In this way, you can ...
- 1,199
3
votes
Accepted
Why is a lower bound necessary in proofs of VC-dimensions for various examples of hypotheses?
Lets use the quotes from the book.
To give an upper bound, we need to prove that no set $S$ of cardinality
$d + 1$ can be shattered by $H$
By doing this, we are proving that $\text{VCdim}(H) <...
- 9,147
2
votes
Accepted
VC dimension of hypothesis space of finite union of intervals
VC dimension is defined for a hypothesis space $H$, e.g. a set of binary classifiers $C \rightarrow \{0, 1\}$. For example, hypothesis space
$$H=\{{\Bbb 1}_{x \le \theta}: \theta \in {\Bbb R}\}$$
has ...
- 9,147
2
votes
Accepted
VC dimension for Gaussian Process Regression
The expressiveness of the gaussian process grows with a number of training points. So, the vapnik-chervonenkis dimension in fact is infinite (pretty much the same way it's infinite for k nearest ...
- 353
2
votes
Why the VC dimension to this linear hypothesis equal to 3?
The VC dimension for the classifier depends on the dimension of space that your data points belong to.
In your problem, if your mean $x\in \mathbb{R^2}$, then the VC dimension is 3. For $\mathbb{R^2}$...
- 2,214
1
vote
What is the exact definition of VC dimension?
So based on the definition we need to find $2^n$ arrangements that can be shattered by a linear boundary, which you have shown in the figure. Therefore, it does not matter if there are other ...
- 11
1
vote
Accepted
Vapnik Chervonenkis dimension of a classifier from the Wikipedia page
Here is good definition of VC-dimension -- https://www.cs.hmc.edu/~yjw/teaching/cs158/lectures/21_VCDimension.pdf
Quotation from link above:
To show that hypothesis class has VC-dimension d in input ...
- 126
1
vote
Disproving or proving claim that if VCdim is "n" then it is possible that a set of smaller size is not shattered
I agree, the claim as written is incorrect. If $C^*$ is shattered by $\mathcal{H}$, and $C\subseteq C^*$, then $C$ is also shattered by $\mathcal{H}$; to be possibly over-pedantic:
For each $B\...
- 11.1k
1
vote
Accepted
VC dimension of half spaces over the real line
First you need to understand how to calculate the VC-dimension. There are two conditions for the VC-dimension to be $n$ (here $n=1$):
You need to find one set of $n$ points that can be shattered (i.e....
oW_♦
- 6,254
1
vote
A question on realizable sample complexity
We want to prove:
If H is PAC learnable, then $\forall \epsilon, \exists C, \forall m \geq m_2:=Clog(1/\epsilon)(m_1+1/\epsilon^2), E[L] \leq \epsilon \mbox{ (a)}$
where $m_1:=m(\epsilon/2,1/2)$
...
- 9,147
1
vote
Why the VC dimension to this linear hypothesis equal to 3?
The VC dimension depends on the dimension of your data and on the family of functions you are evaluating.
In $\mathbb R^2$, the VC dimesion of the family $h(x)$ of oriented lines is 3 beacause, with ...
- 1,648
Only top scored, non community-wiki answers of a minimum length are eligible