COMP 4107 Assignment #1

Due: 1st February 2020 at 11:55 pm

Objective:

The primary objective of this assignment is to have the student review their knowledge of the following areas: linear algebra and simple calculus. The secondary objective is to exercise new concepts related to machine learning: gradient descent and singular value decomposition. Finally, proficiency in python programming is tested.

Submission

Submission should be to cuLearn. All implementations are in python. No other languages are acceptable. You are to upload a zip file containing python files and a single PDF file containing answers to the problems. Python files should be qX.py, where X corresponds to the question number.

Question 1 [5 marks]

Compute the SVD for the matrix below:

SVD matrix

Question 2 [10 marks]

SVD approximation matrix

The left figure above represents the surface. The right figure represents 50 of the singular values. Compute the best rank(2) matrix, A2, approximation to the matrix A. What is ||A - A2||?

Question 3 [15 marks]

Using the matrix A from Question 1, and let b = [1,1,1,1]T, using the gradient descent method, determine the least squares solution of:

least squares

Using a value of δ=0.01, Provide a table giving the values of x and the number of iterations taken to converge for values of ε=0.01,0.05,0.1,0.15,0.2,0.25,0.5. If there are values for which a solution cannot be found document why this is the case.

Question 4 [10 marks]

linear independence

Calculate the inverse for matrix A.

Question 5 [30 marks]

Reading 4 associated with lecture 3 describes an SVD-based method for classifying digits. Section 3 describes a representation of the data that allows SVD to be used where a subset of the images is used for classification. Using the representation of images described in Section 3, generate the results that are seen in Figure 4. Specifically, plot the accuracy as a function of the basis size used in the decomposition. You should run multiple experiments, sampling the original image datasets randomly. This will generate multiple A matrices. Reference 13 of the paper indicates where the MNIST data may be found.

Question 6 [30 marks]

Reading 5 associated with lecture 3 describes an SVD-based method for generating a recommendation system. Using the MovieLens dataset referred to in the paper, recreate the experimental evaluation described in Section 4. Read section 3 on "Incremental SVD Algorithms" before you start. Specifically, you should be able to reproduce Figure 3 and Figure 4, although the absolute values on your y axis for Figure 4 will be quite different because of your personal machine environments.