Fall 2019 CS 475 Machine Learning: Homework 5 1
CS 475 Machine Learning: Homework 5
Dimensionality Reduction, Structured Prediction, and FATE
Due: Thursday December 5, 2019, 11:59pm
100 Points Total Version 1.0
Make sure to read from start to finish before beginning the assignment.
Introduction This assignment will consist of three parts:
• (45 points) - A coding portion, where you will implement two dimensionality re-
duction techniques: PCA and LLE. You will also implement a K-Nearest Neighbors
classifier to operate over your dimensionality reduced data.
• (15 points) - A Jupyter notebook where you will explore bias in word embeddings,
and implement a debiasing technique.
• (40 points) - Written questions about HMMs, CRFs, RNNs and FATE.
1 Programming (45 points)
1.1 K-Nearest Neighbor Classifier
You will implement a K-Nearest Neighbors Classifier (KNN). This is a very simple su-
pervised model, which takes training data xi ∈ X , which is a finite set of d-dimensional
vectors. Each xi is paired with a label yi. “Training” a KNN is trivial: simply store the
data. All of the “work” is done at prediction time. To predict a label for an example x
1. Find the k nearest examples: K(x) = x(1), .., x(k) ∈ X where distance is measured
by Euclidean distance to x.
2. Infer the label for ŷ as the most common label of y(1), ..., y(k), where y(i) is the label
for x(i) ∈ K(x). In case of a tie, select the label with the lowest integer index.
We have implemented the fit function for you (it just saves the data in the model
object). Please implement the predict function for the KNN model in models.py.
You should be able to run this without specifying a dr-algorithm (dimensionality
reduction algorithm), which will just run a KNN model over your raw data. For example,
the command:
python3 main.py --knn-k 5 --test-split data/dev --predictions-file simple-knn-preds.txt
should output line-by-line predictions for the file dev into simple-knn-preds.txt, similar
to past homeworks. You could then evaluate your predictions by running:
python3 accuracy.py --labeled data/labels-mnist-dev.npy --predicted simple-knn-preds.txt
Fall 2019 CS 475 Machine Learning: Homework 5 2
Since KNN uses distance for prediction, larger dimensional data will be slower, and
also suffer from the curse of dimensionality. We ask you to implement KNN as it will
benefit from your dimensionality reduction.
For example, you could run your KNN model on the regular 748-dimension MNIST
data. But this might take a while! We’re going to attempt to fix that in the next two
sections.
1.2 Principal Component Analysis
We discussed PCA as a dimensionality reduction technique in class. PCA is one of many
different techniques, and the choice of method depends on the data and intended use of
the reduced dimension dataset.
PCA relies on eigendecomposition, which factorizes a matrix into a canonical form
consisting of two parts - eigenvalues and eigenvectors (see https://en.wikipedia.org/
wiki/Eigendecomposition_of_a_matrix). The eigenvectors determine the directions of
the new feature space, and the eigenvalues determine their magnitude.
First, preprocess the data matrix: standardize each feature in the dataset to unit scale,
defined as having a mean of zero and a variance of 1. Note that this is for each feature
index, not the example or the entire dataset. You do this by subtracting the mean from
all points and then dividing all points by the standard deviation. Since PCA yields a
feature space that maximizes variance along the axes, it’s important to ensure all features
are measured in the same scale. (If the standard deviation is 0, which can happen in
MNIST, you should not divide at all. This operation will leave you with every feature for
this dimension being 0, which it probably was already.)
Second, calculate the covariance matrix Σ, which is a D ×D matrix (where D is the
number of features). Each element of the matrix Σ represents the covariance between two
features. For a dataset of size N , each element in the matrix is defined as
Σst =
1
N − 1
N∑
i=1
(xis − x¯s)(xit − x¯t) (1)
Third, we are now ready for PCA, which uses an eigensolver to perform eigendecom-
position on the covariance matrix (see Section 1.2.1 for implementation details). For some
square matrix A, it can be factorized as
A = QΛQ−1 (2)
where Q are the eigenvectors and Λ are the eigenvalues.
Finally, select which eigenvectors to use in our lower-dimensional space by using the
top d corresponding eigenvalues (they will be sorted by absolute value). The eigenvalues
indicate the amount of information the eigenvectors contain about the variance within
the overall data. With these eigenvectors, we can build a weight vector W, which is a
D × d weight matrix. Finally, we can calculate our reduced feature space Y,
Y = XW (3)
The result is a reduced dimension data matrix Y of size N × d, where N is the number
of data points.
Fall 2019 CS 475 Machine Learning: Homework 5 3
Figure 1: From https://link.springer.com/article/10.1007%2Fs11692-018-9464-9, an explanation
of the linearity of PCA
1.2.1 Implementation Details
Most of PCA can be implemented using straightforward numpy operations. The most
challenging step is the eigendecomposition. We recommend using the scipy’s eigensolver,
https://docs.scipy.org/doc/scipy/reference/generated/scipy.linalg.eig.html.
Additionally, you may use any function in either numpy or scipy.
You should implement PCA as a subclass of Model. It’s fit function will take in both
your training and test data and jointly reduce all of your data points together. Fit should
then return the dimensionality reduced data in the same order that it’s passed in. This
is important because we will split the data back into training and test splits to perform
KNN. You do not need to implement the predict function for this model.
Here is an example of how your model should run after you’ve implemented PCA:
python3 main.py --knn-k 5 --dr-algorithm pca --target-dim 300 --test-split dev \
--predictions-file pca-knn-preds.txt
You should find this runs a lot faster than without dimensionality reduction!
1.3 Locally Linear Embedding (LLE)
While PCA strictly models linear variabilities in the data (see Figure 1), this strategy fails
when the data lie on a low-dimensional “manifold” (https://en.wikipedia.org/wiki/
Manifold), which can be a non-linear embedding of the data. Non-linear dimensionality
reduction methods attempt to find this manifold and produce a low-dimensional space
that encodes distances and relative position on the manifold.
Locally Linear Embedding (LLE) was introduced by Roweis and Saul in 2000. The
original paper was published in Science, but you can find a more introductory tutorial
here: https://cs.nyu.edu/~roweis/lle/papers/lleintro.pdf. The key insight to
LLE is that if you have enough data points on a manifold, we can assume a point and its
Fall 2019 CS 475 Machine Learning: Homework 5 4
Figure 2: An illustration of LLE from http://science.sciencemag.org/content/290/5500/
2323
nearest neighbors lie in a patch of the manifold that is approximately linear. Thus, LLE
aims to reduce dimensionality by finding linear weights that best reconstruct each point
from its neighbors, and then finding low-dimensional points for which these same weight
matrices apply. LLE is illustrated in Figure 2.
You should begin by preprocessing your data to have features normalized with mean
0 and variance 1 as in PCA.
Then the LLE algorithm can be broken down into 3 steps:
1. For each data point xi, determine the K nearest neighbors (where K is a hyperpa-
rameter fixed ahead of time)
2. For each data point xi, compute the weights wij that best reconstruct xi from its
neighbors (each neighbor is xj, and
∑
j is a sum over neighbors of xi), using the
reconstruction error function
ε(W) =
∑
i
|xi −
∑
j
wijxj|2 (4)
3. Compute the lower-dimensional vectors yi that are best reconstructed by the wij
computed in step 2, using an eigensolver to find the bottom nonzero eigenvectors to
minimize the embedding cost function (same form as in step 2, but now wij fixed
instead of free)
Φ(Y) =
∑
i
|yi −
∑
j
wijyi|2 (5)
We use X to refer to the input data matrix, which consists of N columns of data points
of dimensionality D. We will be returning a low-dimensional embedding matrix Y, which
is d x N where d D. xi and yi refer to the ith column of X and Y respectively, which
corresponds to the ith data point. K is the number of neighbors we will consider. W is
the reconstruction weight matrix, and wij is the entry corresponding to the i
th row and
jth column.
Fall 2019 CS 475 Machine Learning: Homework 5 5
We now present the pseudocode, in the same three high-level steps outlined above.1
We use for loops for simplicity of pseudocode, but we encourage you to consider numpy
speed-ups.
1. Find nearest neighbors
for i ∈ 1 . . . N do
Keep track of the indices of the K nearest neighors as an array n
(1)
i , . . . n
(k)
i
for j ∈ 1 . . . N do
Calculate the Euclidean distance between xi and xj
if xj is in K nearest then
Assign j as a neighbor of i
end if
end for
end for
2. Solve for reconstruction weights
Initialize reconstruction weight matrix W as N x N matrix of zeros.
for i ∈ 1 . . . N do
Initialize Z as D x K matrix.
for k ∈ 1 . . . K do
Set the kth column of Z to be x
n
(k)
i
− xi
end for
Compute local covariance C = ZTZ
Regularization term = 1e−3 × trace(C)
C = C + × I
Solve the linear system Cŵ = 1 for ŵ
for k ∈ 1 . . . K do
w
in
(k)
i
= ŵk/sum(ŵ) where ŵk is the k
th element of ŵ
end for
end for
3. Compute embedding coordinates
Create sparse matrix M = (I−W)T (I−W)
Find bottom d+ 1 eigenvectors of M (corresponding to the smallest eigenvalues)
Remove the eigenvector with eigenvalue 0
Set the rows of Y to be the remaining d eigenvectors
When we refer to “bottom eigenvectors,” we mean the eigenvectors with the smallest
eigenvalues. “Top eigenvectors” have the largest. We can get these easily from any
standard eigensolver, which we’ll detail more in the next section. Because M is symmetric,
it will have only real eigenvalues and eigenvectors, so you don’t have to worry about
complex numbers here.
1Our pseudocode is adapted from the authors’ web page, https://cs.nyu.edu/~roweis/lle/algorithm.html.
Fall 2019 CS 475 Machine Learning: Homework 5 6
1.3.1 Implementation Details
i Just as a small tip, LLE can take a while to train on all 3,000 train examples + 1,000
test examples. It might be a good idea to reduce it down to 1,000 examples total while
you’re developing the algorithm to help you debug.
ii Because we’re working with a symmetric matrix, you’ll want to use the eigensolver pro-
vided with scipy here: https://docs.scipy.org/doc/scipy/reference/generated/
scipy.sparse.linalg.eigsh.html#scipy.sparse.linalg.eigsh. Because we’re look-
ing for the eigenvectors corresponding to the smallest eigenvalues, we’ll want to use
the flag sigma=0.0 (this seems to work better than which=’sm’).
iii Because the eigensolver is a numerical approximation, it is not guaranteed the recover
exact zeros in the bottom eigenvalues. You may use np.finfo(float).eps as the
lower bound.
iv Just as you implemented a subclass of Model for PCA, you’ll do the same for LLE
with the same behavior.
v It is not always trivial to decide k (the number of nearest neighbors) in LLE. For this
assignment, you can use k = 10. You should feel free to play with this, but this setting
should work.
As before, here is an example of how we might run your code
python3 main.py --knn-k 5 --dr-algorithm lle --lle-k 10 --target-dim 300 --test-split dev \
--predictions-file pca-knn-preds.txt
1.4 Programming Details
As before, your code will be evaluated on it’s predictions on held-out test data. We
have provided you with the test-data, so you can ensure that your code does not fail
when running over it, but not the labels. You may compare the scores of your classifier
using different dimensionality reduction techniques on development data with your peers
on Piazza. To make sure that your predictions output is in the correct format, you
should test that accuracy.py can run on your dev predictions, as described in the KNN
instructions.
We will evaluate your code in 2 settings (1) classification accuracy on MNIST test data
when using PCA dimensionality reduction, and (2) classification accuracy on MNIST test
data when using LLE dimensionality reduction.
1.4.1 Data
You will be working with a subset of the popular MNIST 2 digit recognition dataset. This
dataset is a multiclass classification dataset which is composed of 10 classes (0-9). Each
example is a 28 by 28 greyscale image of a handwritten digit (0-9). Our version of the
dataset comes in 3 splits, of which you have 5 files: mnist-train.npy, mnist-dev.npy,
mnist-test.npy, labels-mnist-train.npy, labels-mnist-dev.npy
The training set consists of 3,000 labeled examples of hand written digits. The dev
and test splits each contain 1,000 examples. While this is not a lot of training data (the
actual MNIST dataset has 60,000 examples), we’ve cut things down considerably to help
2https://en.wikipedia.org/wiki/MNIST_database
Fall 2019 CS 475 Machine Learning: Homework 5 7
you run your code faster. You might be surprised at the accuracy of a simple KNN model
in this setting. Your implementations should not take longer than 7-8 minutes to run
with knn-k=5 and lle-k=10 (LLE will be much longer runtime than PCA).
Additionally, your data should contain glove.6B.100d.txt, which you will use for
the Notebook portion of this assignment.
1.4.2 Command Line Arguments
Your code should contain the following command line arguments, which you should not
change:
• --data: Points to the directory containing the MNIST data splits.
• --predictions-file: The file that your predictions will be stored in.
• --test-split: The split (test or dev) that your KNN model will predict over.
• --knn-k: A hyperparameter for your KNN model. How many nearest neighbors to
consider during prediction.
• --dr-algorithm: The type of dimensionality reduction algorithm to use (pca or
lle).
• --target-dim: The number of dimensions to keep with your dr technique.
• --lle-k: A hyperparameter for your lle algorithm, as described above.
Fall 2019 CS 475 Machine Learning: Homework 5 8
2 Jupyter Notebook (15 points)
Lastly, you will explore bias in word embeddings, and implement a debiasing method
in the jupyter notebook we’ve provided to you called FATE.ipynb. Please complete the
notebook by filling in all the TODOs in the coding cells, and answering the questions
with red FILL IN text. You will submit your notebook to Gradescope.
Fall 2019 CS 475 Machine Learning: Homework 5 9
3 Analytical (40 points)
Question 1) (15 points) Expressive power of sequence classifiers Consider the fol-
lowing sequence classification task. We are given an arbitrarily long sequence of tokens
from the alphabet X = {(, ), a, b, c, . . . , z}. In other words, each sequence x ∈ X ? where
(·)? denotes the Kleene closure operator. Our sequence classification task is to predict
whether or not a given x is a well formed—meaning that the parentheses are balanced.
Let Y = {Yes, No} denote the prediction.
Examples :
x1, . . . , x5 = ( ( ( ( ( ⇒ y = No
x1, . . . , x3 = ) ( a ⇒ y = No
x1, . . . , x4 = ( ) ( ) ⇒ y = Yes
x1, . . . , x8 = ( a ( b ) ( ) ) ⇒ y = Yes
Notice that we are not predicting a y label for each position, we are classifying the entire
sequence with a y label. However, the model for predicting the final classification will
make use of hidden states at each position, z1 . . . zT where T = |x|. Each latent state
zt comes from a set Z, the specific set will depend on the model family. For HMMs
and CRFs, Z is a discrete set of symbols of some fixed size. For RNNs, Z is a real-
valued vector of some fixed dimensionality. The latent state may be used to track the
unobserved properties of the input sequence (e.g., some sort of latent representation of
how the parentheses in the expression are matched).
When we are given a new sequence to classify x, we infer the hidden z states according
to our model parameters. We use the final state zT , to predict whether or not the sequence
was well formed. You can make this prediction by either examining the final state itself,
or using the final state as input to a classifier that predicts Yes or No.
1.1: For each of the following family of sequence models, state as to whether there exists
model parameters that can accurately capture the desired behavior. Explain.
(a) Hidden Markov Model
Fall 2019 CS 475 Machine Learning: Homework 5 10
(b) Conditional Random Field
(c) Recurrent Neural Network
1.2: How would your answers to question 1.1 change if the sequences where upper
bounded in length, |x| ≤ Tmax <∞? Explain.
Fall 2019 CS 475 Machine Learning: Homework 5 11
Question 2) CRF vs. HMM (15 points) Consider the following sequence models:
• HMM with K = |Z| latent states and M = |X | possible observations.
• Linear chain CRF over the same state space as the HMM, but with feature function
f(x, yt, yt−1) ∈ RD.
For the following questions give a big-O expression that is a function of K, D, M , and
input length T .
(a) Computing the posterior distribution over a specific label pHMM(Yt = y | x)
(b) Computing the posterior distribution over a specific label pCRF(Yt = y | x)
(c) How many parameters are in the HMM?
Fall 2019 CS 475 Machine Learning: Homework 5 12
(d) How many parameters are in the CRF?
(e) List one advantage and one disadvantage of CRF over HMMs.
Fall 2019 CS 475 Machine Learning: Homework 5 13
Question 3) FATE (10 points) Suppose you work for a bank and you have been tasked
with building a machine learning system that automatically approves or rejects credit
card applications. You are given a dataset that contains a sample of previously processed
applications, for which a human decision maker decided to approve or reject. Each ex-
ample contains information from the application, such as education level, zip code, and
income level, as well as a label indicating the decision (accept/reject). The demographics
of the applicant (gender, age, race, and ethnicity) are not included in the dataset or as
features in the data.
(a) Despite the fact that demographic information is not included in the dataset, you are
concerned that the resulting classifier may be biased against a demographic group.
Name two potential sources of such bias.
(b) Take the same dataset, but add the observation of whether or not the applicant kept in
good credit standing for 5 years after having their application approved (with rejected
candidates labeled as “unknown, due to rejection”). Suppose we trained to predict
the good credit standing rather than the person’s judgement. How would that change
the potential for bias? Explain.
Fall 2019 CS 475 Machine Learning: Homework 5 14
(c) Would using an interpretable machine learning model necessarily reduce bias and
increase fairness?
Fall 2019 CS 475 Machine Learning: Homework 5 15
4 What to Submit
In this assignment you will submit two things.
1. Submit your code (.py files) to cs475.org as a zip file. Your code must be
uploaded as code.zip with your code in the root directory. By ‘in the root
directory,’ we mean that the zip should contain *.py at the root (./*.py) and not
in any sort of substructure (for example hw1/*.py). One simple way to achieve this
is to zip using the command line, where you include files directly (e.g., *.py) rather
than specifying a folder (e.g., hw1):
zip code.zip *.py
A common mistake is to use a program that automatically places your code in a
subfolder. It is your job to make sure you have zipped your code correctly.
We will run your code using the exact command lines described earlier, so make sure
it works ahead of time, and make sure that it doesn’t crash when you run it on the
test data. A common mistake is to change the command line flags. If you do this,
your code will not run.
Remember to submit all of the source code, including what we have provided to you.
We will include requirements.txt and provide the data, but nothing else.
2. Submit your writeup to gradescope.com. Your writeup must be compiled
from latex and uploaded as a PDF. The writeup should contain all of the
answers to the analytical questions asked in the assignment. Make sure to include
your name in the writeup PDF and to use the provided latex template for your
answers following the distributed template. You will submit this to the assignment
called “Homework 5: Dimensionality Reduction, Structured Prediction, and FATE:
Written”.
3. Submit your Jupyter notebook to gradescope.com. Create a PDF version of
your notebook (File → Download As → PDF via LaTeX (.pdf)). Be sure you have
run the entire notebook so we can see all of your output. You will submit this to
the assignment called “Homework 5: FATE: Notebook”.
5 Questions?
Remember to submit questions about the assignment to the appropriate group on Piazza:
https://piazza.com/class/jkqbzabvyr15up.