Note:
You need to submit a report in hard-copy before lecture and your code to Blackboard.
Hard-copy is due in class before lecture and electronic copy is due 11:59PM on Blackboard.
Unlimited number of submissions are allowed on Blackboard and the latest one will be graded.
LFD refers to the textbook \Learning from Data".
(10 points) Problem 1.2 in LFD.
(25 points) Perceptron for Handwritten Digits Recognition: The handwritten digits
les are in the \data" folder: train.txt and test.txt. The starting code is in the \code" folder. In the data le, each row is a data example. The rst entry is the digit label (\1" or \5"), and the next 256 are grayscale values between -1 and 1. The 256 pixels correspond to a 16 16 image. You are expected to implement your solution based on the given codes. The only le you need to modify is the \solution.py" le. You can test your solution by running \main.py" le. Note that code is provided to compute a two-dimensional feature (symmetry and average intensity) from each digit image; that is, each digit image is represented by a two-dimensional vector before being augmented with a \1" to form a three-dimensional vector as discussed in class. These features along with the corresponding labels should serve as inputs to your Perceptron algorithm.
(5 points) Familiarize yourself with the data by completing the show images() function. Include the images you plotted into your report.
(5 points) In this assignment, we already extracted two features, (symmetry and average intensity), to distinguish between 1 and 5. Familiarize yourself with the features by completing the show features() function and include the 2-D scatter plot into your report. For each sample, plot the two features with a red if the label is 1 and a blue + if the label is 5.
(10 points) Complete the perceptron() function. You can test your accuracy results using the \test accuracy()" function in \main.py".
(5 points) Complete the show result() function to plot the test data with the separators. Include the images you plotted into your report.
Deliverable: You should submit (1) a hard-copy report (along with your write-up for other questions) that summarizes your results and (2) the \solution.py" le to the Blackboard.
Note: Please read the \Readme.txt" le carefully before you start this assignment. Please do NOT change anything in the \main.py" and \helper.py" les when you program.
3. (10 points) Given x 2 Rm, y 2 Rn, show that the rank of matrix xyT is one.
1
4. (10 points) Given X = [x1; x2; ; xn] 2
Rm n where xi 2 Rm for all i, and Y T =
[y1; y2; ; yn] 2 Rp n where yi 2 Rp for all i. Show that
n
Xi
XY =
xi(yi)T :
=1
(10 points) Given X 2 Rm n, show that the matrix XT X is symmetric and positive semi-de nite. When is it positive de nite?
(10 points) Given g(x; y) = ex + ey2 + e3xy, compute @y@g :
(25 points) Consider the matrix
1
2 1 3
A = @
1
1
2
A;
3
2
5
Compute the eigenvalues and corresponding eigenvectors of A. You are allowed to use Matlab to compute the eigenvectors (but not the eigenvalues).
What is the eigen-decomposition of A?
What is the rank of A?
Is A positive de nite? Is A positive semi-de nite?
Is A singular?
2
