Description
Problem 1 Let (w, b) ∈ R
d × R and x ∈ R
d
. Assume that kwk2 = 1. Let us consider the point
v defined by v = x − (w · x + b)w.
1. (2 points) Show that w · v + b = 0
2. (3 points) Using the previous question, prove that the following holds:
min
u∈Rd s.t. w·u+b=0
kx − uk2 ≤ |w · x + b|
3. (4 points) Let u ∈ R
d
such that w · u + b = 0. Show that kx − uk2 ≥ kx − vk2.
4. (2 points) Use the above results to find the analytical expression for the `2 distance between
a point x and the hyperplane defined by w · u + b = 0 for all u ∈ R
d
.
Problem 2 Recall the perceptron algorithm from class. It can be found in lecture notes posted
on the course website.
1. (2 points) Let us modify the update rule to add a learning rate α which multiplies the update
applied to weights. The update rule becomes: w
0 ← w + αt(i)x
(i)
. Show that the value of the
learning rate does not change the perceptron’s prediction after an update.
2. (8 points) Implement this modified perceptron algorithm in Python and NumPy. Include a
copy of your code in your submission for this assignment.
3. (1 point) Report the test error of your perceptron on the breast cancer dataset included with
sklearn. Split the dataset (which includes 569 points) in 450 training examples and 119 test
examples. One way to do that is as follows:
from sklearn.datasets import load_breast_cancer
breast_cancer = load_breast_cancer()
X = breast_cancer.data
Y = breast_cancer.target
train_X = X[:450]
test_X = X[450:]
train_Y = Y[:450]
test_Y = Y[450:]
Note that TAs will not have time to help with setting up your machines. If you are unable to
install Python, NumPy, or sklearn on your machine, you can use the notebooks provided for
free on Colab: https://colab.research.google.com.
∗
∗ ∗
