# VC dimension of the class of polynomial classifiers of degree $n$

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 classiﬁcation problem with the instance domain being $$X = \mathbb R$$.

For every $$n \in \mathbb N$$ let $$H_n$$ be the class of polynomial classiﬁers of degree $$n$$; namely, $$H_n$$ is the set of all classiﬁers 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$$.

• What did you try and where did you get stuck?
– Juho
Nov 26, 2019 at 11:28
• I need to confirm that this claim is true. But I don't know how to prove it.
– Ben
Nov 26, 2019 at 11:30
• Could you be more specific? As a first step, do you understand the concepts involved?
– Juho
Nov 26, 2019 at 11:55
• Of course I do. I have provided very specific background.
– Ben
Nov 26, 2019 at 12:12
– D.W.
Nov 27, 2019 at 8:21

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

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

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.