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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.