2
$\begingroup$

I reinforce my education through self-study of Machine Learning. When I come across the problem of Growth Function generated by Convex Set I see only the result and skimming over a proof. I have to accept that $m_{H}(N)=2^{N}$, where $H$ consists of all hypothesis in two dimensions $h:\mathbb{R}^{2}\rightarrow\{-1,1\}$. In every material I've studied authors skim over the proof. Even wiki on the subject of "Shattered set" skim over the problem, and one can read: "With a bit of thought, we could generalize that any set of finite points on a unit circle could be shattered by the class of all convex sets".

Could anyone explain it in simple words and show the proof why for the two-dimensional space when we put all $N$ points on the unit circle then the growth function equals to $2^N$?

$\endgroup$

1 Answer 1

2
$\begingroup$

The growth function is $2^N$ if we can pick a set of points such that the hypothesis set shatters those points. So let's pick points on the unit circle. For any given function $f\in \mathcal{H}$, we can take the convex set determined by the points that $f$ sends to $+1$. Since $f$ is arbitrary, $\mathcal{H}$ shatters these points!

Abu-Mostafa's book "Learning From Data" has a nice section on this example.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .