CS422 - Project2 - Solved

Logistics: You must implement everything stated in this project description that is marked with an implement tag. Whenever you see the write-up tag, that is something that must be addressed in the project README.txt. Graduate students are required to implement everything including items tagged with 622. Students in 422 do not need to complete these extra elements. You cannot import any packages unless specifically noted by the instructor. In this project, you may import the numpy and math packages. You are welcome to ask about particular packages as they come up. The idea is to implement everything from scratch.


1           Perceptron (50 points)
File name: perceptron.py

Implement a function in python:

perceptron_train(X,Y)

that takes training data as input and outputs the weights w, and the bias b of the perceptron. Your function should handle any real-valued features, with feature vectors in any dimension, and binary labels. Write-Up: describe your implementation concisely.

Implement a function in python:

perceptron_test(X_test, Y_test, w, b)

that takes testing data, the perceptron weights and bias as input and returns the accuracy on the testing data. Write-Up: describe your implementation concisely.

You should get the following output for the perceptron when you run the test script.

Perceptron :
1.0
Perceptron :
0.42857142857142855
1

2

2           Gradient Descent (50 points)
Implement a function in python: gradient descent(∇f,xinit,η) that takes the gradient of a function f as input, the starting xinit and the learning rate η. The output of gradient descent is the value of x that minimizes ∇f. ∇f will be in the form of a function, so that you can calculate the gradient at a particular point. That is ∇f is a function with one input x and it outputs the value of the gradient at that point. If we are working with 1D variables, then x= (x1). If x is 2D then x= (x1,x2) and so on. x should be a 1D numpy array. Write-Up: describe your implementation concisely.

If you test your function using f(x) = x2, xinit = 5, and η = 0.1. ∇f = 2x. You should get a final x of 4.56719262e − 05 or something very small like that. It should take 52 steps. Note, I am not checking for

1

gradient equal to 0. I am checking that the magnitude of the gradient is less than some very small value,

0.0001.

For testing purposes: I will test your program with various ∇f.

You should get the following output for the gradient descent when you run the test script.

Gradient Descent :
[4.56719262e−05]
Gradient Descent :
[2.16433186e−55 5.77016976e−03]
1

2

2