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

35 questions
Filter by
Sorted by
Tagged with
45 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 ...
24 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 ...
82 views

93 views

### Classes of circle rims

The input space is a unit circle, $\mathcal{X} = \mathbb{S}^1 \subset \mathbb{R}^2$. There is class $\mathcal{F}$ of arcs on $\mathbb{S}^1$, where a point is labeled 1 if it is on the arc, and 0 ...
59 views

### VC dimension of only the rim of a unit disk

Suppose we have an origin centered circle, ie $x^2 + y^2 =1$, so it's in $\mathbb{R}^2$ (2D). It will be classified as 1 if it lies only on this arc, and will be labeled 0 otherwise. What is the VC ...
85 views

### PAC learning vs. learning on uniform distribution

The class of function $\mathcal{F}$ is PAC-learnable if there exists an algorithm $A$ such that for any distribution $D$, any unknown function $f$ and any $\epsilon, \delta$ it holds that there exists ...
24 views

### Uniform Convergence and VC Theroy

I've started reading more about statistical learning theory, specifically this paper right here and I cannot understand the following part: It turns out the conditions required to render empirical ...
28 views

### Proof of uniform convergence if VC dimension is finite

In the book »Understanding Machine Learning: From Theory to Algorithms«, written by Ben-David and Shalev-Shwartz, there is a proof which I do not understand. The context is proving that if a ...
80 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 ...
64 views

### How can the VC-dimension of Turing machine be finite?

The VC-dimension of a hypothesis class $\mathcal{H}$ is defined to be the size of the maximal set $C$ such that $\mathcal{H}$ cannot shutter. This paper shows that the VC-dimension of the set of all ...
339 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 ...
218 views

### VC Dimension of A Set of Hypothesis

I am confused about what does a VC dimension of a set of hypothesis means. I have two hypothesis, say $H_1$ with VC dimension of $x$, and $H_2$ of VC dimension of $y$. Does this automatically mean ...
107 views

416 views

### The VC dimension when the samples are fixed

The VC dimension is usually used in the following way. There is a space of hypotheses. There is an unknown probability distribution. We sample some training-samples from this distribution. We find the ...
333 views

### VC dimension of monotone disjunctions of length k over n variables?

There are of course $n \choose k$ monotone disjunctions which bounds the VC dimension at $\log_2 {n \choose k}$. I'm wondering if this is bound at $k \log_2 n$? (Possibly follows from combinatorial ...
174 views

### Sample Complexity for Real-Valued PAC-Learnable Functions

Can anyone shed some light on how the VC Dimension affects the sample complexity bounds of infinite hypothesis classes with real-valued outputs in PAC learning, or how to calculate the sample ...
4k views

### VC Dimension Calculation for Intervals

As i See in ML Course a VC dimension calculation is very theoretical. What is the VC-dimension of intervals in R? The target function is specifieed by an interval, and labels any example positive ...
112 views

### If one hypothesis class is a proper subset of another, what is the relation of their VC dimensions?

Assume two hypotheses classes $H_A\subset H_B$ defined over the same instance space $\delta$. Assume also $VC(H_A)=d$, does this mean $VC(H_B)\geq d$ ? where $VC$ is the VC dimension. We can use the ...
629 views

### Why is the VC dimension different on intervals and half intervals?

As I read this lecture for being familiar with VC dimension we find on p. 8: VC(half intervals in $\mathbb{R}$ ) = 1 .... no subset of size 2 can be shattered VC(intervals in $\mathbb{R}$ )...
209 views

### VC dimension of 1-NN classifier for discrete metric space?

We know VC dimension of 1-NN classifier is infinite for continuous metric space. Is there any proof of VC dimension of 1-NN classifier if the metric space is discrete?
Let $C\subseteq 2^X$ be a concept class over $X$ and let $\bar{C}:=\{X\setminus c\mid c\in C\}$ be the complement. Show that $VCdim(C)=VCdim(\bar{C})$. Proof: Let $d:=VC_{dim}(C)$, then there exists ...