Assignment #2: Deep and Recurrent Neural Networks

1 Tensorflow Softmax (20 points)
In this question, we will implement a linear classifier with loss function
Jsof tmax−CE(W ) = CE(y; softmax(xW ))
(Here the rows of x are feature vectors). We will use TensorFlow’s automatic differentiation capability to fit
this model to provided data.
(a) (4 points) Implement the softmax function using TensorFlow in q1 softmax.py. Remember that
softmax(x)i = Pejxeixj (1)
Note that you may not use tf.nn.softmax or related built-in functions. You can run basic (nonexhaustive tests) by running python q1 softmax.py.
(b) (4 points) Implement the cross-entropy loss using TensorFlow in q1 softmax.py. Remember that
CE(y; y^) = −
Nc
X i
=1
yi log(^ yi) (2)
where y 2 R5 is a one-hot label vector and Nc is the number of classes. Note that you may not use
TensorFlow’s built-in cross-entropy functions for this question. You can run basic (non-exhaustive tests)
by running python q1 softmax.py.
(c) (4 points) Carefully study the Model class in model.py. Briefly explain the purpose of placeholder variables and feed dictionaries in tensorflow computations. Fill in the implementations for the add placeholders,
create feed dict in q1 classifier.py.
Hint: Note that configuration variables are stored in the Config class. You will need to use these
configuration variables in the code.
1CS 224d: Assignment #2
(d) (4 points) Implement the transformation for a softmax classifier in function add model in q1 classifier.py.
Add cross-entropy loss in function add loss op in the same file. Use the implementations from the
earlier parts of the problem, not TensorFlow built-ins.
(e) (4 points) Fill in the implementation for add training op in q1 classifier.py. Explain how
TensorFlow’s automatic differentiation removes the need for us to define gradients explicitly. Verify that
your model is able to fit to synthetic data by running python q1 classifier.py and making sure
that the tests pass.
Hint: Make sure to use the learning rate specified in Config.
2 Deep Networks for Named Entity Recognition (35 points)
In this section, we’ll get to practice backpropagation and training deep networks to attack the task of Named
Entity Recognition: predicting whether a given word, in context, represents one of four categories:
• Person (PER)
• Organization (ORG)
• Location (LOC)
• Miscellaneous (MISC)
We formulate this as a 5-class classification problem, using the four above classes and a null-class (O) for
words that do not represent a named entity (most words fall into this category).
The model is a 1-hidden-layer neural network, with an additional representation layer similar to what you
saw with word2vec. Rather than averaging or sampling, here we explicitly represent context as a \window"
consisting of a word concatenated with its immediate neighbors:
x(t) = [xt−1L; xtL; xt+1L] 2 R3d (3)
where the input xt−1; xt; xt+1 are one-hot row vectors into an embedding matrix L 2 RjV j×d, with each row
Li as the vector for a particular word i = xt. We then compute our prediction as:
h = tanh(x(t)W + b1) (4)
y^ = softmax(hU + b2) (5)
And evaluate by cross-entropy loss
J(θ) = CE(y; y^) = −
5X i
=1
yi log ^ yi (6)
To compute the loss for the training set, we sum (or average) this J(θ) as computed with respect to each
training example.
For this problem, we let d = 50 be the length of our word vectors, which are concatenated into a window of width 3 ×50 = 150. The hidden layer has a dimension of 100, and the output layer ^ y has a dimension
of 5.
(a) (5 points) Compute the gradients of J(θ) with respect to all the model parameters:
@J
@U
@J
@b2
@J
@W
@J
@b1
@J
@Li
Page 2 of 7CS 224d: Assignment #2
where
U 2 R100×5 b2 2 R5 W 2 R150×100 b1 2 R100 Li 2 R50
In the spirit of backpropagation, you should express the derivative of activation functions (tanh, softmax)
in terms of their function values (as with sigmoid in Assignment 1). This identity may be helpful:
tanh(z) = 2 sigmoid(2z) − 1
Furthermore, you should express the gradients by using an \error vector" propagated back to each layer;
this just amounts to putting parentheses around factors in the chain rule, and will greatly simplify
your analysis. All resulting gradients should have simple, closed-form expressions in terms of matrix
operations. (Hint: you’ve already done most of the work here as part of Assignment 1.)
(b) (5 points) To avoid parameters from exploding or becoming highly correlated, it is helpful to augment
our cost function with a Gaussian prior: this tends to push parameter weights closer to zero, without
constraining their direction, and often leads to classifiers with better generalization ability.
If we maximize log-likelihood (as with the cross-entropy loss, above), then the Gaussian prior becomes
a quadratic term 1 (L2 regularization):
J
reg(θ) = λ
2
24
X
i;j
W 2
ij + X
i0j0
Ui20j0
35
(7)
and we optimize the combined loss function
Jfull(θ) = J(θ) + Jreg(θ) (8)
Update your gradients from part (a) to include the additional term in this loss function (i.e. compute
dJfull
dW , etc.).
(c) (5 points) In order to avoid neurons becoming too correlated and ending up in poor local minimina, it
is often helpful to randomly initialize parameters. One of the most frequent initializations used is called
Xavier initialization2.
Given a matrix A of dimension m × n, select values Aij uniformly from [−?; ?], where
? =
p6
pm + n (9)
Implement the initialization for use in xavier weight init in q2 initialization.py and use it
for the weights W and U.
(d) (20 points) In q2 NER.py implement the NER window model by filling in the appropriate sections. The
gradients you derived in (a) and (b) will be computed for you automatically, showing the benefits that
automatic differentiation can provide for rapid prototyping.
Run python q2 NER.py to evaluate your model’s performance on the dev set, and compute predictions
on the test data (make sure to turn off debug settings when doing final evaluation). Note that the test
set has only dummy labels; we’ll compare your predictions against the ground truth after you submit.
Deliverables:
1Optional (not graded): The interested reader should prove that this is indeed the maximum-likelihood objective when
we let Wij ∼ N (0; 1=λ) for all i; j.
2This is also referred to as Glorot initialization and was initially described in http://jmlr.org/proceedings/papers/
v9/glorot10a/glorot10a.pdf
Page 3 of 7CS 224d: Assignment #2
• Working implementation of the NER window model in q2 NER.py. (We’ll look at, and possibly
run this code for grading.)
• In your writeup (i.e. where you’re writing the answers to the written problems), briefly state
the optimal hyperparameters you found for your model: regularization, dimensions, learning rate
(including time-varying, such as annealing), SGD batch size, etc. Report the performance of your
model on the validation set. You should be able to get validation loss below 0:2.
• List of predicted labels for the test set, one per line, in the file q2 test.predicted.
• Hint: When debugging, set max epochs = 1. Pass the keyword argument debug=True to the
call to load data in the init method.
• Hint: This code should run within 15 minutes on a GPU and 1 hour on a CPU.
3 Recurrent Neural Networks: Language Modeling (45 points)
In this section, you’ll implement your first recurrent neural network (RNN) for building a language model.
Language modeling is a central task in NLP, and language models can be found at the heart of speech
recognition, machine translation, and many other systems. Given words x1; : : : ; xt, a language model predicts the following word xt+1 by modeling:
P(xt+1 = vj j xt; : : : ; x1)
where vj is a word in the vocabulary.
Your job is to implement a recurrent neural network language model, which uses feedback information
in the hidden layer to model the \history" xt; xt−1; : : : ; x1. Formally, the model3 is, for t = 1; : : : ; n − 1:
e(t) = x(t)L (10)
h(t) = sigmoid ?h(t−1)H + e(t)I + b1? (11)
y^(t) = softmax ?h(t)U + b2? (12)
P¯(xt+1 = vj j xt; : : : ; x1) = ^ yj(t) (13)
where h(0) = h0 2 RDh is some initialization vector for the hidden layer and x(t)L is the product of L with
the one-hot row-vector x(t) representing index of the current word. The parameters are:
L 2 RjV j×d H 2 RDh×Dh I 2 Rd×Dh b1 2 RDh U 2 RDh×jV j b2 2 RjV j (14)
where L is the embedding matrix, I the input word representation matrix, H the hidden transformation
matrix, and U is the output word representation matrix. b1 and b2 are biases. d is the embedding dimension,
jV j is the vocabulary size, and Dh is the hidden layer dimension.
The output vector y^(t) 2 RjV j is a probability distribution over the vocabulary, and we optimize the (unregularized) cross-entropy loss:
J(t)(θ) = CE(y(t); y^(t)) = −
jV j
X i
=1
y
(t)
i log ^ yi(t) (15)
3This model is adapted from a paper by Toma Mikolov, et al. from 2010: http://www.fit.vutbr.cz/research/groups/
speech/publi/2010/mikolov_interspeech2010_IS100722.pdf
Page 4 of 7CS 224d: Assignment #2
where y(t) is the one-hot vector corresponding to the target word (which here is equal to xt+1). As in Q 2,
this is a point-wise loss, and we sum (or average) the cross-entropy loss across all examples in a sequence,
across all sequences4 in the dataset in order to evaluate model performance.
(a) (5 points) Conventionally, when reporting performance of a language model, we evaluate on perplexity,
which is defined as:
PP(t) ?y(t); y^(t)? = P¯(xpred t+1 = xt+1 1 j xt; : : : ; x1) = Pj jV=1 j y1j(t) · y^j(t) (16)
i.e. the inverse probability of the correct word, according to the model distribution P¯. Show how you can
derive perplexity from the cross-entropy loss (Hint: remember that y(t) is one-hot!), and thus argue that
minimizing the (arithmetic) mean cross-entropy loss will also minimize the (geometric) mean perplexity
across the training set. This should be a very short problem - not too perplexing!
For a vocabulary of jV j words, what would you expect perplexity to be if your model predictions were
completely random? Compute the corresponding cross-entropy loss for jV j = 2000 and jV j = 10000, and
keep this in mind as a baseline.
(b) (5 points) As you did in Q 2, compute the gradients with for all the model parameters at a single point
in time t:
@J (t)
@U
@J (t)
@b2
@J (t)
@L
x(t)
@J (t)
@I
(t)
@J (t)
@H
(t)
@J (t)
@b1 (t)
where L
x(t) is the column of L corresponding to the current word x(t), and (t) denotes the gradient for
the appearance of that parameter at time t. (Equivalently, h(t−1) is taken to be fixed, and you need not
backpropagate to earlier timesteps just yet - you’ll do that in part (c)).
Additionally, compute the derivative with respect to the previous hidden layer value:
@J (t)
@h(t−1)
(c) (5 points) Below is a sketch of the network at a single timestep:
x(t)
h(t−1) h(t)
y^(t)
:::
Draw the \unrolled" network for 3 timesteps, and compute the backpropagation-through-time gradients:
@J (t)
@L
x(t−1)
@J (t)
@H
(t−1)
@J (t)
@I
(t−1)
@J (t)
@b1 (t−1)
4We use the tensorflow function sequence loss to do this.
Page 5 of 7CS 224d: Assignment #2
where
(t−1) denotes the gradient for the appearance of that parameter at time (t − 1). Because parameters are used multiple times in feed-forward computation, we need to compute the gradient for each
time they appear.
You should use the backpropagation rules from Lecture 5 5 to express these derivatives in terms of
error term
δ(t−1) = @J (t)
@h(t−1)
computed in the previous part. (Doing so will allow for re-use of expressions for t − 2, t − 3, and so on).
Note that the true gradient with respect to a training example requires us to run backpropagation all
the way back to t = 0. In practice, however, we generally truncate this and only backpropagate for a fixed
number τ ≈ 3 − 5 timesteps.
(d) (3 points) Given h(t−1), how many operations are required to perform one step of forward propagation
to compute J (t)(θ)? How about backpropagation for a single step in time? For τ steps in time? Express
your answer in big-O notation in terms of the dimensions d, Dh and jV j(Equation 14). What is the slow
step?
(e) (20 points) Implement the above model in q3 RNNLM.py. Data loaders and other starter code are
provided. Follow the directions in the code to understand which parts need to be filled in. Running
python q3 RNNLM.py will run the model. Note that you may not use built-in tensorflow functions
such as those in the rnn cell module.
Train a model on the ptb-train data, consisting of the first 20 sections of the WSJ corpus of the Penn
Treebank. As in Q 2, you should tune your model to maximize generalization performance (minimize
cross-entropy loss) on the dev set. We’ll evaluate your model on an unseen, but similar set of sentences.
Deliverables:
• In your writeup, include the best hyperparameters you used (training schedule, number of iterations,
learning rate, backprop timesteps), and your perplexity score on the ptb-dev set. You should be
able to get validation perplexity below 175.
• Include your saved model parameters for your best model; we’ll use these to test your model.
• Hint: When debugging, set max epochs = 1. Pass the keyword argument debug=True to the
call to load data in the init method.
• Hint: On a GPU, this code should run quickly (below 30 minutes). On a CPU, the code may take
up to 4 hrs to run.
(f) (7 points) The networks that you’ve seen in Assignment 1 and in q2 of this assignment are discriminative models: they take data, and make a prediction. The RNNLM model you’ve just implemented is
a generative model, in that it actually models the distribution of the data sequence x1; : : : ; xn. This
means that not only can we use it to evaluate the likelihood of a sentence, but we can actually use it to
generate one!
After training, in q3 RNNLM.py, implement the generate text() function. This should run the
RNN forward in time, beginning with the index for the start token <eos, and sampling a new word
xt+1 from the distribution y^(t) at each timestep. Then feed this word in as input at the next step, and
repeat until the model emits an end token (index of </eos).
5http://cs224d.stanford.edu/lectures/CS224d-Lecture5.pdf
Page 6 of 7CS 224d: Assignment #2
Deliverables:
• Include 2-3 generated sentences in your writeup. See if you can generate something humorous!
Completely optional, not graded: If you want to experiment further with language models, you’re
welcome to load up your own texts and train on them - sometimes the results can be quite entertaining! (See
http://kingjamesprogramming.tumblr.com/ for a great one6 trained on a mix of the King James
Bible and the Structure and Interpretation of Computer Programs.)