## 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.

∗

∗ ∗