# What is the maximum number of dichotomies in a square?

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.

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?

• "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 7, 2019 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 8, 2019 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.