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$ Welcome to AI.SE @Rain. It looks like this might be a homework question. If so, you should use the homework tag, and we'll give you answers that provide some help without directly answering your question. If this is not homework, let us know, and we can answer this question directly. $\endgroup$ – John Doucette Nov 4 '19 at 16:18
  • $\begingroup$ @ John Doucette I am a self-learner of machine learning and I find this in the internet source. Please provide me some help on this so that I can understand Machine learning more. Thanks $\endgroup$ – Rain Nov 6 '19 at 2:06
  • $\begingroup$ @Rain Please, provide a link to the resource that contains this problem. The context may help people to help you. $\endgroup$ – nbro Nov 7 '19 at 1:24
  • $\begingroup$ me-ramesh.blogspot.com/p/machine-learning.html (in the middle describing the square case) $\endgroup$ – Rain Nov 7 '19 at 9:08
  • $\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
  • 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.
| improve this answer | |

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.