Description
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 corresponding 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
IPython Notebook:
1 import numpy as np
2 from scipy import misc
3 from matplotlib import pylab as plt
4 import matplotlib.cm as cm
5 %matplotlib inline
6
7 train_labels, train_data = [], []
8 for line in open(’./faces/train.txt’):
9 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
column in X then dividing by the number of faces. Display the average face as a grayscale
image.
2
CS5785 Homework 2 Page 3
(d) Mean Subtraction. Subtract average face µ from every column in X. That is, xi := xi ° µ,
where xi is the i-th column 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 precomputed 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
r columns in U and first r rows in VT to approximate X. That is, we can approximate X by
Xˆ r = U[:,: r ] ß[: r,: r ] VT [: r,:]. The matrix Xˆ r is called rank-r approximation of X. Plot the
rank-r approximation error kX°Xˆ rkF
3 as a function of r when r = 1, 2,…, 200.
(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.
2. What’s Cooking?
spaghetti,
tomatoes, olive oil,
red onion, garlic,
red pepper, basil,
black pepper,
cheese
Italian Food!
(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?
(c) Represent each dish by a binary ingredient feature vector. Suppose there are d different ingredients 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 }
3k.kF is the Frobenius Norm of a matrix: kAkF =
qPm
i=1
Pn
i=1 |ai j |
2, which can be directly computed in numpy.
3
CS5785 : Homework 2 Page 4
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 recommend 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. RLU Exercise 11.3.1 (SVD of Rank Deficient Matrix)
4
