Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
28 views

“Concept Class” in Machine Learning

I was reading this famous paper and encountered the term "concept class". There's one example given: union of balls in $n$-dimensional space. But one single example is not clear enough. Can anyone ...
0
votes
0answers
79 views

What will be the VC dimension of a axis aligned cuboid? Can someone explain with an example?

I am new to machine learning and while going through Vc dimensions I came across that the Vc dimension of a rectangle is 4. Is the Vc dimension of a cuboid 6?
0
votes
0answers
16 views

upper bound of VC dimension in terms of Rademacher complexity or stability coefficient

For a function class $\mathcal{H}$, suppose its VC dimension is $d_\mathcal{H}$, its Rademacher complexity is $R_\mathcal{H}$, and its stability coefficient is $\beta_\mathcal{H}$. From Corollaries ...
1
vote
1answer
183 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
114 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
249 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.
-1
votes
1answer
126 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, ...
1
vote
0answers
331 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 ...
0
votes
0answers
103 views

VC dimension of finite unions of one-sided intervals

What is the VC dimension of $k$ finite unions of one-sided intervals: If we take 3 one-sided intervals like $(-\infty, a_1] $, $(-\infty, a_2] $ and $(-\infty, a_3] $, I think union of these ...
2
votes
1answer
52 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 ...
0
votes
0answers
115 views

VC dimension shattering question

I am preparing for an exam and I really can't figure out this question: Suppose you are given Χ, which is the set of binary strings of length 5. Let C be the set of classifiers over Χ where each ...
1
vote
1answer
379 views

VC dimension of decision tree

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 ...
0
votes
0answers
45 views

Machine learning - shatter the point and VC dimension

I failed to understand this question , I'm not strong with all the upper-bound topic I would really appreciate a solution with good explanation, heres the question: Class C includes functions of the ...
1
vote
0answers
510 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
580 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 ...
0
votes
0answers
43 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 ...
6
votes
0answers
210 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
58 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 ...
1
vote
0answers
241 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 ...
10
votes
1answer
2k 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
160 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
82 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
2k 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
295 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
88 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
156 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
6k 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
102 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
409 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
75 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
581 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 ...
3
votes
0answers
307 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}(\...
4
votes
2answers
1k 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}}...
9
votes
3answers
2k 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 ...
12
votes
1answer
1k 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
504 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
654 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
149 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 ...
11
votes
2answers
2k 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
3k 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. ...
9
votes
3answers
5k 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 ...
2
votes
1answer
492 views

How to compute minimum required VC dimension for a classifer to classify a specific data

Suppose we're given an N dimensional data to classify. To cope with this task we may choose a classifier that suits our desires more. However obviously not every classifier is capable of classifying ...
7
votes
1answer
1k views

Do ensemble techniques increase VC-dimension?

Techniques like Adaboost use a ensemble of weak classifiers to obtain a "better" classifier. Does(Can) the final classifier have a greater VC-dimension than the weak classifier? An intuitive ...
3
votes
3answers
581 views

About Akaike's criterion and VC-dimension of linear regressors

Akaike's model selection criterion is usually justified on the base that the empirical risk of a ML estimator is a biased estimator of the true risk of the best estimator in the parametric family, say ...
8
votes
1answer
2k views

Calculating VC-dimension of a neural network

If I have some fixed non-recurrent (DAG) topology (fixed set of nodes and edges, but the learning algorithm can vary the weight on the edges) of sigmoid neurons with $n$ input neurons which can only ...
16
votes
2answers
699 views

What are alternatives to VC-dimension for measuring the complexity of neural networks?

I have come across some basic ways to measure the complexity of neural networks: Naive and informal: count the number of neurons, hidden neurons, layers, or hidden layers VC-dimension (Eduardo D. ...
6
votes
3answers
4k views

VC dimension of SVM with polynomial kernel in $\mathbb{R^{2}}$

What is the VC dimension of SVM with the polynomial kernel $k(x,x')=(1+<x,x'>_{\mathbb{R^{2}}})^{2}$ for binary classification in $\mathbb{R^{2}}$? It would be equal or more than v iff ...