EE 660 Homework Week 4 

- 1 -
EE 660 Homework Week 4 
1. AML Problem 1.7(a) (p. 36), plus the following part:
(b) Take the scenario of part (a), for the case of 1,000 coins, and � = 0.05.
Consider the following interpretation in applying it in a machine learning
setting.
There is one hypothesis that is given (one decision boundary and
corresponding set of decision regions, or one decision rule); call it ℎ.
The out of sample error is �)*+(ℎ) = 0.05, and the in-sample error
depends on the dataset drawn.
Hint: The number of tosses of a coin, , corresponds to the size of a
dataset.
Complete the machine-learning interpretation by answering the following:
(i) What do the 1000 coins represent?
(ii) What does the calculation in part (a), for 1000 coins and � = 0.05,
represent?
(iii) In this interpretation, take the most general version of the Hoeffding
inequality in Ch. 1:
�[|� − �| �] ≤ 2��:;<=
Give values (or expressions) for .
2. AML Problem 2.1 (p. 69).
3. AML Problem 2.2 (p. 69) Assume feature space is 2D. A “positive rectangle” is a
rectangle-shaped decision boundary, and has value (label) +1 inside and value (label)
–1 outside. The sides of the rectangle are parallel to the coordinate axes.
Hint for the last question: the bound is a polynomial in N.
4. [Based on AML Exercise 2.1, p. 45.]:
(a) Find the smallest break point k for the hypothesis set consisting of Positive
Rays (defined in Example 2.2).
(b) Find the smallest break point k for the hypothesis set consisting of Positive
Intervals (defined in Example 2.2).
HW4 continues on next page…
N = 10
µ,ν,and M
Please note: in AML, Exercises are embedded in the text of each section; Problems are
at the end of each chapter. Please be sure you work the assigned problem or exercise to get
credit.
- 2 -
Reading
AML Ch. 2. Specifically, review pp. 39-49 (most of this was covered in Lecture 8),
and read pp. 50-68. The “safe skip” part is optional reading, and the “Sketch of the
proof” after Theorem 2.5 is also optional reading.
Problems on the reading
5. AML Exercise 2.6 (p. 60).
6. AML Exercise 2.8 (p. 63). Note that in AML notation is in our class notation
( = best chosen hypothesis in ).
g h
g
H