Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

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

45 questions
Filter by
Sorted by
Tagged with
1 vote
24 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 = \{\...
• 111
1 vote
72 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 ...
75 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?
34 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 ...
• 29
70 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 ...
• 29
1 vote
64 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 ...
• 21
1 vote
102 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 ...
• 11
1 vote
80 views

1 vote
95 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 ...
• 293
1 vote
117 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 ...
• 293
242 views

1 vote
397 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 ...
• 142
6k 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 <= ...
• 133
563 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 ...
• 133
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 ...
• 1,369
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. ...
• 1,369
75 views

• 677
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)$ ...
• 317
341 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{...
• 141
264 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 ...
• 677
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 "...
733 views

### Vapnik-Chervonenkis Dimension: why cannot four points on a line be shattered by rectangles?

So I'm reading "Introduction to Machine Learning" 2nd edition, by Bishop, et. all. On page 27 they discuss the Vapnik-Chervonenkis Dimension which is, "The maximum number of points that can be ...
• 1,105
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: ...