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
0
votes
1
answer
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
0
answers
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 ...
- 151
0
votes
0
answers
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?
0
votes
0
answers
23
views
error bound for semi-online Learning problem
I want to solve the following problem:
Consider the noise-free classification setup. Let $\mathcal{F}$ denote an infinite class of (binary) classifiers with finite
VC dimension $d$. Let $f* ∈ \...
- 1
0
votes
0
answers
19
views
Example for Tightness of Sauer-Shelah-Vapnik-Chervonenkis Lemma
I was given the task to find an example of a family of events such that the SSVC-Lemma is tight.
Where the Lemma states:
Assume that the Vapnik-Chervonenkis Dimension (VC-dim) of the family of events ...
- 1
0
votes
0
answers
30
views
Could we code a program to compute VC-dimension of any given hypothesis class?
I've been studying machine learning theory and the fundamental theorem of the statistical learning for a while, but I still didn't found a general algorithm that could compute the VC dimension of any ...
- 1
0
votes
0
answers
21
views
Vapnik-Chervonenkis dimension of hypergraph, given bound on number of hyperedges
in studying now about Vapnik-Chervonenkis dimension, and there is one question that I not able to solve.
Let $\textrm{(X , R)}$ be a range space so that any hypergraph $\textrm{(V, F)}$ in it ...
- 1
1
vote
0
answers
23
views
Is infinite VC-dim equivalent to universal approximator?
If $m$ is the VC-dim then it means there is no configuration of $m+1$ datapoints we can shatter. But there could be configurations of $m$ datapoints we cannot shatter. Hence my confusion and my ...
- 213
2
votes
1
answer
747
views
What is the VC dimension for logistic regresion?
I know that the VC dimension for a perceptron is 3, but what is it for a logistic regression model?
- 71
2
votes
0
answers
81
views
Hypothesis class with n elements that shatters a set C of n/2 points
I started learning Advanced Machine Learning and came across a problem that stuck. I would be grateful if you could help me with some ideas or solutions:
What is the maximum value of the natural even ...
- 21
1
vote
0
answers
67
views
The VC dimension of a mixture of normal laws
In his Statistical Learning Theory (1998), Vapnik presents the following mixture of two normal laws (p.236), in which the parameters $a$ and $\sigma$ are unknown:
$$p(z;a;\sigma)=\frac{1}{2}\mathcal{N}...
- 339
2
votes
0
answers
99
views
Is the VC dimension of a MLP regressor a valid upper bound on how many points it can exactly fit?
I want to calculate an upper bound on how many training points an MLP regressor can fit with ~0 error. I don't care about the test error, I want to overfit as much as possible the (few) training ...
- 21
0
votes
1
answer
35
views
Characterizations of uniformly learnable function classes in the distribution-specific setting
Let $X$ be some input domain (a measurable space). Then let $D$ be some class of probability distributions on $X\times\{0,1\}$. We will call such distributions learning tasks. We say that $D$ is ...
- 419
1
vote
0
answers
70
views
Sample complexity and VC dimension
I'm studying VC-dimension and sample complexity, and I'd like to understand whether I understand it correctly via the following example.
Let $X = \mathbb{R}$ and $\mathcal{H} = \{ h_{\theta}(x)=\text{...
- 167
4
votes
1
answer
208
views
Distributional Assumptions in Machine Learning
In more classical statistical methods like linear regression, we can quantify how well our model generalizes under certain strong assumptions. For example, we know that $\hat Y = X \hat \beta \sim \...
- 298
1
vote
0
answers
83
views
VC-Dimensions and PAC-learning of some specific certain class of classifiers
I'm learning VC-dimensions and PAC-learnability right now and I need some help. I'm answering a practice exercise question that I'm prepping for an exam. So suppose we have some domain $\mathcal{X} = \...
- 11
1
vote
0
answers
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
0
answers
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
1
answer
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
3
votes
1
answer
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 ...
- 83
1
vote
1
answer
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
2
votes
1
answer
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
1
answer
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
0
votes
1
answer
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
3
votes
0
answers
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
1
answer
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 ...
user294054
3
votes
1
answer
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
0
answers
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
0
answers
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
2
votes
1
answer
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
0
votes
1
answer
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
0
answers
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
2
votes
0
answers
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
4
votes
1
answer
396
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(...
- 4,106
4
votes
2
answers
7k
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 ...
- 81
2
votes
0
answers
650
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 ...
- 214
0
votes
1
answer
1k
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.
- 125
0
votes
3
answers
1k
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, ...
- 125
2
votes
0
answers
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
2
votes
1
answer
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
1
answer
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 ...
- 11
2
votes
1
answer
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
2
votes
0
answers
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
0
answers
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 ...
- 460
9
votes
1
answer
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
0
answers
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
2
votes
0
answers
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 ...
- 129
12
votes
1
answer
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 ...
- 785
2
votes
1
answer
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
0
answers
154
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 ...
- 53