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

39 questions
Filter by
Sorted by
Tagged with
41 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 ...
64 views

76 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 ...
63 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 ...
139 views

368 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 ...
5k 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 <= ...
504 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 ...
20k 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. ...
69 views

977 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)$ ...
335 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{...
261 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 ...
2k 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: ...