# Derivation of VC dimension of linear regression

Looking at these slides, we see the following definition for the VC dimension of a class of real-valued functions:

So I want to derive the VC dimension of linear regression. For starters I'm not going to use an intercept so $\theta = (\theta_1, \theta_2)$.

That means I'm considering functions of the form $$f_y(x, \theta) = \begin{cases} 1 &&x^T \theta > y \\ -1 && \textrm{o.w.}\end{cases}$$

This means our decision boundary is $x^T \theta = y \iff x_2 = \frac{y}{\theta_2} - \frac{\theta_1}{\theta_2}x_1$ for a fixed $y$. Now if $y \neq 0$ we can create any line in $\mathbb R^2$ from this, so we can shatter 3 points. If $y = 0$ all of our lines go through the origin so we can only shatter 2 points.

By the above definition, this now means that we have $$v_y = \begin{cases}3 && y \neq 0 \\ 2 && y = 0\end{cases}$$ so the overall VC dim $v$ is equal to 3. Is this all correct?

How do things change when we add an intercept, so $x = (1, x_1, x_2)$ and $\theta = (\theta_0, \theta_1, \theta_2)$? In $\mathbb R^2$ these are all still just lines, so is the only difference that now $v_y = 3$ for all $y \in \mathbb R$?