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.

15 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4 votes
0 answers

VC dimension and binary operations

There are two classes of binary functions, $F_1,F_2$. The VC-dimension of $F_i$ is $d_i$. Is there any simple formula for the VC-dimension of the following classes? $F_\lor := \{ f_1(x) \lor f_2(x) |...
Erel Segal-Halevi's user avatar
3 votes
0 answers

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 ...
seteropere's user avatar
2 votes
0 answers

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 ...
Dmitry's user avatar
  • 315
1 vote
0 answers

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 ...
JustBlaze's user avatar
1 vote
0 answers

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 = \{\...
Vassily's user avatar
  • 111
1 vote
0 answers

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 ...
somefellow's user avatar
1 vote
0 answers

VC Dimension of the class of $k$-dimensional cross-polytope (1-norm ($l_1$) ball)

What is the VC Dimension of the class of $k$-dimensional cross-polytope (1-norm ($l_1$) balls)? A $k$-dimensional $l_1$ ball with radius $r\in \mathcal R$ and center $\mathbb v\in \mathcal R^k$ is $\{\...
NineDarkOldAncestor's user avatar
1 vote
0 answers

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 ...
Gavin Gale's user avatar
1 vote
0 answers

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 ...
Ashley's user avatar
  • 11
1 vote
0 answers

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 ...
seteropere's user avatar
1 vote
0 answers

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?
user's user avatar
  • 131
0 votes
0 answers

Question about machine learning

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 ...
hah's user avatar
  • 29
0 votes
0 answers

VC dimension of a combination of two hypothesis classes

I have found this exercise and I cannot solve it: In $X=\mathbb R^2$, let's observe two models $H_1$ (rectangle with sides parallel to the coordinate axes) and $H_2$ (lines). We define a model $H_3$ ...
temp1231233232's user avatar
0 votes
0 answers

VC dimension of axis-aligned hyperplanes and their complements

This is a problem of VC that I've been trying to solve. Any help is appreciated. Let's assume hypothesis classes $H_{\mathit{init}}$ of initial segments over domain $X = \mathbb R$ and $H_{\mathit{...
brianoconner's user avatar
-1 votes
1 answer

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 ...
anonymus's user avatar