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.

Filter by
Sorted by
Tagged with
0
votes
1answer
14 views

What can be said about distribution which has a predictor in a class with VC dimension k?

Suppose, a distribution D on X x {0, 1} has a predictor with 0 loss in a function class with VC dimension k < $\infty$. What does it say about this distribution?
1
vote
1answer
31 views

If the VC dimension of class H is D, does it shatter any set of size D, or just one?

From Wikipedia The VC dimension D of class H is the largest cardinality of sets shattered by H. Does it mean that the class shatters any set on cardinality D?
2
votes
0answers
27 views

Relationship between finite VC dimension and Lipschitzness

It appears that functions with finite VC dimension can not "change too fast", so they have to be Lipschitz. Is this the case? Is there a known relation between VC dimension and ...
0
votes
1answer
40 views

Why do neural networks outperform SVMs on image recognition if SVMs have the less generalization error?

Why do neural networks outperform SVMs if SVMs have the less generalization error according to Vapnik? Is generalization error only useful in data scarce environments? Is it because neural networks ...
0
votes
0answers
21 views

Is VC theory just for classification problems or is it also used for multiple linear regression?

I have been reading up on VC theory as a component of statistical learning theory the last few days, and how it allows you to bound the generalization error for classification problems. What about ...
2
votes
1answer
94 views

What is alpha in Vapnik's statistical learning theory?

I'm currently studying Vapnik's theory of statistical learning. I rely on Vapnik (1995) and some secondary literature that is more accessible to me. Vapnik defines a learning machine as 'an object' ...
1
vote
0answers
52 views

VC dimension upper bound of linear kernel SVM

In the book Statistical learning theory by Vapnik, a theorem is presented regarding the maximal VC dimension of a separating hyperplane classifier (that is, in in a SVM setting). A subset of ...
1
vote
0answers
13 views

Relation between nonlinearity and hypothesis set in the view of bias variance trade off

I understand bias variance Trade off pretty well in terms of linear regression. As when the functions gets more wiggly (higher degrees) then variance on test set increases. Makes sense. However, in a ...
0
votes
0answers
31 views

Combinatorial Dimension of Statistical Models for Point Process Data

What measure of combinatorial complexity can be used for models fitted on point process data (e.g. Hawkes or Poisson processes)? Is VC dimension or some generalization of it (e.g. Pollard's pseudo-...
1
vote
1answer
78 views

Shattering threshold functions in $\mathbb{R}$ (VC theory)

The book "Understanding Machine Learning" has the following example in the section on VC dimension: Let $\mathcal{H}$ be the class of threshold functions over $\mathbb{R}$ (real numbers). Take a ...
0
votes
0answers
9 views

VC dimension of space dividing planes

I was solving questions about finding the VC dimension of some binary classifiers, and I couldn't solve this one: $\mathcal{H}$ is a hypothesis set on $\mathbb{R}^d$, given by: $\mathcal{H}=\{f_{T, ...
0
votes
1answer
23 views

How do you prove that the following 2 hypothesis classes' VC-dimensions are equal?

Given a hypothesis class $H=\{h:X\to\{0,1\}\}$. Let $c\in H$ be the correct predictor. Denote $H^c = \{c\Delta h:h\in H\}$, where $c\Delta h=(h\backslash c)\cup (c\backslash h)$. Please prove that ...
1
vote
0answers
41 views

VC-dimension and fundamental theorem

I do not understand why the correct answer is what is written below, and how it follows from the fundamental theorem of learning theory. I thought it was connected to weak learners, but according to ...
0
votes
1answer
619 views

What is the VC dimension of k-nearest-neighbours with k=1?

I would answer that it is $\infty$, but I have a gut feeling this may not be the correct answer... May I present my proof attempt that it is indeed $\infty$, so that you can clear any misconceptions ...
4
votes
1answer
189 views

Rademacher Bound, An Alternative to Cross Validation for Ridge?

Below is a theorem from the book "Foundations of Machine Learning". It specifies the generalization bounds for Kernel Ridge Regression by making use of the Rademacher Complexity on linear models. $R(...
1
vote
1answer
2k views

VC dimension of sine family is infinite?

From what I understand, the VC dimension of an hypothesis class is given by the maximum number of points in general position (or random) on the domain space that can be arbitrarily labeled by the ...
2
votes
0answers
224 views

VC dimension of rectangles in 2D space

I understand that the VC dimension of axis-aligned rectangles is 4 because there exists a set of 4 points that can be shattered by a rectangle and any set of 5 points cannot be shattered by a ...
0
votes
1answer
664 views

VC dimension of Parity Function

Reference: Machine Learning Foundations lecture by Yishay Mansour. I am struggling to understand the explanation when they arrive at $X_S(e_j)$ Could someone provide some details? Thanks.
0
votes
2answers
494 views

VC dimension of signed intervals

Understanding Machine Learning: From Theory to Algorithms, Section 6.8, Question 9 is Let $\mathcal H$ be the class of signed intervals, that is, $\mathcal H = \{ h_{a,b,s} : a \le b, s \in \{-1, ...
2
votes
0answers
816 views

Upper and lower bounds for VC dimension of union and intersection of hypothesis sets

Suppose we have K hypothesis sets - $H_1, H_2,...,H_K$, each with VC dimension $d_{VC}(H_i)$. What will be the upper and lower bounds on the VC dimensions of the union and intersection of these ...
2
votes
1answer
77 views

Can the Vapnik-Chervonenkis inequality be generalised to non-zero-one error functions?

I learned about the VC inequality of the bound of difference between training errors and generalisation errors. The two places (Stanford CS229 notes and Wikipedia) where I read about the theorem both ...
1
vote
1answer
806 views

VC dimension of decision tree [duplicate]

I encountered a question that I really can't figure out: Suppose your hypothesis class(H) consists of decision trees with 7 nodes that splits on only one feature. How to calculate the VC dimension of ...
2
votes
1answer
1k views

How to compute number of dichotomies/growth function value?

I am studying the book 'learning from data' by Mostafa. I understand that the number of dichotomies for positive rays on the number line is $N+1$ (ie if you have one point, $x$, on the number line, ...
2
votes
0answers
989 views

Derivation of VC dimension of linear regression

Looking at these slides, we see the following definition for the VC dimension of a class of real-valued functions: So I want to derive the VC dimension of linear regression. For starters I'm not ...
1
vote
0answers
48 views

Is it a sin to plot data when you don't have a test set?

Let's say I have an Excel workbook containing data I want to analyse. I plot the data in Excel and see it has roughly a linear shape. Therefore, I use Excel to draw me the fitted line and brag to my ...
5
votes
1answer
437 views

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 ...
1
vote
0answers
72 views

Does pca increases my model's VC dimension?

Does implementing pca to the training set considered as learning and adds VC dimension to the whole model? I am currently using support vector machines to classify my inputs into 2 groups and I found ...
2
votes
0answers
587 views

VC dimension upper bound for Random Forest [duplicate]

I encounter such an exercise question as below and have no clue so far. Consider using decision trees/forests to implement Boolean functions, i.e. classifiers from {0,1}n to{0,1}. 1) Give a ...
11
votes
1answer
3k views

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 ...
1
vote
1answer
251 views

Understanding the Vapnik and Chervonenkis Theorem

I am currently studying VC theory and have question to better understand the main theorems inside. I hope that someone who deeply understands it might be willing to give me some intuition on how to ...
1
vote
0answers
97 views

PAC learnability of real valued function w.r.t. zero loss function

The necessary and sufficient conditions for learning to occur in the task of binary classification are among the fundamental results in learning theory. In the sources I'm familiar with, this theorem ...
2
votes
0answers
3k views

General formula for the VC Dimension of a SVM

I am interested in the question of the Vapnik–Chervonenkis (VC) dimension of Support Vector Machines (SVM). Until now, I have only found partial results related to particular cases of SVM. Some ...
1
vote
0answers
368 views

Upper bound for the VC dimension of NN with $L$ layers of $d$ nodes each

I'm trying to give an upper bound for the VC dimension of the hypotheses class $H$ of NN with binary output, $L$ layers (feedforward, fully connected), each layer except the output layer contains $d$ ...
0
votes
0answers
103 views

Statistical Learning Theory - Loss Function

I am reading Vapnik's "Statistical Learning Theory" and I am confused about his use of Q(z,alpha). On page 23 he explains that Q is the loss function which takes as argument a function g, the function ...
6
votes
0answers
236 views

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

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 ...
17
votes
1answer
9k views

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 ...
3
votes
1answer
136 views

How does depth-efficiency help neural networks learn?

Depth efficiency is an accepted result about neural networks that says the expressiveness of a network with additional layers can only be matched by a shallow network with exponentially many more ...
6
votes
0answers
447 views

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 ...
1
vote
0answers
106 views

Are VC dimensionality and dimension of kernel used in SVM related?

Are VC dimensionality and dimension of kernel used in SVM related to each other? or are they independent parameters in a classification process ?
4
votes
3answers
642 views

random forest - summarize two features in one without losing information

I am training a random forest on a dataset including both categorical and numerical features. In particular I have a binary feature, call it $x_1$, which has $0$ or $1$ as possible outcomes. I also ...
2
votes
0answers
520 views

VC dimension of a quadratic binary classifier

Assume we have a set of training data $\{\boldsymbol{x}_i, y_i\}_{i=1}^n$ from $\mathbb{R}^2 \times \{-1, 1\}$. The hypotheses $\mathcal{H} $ are all classifiers with the form $\hat{y} = \text{sign}(\...
5
votes
2answers
2k views

How to make the conclustion that VC-dimension for hyperplane in $\mathbb{R^{3}}$ is strictly less than $\mathbb{R^{4}}$?

Given four points in $\mathbb{R^{3}}$ real space, $S = \{(1, 1, 1), (1, 1, -1), (-1, -1, 1), (-1, -1, -1)\} \in \mathbb{R^{3}}$. Will these four points be shattered by a hyperplane in $\mathbb{R^{3}}...
12
votes
3answers
4k views

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 ...
15
votes
1answer
2k views

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 ...
5
votes
1answer
615 views

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 ...
4
votes
1answer
827 views

What is the VC Dimension of a Naive Bayes Classifier?

How do you calculate the VC dimension of a Naive Bayes classifier with say K features?
2
votes
0answers
187 views

Is there a known relationship between the Intrinsic Dimensionality of a dataset and the VC dimension of a model?

We know that the Intrinsic Dimension of a dataset gives the low dimensional sub manifold in which the real data distribution lies. On the other hand, the VC dimension of a model gives the bounds for ...
12
votes
2answers
4k views

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 ...
10
votes
1answer
5k views

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. ...
10
votes
3answers
8k views

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 ...