# VC dimension of linear decision surface

In chapter 7 of Mitchell it states (paraphrasing):

The VC dimension of the set of hypotheses of the form $[a,b]$ and instance space $X = \mathbb{R}$ is 2. This is because no subset of size 3 can be shattered with such hypotheses.

The example given is that wlog, $S = {x_0, x_1, x_2}$ and $x_0<x_1<x_2$, we cannot have an interval shatter the dichotomy with $x_0, x_2$.

In the case of a straight line and points in the cartesian plane, the VC dimension is 3, even though if the points are colinear, we cannot shatter 3 points, we can shatter other cases of 3 points..

I am really confused about the difference here, why can't I say that because interval hypotheses can shatter the dichotomy with $x_0, x_1$ and $x_1, x_2$ that the VC dimension of interval hypotheses is 3?

Similarly, with hypotheses of straight lines and 4 points, clearly if we put 2 points on either side of a straight line, that is an example of shattering that particular case, yet it is in fact the case that 'no set of size 4 can be shattered by a straight line' -- is this example set not a set of size 4?

You have to be careful with the quantifiers:

A set is shattered by the hypothesis space if every subset of that set is described by some hypothesis.

The VC dimension is the highest number so that there is a set of that cardinality that can be shattered.

For the case of 3 distinct points $S = \{ x,y,z \}$ ($x < y < z$) on a line: in order to shatter it using intervals, it must be the case that every subset of $S$ can be written as $S \cap [a,b]$ for some $a$ and $b$. But there are no $a,b$ so that $\{x,z\} = S \cap [a,b]$, since $x < y < z$ will imply that $y \in S \cap [a,b]$ if $x,z \in S \cap [a,b]$.

"Similarly, with hypotheses of straight lines and 4 points, clearly if we put 2 points on either side of a straight line, that is an example of shattering that particular case, yet it is in fact the case that 'no set of size 4 can be shattered by a straight line"

This is not an example of shattering. In order to shatter a set $C$ using a family of hypothesis $H$, it must be the case that every subset of $C$ can be described as $C$ intersected with a hypothesis.

For the example of $C$ being 4 points, arranged as the points of a square, with $A,B$ and $C,D$ pairs of diagonally opposite points, you cannot create the dichotomy $A,B$ vs. $C,D$ using a line. It is harder to show that for any set of four points, there is some dichotomy of that set that you cannot describe with a line.

There's a good picture of this on wikipedia, so I'll just link you there: https://en.wikipedia.org/wiki/VC_dimension

See example 4. I also recommend reading the definitions as explained on wikipedia, VC dimension of a set-family, since that may help.

• thanks, this makes sense now.. am I right in my reasoning: in order for a set to be shattered, it must be that all combinations of that set must be separated? so in the case of 2 points either side of a line, it must be that all $2^4$ combinations of labels for those 4 points must be able to be separated by the line, without the points moving? Jun 19, 2017 at 7:12
• Combination is not really the right word (to my ears anyway) -- maybe two set partitions would be better. Provided you mean the $2^4$ combinations of labels with two colors (or two label types), then yes. (Note that hidden here is the useful bijection: Powerset(S) = Functions(S, \{0,1\})\$.) I think what you are saying sounds correct, terminological nit picking aside. Jun 21, 2017 at 4:26
• @dimebucker91 Yes, see comment for more discussion. Jun 21, 2017 at 4:27
• @dimebucker91 btw, check out the comments on this link for a very nice explanations: math.stackexchange.com/questions/96655/… Jun 21, 2017 at 4:28