Statistical Analysis Stack Exchange
Statistical Analysis Stack Exchange

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.

69 questions
17
votes
2 answers

What is the VC dimension of a decision tree?

What is the VC dimension of a decision tree with k splits in two dimensions? Let us say the model is CART and the only allowed splits are parallel to the axes. So for one split we can order 3 points in a triangle and then for any labeling of the…
Tal Galili
  • 19,935
  • 32
  • 133
  • 195
16
votes
2 answers

What are alternatives to VC-dimension for measuring the complexity of neural networks?

I have come across some basic ways to measure the complexity of neural networks: Naive and informal: count the number of neurons, hidden neurons, layers, or hidden layers VC-dimension (Eduardo D. Sontag [1998] "VC dimension of neural networks"…
Artem Kaznatcheev
  • 2,569
  • 1
  • 20
  • 38
14
votes
1 answer

What does VC dimension tell us about deep learning?

In basic machine learning we are taught the following "rules of thumb": a) the size of your data should be at least 10 times the size of the VC dimension of your hypothesis set. b) a neural network with N connections has a VC dimension of…
Fequish
  • 697
  • 2
  • 5
  • 17
14
votes
3 answers

VC dimension of a rectangle

The book "Introduction to Machine learning" by Ethem Alpaydın states that the VC dimension of an axis-aligned rectangle is 4. But how can a rectangle shatter a set of four collinear points with alternate positive and negative points?? Can someone…
kaz
  • 243
  • 1
  • 2
  • 5
13
votes
2 answers

VC dimension of regression models

In the lecture series Learning from Data, the professor mentions that the VC dimension measures the model complexity on how many points a given model can shatter. So this works perfectly well for classification models where we could say out of N…
karthikbharadwaj
  • 274
  • 2
  • 8
12
votes
1 answer

Generalization bounds on SVM

I am interested in theoretical results for the generalization ability of Support Vector Machines, e.g. bounds on the probability of classification error and on the Vapnik-Chervonenkis (VC) dimension of these machines. However, reading through the…
Daneel Olivaw
  • 745
  • 7
  • 18
12
votes
2 answers

Calculating VC-dimension of a neural network

If I have some fixed non-recurrent (DAG) topology (fixed set of nodes and edges, but the learning algorithm can vary the weight on the edges) of sigmoid neurons with $n$ input neurons which can only take strings in $\{-1,1\}^n$ as input and lead to…
Artem Kaznatcheev
  • 2,569
  • 1
  • 20
  • 38
11
votes
3 answers

Why is VC dimension important?

Wikipedia says that: VC dimension is the cardinality of the largest set of points that a algorithm can shatter. For instance, a linear classifier has a cardinality n+1. My question is why do we care? Most datasets that you do linear…
Undergradstudent
  • 270
  • 2
  • 9
10
votes
1 answer

VC-Dimension of k-nearest neighbor

What is the VC-Dimension of the k-nearest neighbor algorithm if k is equal to the number of training points used? Context: This question was asked in a course I take and the answer given there was 0. I do, however, not understand why this is the…
Julius Maximilian Steen
  • 203
  • 2
  • 5
9
votes
1 answer

What is the utility/significance of PAC learnability and VC dimension?

I've been reading Shalev-Shwartz & Ben-David's book, "Understanding Machine Learning", which presents the PAC theory in its Part I. While the theory of PAC learnability does appear very elegant and remarkable to me, I'm not so sure about its…
syeh_106
  • 746
  • 4
  • 15
8
votes
1 answer

Do ensemble techniques increase VC-dimension?

Techniques like Adaboost use a ensemble of weak classifiers to obtain a "better" classifier. Does(Can) the final classifier have a greater VC-dimension than the weak classifier? An intuitive explanation would suffice.
shyamupa
  • 383
  • 2
  • 9
7
votes
3 answers

VC dimension of SVM with polynomial kernel in $\mathbb{R^{2}}$

What is the VC dimension of SVM with the polynomial kernel $k(x,x')=(1+_{\mathbb{R^{2}}})^{2}$ for binary classification in $\mathbb{R^{2}}$? It would be equal or more than v iff there exists a set of v points such that, any labeling (-1 or…
Wok
  • 1,065
  • 10
  • 22
7
votes
0 answers

Rank of kernel Gram matrix and classifier performance

In kernel machines we have some kernel function $k$ and we compute the $n \times n$ Gram matrix $K$ where $K_{ij} = k(x_i, x_j)$ for observations $x_i, x_j \in \mathbb R^p$. I'm letting $n$ denote the number of observations and $p$ the number of…
alfalfa
  • 581
  • 3
  • 13
6
votes
0 answers

Is that possible to estimate the VC dimension for GBM (or more specific XGBoost)?

Is there any simple way to estimate the VC dimension for GBM? Or, for more specific implementation XGBoost? XGBoost usually has large variability when training on a dataset with less than 500 samples more than 1000 features. Is there any way to…
user2149631
  • 439
  • 2
  • 10
6
votes
1 answer

Relationship between VC dimension and degrees of freedom

I'm studying machine learning and I feel there is a strong relationship between the concept of VC dimension and the more classical (statistical) concept of degrees of freedom. Can anyone explain such a connection?
stochazesthai
  • 4,616
  • 2
  • 18
  • 26
1
2 3 4 5