# What is the VC dimension of the hypothesis class $H=\left\{f_{\theta_{1}, \theta_{2}}: R^{2} \rightarrow\{0,1\} \mid 0<\theta_{1}<\theta_{2}\right\}$?

I would like to know what is the VC dimension of the following hypothesis class.

$$H=\left\{f_{\theta_{1}, \theta_{2}}: R^{2} \rightarrow\{0,1\} \mid 0<\theta_{1}<\theta_{2}\right\}$$

where $$f_{\theta_{1}, \theta_{2}}(x, y)=1$$ if $$\theta_{1} x \leqslant y \leqslant \theta_{2} x,$$ else $$f_{\theta_{1}, \theta_{2}}(x, y)=0$$.

I am not really sure how to prove it. What do you think?

The VC-dimension of your hypothesis class $$\mathcal H$$ is 2. To see this, we begin by showing that $$\mathcal H$$ shatters any 2-element set $$\{(a_1 a_2), (b_1, b_2)\}$$ of real numbers where all components of the pairs are positive:

1. $$\emptyset$$ is accounted for by $$f_{c, c + \varepsilon}$$ for any real $$c$$ such that $$ca_1 \neq a_a$$ and $$cb_1 \neq b_2$$ and some sufficiently small $$\varepsilon > 0$$.
2. $$\{a\}$$ (and similarly $$\{b\}$$) is accounted for by $$f_{c, c + \varepsilon}$$ where $$c = a_2/a_1$$ and $$\varepsilon > 0$$ is sufficiently small.
3. $$\{a, b\}$$ is accounted for by $$f_{\varepsilon, c}$$ for some sufficiently small $$\varepsilon > 0$$ and some sufficiently large $$c$$ (specifically, one can set $$\varepsilon = \min \{a_2 / a_1, b_2 / b_1\} / 2$$ and $$c = 1 + \max \{a_2 / a_1, b_2 / b_1\}$$)

This yields $$\operatorname{VC}(\mathcal H) \geq 2$$.

Now consider some arbitrary set $$X = \{(a_1, a_2), (b_1, b_2), (c_1, c_2)\}$$ of pairwise distinct points in $$\mathbb R^2$$. If the points in $$X \cup \{(0, 0)\}$$ are not in general position then $$\mathcal H$$ cannot shatter $$X$$ as it means that there are at least two points $$s, t \in X$$ which fall onto a line with the origin and as every classifier in $$\mathcal H$$ has linear decision boundaries it must always label $$s$$ and $$t$$ the same way, preventing it from shattering any set containing these points.

So let us assume that $$X \cup \{(0, 0)\}$$ is a set of points in general position and shattered by $$\mathcal H$$. As all functions $$f_{\theta, \varphi} \in \mathcal H$$ represent areas between two lines with positive slopes (since we require $$0 < \theta < \varphi$$) we can infer that all the lines connecting points in $$X$$ with the origin also must have positive slopes (note that $$X$$ is not in general position when the origin is an element of $$X$$). Hence we can order the points in $$X$$ ascendingly by these slopes, i.e. we may write $$a_2 / a_1 < b_2/ b_1 < c_2 / c_1$$ and since this requires all $$x$$-coordinates of the points in $$X$$ to be nonzero, we can simplify the expression for the preimage of $$1$$ of any $$f_{\theta, \varphi} \in \mathcal H$$ restricted to $$X$$ to $$f_{\theta, \varphi}|_X(x, y)^{-1} = \{(x, y) \in X \mid \theta \leq y / x \leq \varphi\}$$ by dividing by $$x$$. Now consider the subset $$X' = \{a, c\}$$ of $$X$$ and suppose $$f_{\theta, \varphi} \in \mathcal H$$ accounts for $$X'$$, i.e. $$f_{\theta, \varphi}|_X^{-1}(1) = X'$$. But then we must have $$\theta \leq a_2 / a_1 < b_2 / b_ 1 < c_2 / c_1 \leq \varphi$$ which yields $$f_{\theta, \varphi}|_X(b) = 1$$ and thus $$f_{\theta, \varphi}$$ does not account for $$X'$$ which is a contradiction. Therefore $$\mathcal H$$ does not shatter $$X$$ and and thus no set of size $$\geq 3$$.

It follows that $$2 \leq \operatorname{VC}(\mathcal H) < 3$$ and thereby $$\operatorname{VC}(\mathcal H) = 2.$$

• Thanks for the amazing explanation. Is it easy to make an example with 3 samples that give an intuition of how you proved that it the VC(H) cannot be more than 3? – hinduml Jun 15 '20 at 10:39
• For $\operatorname{VC}(\mathcal H) < 3$ we need to show that no such sample exists, so considering examples is not enough. However, the idea here is a geometric one: Note that the set where some $f \in \mathcal H$ is 1 is the area between two lines with positive slopes, so if $f$ is 1 on the two "outer" samples then it must also be 1 on the "middle" sample so it cannot shatter any such set. I wrote a formal proof for this (which is a bit more involved and technical) but the idea is rather simple if you draw up a picture :) – Watercrystal Jun 15 '20 at 11:20
• Thanks a lot for the explanation, its really helpful. – hinduml Jun 15 '20 at 11:57
• Glad I could help out :) – Watercrystal Jun 15 '20 at 12:02
• The two linear functions that bound the area are $\theta x$ and $\varphi x$ with $0 < \theta < \varphi$ required by your definition. If the slope is $> 0$, then it must be positive. The value of $x$ does not play a role for that. However, a linear function $ax$ with a positive slope (i.e. $a > 0$) attains negative values when $x$ is negative. – Watercrystal Jun 15 '20 at 15:30