26 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 ...
Vladislav Gladkikh's user avatar
19 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_'s user avatar
  • 6,327
6 votes

What is the exact definition of VC dimension?

The points should fulfil points in general condition before consider for VC dimension.
biddut's user avatar
  • 161
5 votes

How to calculate VC-dimension?

The VC dimension of a classifier is determined the following way: ...
Martin Thoma's user avatar
  • 18.8k
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. ...
Kaladin's user avatar
  • 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 ...
OmG's user avatar
  • 1,219
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) <...
Esmailian's user avatar
  • 9,252
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 ...
Esmailian's user avatar
  • 9,252
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 ...
Kirill Fedyanin's user avatar
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}$...
user12075's user avatar
  • 2,254
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 ...
user112189's user avatar
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 ...
Sharov's user avatar
  • 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\...
Ben Reiniger's user avatar
  • 11.6k
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_'s user avatar
  • 6,327
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)$ ...
Esmailian's user avatar
  • 9,252
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 ...
ignatius's user avatar
  • 1,658

Only top scored, non community-wiki answers of a minimum length are eligible