3

I am new to machine learning. I am reading this blog post on the VC dimension.

$\mathcal H$ consists of all hypotheses in two dimensions $h: R^2 → \{−1, +1 \}$, positive inside some square boxes and negative elsewhere.

An example.

enter image description here

My questions:

  1. What is the maximum number of dichotomies for the 4 data points? i.e calculate mH(4)

  2. It seems that the square can shatter 3 points but not 4 points. The $\mathcal V \mathcal C$ VC dimension of a square is 3. What is the proof behind this?

Rain
  • 31
  • 1
  • "What is the maximum number of dichotomies for the 4 data points?", but in the picture you're showing, there are 5 data points (or numbers). – nbro Nov 07 '19 at 17:23
  • The picture is just an example showing one of the possibilities of data points distributions. For point INSIDE the square, it is +1, For point OUTSIDE the square, it is -1. My question is asking 4 points, it is correct and unrelated to 5 points in my drawing. – Rain Nov 08 '19 at 02:17

1 Answers1

1
  • The number of dichotomies of 4 data points will clearly be $2^4 = 16$. According to these slides the definition of dichotomy in context of Statistical Learning is:

Different ‘hypotheses’ over the finite set of $N$ input points.

Which basically means hypotheses with unique behaviours over the input points. Two or more different hypotheses can have same behaviour on the data points (consider the case of a square covering the $4$ data points, an even larger square will also cover the $4$ data points. Thus they are different hypotheses but have same behaviour) and hence emphasis on the term unique.

  • The proof of axis aligned squares having $\mathcal V \mathcal C$ dimension $3$ can be found here. It's pretty straightforward so I don't want to explain it here.