# 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
32 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
123 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 ...
1 vote
81 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$. ...
61 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
31 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 \begin{equation} \mathcal{F}_2 = \{\...
1 vote
99 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 ...
116 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?
39 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 ...
1 vote
160 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 ...
1 vote
300 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
95 views

1 vote
153 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
220 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 ...
424 views

1 vote
423 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 ...
7k views

### VC Dimension of Origin-Centered Circle

Is the VC dimension of an origin-centered circle 1 or 2? It seems to me that the VC dimension of an origin centered circle should be 1, because for two points with distances from the origin r1 <= ...
620 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 ...
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 ...
22k views

### Why is deep learning hyped despite bad VC dimension?

The Vapnik–Chervonenkis (VC)-dimension formula for neural networks ranges from $O(E)$ to $O(E^2)$, with $O(E^2V^2)$ in the worst case, where $E$ is the number of edges and $V$ is the number of nodes. ...
83 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)$ ...
344 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 ...
3k views

### VC dimension of linear separator in 3D

I am confused about the Vapnik-Chervonenkis dimension of a linear separator in 3 dimensions. In three dimensions, a linear separator would be a plane, and the classification model would be "...
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: ...