Understanding Machine Learning: From Theory to Algorithms

42 A Gentle Start

1. LetAbe the algorithm that returns the smallest rectangle enclosing all
   positive examples in the training set. Show thatAis an ERM.


2. Show that ifAreceives a training set of size≥4 log(4/δ)then, with proba-
   bility of at least 1−δit returns a hypothesis with error of at most.
   Hint: Fix some distributionDoverX, letR∗=R(a∗ 1 ,b∗ 1 ,a∗ 2 ,b∗ 2 ) be the rect-
   angle that generates the labels, and letfbe the corresponding hypothesis.
   Leta 1 ≥a∗ 1 be a number such that the probability mass (with respect
   toD) of the rectangleR 1 =R(a∗ 1 ,a 1 ,a∗ 2 ,b∗ 2 ) is exactly/4. Similarly, let
   b 1 ,a 2 ,b 2 be numbers such 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/4. LetR(S) be the rectangle returned byA. See illustration in
   Figure 2.2.

+

+

+

+

+

R∗

R(S)

R 1

Figure 2.2Axis aligned rectangles.

• Show thatR(S)⊆R∗.


• Show that ifS contains (positive) examples in all of the rectangles
  R 1 ,R 2 ,R 3 ,R 4 , then the hypothesis returned byAhas error of at
  most.


• For eachi∈ { 1 ,..., 4 }, upper bound the probability thatSdoes not
  contain an example fromRi.


• Use the union bound to conclude the argument.

3. Repeat the previous question for the class of axis aligned rectangles inRd.


4. Show that the runtime of applying the algorithmAmentioned earlier is
   polynomial ind, 1 /,and in log(1/δ).