Questions tagged [vc-theory]
The vc-theory tag has no usage guidance.
30
questions
28
votes
3
answers
37k
views
What is the exact definition of VC dimension?
I'm studying machine learning from Andrew Ng Stanford lectures and just came across the theory of VC dimensions. According to the lectures and what I understood, the definition of VC dimension can be ...
- 383
16
votes
2
answers
37k
views
How to calculate VC-dimension?
Im studying machine learning, and I would like to know how to calculate VC-dimension.
For example:
$h(x)=\begin{cases} 1 &\mbox{if } a\leq x \leq b \\
0 & \mbox{else } \end{cases} $, with ...
- 173
10
votes
1
answer
11k
views
With regards to VC-dimension, why can you shatter 3 points with circles but not 4 points?
When using VC-dimensions to estimate the capability of a binary classifier, you can find 3 points in R2 that can be shattered, e.g.:
But you can not shatter any 4 points with a circle.
This is ...
- 22.1k
4
votes
1
answer
3k
views
VC dimension of hypothesis space of finite union of intervals
I have the following concept:
$$C = \left\{\bigcup_{i=1}^{k}(a_i, b_i): a_i, b_i \in {\Bbb R}, a_i < b_i, i=1,2,..,k\right\}
$$
and was wondering how to determine the VC dimension of C?
2
votes
1
answer
870
views
Why is a lower bound necessary in proofs of VC-dimensions for various examples of hypotheses?
In the book "Foundations of Machine Learning" there are examples of proving the VC dimensions for various hypotheses, e.g., for axis-aligned rectangles, convex polygons, sine functions, hyperplanes, ...
- 161
2
votes
2
answers
5k
views
Why the VC dimension to this linear hypothesis equal to 3?
I am trying hard to understand this. Here is the scenario:
X = R^2
H = { h(x) = x + 10 }
I need to calculate the VC dimension for the above linear separator. ...
- 611
2
votes
1
answer
88
views
A question on realizable sample complexity
I came across the following exercise, and I just can't seem to crack it:
Let $l$ be some loss function such that $l \leq 1$. Let $H$ be some hypothesis class, and let $A$ be a learning algorithm. ...
2
votes
0
answers
180
views
calculate the VC-dimension [closed]
I have a question about VC-dimension. I have this claim and I need to find out what its VC-dimension is
$ H\subseteq\{0,1\}^n $ collection of Boolean functions over n
In my opinion the answer should ...
- 121
2
votes
0
answers
124
views
VC Dimensions in Machine Learning
Hello I'm learning about VC dimensions in machine learning. The class of classifiers $H$ where $h \in H$ if $h \in \mathbb{R} \rightarrow \{0,1\}$ is what I believe is simply binary classifiers (with ...
- 21
2
votes
0
answers
237
views
Find VC dimension
I'm studying theoretical machine learning at university, and I have this problem in textbook, that I have no Idea how to start.
In space $X=R^2$ are given two models $H_1$ (rectangle with sides ...
- 29
2
votes
0
answers
157
views
Intuition behind Occam's Learner Algorithm using VC-Dimension
So I'm learning about Occam's Learning algorithm and PAC-Learning where for a given hypothesis space $H$, if we want to have a model/hypothesis $h$ that has an True error of $error_D \leq \epsilon$, ...
- 101
2
votes
0
answers
594
views
How to determine the VC Dimension of axis-aligned, origin-centered ellipses?
I've been trying to determine the VC dimension of ellipses which are origin centered and axis aligned. My first approach was to find some equivalence to a threshold classifier function family of the ...
- 21
1
vote
1
answer
258
views
VC-dimension of the infinite set of convex bodies?
I try to find and prove the VC-dimension of the infinite set of (uni-directional) convex bodies. From intuition, it's clear to me that it goes to infinity, but I don't know the correct way to prove it ...
- 113
1
vote
1
answer
37
views
Disproving or proving claim that if VCdim is "n" then it is possible that a set of smaller size is not shattered
Today in the lecture the lecturer said something I found peculiar, and I felt very inconvenient when I heard it:
He claimed, that if the maximal VCdim of some hypothesis class is $n\in\mathbb N$, then ...
- 11
1
vote
1
answer
511
views
VC dimension of half spaces over the real line
I'm studying VC dimension and I'm having a little difficulty understanding it. I read lots of explanations, but when I come across this simple exercise I did not get a good intuition. The problem is ...
- 113
1
vote
0
answers
47
views
Occam's factor and the VC dimension
I was watching this lecture by Prof. Dr. Philipp Hennig (Probabilistic ML) and when he reached this formula which is the type two maximum log likelihood I had the following question:
The Occam's ...
1
vote
0
answers
168
views
1
vote
1
answer
428
views
Calculation of VC dimension of simple neural network
Suppose I have a perceptron with one-hidden layer, with the input - one real number $x \in \mathbb{R}$, and the activation function of the output layers - threshold functions:
$$
\theta(x) =
\begin{...
1
vote
1
answer
218
views
Growth function of a 6-dimensional linear classifier
In our course, we are dealing with a d-dimensional classification problem
($\chi = \mathbb{R}^{d}$ as our input space, and $y = \{-1,+1\}$). Our hypothesis class $H$ consists of all hypotheses of the ...
- 13
0
votes
1
answer
43
views
VC-dimension proof for a family of classifiers
I've been working on determining the VC-dimension of a specific family of classifiers, and I would like to get some feedback on the proof I've come up with. The family of classifiers is defined as ...
- 1
0
votes
1
answer
160
views
VC dimension for Gaussian Process Regression [closed]
In neural networks, the VC dimension $d_{VC}$ equals approximately the number of parameters (weights) of the network. The rule of thump for good generalization is then $N \geq 10 d_{VC} \approx 10 * (\...
- 111
0
votes
1
answer
111
views
Vapnik Chervonenkis dimension of a classifier from the Wikipedia page
The Vapnik Chervonenkis dimension is defined by the wikipedia page here for a classification model as:
A classification model $f$ with some parameter vector $\theta$ is said to shatter a set of data ...
- 119
0
votes
0
answers
38
views
Determining VCdim for union of subspaces $H_i$ - short question
Consider $\mathcal{H} = \mathcal{H}_1 \cup \mathcal{H}_2 \cup \mathcal{H}_3$, where:
$\mathcal{H_1} = \{h_{a} : \mathbb{R} \rightarrow \{0,1\} \ | \ h_{a}(x) = 1_{[x \geq a]}(x) = 1_{[a, +\infty)}(x), ...
0
votes
0
answers
8
views
Learning Theory - PAC learning, hypothesis class containing the true classifier
For a given hypothesis space $H$, assuming $f\in H$ where $f$ is the true classifier, you can choose a group $S~D$ where $D$ is a distribution, with a large enough sample complexity, such that the ...
- 111
0
votes
0
answers
22
views
VC dimension of a class H that assigns 1 to at most k points or that assigns 0 to at most k points
Let $X$ be a finite domain and $k$ a number such that $k\le|X|$. Consider the hypothesis class
$$
H:=\{h:|\{x\in X:h(x)=1\}|\le k\text{ or }|\{x\in X:h(x)=0\}|\le k\}.
$$
Find the VC dimension of $H$.
0
votes
1
answer
27
views
the VCdim of class of double parameter threshold functions
Let $H$ be a family of classifiers such that $H=\{ h_{a,b} : a,b\in \mathbb{R}\}$ where $h_{a,b}(x,y)=1$ iff $x\geq a$ and $y\geq b$.
I've proved that for $C=\{m=(x,y)\}$, $H$ shatters $C$.
However, ...
- 111
0
votes
1
answer
421
views
VC-dimension of the class of hypotheses that assign label $1$ to exactly $k$ points of some finite domain $\mathcal{X}$
Let $\mathcal{X}$ be a finite domain and $k$ a number such that $k\leq|\mathcal{X}|$. Consider the hypothesis class
$\mathcal{H}:=\big\{h:|\{\mathbf{x}\in\mathcal{X}:h(\mathbf{x})=1\}|=k\bigr\}$;
that ...
- 3
0
votes
1
answer
225
views
VC- dimension calculate
Let X = {1, 2, 3, ... , 100}. Let H be the class of all subsets of X that contain at least 20 and at most 80 elements. What is the VC-dimension of H?
0
votes
0
answers
76
views
VC Dimension of a Countably Infinite Class
I know that there are many examples of classes where the VC Dimension is finite/infinite even though the size of the class is Uncountably Infinite.
However, I could not argue if the VC Dimension of a ...
0
votes
0
answers
105
views
Growth function of the class of all circles in the plane
I know that the VC dimension for this problem is 3. My concern is about the growth function. The following bound is obtained using the VC dimension:
$$m_{\mathcal{H}}(n)\le \sum_{k=0}^3\,{n\choose k}$$...
- 1