$[6$ points$]$ Here we will give an illustrative example of a weak learner for a simple concept

class. Let the domain be the real line, $R,$ and let $C$ refer to the concept class of $"3-$piece

classifiers", which are functions of the following form: for ${}_1<msub><mrow><mi></mi></mrow><mrow><mn>2</mn></mrow></msub>$ and bin$\{-1,1\},h_{{}_1,{}_2,b}(x)$

is $b$ if xin$[{}_1,{}_2]$ and $-b$ otherwise. In other words, they take a certain Boolean value inside

a certain interval and the opposite value everywhere else. For example, $h_{10,20,1}(x)$ would be

$+1$ on $10,20,$ and $-1$ everywhere else. Let $H$ refer to the simpler class of "decision stumps",

i$.$e$.$ functions $h_{,b}$ such that $h(x)$ is $b$ for all $x$ and $-b$ otherwise.

$($a$)$ Show formally that for any distribution on $R($assume finite support, for simplicity; i$.$e$.,$

assume the distribution is bounded within $-B,B$ for some large $B)$ and any unknown

labeling function cinC that is a $3-$piece classifier, there exists a decision stump hinH

that has error at most $\frac{1}{3},$ i$.$e$.P[h(x)c(x)]\frac{1}{3}.$

$($b$)$ Describe a simple, efficient procedure for finding a decision stump that minimizes error

with respect to a finite training set of size $m.$ Such a procedure is called an empirical

risk minimizer $($ERM$).$

$($c$)$ Give a short intuitive explanation for why we should expect that we can easily pick $m$

sufficiently large that the training error is a good approximation of the true error, i$.$e$.$

why we can ensure generalization. $($Your answer should relate to what we have gained in

going from requiring a learner for $C$ to requiring a learner for $H.)$ This lets us conclude

that we can weakly learn $C$ using $H.$