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

64 questions
Filter by
Sorted by
Tagged with
0answers
11 views

### Generalization bound for parameters rather than loss functions

I was wondering if it is possible to obtain high probability bounds (provided finite sample size of the training data) for the distance (say in the l-1 or l-2 norm) between the best parameter set and ...
0answers
160 views

### VC-Dimension of Axis-Aligned Right Triangles and 5-point Convex Hull

I am having trouble proving the following fact about the VC dimension of triangles. Consider axis-aligned right triangles in the plane, with the the right angle in the lower left corner. The ...
0answers
25 views

### VC dimension calculation

I am currently trying to evaluate the model's VC dimensions. I don't need any fancy calculations, just an estimation of which model has more said dimensions. As far as I have understood from various ...
0answers
29 views

### VC generalization bound example question

I feel it's a really basic problem yet I can't wrap my head around it. The problem is Exercise 2.5 from Yaser S. Abu-Mostafa's book Learning From Data. We are given a learning model with growth ...
1answer
44 views

### What is the difference between sieve estimation and structural risk minimization?

I was wondering if you could help me out. I am quite confused about the difference between sieve estimators (Ulf Grenander) and structural risk minimization (SRM) (Vladimir Vapnik). Could anyone give ...
0answers
16 views

### Finite sample behavior of learning algorithms

In machine learning, given a joint distribution $\mathbb P_{X, Y}$, where $Y=\{0, 1\}$ making it a binary classification problem, and $N$ iid training samples $\{(x_i, y_i)\}_{i=1}^N$ and iid test ...
1answer
115 views

### VC dimension and two definitions, which of them is correct?

Are these two definition is contrast to each others? option (4) says cannot shatter "one of..." says one... but other slides as follows tells us "no set of k+1 points..." which ...
1answer
38 views

### VC Dimension Doubt and one facts

I see following slides in a video on YouTube: I ran into a doubt. VC dimension of a line that is parallel to one of axis (X or Y axis) is equal to $2$. can I tell $(-\infty, x]$ is equal to case $H1$ ...
1answer
102 views

### VC dimension of a greedy decision tree vs a optimal decision tree

Take the 𝐶𝐴𝑅𝑇 binary splitting tree, for example, the practical implementation is a greedy splitting procedure. With some fixed depth ℎ, one can fit an optimal decision tree (by trying every ...
0answers
24 views

### Are maximum a posteriori estimation, regularized estimation, and structural risk minimization all completely equivalent?

In many classical cases, MAP estimation and, e.g., regularized least squares estimation are equivalent. So my guess would be that one could - in theory - always construct a likelihood / cost function ...
1answer
19 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?
1answer
68 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?
0answers
47 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 ...
1answer
47 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 ...
0answers
41 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 ...
1answer
109 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' ...
0answers
87 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 ...
0answers
15 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 ...
1answer
161 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 ...
1answer
30 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 ...
0answers
49 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 ...
1answer
1k 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 ...
1answer
246 views

0answers
1k 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 ...
1answer
86 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 ...
1answer
1k 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 ...
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, ...
0answers
1k 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 ...
0answers
50 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 ...
1answer
662 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 ...
0answers
81 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 ...
0answers
698 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 ...
1answer
4k 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 ...
1answer
310 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 ...
0answers
103 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 ...
0answers
4k 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 ...
0answers
392 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$ ...
0answers
113 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 ...
0answers
270 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 ...
2answers
11k 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 ...
1answer
151 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 ...
0answers
463 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 ...
0answers
107 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 ?
3answers
670 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 ...
0answers
620 views