(Solved): Axis aligned rectangles: An axis aligned rectangle classifier in the plane is a classifier that as ...

Axis aligned rectangles: An axis aligned rectangle classifier in the plane is a classifier that assigns the value 1 to a point if and only if it is inside a certain rectangle. Formally, given real numbers $$a_1?b_1,a_2?b_2$$, define the classifier $$h_{\left(a_1,b_1,a_2,b_2\right)}$$ by $$h_{\left(a_1,b_1,a_2,b_2\right)}\left(x_1,x_2\right)=\{\begin{array}{ll}1& \text{ if }{a}_1?x_1?b_1\text{ and }{a}_2?x_2?b_2\\ 0& \text{ otherwise }\end{array}.$$ The class of all axis aligned rectangles in the plane is defined as $${\mathcal{H}}_{\text{rec }}^2=\left\{h_{\left(a_1,b_1,a_2,b_2\right)}:a_1?b_1\text{, and }{a}_2?b_2\right\}.$$ Note that this is an infinite size hypothesis class. Throughout this exercise we rely on the realizability assumption. 1. Let $$A$$ be the algorithm that returns the smallest rectangle enclosing all positive examples in the training set. Show that $$A$$ is an ERM. 2. Show that if $$A$$ receives a training set of size $$?\frac{4\log (4/?)}{?}$$ then, with probability of at least $$1??$$ it returns a hypothesis with error of at most $$?$$. Hint: Fix some distribution $$\mathcal{D}$$ over $$\mathcal{X}$$, let $$R^{?}=R\left(a_1^{?},b_1^{?},a_2^{?},b_2^{?}\right)$$ be the rectangle that generates the labels, and let $$f$$ be the corresponding hypothesis. Let $$a_1?a_1^{?}$$ be a number such that the probability mass (with respect to $$\mathcal{D}$$ ) of the rectangle $$R_1=R\left(a_1^{?},a_1,a_2^{?},b_2^{?}\right)$$ is exactly $$?/4$$. Similarly, let $$b_1,a_2,b_2$$ be numbers such that the probability masses of the rectangles $$R_2=R\left(b_1,b_1^{?},a_2^{?},b_2^{?}\right),R_3=R\left(a_1^{?},b_1^{?},a_2^{?},a_2\right),R_4=R\left(a_1^{?},b_1^{?},b_2,b_2^{?}\right)$$ are all exactly $$?/4$$. Let $$R(S)$$ be the rectangle returned by $$A$$. See illustration in Figure $$2.2$$. Figure 2.2 Axis aligned rectangles. - Show that $$R(S)?R^{?}$$. - Show that if $$S$$ contains (positive) examples in all of the rectangles $$R_1,R_2,R_3,R_4$$, then the hypothesis returned by $$A$$ has error of at most $$?$$. - For each $$i?\{1,\dots ,4\}$$, upper bound the probability that $$S$$ does not contain an example from $$R_i$$. - Use the union bound to conclude the argument. 3. Repeat the previous question for the class of axis aligned rectangles in $${\mathbb{R}}^d$$. 4. Show that the runtime of applying the algorithm $$A$$ mentioned earlier is polynomial in $$d,1/?$$, and in $$\log (1/?)$$.