CS4786/5786: Machine Learning for Data Science, Fall 2017
09/21/2017: Assignment 3: Principal Component Analysis and Random Projections
Instructions Due at 11:59pm October 4th on CMS. Submit what you have at least once, an hour
before that deadline, even if you haven’t quite added all the finishing touches — CMS allows
resubmissions up to, but not after, the deadline. If there is an emergency such that you need an
extension, contact the professor. You have a slip day of at most one day for the assignment. The
assignment is to be done individually. You will submit both a writeup and some datafiles you
create. The writeup can be handwritten or typeset, but please make sure it is easily readable either
way. Keep an eye on the course webpage for any announcements or updates.
Academic integrity policy We distinguish between “merely” violating the rules for a given as-
signment and violating academic integrity. To violate the latter is to commit fraud by claiming
credit for someone else’s work. There is a zero-tolarance policy for this course when it comes
to academic integrity. For this assignment, an example of the former would be getting an answer
from person X but stating in your homework that X was the source of that particular answer. In
this case depending on how much help you got from person X, we would award points. But this
won’t be considered academic fraud. You would cross the line into fraud if you did not mention
X. The worst-case outcome for the former is a grade penalty; the worst-case scenario in the latter
is academic-integrity hearing procedures. I will go over assignments by various students to check.
Further, when possible we will run automated procedures to check.
The way to avoid violating academic integrity is to always document any portions of work you
submit that are due to or influenced by other sources, even if those sources weren’t permitted by
the rules.1
1We make an exception for sources that can be taken for granted in the instructional setting, namely, the course
materials. To minimize documentation effort, we also do not expect you to credit the course staff for ideas you get
from them, although it’s nice to do so anyway.
1
Q1 (Rotational Invariance of PCA). In this problem, we shall see that PCA is rotationally
invariant, and how we can use this property to do some cool stuff, such as deal with seemingly
arbitrary reorderings of features (sample real-life setting: when you get data measurements from
different sources that didn’t check with each other ahead of time). We shall build up to our finale
by walking you through various steps.
1. (warmup to make sure you have the right tools available; nothing to turn in) We have pro-
vided you with two sets of data points in 2d-gaussian.csv and 2d-gaussian-rotated.csv.
Using your favorite programming language or tool, load these files into two data matrices,
which we’ll refer to as XI and XII (we’re using Roman numerals here in an attempt to avoid
notational clashes), and scatter-plot these two set of points on the two- dimensional plane.
You should get the following (up to choice of graphical elements like color, style. of points,
and so on). Notice how the second set of points is simply a rotation of the first set; in that
sense, they are two differently-but-relatedly-featurized versions of the same data.
���
��
��
��
���
��� �� �� �� ���
���
����
2. Run PCA on XI and XII to get two corresponding projection matrices WI and WII. (Refer
back to the code posted on the course lectures page for examples of how to do this in various
languages.) Recall that the columns of these two matrices are the principal directions, i.e.,
the eigenvectors of the corresponding covariance matrices. Then, apply the projections WI
and WII to their corresponding data matrices XI and XII to yield YI and YII.
Examine WI and WII and verify that they are different 2 2 matrices. Similarly, examine
the two covariance matrices and verify that they are different 2 2 matrices. (Check your
understanding by verifying that you understand why the shapes are 2 2. We can help you
with this in office hours.) But then, examine YI and YII (you may wish to use scatterplots
to do this, but you don’t have to). You should see that the absolute values of corresponding
entries are . . . the same!
Finally, given the non-rotation matrix2
A =
:7071068 :7071068
:56 :1
;
2That is, the transpose of A is not A’s inverse.
2
run PCA on XIA to get a third projection matrix WIII and corresponding projection YIII.
Check to see that YIII is not the same as YI (you may wish to use scatterplots to do this, but
you don’t have to).
Explain in at most 10 sentences why all the projection matrices and covariance matrices you
get are different, and yet YI = YII, whereas YI 6= YIII. Make reference to the concepts illus-
trated in Figure 2 of http://www.cs.cornell.edu/Courses/cs4786/2015sp/lectures/lecnotes2.
pdf. You may not just say, “this happens because PCA is rotation invariant”, since (a) we
haven’t really defined what that means yet, and (b) since we haven’t given a definition, that
statement as it stands doesn’t seemingly make sense yet in light of the fact that the Ws differ.
Hint: We cannot imagine a correct answer that doesn’t make use of the special meanings
that the wts produced by PCA have.
3. Let’s generalize what we’ve just observed. A rotation matrix is a square matrix whose trans-
pose is its inverse. (Intuition: a clockwise rotation can be undone via counterclockwise rota-
tion by the same angular amount.) As usual, let our nd-dimensional data vectors be denoted
by x1;:::;xn (example: the rows of your XI matrix above) and let R be a d d rotation
matrix. For simplicity, you may assume that the xts have been centered. Let x0t = Rxt for
each of the n xts (example: the rows in your XII matrix above), forming a second dataset.
Now, for any K we pick, let us use PCA on each of the two data sets to obtain K-dimensional
projections y1;:::;yn and y01;:::;y0n, respectively.
(a) Write down a relationship between the two PCA projection matrices W and W0 in
terms of the rotation matrix R, and explain mathematically how you arrived at this
answer.
(b) Expand on your explanation from the previous subpart (Q1(2)) where you dealt with
the two-dimensional matrices XI and XII and the fact you just proved (Q1(3a)) to
explain why, for any t2f1;:::;ng, the entries of yt and y0t are the same up to sign.
Hint: to explain why the signs in corresponding entries might be flipped, consider the
following question: if a vector b is an eigenvector of matrix C, must it follow that -b
is?
4. Now lets move on to the magic trick!
The story:
You have an artist friend Picasso living in Spain who is into cubism (or, rather, squar-
ism — we didn’t know how to make cubistic smileys :) ). When you first met, both
of you drew a picture of the same smiley face, except that you drew a regular smiley
face, whereas he drew a “cubistic” version of it (these are the files smilie1.jpeg and
cubistsmilie1.jpeg). Since then, you have sketched many a smiley face (smilie2.jpeg
to smilie28.jpeg) and so has Picasso in his cubistic style. (cubistsmilie2.jpeg
to cubistsmilie28.jpeg). But of course, these are portraits of different faces, since
he lives in Spain and you don’t. You’ve stored the data for your non-cubist smileys in
3
X smilie.csv: each row i, i ranging from 1 to 28, is the (105 105)-dimensional data
vector for your corresponding smiley face smiliei.jpeg.
Picasso decides to send you his latest portraits, but, data rates being what they are, and he
being the suspicious type to boot3, would like to economize on how much data he sends.
Having heard about this dimension-reduction stuff, he performs PCA on the set of images
that he has, obtains a 20-dimensional representation for each of his cubistic smileys, and then
emails them to you. Specifically, he emails only his ~y’s — we will, in what is unfortunately
not an exact visual analogy, use tildes to indicate cubism — and nothing else. We have
stored these projections for you in file cubist email.csv, wherein row t is ~yt, whose
20 entries are stored as 20 floats separated by commas. The first row of this file is the 20
dimensional projection of the image you and Picasso sketched together.
Upon receipt, you perform. PCA on the images you sketched to obtain projection matrix W
and the mean of your x’s, which we will refer to . Now you simply use the 20-dimensional
vectors Picasso sent over and reconstruct these images based on your W and calculated
from your non-cubistic set of sketches.
What do you think you would see? Try it out on the data we have provided!
How to try out the above:
Remember that any two low-dimensional projections produced via PCA of the same data will
have the same absolute values for the entries of the y’s but might have their signs flipped
on coordinates. This is annoying, but can be fixed because, luckily, there exists that first
image of the same smiley face that you and Picasso each drew in your own style. Take
your projection y1 and Picasso’s projection ~y1 corresponding to this face. Now, if on any
coordinate, the sign of ~y1 and y1 are different, then for this coordinate flip the sign of all the
~yt’s. Finally, take the new ~yt’s and perform. image reconstruction based on your PCA:
^xt = W~yt +
for each of the cubistic image (and then transform. them back into images).
Techie version of the story:
Your goal is to understand why you see what you see when you do this reconstruction. Of
course, we need to explain how the cubistic smileys are generated. We start with a regular
smiley face, which is a 105 105 pixel image. We block the image into 21 21 size patches.
Since 105=21 = 5, we have 5 5 = 25 total patches. We pick a fixed reordering of these
25 patches and simply reorder the patches in the regular smiley faces to create a “cubistic”
version of the image.
Question: Given the way the cubistic smiley faces are generated, and based on the previous
subparts this question, explain the quality of the images you reconstructed based on the email
Picasso sent you.
3http://www.bbc.com/news/entertainment-arts-31435906
4
Hint: ask yourself, can reordering the pixels be written as a rotation of x’s? Even if so, how
can this help, given that you don’t know what that specific rotation was?
Deliverables: You only turn in wriute-up for this question.
Q1.1 Nothing to turn in.
Q1.2 Your explanation. This can be in plain english or if you prefer having some equations
go for it as well. but make sure your explanations are clear.
Q1.3 a. Mathematical relationship between W and W0. b. Reason why signs can be flipped,
in words or equations.
Q1.4 Apart from your explanation/what you did. Turn in two example images that were
reconstructed.
5
Q2 (Random Projections).
Generate a data set consisting of 100 1000-dimensional points. For each point xt in the data
set, ensure that their norm (distance to 0) is exactly 1. We shall perform. PCA and random
projections on this data set. To evaluate our projections we shall use the following metric on
how well each projection preserves distances:
Err(y1;:::;yn;x1;:::;xn) = 2n(n 1)
nX
t=1
nX
s=t+1
(kyt ysk2 kxt xsk2)
You shall pick K = 1 and perform. PCA and random projections on the data set. Your task
in this problem is to create the data sets such that the Err of Random Projection is much
smaller compared to that of PCA. (the Err of PCA should be at least 0:9 more than the
Err of random projection).
Deliverables: Submit your dataset as csv files RpBeatsPCA.csv (so, the file should
consist of 100 lines, each with thousand numbers separated by commas). Also, in your
assignment writeup, explain how you generated the data set and the rationale behind this
choice. Specifically, give the mathematical intuition with some formalism as to why the
error in PCA will be much higher than that of random projections. Your rationale should
explain how you used the properties of what RP and PCA produce to guide your thinking.
Your data file can satisfy the criterion and you can still get a score of 0 for this question!
Its all about your explanation.