An axis aligned rectangle classifier in the plane is a classifier that assigns the value 1...

 

Transcribed Image Text:

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. 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 > = 4 log(4/5) E then, with proba- bility of at least 1 - 8 it returns a hypothesis with error of at most . Hint: Fix some distribution D over X, let R* R(a, b, a, b) be the rect- angle that generates the labels, and let be the corresponding hypothesis. Let aa be a number such that the probability mass (with respect to D) of the rectangle R R(a, a1, a2, b) is exactly /4. Similarly, let b1, a2, b2 be numbers such that the probability masses of the rectangles R2 = R(b1, b, az, b), R R(a, b, a, a2), R4 R(a, b, b2, b) are all exactly /4. Let R(S) be the rectangle returned by A. See illustration in Figure 2.2. = = = + R* R(S) Figure 2.2 Axis aligned rectangles. Show that R(S) R*. RI Show that if S contains (positive) examples in all of the rectangles R1, R2, R3, R4, then the hypothesis returned by A has error of at most . For each i = {1,..., 4}, upper bound the probability that S does not contain an example from Ri. Use the union bound to conclude the argument. 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. 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 > = 4 log(4/5) E then, with proba- bility of at least 1 - 8 it returns a hypothesis with error of at most . Hint: Fix some distribution D over X, let R* R(a, b, a, b) be the rect- angle that generates the labels, and let be the corresponding hypothesis. Let aa be a number such that the probability mass (with respect to D) of the rectangle R R(a, a1, a2, b) is exactly /4. Similarly, let b1, a2, b2 be numbers such that the probability masses of the rectangles R2 = R(b1, b, az, b), R R(a, b, a, a2), R4 R(a, b, b2, b) are all exactly /4. Let R(S) be the rectangle returned by A. See illustration in Figure 2.2. = = = + R* R(S) Figure 2.2 Axis aligned rectangles. Show that R(S) R*. RI Show that if S contains (positive) examples in all of the rectangles R1, R2, R3, R4, then the hypothesis returned by A has error of at most . For each i = {1,..., 4}, upper bound the probability that S does not contain an example from Ri. Use the union bound to conclude the argument.