The VCdim of a finite hypothesis class $H$ cannot be larger than $\log_2(H)$. But was is an example of a hypothesis class that has VCdim exactly equal to that quantity? For a reference, this is a question from the textbook Understanding Machine Learning by Shalev-Shwartz and Ben-David.

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 Countably Infinite class is always finite? (I feel that its size will be "smaller" than the size of a power set of an arbitrarily large set) Any help on this is appreciated.

A circle (r,c) is defined by its center “c” and its radius r. You are given the following set of classifiers: for 2d inputs points x, f(r,c,x) = 1 if x is inside the circle (r,c), and -1 otherwise. What is the VC dimension of this hypothesis class?

Consider a data setup of one-dimensional data ∈ R1, where the hypothesis space H is parametrized by {p,q} where x is classified as 1 iff p < x < q. What will be the VC(H)? Here's my approach: Since 1D data so we can represent the hypothesis space in a number line. We will consider 2 points and try all possibilities and see if they can all be classified correctly. Assume data points are d1 and d2. case1: p < …

I am learning the VC dimension. How do I calculate the H in the VC dimension? Let the domain set be $X = R2$, the label set be $Y = {0, 1}$ and the hypothesis class be $H = {h(a,b,c,d): a, b, c, d \in R}$, where for $(x, y) \in R2$ we have: $h(a,b,c,d)(x, y) =$ \begin{cases} 1 & \text{if $x \ge a$ and $y \ge b$} \\ & \text{or $x \ge c$ and $y \ge d$} \\ 0 …

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 be that the rank of VC-dimension should be 3 or n + 1 but I'm not sure. By the definition of VC-dimension, the max rank will be equal to the size of the field +1. that means n+1. I'm not sure why because the functions …

I'm still unsure as to how to get the VC-dimension of some certain hypothesis classes. So for example we have $\mathcal{X} = \mathbb{R}$ and $\mathcal{Y} = \{ 0,1 \}$ and the hypothesis class $\mathcal{H} = \{ h(x) \}$ where $h(x) = 1$ if $|x| \in S$ where $S = [1,2) \cup [3,4) \cup [5,6) \cup ...$. My intuition is that I pick any set of points $\{x\} \in \mathcal{X}$. And then an adversary labels all such points arbitrarily. Then I …

I was wondering in the process of counting the VC dimensions: Show that there is a set of n points that can be shattered. No set of n+1 points is shattered. Does this mean that I don't necessarily need to ensure that all sets of n points in the space can be shattered to show VC dimension as n? And it is enough to show that there exists a set of n points that can be shattered?

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 mapping from the real numbers to 0 or 1). And with $\mathcal{X} = \mathbb{R}$, is it true that the VC dimension is $\infty$. My intuition to this is that $H$ is a rich set of classifiers that contains any sort of mapping between real numbers and 0 …

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 points $(x_1, \ldots x_n)$ if, for all assignments of labels to those points, there exists some $\theta$ such that the model $f$ makes no errors when evaluating that set of data points. I am trying to understand the second example. Suppose I have a model $f$ with …

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 formally. Any clue for direction?

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 parallel to the coordinate axes) and $H_2$ (lines). We define a model $H_3$ such that every hypothesis is a combination of one hypothesis from $H_1$ and one from $H_2$. Prove or disprove that the model $H_3$ has a bigger VC dimension (Vapnik–Chervonenkis dimension) then the VC dimensions …

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 * (\text{number of weigts})$. What is the VC dimension for Gaussian Process Regression ? My domain is $X = \mathbb{R}^{25}$, meaning I have 25 features, and I want to determine the number of samples $N$ I must have to archive good generalization.

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 it is possible that there is some $i<n$ such that for every subset C of size i the subset C is not shattered. Is his claim true? I thought that we can take some subset of size $i,\forall i\in [n]$of the set C* which satisfies …

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 given as, If you can find a set of $n$ points, so that it can be shattered by the classifier (i.e. classify all possible $2^n$ labeling correctly) and you cannot find any set of $n+1$ points that can be shattered (i.e. for any set of $n+1$ points …

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. Somehow, the VC dimension for this linear separator is 3. I just cannot understand how. According to what I understand, VC dimension is the size of the largest finite subset of X which can be shattered by h. So if there exists a subset of …

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{cases} 0, x \leq 0 \\ 1, x > 0 \end{cases} $$ The hidden layer may contain $k$ units and I would like to calculate the VC dimension of this feed-forward neural network. The VC dimension is defined as a cardinality of the maximal set, that can be …

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}$$ When I simulate this hypothesis set up to $n= 10$, the maximum number of dichotomies I obtain is exactly $\sum_{k=0}^{3}\,{n\choose k}$. Is it by coincidence or is there a way to prove this?

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, etc. All proofs first derive a lower bound, and then show an upper bound. However, why not just derive the upper bound since the definition of VC dimension only cares about the "largest" set that can be shattered by hypothesis set $\mathcal{H}$? Since all examples ends up with a lower bound matching the …

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?