Compute the growth function of a hypothesis set $H(N)($referring to week $4\text{'}$s slide page $25)$ in each of

the following cases.

$(1)$ Positive rays: $H$ consists of all hypotheses $h$:$R\{-1,+1\}$ of the form $h(x)=$sign$(x-a),$ i$.$e$.,$ the

hypotheses are defined in a one$-$dimensional input space, and they return $-1$ to the left of some value $a$

and $+1$ to the right of a$.$ The illustration is as follows,

PAGE $2$ OF $3$

CSCI$3320$

FUNDAMENTALS OF MACHINE LEARNING

Hint: When $N=2,$ there are three different dichotomies according to its definition, see figure below:

Positive rays:

$(1)$

$(2)$

$(3)$

$N=2$

so $H(2)=3.$

$(2)$ Positive intervals: $H$ consists of all hypotheses that return $+1$ with some interval and $-1$ otherwise.

Each hypothesis is specified by the two end values of that interval. The illustration is as follows,

Hint: When $N=3,$ there are seven different dichotomies according to its definition, see the figure below:

Positive intervals: