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
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 ...
1
vote
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 ...
0
votes
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 ...
1
vote
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 ...
1
vote
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 ...
0
votes
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 ...
2
votes
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 ...
1
vote
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$ ...
0
votes
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 ...
0
votes
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 ...
0
votes
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?
0
votes
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?
2
votes
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 ...
1
vote
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 ...
0
votes
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 ...
2
votes
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' ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
0
votes
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 ...
1
vote
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 ...
0
votes
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 ...
4
votes
1answer
246 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
2answers
4k 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
284 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
809 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
608 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
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 ...
2
votes
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 ...
1
vote
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 ...
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
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 ...
1
vote
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 ...
7
votes
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 ...
1
vote
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 ...
2
votes
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 ...
12
votes
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 ...
2
votes
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 ...
1
vote
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 ...
2
votes
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 ...
1
vote
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$ ...
0
votes
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 ...
6
votes
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 ...
17
votes
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 ...
3
votes
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 ...
6
votes
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 ...
1
vote
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 ?
4
votes
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 ...
2
votes
0answers
620 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}}...