0
$\begingroup$

I came across this statement on page 85 of the book "understanding machine learning: from theory to algorithms"

The general idea is as follows:

Consider a binary classification problem with the instance domain being $X = \mathbb R$.

For every $n \in \mathbb N$ let $H_n$ be the class of polynomial classifiers of degree $n$; namely, $H_n$ is the set of all classifiers of the form $h(x) = \operatorname{sign}(p(x))$, where $p\colon \mathbb R \to \mathbb R$ is a polynomial of degree $n$.

Prove that the VC dimension of $H_n$ is $n+1$.

$\endgroup$
7
  • 2
    $\begingroup$ What did you try and where did you get stuck? $\endgroup$
    – Juho
    Nov 26, 2019 at 11:28
  • $\begingroup$ I need to confirm that this claim is true. But I don't know how to prove it. $\endgroup$
    – Ben
    Nov 26, 2019 at 11:30
  • $\begingroup$ Could you be more specific? As a first step, do you understand the concepts involved? $\endgroup$
    – Juho
    Nov 26, 2019 at 11:55
  • $\begingroup$ Of course I do. I have provided very specific background. $\endgroup$
    – Ben
    Nov 26, 2019 at 12:12
  • $\begingroup$ We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. Also, we're a question-and-answer site, so we require you to articulate a specific question about your task. We're not looking for questions that are just the statement of an exercise-style task. Finally, I see that your task is quoted. Please attribute the source of all copied or quoted material. $\endgroup$
    – D.W.
    Nov 27, 2019 at 8:21

2 Answers 2

3
$\begingroup$

The idea is that a polynomial of degree $n$ has at most $n$ roots, and so can change signs at most $n$ times. Therefore no polynomial of degree $n$ can form an alternating pattern +-+-... or -+-+... of length $n+2$. This shows that the VC dimension is at most $n+1$.

On the other hand, for any set of $n+1$ pairs $(x_1,y_1),\ldots,(x_{n+1},y_{n+1})$, there is a polynomial of degree $n$ which interpolates them, given by the Lagrange interpolation formula. Using $y_i = \pm 1$, you can easily show that any set of $n+1$ points is shattered. Therefore the VC dimension is exactly $n+1$.

$\endgroup$
6
  • $\begingroup$ If you can prove it, then it must be true. $\endgroup$ Nov 4, 2020 at 20:01
  • $\begingroup$ If the proof works, then the result is true. You can try checking the special case $d=0$: see what the proof simplified to. $\endgroup$ Nov 5, 2020 at 7:37
  • $\begingroup$ The polynomials $1$ and $-1$ shatter any single point. $\endgroup$ Nov 5, 2020 at 9:02
  • 1
    $\begingroup$ The polynomials $1$ and $-1$ have degree $0$. $\endgroup$ Nov 5, 2020 at 10:25
  • $\begingroup$ You can check this using the definition of VC dimension. $\endgroup$ Nov 5, 2020 at 11:58
1
$\begingroup$

Here is a proof (not the only one). This proof appeals to the fact that our hypothesis class is a subset of a linear hypothesis class of degree $n+1$.

Let $\cal{P}_n$ denote the set of all d-degree polynomials $p_n: \mathbb{R} \to \mathbb{R}$.

Define the hypothesis class as follows: $$ \cal{H}_{P_n} := \{ f_n : f_d(x) = \textbf{sign}(p_n(x)), \quad x \in \mathbb{R},\quad p_n \in \cal{P}_n \} $$

That is, $\cal{H}_{P_n}$ is the set of all d-degree classifiers.

We want to show that $VC(\cal{H}_{P_n}) = n + 1$. We will do so in two steps.


Step 1: Show that $VC(\cal{H}_{P_n}) \le n + 1$.

Proof: In this step, we are showing that $\cal{H}_{P_n}$ is a subset of the class of all linear classifiers $f_l:\mathbb{R}^{n+1} \to \mathbb{R}$.

