I am studying the book "Understanding Machine Learning: From Theory to Algorithms". I am struggling to understand the solution to exercise 3 (2) on page 41.
Exercise:
An axis aligned rectangle classifier in the plane is a classifier that assigns 1 to a point if and only if it is inside a certain rectangle. Formally, given real numbers $a_1\leq b_1, a_2\leq b_2,$ define the classifier $h_{(a_1, b_1, a_2, b_2)}$ by $$ h_{(a_1, b_1, a_2, b_2)}(x_1, x_2) = \begin{cases}1&\textrm{if $a_1\leq x_1\leq b_1$ and $a_2\leq x_2\leq b_2$}\\ 0&\textrm{otherwise}\end{cases} $$ The class of all axis aligned rectangles in the plane is defined as $\mathcal{H}_\mathrm{rec}^2 = \{h_{(a_1, b_1, a_2, b_2)}:\textrm{$a_1\leq b_1$ and $a_2\leq b_2$}\}$...rely on realizability assumption. Let $A$ be an algorithm that returns the smallest rectangle enclosing all positive examples in the training set. It is shown in (1) that $A$ is an ERM.
(2): Show that if $A$ receives a training set of size $\geq \frac{4\log(4/\delta)}{\epsilon}$ then, with probability of at least $1-\delta$ it returns a hypothesis with error of at most $\epsilon$.
Hint: Fix some distribution $\mathcal{D}$ over $\mathcal{X}$, let $R^*=R(a_1^*,b_1^*,a_2^*,b_2^*)$ be the rectangle that generates the labels, and let $f$ be the corresponding hypothesis. Let $a_1\geq a_1^*$ be a number such that the probability mass (w.r.t $\mathcal{D}$) of the rectangle $R_1=R(a_1^*,a_1,a_2^*,b_2^*)$ is exactly $\epsilon/4$. Similarly, let $b_1,a_2,b_2$ be numbers suh that the probability masses of the rectangles $R_2=R(b_1,b_1^*,a_2^*,b_2^*),R_3=R(a_1^*,b_1^*,a_2^*,a_2),R_4=R(a_1^*,b_1^*,b_2,b_2^*)$ are all exactly $\epsilon/4$. Let $R(S)$ be the rectanlge returned by $A$. See the following illustration:
- Show that $R(S)\subset 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 $\epsilon$.
- For each $i\in\{1,...,4\}$, upper bound the probability that $S$ does not contain an example from $R_i$
- Use the union bound to conclude the argument.
From the solution manual, here is the answer on page 2:
Fix some distribution $\mathcal{D}$ over $\mathcal{X}$, and define $R^*$ as in the hint. Let $f$ be the hypothesis associated with $R^*$ a training $S$, denoted $R(S)$ the rectagnle returned by the proposed algorithm and by $A(S)$ the corresponding hypothesis. The definition of algorithm $A$ implies that $R(S)\subset R^*$ for every $S$. Thus, $$L_{(\mathcal{D},f)}(R(S))=\mathcal{D}(R^*\setminus R(S))$$
Fix some $\epsilon\in(0,1)$. Define $R_1,R_2,R_3,R_4$ as in the hint. For each $i\in[4]$, define the event $$F_i=\{S|_x:S|_x\cap R_i=\emptyset\}$$
Applying the union bound we obtain
$$\mathcal{D}^m(\{S:L_{(\mathcal{D},f)}(A(S))\gt \epsilon\})\leq \mathcal{D}^m\left(\bigcup^4_{i=1}F_i\right)\leq \sum^4_{i=1}\mathcal{D}^m(F_i)$$
So the above is what I don't understand:
Why is $$\mathcal{D}^m(\{S:L_{(\mathcal{D},f)}(A(S))\gt \epsilon\})\leq \mathcal{D}^m\left(\bigcup^4_{i=1}F_i\right)$$
I know what these quantities mean:
- $\mathcal{D}^m(\{S:L_{(\mathcal{D},f)}(A(S))\gt \epsilon\})$ is equivalent to "the probability of observing samples $S$ such that when algorithm $A$ is applied to $S$, the true error is greater than $\epsilon$.
- $\mathcal{D}^m\left(\bigcup^4_{i=1}F_i\right)$ is equivalent to "the probability of observing samples which don't intersect $R_1$ or $R_2$ or $R_3$ or $R_4$.
But why is the inequality true? The root of my understanding is that I can't understand how $\epsilon$ and $A(S)$ are supposed to be involved in interpreting this inequality. As in I don't understand geometrically how $A(S)$ and $\epsilon$ form subsets in the context of the figure above. I can easily imagine the sets $F_i$ though.
