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?


1 Answer 1


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

  • $\begingroup$ 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? $\endgroup$
    – hinduml
    Jun 15, 2020 at 10:39
  • $\begingroup$ 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 :) $\endgroup$ Jun 15, 2020 at 11:20
  • $\begingroup$ Thanks a lot for the explanation, its really helpful. $\endgroup$
    – hinduml
    Jun 15, 2020 at 11:57
  • $\begingroup$ Glad I could help out :) $\endgroup$ Jun 15, 2020 at 12:02
  • $\begingroup$ 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. $\endgroup$ Jun 15, 2020 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.