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

49 questions
Filter by
Sorted by
Tagged with
74 views

### How to calculate the growth function of a hypothesis class?

I have this hypothesis class: H = {ha : R → {0, 1} | a > 0, a ∈ R, where ha(x) = 1−a,a = { 1, x ∈ [−a, a] 0, x ̸ ∈ [−a, a] } I need to compute the growth function for m>= 0. So I think that this ...
1 vote
193 views

### Infinite VC Dim not PAC learnable

This is usually shown by an application of the Statistical No Free Lunch Theorem. But is this possible to show this by working simply with the definition of PAC learnability and the sample complexity ...
2k views

### VC dimension of the class of polynomial classifiers of degree $n$

I came across this statement on page 85 of the book "understanding machine learning: from theory to algorithms" The general idea is as follows: Consider a binary classiﬁcation problem with the ...
1 vote
136 views

### How can I understand the proof of the VC dimension of half-spaces in d-dimensions?

Statement : A half space is set of all points on one side of a linear separator, i.e., a set of the form $\{x \mid w^{T}x \ge t\}$. The VC-dimension of half spaces in $d$-dimensions is at least $d+1$. ...
64 views

### Multi-class sample complexity for PAC learning using "VC dimension"

VC dimension covers the binary classification case, i.e. when we want to get a predictor $X \to \{0, 1\}$. Using VC dimension, we can get the upper bound on the sample complexity for PAC-learning. In ...
1 vote
32 views

### pseudo dimension of the minimum of functions

Suppose a real-valued function class $\mathcal{F}$ with pseudo dimension less than $d$, I am wondering what is the pseudo dimension of the following function class \mathcal{F}_2 = \{\...
1 vote
104 views

### Hoeffding's inequality applicability for sample complexity

I am trying to determine some bounds for sample complexity. Suppose we have a bounded loss function $\ell$ and target function $f:\mathcal{X}\to\mathcal{Y}$. Hypothesis $h$ is learned, then the ...
1 vote
295 views

### Proof of Calculating VC-Dimensions

I still have some doubts for finding the VC-dimension. Suppose $\mathcal{H}$ has VC-dimension $n$. This is the process of how I think about it: (1) Show that there is a set of $n$ points that can be ...
124 views

### Uniform convergence of union of hypothesis

Let $H_{1}$ and $H_{2}$ are two hypothesis classes over some domain $X$1. If both $H_{1}$ and $H_{2}$ have the uniform convergence property, then do $H_{1}$ U $H_{2}$ have uniform convergence?
41 views

Hello everyone I am new to the site, I have a question that was in the test and did not understand the parts that are in the question. This question from a test I failed to pass, in a machine learning ...
80 views

### prove that 2 collection have the same VC-dimensions

I'm new here on the site, I'm a final year student in computer science. In a machine learning course, there was a question on a test that I could not understand. The question goes like this: Suppose ...
643 views

### Do I have the right definition of VC dimension?

I am having some trouble understanding the notion of the VC dimension. The definition I have is the following: The VC dimension of a set of hypothesis functions $H$ is the cardinality of the ...
1 vote
371 views

### VCdim of concentric circles

I have researched this topic in the last time, but no usefull results for me. So I'm here and I please you to help me with the following problem: What is $VCdim$($\mathcal{H}$), where $\mathcal{H}$ is ...
1 vote
97 views

1 vote
190 views

### VC dimension of set of functions

Let $\chi$ be an instance space and $H \in \{0, 1\}^\chi$ a class with finite VC-dimension. For each $x \in X$ we consider $z_x\colon H \rightarrow \{0, 1\}$ s.t. $z_x(h) = h(x), \forall h \in H$. Let ...
1 vote
275 views

### Understanding growth function of closed intervals in $\mathbb{R}$

I as studying VCdimensions and growth functions and found the following example on Wikipedia: The domain is the real like $\mathbb{R}$. The set H contains all the real intervals, i.e., all sets of ...
484 views

1 vote
430 views

### Geometric intuition behind VC-dimension

Recently, I learnt about VC-dimension and how its boundedness assures PAC learnability on uncountable range spaces (let's assume that hypothesis class is the same as the family of concepts we want to ...
1k views

### Is it a problem that "successful" machine learning algorithms have large VC dimension?

In my limited exposure, it appears that "successful" machine learning algorithms tend to have very large VC dimension. For example, XGBoost is famous for being used to win the Higgs Boson Kaggle ...
84 views

1k views

### VC dimension and optimal mistake bound

I have a question regarding optimal mistake bound for learning algorithm There is a famous fact that $VC(C) \leq Opt(C)$, where $C$ - set of learning concepts, VC(C) - VC dimension of C, $Opt(C)$ ...
345 views

### How to determine the size of training data using VC dimension?

I want to determine the size of training data ($m$) when I know the parameters $VC(H)$, $δ$ and $e$. As I know the $VC$ bound satisfy this equation:  \mathrm{error}_{\mathrm{true}}(h) \le \mathrm{...
265 views

### How to find the shattered set size for unknown hypothesis target

My aim is to prove a VC-dimension $d$ for different problems. All the problems I have do not have a target function (or concept) explicitly stated. This unlike most of the examples I came through. For ...
My goal is to solve the following problem, which I have described by its input and output: Input: A directed acyclic graph $G$ with $m$ nodes, $n$ sources, and $1$ sink ($m > n \geq 1$). Output: ...