0

A classification problem is considered with observations $x \in \mathbb{R}^2$ and responses $y \in \{0,1\}$. There is a set of axis-aligned rectangle classifiers $F$. Particularly, сlassifier $f_{a,b} \in F$ is defined so: if $a_1 \le x_1 \le b_1 ,\space a_2 \le x_2 \le b_2$ $f(x)=1$ else $f(x)=0$.

The problem is to determine Vapnic-Chervonenkis dimension and growth function for set $F$.

I found here that VC-dimension is 4. But I have no idea how to find growth function.

Sergey
  • 9

1 Answers1

1

The VC-dimension is the size of the largest set that can be fully shattered by H an Hypothesis set. Purely combinatorial notion.

VCdim(H) = max{m: H (m)=2**m}.

http://www.cs.nyu.edu/~mohri/mls/lecture_3.pdf

As you can see in this pdf, page 25, for one axis aaligned rectangle the VC-dim is 4

"No set of five points can be shattered: label negatively the point that is not near the sides"

But, in your example there seems to be 2 rectangles so you can shatter more complex point configurations, the VC dim will be higher.

mrauto
  • 11
  • In my example there is one rectangle too. It seems that there is no difference between my example and example in pdf you referenced. – Sergey Oct 24 '14 at 16:14
  • you're right, you have a single axis aligned rectangle, my bad.
    in this case, the break point is at 5, (first counter example: 5points not shatterable by rectangle by labelling nega tive the point inside the 4 others) Thus the VC dimension is 4 and for m points the growth function will be O(m4) which is much less than 2m after the break point (inclusive) The exact polynomial of degree 4 is not necessarily obvious... (combinatorics)     – mrauto Nov 05 '14 at 07:31