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?

  • $\begingroup$ "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). $\endgroup$ – nbro Nov 7 '19 at 17:23
  • $\begingroup$ 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. $\endgroup$ – Rain Nov 8 '19 at 2:17
  • 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.

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.