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

75 questions
Filter by
Sorted by
Tagged with
66 views

### 2d rectangle vc-dimension shattering 5 points

I have seen in many places that the vc-dimension of H, an hypostases class which consists of rectangles parallel to the axis is 4. yet when constructing this 2D constellation of points i can't ...
1 vote
26 views

### Confirming my interpretation on a comment by Vladimir Vapnik

In the preface to the first edition of his book The Nature of Statistical Learning Theory, Vapnik makes the following comment: Between 1960 and 1980 a revolution in statistics occurred: Fisher's ...
7 views

### VC dimension of an SVM with Radial basis function as kernel [duplicate]

How is the VC dimension of an SVM with Radial basis function as kernel bounded although it is projected to an infinite dimension?
23 views

• 167
208 views

• 11
1 vote
974 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 ...
• 113
1 vote
159 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 ...
• 514
1 vote
263 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 ...
• 111
261 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 ...
1 vote
136 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$ ...
• 13
297 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 ...
• 161
1 vote
25 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?
• 253
329 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?
• 253
183 views

### Relationship between finite VC dimension and Lipschitzness [closed]

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 ...
• 253
1 vote
58 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 ...
171 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' ...
• 83
1 vote
333 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
21 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 ...
• 287
371 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 ...
• 507
94 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 ...
• 313
1 vote
72 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 ...
• 11
3k 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 ...
• 141
396 views

• 125
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 ...
• 121
215 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 ...
• 151
1 vote
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 ...
2k 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, ...
• 323
2k 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 ...
• 621
1 vote
53 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 ...
1k 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 ...
• 826
1 vote
100 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 ...
• 21
798 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 ...
5k 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 ...
426 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 ...
• 459
1 vote