That is, denote the class of all such linear classifiers as $\cal{H}_{l_{d+1}}:= \{f_l: f_l(x) = \textbf{sign}(\langle w, x \rangle), \quad w, x \in \mathbb{R}^{n+1}\}$. Take as given that $VC(\cal{H}_{l_{n+1}}) = n + 1$.

Then, notice we can write any polynomial $p_n$ as a dot product between a vector of constants $c \in \mathbb{R}^{n+1}$ and a basis vector $\phi(x) :=\{1, x, x^2, \dots, x^n\}$, that is: $p_d(x) = \langle w, \phi(x) \rangle$.

Then, we can see that a polynomial is a type of linear function in the space of $\phi(x)$. Hence, (and you might need to do some thinking here to convince yourself),

$$ \cal{H}_{P_n} \subset \cal{H}_{l_{n+1}} $$

Since the VC dimension of a smaller class of functions is less than or equal to the VC dimension of a greater class of functions,

$$ VC(\cal{H}_{P_n}) \le VC(\cal{H}_{l_{n+1}}) = n +1 $$

Hence, $VC(\cal{H}_{P_n}) \le n + 1$.


Step 2: Show that $VC(\cal{H}_{P_n}) \ge n + 1$.

Proof: The idea of this step is to show that $\cal{H}_{P_n}$ shatters at least $n + 1$ points. In order words, we want to show that we can find a set of $n+1$ points $\{x_1, x_2,...,x_{n+1}\} \subset \mathbb{R}$ such that $\{(f_d(x_1), f_d(x_2),\dots, f_d(x_{n+1}) ): f_d\in \cal{H}_{P_n}\}=\{-1,1\}^{n+1}$. (In other words, we can produce any possible label vector $y\in \mathbb{R}^{n+1}$, $y_i \in \{-1,1\} \forall i \in [n+1]$, using functions from our hypothesis class $\cal{H}_{P_n}$).

Here, you can use Vandermonte's Matrix Theorem that says that the $(n+1)\times(n+1)$ matrix produced by making columns out of $\phi(x_i), i \in [n+1]$ is invertible if and only if the $x_i$'s are all distinct (no duplicates). Writing this explicitly:

$$ \begin{bmatrix} \phi(x_1) & \dots & \phi(x_{n+1})\\ \downarrow & & \downarrow \end{bmatrix} = \begin{bmatrix} 1 & 1 & \dots & 1\\ x_1 & x_2 & \dots & x_{n+1}\\ x_1^2 & x_2^2 & \dots & x_{n+1}^2\\ \vdots & & \dots & \vdots\\ x_1^{n+1} & x_2^{n+1} & \dots & x_{n+1}^{n+1}\\ \end{bmatrix} $$

That is to say, $\phi(x_1), \dots \phi(x_{n+1})$ are linearly independent, and since this is a square matrix, the rows are also linearly independent. Notice that the rows represent a single polynomial function when you pass a constant vector $c \in \mathbb{R}^{n+1}$. Therefore, the rows span $\mathbb{R}^{n+1}$. That is, for any point $v \in \mathbb{R}^{n+1}$, there exists a unique solution $w\in \mathbb{R}^{n+1}$ such that $w_0 + w_1 x_i + w_2 x_i^2 + \dots + w_n x_i^n = v_i, \quad \forall i \in [n+1]$.

Moreover, this is true for a label vector $y \in \mathbb{R}^{n+1}$. In other words, given a set of (distinct) points $\{x_1,\dots, x_{n+1}\}$ and associated (arbitrary) labels we can find weights $w \in \mathbb{R}^{n+1}$ to create a d-degree polynomial $p_d$ that perfectly interpolates each point $y_i \in \{-1,1\}, \forall i \in [n+1]$.

Hence, $\cal{H}_{P_n}$ shatters $n+1$ points. Therefore, $VC(\cal{H}_{P_n}) \ge n + 1$.


Step 3: Show $VC(\cal{H}_{P_n}) = n + 1$.

Proof: By steps 1 and 2, it follows that $VC(\cal{H}_{P_n}) = n + 1$.

q.e.d.

$\endgroup$

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.