Homework 2 Solution

PROGRAMMING EXERCISES

1. Eigenface for face recognition.









In this assignment you will implement the Eigenface method for recognizing human faces. You will use face images from The Yale Face Database B, where there are 64 images under different lighting conditions per each of 10 distinct subjects, 640 face images in total. With your implementation, you will explore the power of the Singular Value Decomposition (SVD) in representing face images.

Read more (optional):

    • Eigenface on Wikipedia: https://en.wikipedia.org/wiki/Eigenface

    • Eigenface on Scholarpedia: http://www.scholarpedia.org/article/Eigenfaces

    (a) Download The Face Dataset. After you unzip faces.zip, you will find a folder called images which contains all the training and test images; train.txt and test.txt specifies the training set and test (validation) set split respectively, each line gives an image path and the correspond-ing label.

    (b) Load the training set into a matrix X: there are 540 training images in total, each has 50 £ 50 pixels that need to be concatenated into a 2500-dimensional vector. So the size of X should be 540 £2500, where each row is a flattened face image. Pick a face image from X and display that image in grayscale. Do the same thing for the test set. The size of matrix Xtest for the test set should be 100 £2500.

Below is the sample code for loading data from the training set. You can directly run it in Jupyter Notebook:


    • import numpy as np

    • from scipy import misc

    • from matplotlib import pylab as plt

4import matplotlib.cm as cm

5%matplotlib inline

6

    • train_labels, train_data = [], []

    • for line in open('./faces/train.txt'):

    • im = misc.imread(line.strip().split()[0])

    10 train_data.append(im.reshape(2500,))

    11 train_labels.append(line.strip().split()[1])

    12 train_data, train_labels = np.array(train_data, dtype=float), np.array(train_labels, dtype=int)

13

    14 print train_data.shape, train_labels.shape

    15 plt.imshow(train_data[10, :].reshape(50,50), cmap = cm.Greys_r)

    16 plt.show()


    (c) Average Face. Compute the average face „ from the whole training set by summing up every row in X then dividing by the number of faces. Display the average face as a grayscale image.

2
CS5785 Fall 2019: Homework 2    Page 3



    (d) Mean Subtraction. Subtract average face „ from every row in X. That is, xi :˘ xi ¡ „, where xi is the i -th row of X. Pick a face image after mean subtraction from the new X and display that image in grayscale. Do the same thing for the test set Xtest using the pre-computed average face „ in (c).

    (e) Eigenface. Perform Singular Value Decomposition (SVD) on training set X (X ˘ U§VT ) to get matrix VT , where each row of VT has the same dimension as the face image. We refer to vi, the i -th row of VT , as i -th eigenface. Display the first 10 eigenfaces as 10 images in grayscale.

(f ) Low-rank Approximation. Since § is a diagonal matrix with non-negative real numbers on the diagonal in non-ascending order, we can use the first r elements in § together with first
    • columns in U and first r rows in VT to approximate X. That is, we can approximate X by
ˆ
T


ˆ
Xr ˘ U[:, : r ] §[: r, : r ] V

[: r, :]. The matrix Xr is called rank-r approximation of X. Plot the


ˆ
2
as a function of r when r ˘ 1, 2, . . . , 200.
rank-r approximation error kX ¡XrkF


    (g) Eigenface Feature. The top r eigenfaces VT [: r, :] ˘ {v1, v2, . . . , vr }T span an r -dimensional linear subspace of the original image space called face space, whose origin is the average face „, and whose axes are the eigenfaces {v1, v2, . . . , vr }. Therefore, using the top r eigenfaces {v1, v2, . . . , vr }, we can represent a 2500-dimensional face image z as an r -dimensional feature vector f: f ˘ VT [: r, :] z ˘ [v1, v2, . . . , vr ]T z. Write a function to generate r -dimensional feature matrix F and Ftest for training images X and test images Xtest, respectively (to get F, multiply X to the transpose of first r rows of VT , F should have same number of rows as X and r columns; similarly for Xtest).

    (h) Face Recognition. Extract training and test features for r ˘ 10. Train a Logistic Regression model using F and test on Ftest. Report the classification accuracy on the test set. Plot the classification accuracy on the test set as a function of r when r ˘ 1, 2, . . . , 200. Use “one-vs-rest” logistic regression, where a classifier is trained for each possible output label. Each

labels as






spaghetti,

tomatoes, olive oil,

red onion, garlic,   Italian Food!
red pepper, basil,

black pepper,

cheese


    (a) Join the What’s Cooking competition on Kaggle.  Download the training and test data (in

.json). The competition page describes how these files are formatted.

    (b) Tell us about the data. How many samples (dishes) are there in the training set? How many categories (types of cuisine)? Use a list to keep all the unique ingredients appearing in the training set. How many unique ingredients are there?

2k.kF is the Frobenius Norm of a matrix: kAkF ˘ q
P
m
P
n


i ˘1

i ˘1 jai j j2, which can be directly computed in numpy.



3
CS5785 Fall 2019: Homework 2    Page 4



    (c) Represent each dish by a binary ingredient feature vector. Suppose there are d different in-gredients in total from the training set, represent each dish by a 1£d binary ingredient vector x, where xi ˘ 1 if the dish contains ingredient i and xi ˘ 0 otherwise. For example, suppose all the ingredients we have in the training set are { beef, chicken, egg, lettuce, tomato, rice } and the dish is made by ingredients { chicken, lettuce, tomato, rice }, then the dish could be represented by a 6 £1 binary vector [0, 1, 0, 1, 1, 1] as its feature or attribute. Use n £d feature matrix to represent all the dishes in training set and test set, where n is the number of dishes.

    (d) Using Naïve Bayes Classifier to perform 3 fold cross-validation on the training set and report your average classification accuracy. Try both Gaussian distribution prior assumption and Bernoulli distribution prior assumption.

    (e) For Gaussian prior and Bernoulli prior, which performs better in terms of cross-validation accuracy? Why? Please give specific arguments.

(f ) Using Logistic Regression Model to perform 3 fold cross-validation on the training set and report your average classification accuracy.

    (g) Train your best-performed classifier with all of the training data, and generate test labels on test set. Submit your results to Kaggle and report the accuracy.


WRITTEN EXERCISES



You can find links to the textbooks for our class on the course website.

Submit the answers to these questions along with your writeup as a single .pdf file. We do recom-mend you to type your solutions using LaTeX or other text editors, since hand-written solutions are often hard to read. If you handwrite them, please be legible!



    1. HTF Exercise 4.1 (From Generalized to Standard Eigenvalue Problem)

    2. HTF Exercise 4.2 (Correspondence between LDA and classification by linear least squares.)

    3. SVD of Rank Deficient Matrix. Consider matrix M. It has rank 2, as you can see by observing that

there times the first column minus the other two columns is 0.
    • 3
1   0   3

63
7
27



6

¡2

7


M
˘ 6
2

8
7
.
(1)


0
¡1
1




6
5
8
7
7



6



7



4



5


(a) Compute the matrices MT M and M MT .

(b) Find the eigenvalues for your matrices of part (a).

(c) Find the eigenvectors for the matrices of part (a).

(d) Find the SVD for the original matrix M from parts (b) and (c). Note that there are only two nonzero eigenvalues, so your matrix § should have only two singular values, while U and V have only two columns.

4
CS5785 Fall 2019: Homework 2    Page 5



    (e) Set your smaller singular value to 0 and compute the one-dimensional approximation to the matrix M.

































































5