CS1675: Homework 5 solution


Original Work


Rate this product

You will trace through a run of the perceptron algorithm.

You have the following two-dimensional data: {(-1,-4), (-3,-1), (-3,-2), (-2,1), (-1,-1), (4,5), (1,3), (4,0), (3,2), (5,3)}. The first five data points belong to the positive class, and the second set of five to the negative class. This data is linearly separable and can be plotted in 2D using its two feature dimensions. Your goal is to create figures similar to Figure 4.7 in Bishop.

Instead of a basis function, you will just use x, i.e. φ(x) = x.

In a script perceptron.m, implement the perceptron algorithm and use it, along with some provided plotting code, to trace through several iterations of the method:

  1. [5 pts] First, represent the data and labels, with samples as the rows and features (coordinates) as the columns. Use all the data for training since we won’t test but will only visualize what the method is learning. Set the learning rate η to 0.1. Initialize the weight vector to a vector of random numbers.
  2. [5 pts] Compute the predicted label vector Y_pred by multiplying the weights and features, and checking the sign of the result. Use the Matlab function sign. If the predicted label is 0, set it to 1.
  3. [5 pts] Compute the accuracy of the current prediction for each training sample. While the accuracy for some sample is not 1, loop as follows.
  4. [5 pts] Find a sample whose label isn’t accurately predicted. If there are multiple such samples, choose at random. Compute the weight update for that misclassified sample. Then predict all labels again using the new weights, and check the accuracy.
  5. [5 pts] Use the provided plot_points_w.m function to plot the data points and the direction of the weight vector. This function shows positive samples as open circles, and negative samples as filled circles. It shows correctly classified samples in green, and misclassified samples in red. It also outputs the iteration ID and the two feature dimensions for the misclassified example that is being used to correct w. This script requires that you keep an iteration counter ct and an index for which misclassified point was selected in a given iteration as sel. Name your weights vector variable w, your data matrix X (with samples as the rows), your vector of true labels Y, and your predicted labels Y_pred.
  6. [5 pts] In a file report.pdf/docx, show the process for three consecutive iterations of the method, i.e. include three figures output by the plotting function provided. If too many (or too few) iterations are taking place, terminate the run and start another run.

Submission: Please include the following files:

  • perceptron.m
  • report.pdf/docx