## Description

1. (100 points)(Coding Task) In this assignment, you will implement a recurrent neural network

(RNN) for language modeling using Pytorch. The task is to predict word xt+1 given words

x1, . . . , xt

:

P(xt+1 = vj |xt

, . . . , x1)

where vj is the j-th word in the vocabulary. The file“utils.py” gives an example of how to

generate the vocabulary. You can read it if interested. With the vocabulary, we can transform

a word xi

into a one-hot vector.

Our RNN model is, for t = 1, . . . , n − 1:

e

(t) = x

(t)L,

h

(t) = sigmoid(h

(t−1)H + e

(t)

I + b1),

yˆ

(t) = softmax(h

(t)U + b2),

P¯(xt+1 = vj |xt

, . . . , x1) = ˆy

(t)

j

.

where the first line actually corresponds to a word embedding lookup operation. h

(0) is the

initial hidden state, ˆy

(t) ∈ R

|V | and its j-th entry is ˆy

(t)

j

.

Training parameters θ in this model are:

1

· L – embedding matrix which transforms words in the vocabulary into lower dimensional

word embedding.

· H – hidden transformation matrix.

· I – input transformation matrix which takes word embedding as input.

· U – output transformation matrix which projects hidden state into prediction vector.

· b1 – bias for recurrent layer.

· b2 – bias for projection layer.

(a) (10 points) Let the dimension of word embedding as d, the size of vocabulary as |V |, the

number of hidden units as D, please provide the size of each training parameter above.

(b) (30 points) To train the model, we use cross-entropy loss. For time step t (note that for

language model, we have loss for every time step), we have:

E

(t)

(θ) = CE(y

(t)

, yˆ

(t)

) = −

X

|V |

j=1

y

(t)

j

log(ˆy

(t)

j

),

where y

(t)

is the one-hot vector corresponding to the target word, which here is equal to

x

(t+1). For a sequence, we sum and average the loss of every time step.

PyTorch does not require the implementation of back-propagation, but you should

know the details. Compute the following gradients at a single time step t:

∂E(t)

∂U ,

∂E(t)

∂b2

,

∂E(t)

∂I

(t)

,

∂E(t)

∂H

(t)

,

∂E(t)

∂b1

(t)

,

∂E(t)

∂h(t−1)

where |(t) denotes the gradient with respect to time step t only. Note that we have

weight sharing in recurrent layer, so in practice, the back-propagation would update the

parameters according to the gradients across all time steps. Hint:

∂E(t)

∂U = (h

(t)

)

T

(ˆy

(t) − y

(t)

)

Make sure you understand this hint and you can use it directly in your answer.

(c) (10 points) To evaluate a language model, we use perplexity, which is defined as the

inverse probability of the target word according to the model prediction P¯:

P P(t)

(y

(T)

, yˆ

(t)

) = 1

P¯(x

pred

t+1 = xt+1|xt

, . . . , x1)

=

1

P|V |

j=1 y

(t)

j

yˆ

(t)

j

.

Show the relationship between cross-entropy and perplexity.

(d) (50 points) Read the starting code very carefully and implement the above model by

completing RNNLM.py. You only need to code some parts related to the RNN model,

such as the architecture, loss function. Follow the instructions in the starting code to

understand which parts need to be filled in. When you are done, run python RNNLM.py.

The starting code supports GPU computation and also provides guidelines on how to

support CPU. It is very straightforward but note that CPU computation is slow! You

should change the hyperparameters to explore the best configurations. Submit the code

2

with your best hyperparameters. Also report the best testing perplexity score. This

model is a generative model. At the end of the run, it uses the trained language model

to generate sentences with the start words you provide. Be creative and report any

results that you think are interesting. Please summarize your results and observations.

2. (30 points) As introduced in class, the attention mechanism can be written into:

Attention(Q, K, V ) = softmax(QKT

)V.

By adding linear transformations on Q, K, and V , it turns into:

Attention(QWQ, KWK, V WV

) = softmax

QWQ(KWK)

T

V WV

.

Here, we set Q ∈ R

n×d

, WQ ∈ R

d×d

, K ∈ R

n×d

, WK ∈ R

d×d

, V ∈ R

n×d

, WV ∈ R

d×d

.

We’ve also covered the multi-head attention:

MultiHead(Q, K, V ) = Concat(head1, . . . , headh),

where

headi = Attention(QWQ

i

, KWK

i

, V WV

i

), i = 1, . . . , h.

Here, Q, K, V are the same as defined above. We set W

Q

i ∈ R

d× d

h , WK

i ∈ R

d× d

h , WV

i ∈ R

d× d

h .

(a) (15 points) Compute and compare the number of parameters between the single-head

and multi-head attention.

(b) (15 points) Compute and compare the amount of computation between the single-head

and multi-head attention, including the softmax step. Use the big-O notation to show

your results.

(Hint1: For (b), what we talked about in class may not be precise.)

(Hint2: Quoted from the paper (https://arxiv.org/pdf/1706.03762.pdf), “Due to

the reduced dimension of each head, the total computational cost is similar to that of

single-head attention with full dimensionality.”)

3. (20 points) For deep learning on graph data, we have learned GCNs, which aggregate information from neighboring nodes. The layer-wise forward-propagation operation of GCNs can

be expressed as

Xl+1 = σ(AXlWl

),

where Xl and Xl+1 are the input and output matrices of layer l, respectively, and A is the

adjacency matrix.

(a) (10 points) One limitation of this simple model is that multiplication with A means each

center node sums up feature vectors of all neighboring nodes but not the node itself.

How to fix this limitation with a simple modification on A?

(b) (10 points) Another limitation is that A is not normalized. The multiplication of A will

change the scale of feature vectors. Suppose we want to normalize A such that all rows

sum to one. How to fix this limitation with a simple modification on A?