Homework Assignment #2 Solution

Description

• Overview

1.1 Canadian Hansards

The main corpus for this assignment comes from the o cial records (Hansards) of the 36^th Canadian Parliament, including debates from both the House of Representatives and the Senate. This corpus is available at /u/cs401/A2/data/Hansard/ and has been split into Training/ and Testing/ directories.

This data set consists of pairs of corresponding les (*.e is the English equivalent of the French *.f) in which every line is a sentence. Here, sentence alignment has already been performed for you. That is, the n^th sentence in one le corresponds to the n^th sentence in its corresponding le (e.g., line n in fubar.e is aligned with line n in fubar.f). Note that this data only consists of sentence pairs; many-to-one, many-to-many, and one-to-many alignments are not included.

1.2 Seq2seq

We will be implementing a simple seq2seq model, with and without attention, based largely on the course material. You will train the models with teacher-forcing and decode using beam search. We will write it in PyTorch version 1.2.0 (https://pytorch.org/docs/1.2.0/), which is the version installed on the teach.cs servers. For those unfamiliar with PyTorch, we suggest you rst read the PyTorch tutorial (https: //pytorch.org/tutorials/beginner/deep_learning_60min_blitz.html).

1.3 Tensors and batches

PyTorch, like many deep learning frameworks, operate with tensors, which are multi-dimensional arrays. When you work in PyTorch, you will rarely if ever work with just one bitext pair at a time. You’ll instead be working with multiple sequences in one tensor, organized along one dimension of the batch. This means that a pair of source and target tensors F and E actually correspond to multiple sequences

• = (F_1:⁽ⁿ_S⁾_(n) )_n2[1;N], E = (E_1:⁽ⁿ_T⁾_(n) )_n2[1;N]. We work with batches instead of individual sequences because: a) backpropagating the average gradient over a batch tends to converge faster than single samples, and b)

sample computations can be performed in parallel. For example, if we want to multiply source sequences F ⁽ⁿ⁾ and F ⁽ⁿ⁺¹⁾ with an embedding matrix W , we can tell one CPU core to compute the result for F ⁽ⁿ⁾ and another for F ⁽ⁿ⁺¹⁾, halving the overall time it would take to multiply them independently. Learning to work with tensors can be di cult at rst, but is integral to e cient computation. We suggest you read more about it in the NumPy docs (https://docs.scipy.org/doc/numpy/user/theory.broadcasting. html#array-broadcasting-in-numpy), which PyTorch borrows for tensors.

Copyright c 2020 University of Toronto. All rights reserved.

1.4 Di erences from the lectures

There are two changes to the seq2seq architectures that we make for this assignment. First, instead of scaled dot-product energy scores for attention score(a; b) = jaj ¹⁼²ha; bi, we’ll use the cosine similarity between vectors a and b:

ha; bi

score(a; b) = _{kak2 kbk2}

The second relates to how we calculate the rst hidden state for the decoder when we don’t use attention. Recall that a bidirectional recurrent architecture processes its input in both directions separately: the forward direction processes (x₁; x₂; : : : ; x_S) whereas the backward direction processes (x_S; x_{S 1}; : : : ; x₁).

The bidirectional hidden state concatenates the forward and backward hidden states for the same time

h_t = [h^forward_t; h^backward_t]. This implies h_S has processed all the input in the forward direction, but only one input in the backward direction (and vice versa for h₁). To ensure the decoder gets access to all input from both directions, you should initialize the rst decoder state

~	forward	backward	]
h1	= [hS	; h1

~

When you use attention, set h₁ = 0.

• Your tasks

2.1 Setup

You are expected to run your solutions on teach.cs. Both code and data are available in the /u/cs401/A2/ directory on teach. Speci cally, starter code is available in the code/ sub-directory. The Hansards parallel text data are located in the data/ sub-directory.

Copy the code from the code/ directory into your working directory to get started. You should have the les a2 bleu score.py, a2 abc.py, a2 encoder decoder.py, a2 training and testing.py, a2 dataloader.py, a2 run.py, test a2 bleu score.py, and test a2 encoder decoder.py.

2.2 Calculating BLEU scores

Modify a2 bleu score.py to be able to calculate BLEU scores on single reference and candidate strings.

We will be using the de nition of BLEU scores from the lecture slides:

BLEU = BP_C (p₁p₂ : : : p_n)⁽¹⁼ⁿ⁾

To do this, you will need to implement the functions grouper(…), n gram precision(…),

brevity penalty(…), and BLEU score(…). Make sure to carefully follow the doc strings of each function. Do not re-implement functionality that is clearly performed by some other function.

Your functions will operate on sequences (e.g., lists) of tokens. These tokens could be the words themselves (strings) or an integer ID corresponding to the words. Your code should be agnostic to the type of token used, though you can assume that both the reference and candidate sequences will use tokens of the same type.

2.3 Building the encoder/decoder

You are expected to ll out a number of methods in a2 encoder decoder.py. These methods belong to sub-classes of the abstract base classes in a2 abcs.py. The latter de nes the abstract classes EncoderBase, DecoderBase, and EncoderDecoderBase, which implement much of the boilerplate code necessary to get

a seq2seq model up and running. Though you are welcome to read and understand this code, it is not necessary to do so for this assignment. You will, however, need to read the doc strings in a2 abcs.py to understand what you’re supposed to ll out in a2 encoder decoder.py. Do not modify any of the code in a2 abcs.py.

A high-level description of the contents of the requirements for a2 encoder decoder.py follows here.

More details can be found in the doc strings in a2 fabcs,encoder decoderg.py.

2.3.1 Encoder

a2 encoder decoder.Encoder will be the concrete implementation of all encoders you will use. The encoder is always a multi-layer neural network with a bidirectional recurrent architecture. The encoder gets a batch of source sequences as input and outputs the corresponding sequence of hidden states from the last recurrent layer.

Encoder.init submodules(…) should be lled out to initialize a word embedding layer and a recur-rent network architecture. Encoder.get all rnn inputs(…) accepts a batch of source sequences F_1:⁽ⁿ_S⁾_(n) and lengths S⁽ⁿ⁾ and outputs word embeddings for the sequences x⁽_1:ⁿ_S⁾_(n) .

⁽ⁿ⁾

Encoder.get all hidden states(…) converts the word embeddings x_1:S(n) into hidden states for

⁽ⁿ⁾

the last layer of the RNN h_1:S(n) (note we’re using (n) here for the batch index, not the layer index).

2.3.2 Decoder without attention

a2 encoder decoder.DecoderWithoutAttention will be the concrete implementation of the decoders that do not use attention (so-called \transducer” models). Method implementations should thus be tailored to not use attention.

In order to feed the previous output into the decoder as input, the decoder can only process one step of input at a time and produce one output. Thus DecoderWithoutAttention is designed to process one slice of input at a time (though it will still be a batch of input for that given slice of time). The goal, then, is to take some target slice from the previous time step E_t⁽ⁿ⁾₁ and produce an un-normalized log-probability

distribution over target words at time step t, called logits⁽_tⁿ⁾. Logits can be converted to a categorical distribution using a softmax:

exp(logits(n))

P (yt(n) = ij : : 🙂 =

t;i

exp(logits

(n)

)

j

t;j

…)

DecoderWithoutAttention.init

submodules(

P should be lled out to initialize a word embedding

layer, a recurrent cell, and a feed-forward layer to convert the hidden state to logits.

~(n)

DecoderWithoutAttention.get

first

hidden

state(…)

produces h1

given the encoder hidden

states h⁽_1:ⁿ_S⁾_(n) .

DecoderWithoutAttention.get current rnn input(…) takes the previous target E_t⁽ⁿ⁾₁ (or the pre-

vious output y_t⁽ⁿ⁾₁ in testing) and outputs word embedding x~⁽_tⁿ⁾ for the current step.

							(n)	~(n)
DecoderWithoutAttention.get		current		hidden		state(…) takes x~t		and ht 1	and produces the
~(n)
current decoder hidden state ht 1.
						~(n)			(n)
DecoderWithoutAttention.get		current		logits(…) takes ht			and produces logitst			.

get current hidden states(…) and get current logits(…). The remaining methods must be re-implemented, but slightly modi ed for the attention context.

Two new methods must be implemented for DecoderWithAttention.

~(n)

DecoderWithAttention.get energy scores(…) takes in a decoder state h_t and all encoder hidden states h⁽_1:ⁿ_S⁾_(n) and produces energy scores for that decoder state but all encoder hidden states: e⁽_t;ⁿ_1:⁾_S(n) .

~(n)	(n)
DecoderWithAttention.attend(…) takes in a decoder state ht	and all encoder hidden states h1:S(n)

and produces the attention context vector c⁽_tⁿ⁾. Between get energy scores and attend, use

get attention weights(…) to convert e⁽_t;ⁿ_1:⁾_S(n) to _t;⁽ⁿ_1:⁾_S(n) , which has been implemented for you.

2.3.4 Putting it together: the Encoder/Decoder

a2 encoder decoder.EncoderDecoder coordinates the encoder and decoder. Its behaviour depends on whether it’s being used for training or testing. In training, it receives both F_1:⁽ⁿ_S⁾_(n) and E_1:⁽ⁿ_T⁾_(n) and outputs logits⁽_1:ⁿ_T⁾_(n) un-normalized log-probabilities over y_1:⁽ⁿ_T⁾_(n) . In testing, it receives only F_1:⁽ⁿ_S⁾_(n) and outputs K

(n;k)

paths from beam search per batch element n: y_{1:T (n;k)} .

EncoderDecoder.init submodules(…) initializes the encoder and decoder.

EncoderDecoder.get logits for teacher forcing(…) provides you the encoder output h⁽_1:ⁿ_S⁾_(n) and

the targets E_1:⁽ⁿ_T⁾_(n) and asks you to derive logits⁽_1:ⁿ_T⁾_(n) according to the MLE (teacher-forcing) objective. EncoderDecoder.update beam(…) asks you to handle one iteration of a simpli ed version of the beam search from the slides. While a proper beam search requires you to handle the set of nished paths f, update beam doesn’t need to. Letting (n; k) indicate the n^th batch elements’ k^th path:

(n;k!v)		~(n;k)
8n; k; v:bt;0	!v)	ht+1
bt;(n;k1		[bt;(n;k1		); v]
	(n;k!v)			(n;k)	~(n;k)
log P (bt			)	P (bt	) + log P (yt+1 = vjht+1	)

In a2 training and testing.compute batch total bleu(…), you are given reference (from the dataset) and candidate batches (from the model) in the target language and asked to compute the to-tal BLEU score over the batch. You will have to convert the PyTorch tensors in order to use

a2 bleu score.BLEU score(…).

In a2 training and testing.compute average bleu over dataset(…), you are to follow instruc-tions in the doc string and use compute batch total bleu(…) to determine the average BLEU score over a data set.

In a2 training and testing.train for epoch(…), once again follow the doc strings to iterate through a training data set and update model parameters using gradient descent.

2.5 Running the models

Once you have completed the coding portion of the assignment, it is time you run your models. In order to do so in a reasonable amount of time, you’ll have to train your models using a machine with a GPU. A number of teaching labs in the Bahen building have GPUs (listed in https://www.teach.cs.toronto. edu/faq.html#ABOUT4), but you must log in at the physical machines to use them (as opposed to remote access). Even on a GPU, the code can take upwards of 2 hours to complete in full. Be sure to plan accordingly!

If you have access to your own GPU, you may run this code locally and report the results. However, any modi cations you make to run the code locally must be reverted to work on teach before you submit!

You are going to interface with your models using the script a2 run.py. This script glues together the components you implemented previously. The only meaningful remaining code is in a2 dataloader.py, which converts the Hansard sentences into sequences of IDs. Su ce to say that you do not need to know how either a2 run.py nor a2 dataloader.py works, only use them (unless you are interested).

Run the following code block line-by-line from your working directory. In order, it:

1. Builds maps between words and unique numerical identi ers for each language.

2. Splits the training data into a portion to train on and a hold-out portion.

3. Trains the encoder/decoder without attention and stores the model parameters.

4. Trains the encoder/decoder with attention and stores the model parameters.

5. Returns the average BLEU score of the encoder/decoder without attention on the test set.

6. Returns the average BLEU score of the encoder/decoder with attention on the test set.

TRAIN=/h/u1/cs401/A2/data/Hansard/Training/

TEST=/h/u1/cs401/A2/data/Hansard/Testing/

# 1.

python3.7 a2_run.py vocab $TRAIN e vocab.e.gz python3.7 a2_run.py vocab $TRAIN f vocab.f.gz # 2.

python3.7 a2_run.py split $TRAIN train.txt.gz dev.txt.gz

# 3.

python3.7 a2_run.py train $TRAIN \

vocab.e.gz vocab.f.gz \

train.txt.gz dev.txt.gz \

model_wo_att.pt.gz \

–device cuda

# 4.

python3.7 a2_run.py train $TRAIN \

vocab.e.gz vocab.f.gz \

train.txt.gz dev.txt.gz \

model_w_att.pt.gz \

–with-attention \

–device cuda

# 5.

python3.7 a2_run.py test $TEST \

vocab.e.gz vocab.f.gz model_wo_att.pt.gz \

–device cuda

# 6.

python3.7 a2_run.py test $TEST \

vocab.e.gz vocab.f.gz model_w_att.pt.gz \

–with-attention –device cuda

Steps 1 and 2 should not fail and need only be run once. Step 3 onward depend on the correctness of your code.

In a le called analysis.txt, provide the following:

The printout after every epoch of the training loop of both the model with attention and without. Clearly indicate which is which.

The average BLEU score reported on the test set for each model. Again, clearly indicate which is which.

A brief discussion on your ndings. Was there a discrepancy in between training and testing results? Why do you think that is? If one model did better than the other, why do you think that is?

2.6 Bonus [up to 15 marks]

We will give bonus marks for innovative work going substantially beyond the minimal requirements. How-ever, your overall mark for this assignment cannot exceed 100%. Submit your write-up in bonus.txt.

You may decide to pursue any number of tasks of your own design related to this assignment, although you should consult with the instructor or the TA before embarking on such exploration. Certainly, the rest of the assignment takes higher priority. Some ideas:

Perform substantial data analysis of the error trends observed in each method you implement. This must go well beyond the basic discussion already included in the assignment.

There are many possible ways to assemble attentions for the encoder / decoder. For example, dot-product attention similar to (Vaswani et al., 2017)¹, and structured self attention (Lin et al., 2017)². Analyze several attention mechanisms, compare their performances, and include discussions towards their reasons of the performance di erences.

• https://arxiv.org/abs/1706.03762

• https://arxiv.org/abs/1703.03130

• Submission requirements

This assignment is submitted electronically. Submit your assignment on MarkUs. Do not tar or compress your les, and do not place your les in subdirectories. Do not format your discussion as a PDF or Word document | use plain text only. You should submit:

1. The les a2 bleu score.py, a2 encoder decoder.py, and a2 training and testing.py that you lled out according to assignment speci cations. We will not accept a2 abc.py, a2 dataloader.py, nor a2 run.py – your assignment must be compatible with the versions we provided you.

2. Your write-up on the experiment in analysis.txt.

3. If you are submitting a bonus, tell us what you’ve done by submitting a write-up in bonus.txt. Please distribute bonus code amongst the above *.py les, being careful not to break functions, methods, and classes related to the assignment requirements.

You should not submit any additional les that you generated to train and test your models. For example, do not submit your model parameter les *.pt.gz or vocab les *.fe,fg.gz. Only submit the above les. Additional source les containing helper functions are not permitted.

• Suggestions

A.1 Check Piazza regularly

Updates to this assignment as well as additional assistance outside tutorials will be primarily distributed via Piazza (http://piazza.com/utoronto.ca/winter2020/csc4012511/home). It is your responsibility to check Piazza regularly for updates.

A.2 Using your own computer

If you want to do some or all of this assignment on your laptop or other computer, you will have to do the extra work of downloading and installing the requisite software and data. You take on the risk that your computer might not be adequate for the task. You are strongly advised to upload regular backups of your work to teach.cs, so that if your machine fails or proves to be inadequate, you can immediately continue working on the assignment at teach.cs. When you have completed the assignment, you should try your programs out on teach.cs to make sure that they run correctly there. A submission that does not work on teach.cs will get zero marks.

A.3 Unit testing

We strongly recommend you test the methods and functions you’ve implemented prior to running the train-ing loop. You can test actual output against expected input for complex methods like update beam(…). The Python 3.7 teach environment has installed pytest (https://docs.pytest.org/en/5.1.2/). We have included some preliminary tests for BLEU score(…) and update beam(…). You can run your test suite on teach by calling

python3.7 -m pytest

While the test suite will execute initially, the provided tests will fail until you implement the necessary methods and functions. While passing these initial tests is a necessity for full marks, they are not su cient on their own. Please be sure to add your own tests.

Unit testing is not a requirement, nor will you receive bonus marks for it.

A.4 Debugging remotely

While you will be unable to use the teaching labs’ GPUs remotely, you can still debug your program remotely on the teach server on the CPU. The following commands may be used to set up a smaller task with fewer parameters and a much shorter runtime.

# Variables TRAIN and TEST as before.

export OMP_NUM_THREADS=4 # avoids a libgomp error on teach

• create an input and output vocabulary of only 100 words python3.7 a2_run.py vocab $TRAIN e vocab_tiny.e.gz –max-vocab 100 python3.7 a2_run.py vocab $TRAIN f vocab_tiny.e.gz –max-vocab 100

• only use the proceedings of 4 meetings, 3 for training and 1 for dev python3.7 a2_run.py split $TRAIN train_tiny.txt.gz dev_tiny.txt.gz –limit 4

• use far fewer parameters in your model

python3.7 a2_run.py train $TRAIN \

vocab_tiny.e.gz vocab_tiny.f.gz \

train_tiny.txt.gz dev_tiny.txt.gz \

model.pt.gz \

–epochs 2 \

–word-embedding-size 51 \

–encoder-hidden-size 101 \

–batch-size 5 \

–cell-type gru \

–beam-width 2

Each epoch on teach should be less than 30 seconds using these settings. Note that your BLEU will likely in the reduced vocabulary condition – even using very few parameters – since your model will end up learning to output the out-of-vocabulary symbol. Do not report your ndings on the toy task in analysis.txt.

You can (and should) experiment with di erent sizes, types, and widths before running. You can check what you can modify with the command a2 run.py -h. At some point, you may come across the error:

RuntimeError: Beam search has not finished by t=100. Increase …

This just means your model failed to output an end-of-sequence token after t = 100. This does not necessarily mean you made a mistake – you just might’ve found a parameter combination that fails to learn anything. Try increasing the number of parameters, the number of proceedings, and/or changing the cell type. If the problem persists, you might have a bug.

A.5 Recurrent cell type

You’ll notice that the code asks you to set up a di erent recurrent cell type depending on the setting of the attribute self.cell type. This could be an LSTM, GRU, or RNN (the last refers to the simple linear weighting h_t = (W [x; h_{t 1}] + b) that you saw in class). The three cell types act very similarly – GRUs and RNNs are largely interchangeable from a programming perspective – except the LSTM cell often requires you to carry around both a cell state and a hidden state. Pay careful attention to the documentation for when h t, htilde t, etc. might actually be a pair of the hidden state and cell state as opposed to just a hidden state. Sometimes no change is necessary to handle the LSTM cell. Other times you might have to repeat an operation on the elements individually. Take advantage of the following pattern:

if self.cell_type == ’lstm’:

• do something

else:

• do something else

Be sure to rerun training with di erent cell types (i.e. use the ag –cell-type) to ensure your code can handle the di erence.

• Teaching lab reservations

The teaching labs are frequently booked for courses in order to perform course lab work. As a result, workstations will be occupied during these times and, even if you were able to nd a seat, you might be asked to leave. Below is a schedule of the days of the week and the times various labs are booked during the term ( marks occupied).

time	BA2200		BA3175		BA3185	BA3195
			Monday
10-11am
12-2pm
2-3pm
8-9pm
			Tuesday
1-3pm
6-8pm
8-9pm
		Wednesday
12-2pm
2-4pm
4-5pm
6-8pm
			Thursday
9-9pm
			Friday
10-12pm
1-4pm
4-6pm

• Variable names and slides

We try to match the variable names in a2 abc.py to those in the lecture slides on machine translation.

The table below serves as reference for converting between the two.

In general, we denote a speci c indexed value of a variable from the slides, such as E_t, with an underscored variable name, e.g. E t. When an index is omitted, it means the variable contains all the indexed values at once, e.g. F corresponds to F_1:S.

Note that the slides are 1-indexed, whereas code is 0-indexed. Also, all variables in the PyTorch code are batched, but the slides only look at one sequence at a time.

Variable

Slides

Notes

F

F1:S

Source sequence.

F

lens

S

In the code, the maximum-length source sequence in the

batch is said to have length S. The actual length of each

sequence in the batch (before padding) is stored in F

lens.

x

x

Encoder RNN inputs.

h

h1:S

Encoder hidden states.

Always refers to the last encoder

layer’s hidden states, with both directions concatenated.

~

htilde

0

h1

The rst decoder hidden state.

E

tm1

Et

1

The target token at t

1 (previous).

xtilde

t

x~t

Decoder RNN input at time t (current).

~

htilde

t

ht

Decoder hidden state at time t (current).

For the LSTM

architecture, this can be a pair with the cell state. Note in

the beam search update htilde

t also includes paths, i.e.

~(1:K)

.

ht

logits

t

log P (ytj : : 🙂 + C

Un-normalized log-probabilities over the target vocabulary

at time t (current). Pre-softmax.

E

E1:T

Target sequence.

logits

log P (ytj : : 🙂1:T + C

Un-normalized log-probabilities over the the target vocabu-

lary across each time step. Pre-softmax.

(1:K)

b

tm1

1

bt 1;1

All pre xes in the beam search at time t

1 (previous).

logpb

tm1

log P (bt(1:1K))

The log-probabilities of the beam search pre xes up to time

t

1 (previous).

logpy

t

log P (ytj : : 🙂

Valid (normalized) log-probabilities over the target vocabu-

lary at time t (current). Post-softmax.

b

t

0

bt;(1:0

K)

Decoder hidden states at time t (current).

The di erence

(1:K)

~(1:K)

between bt;0

and ht

is contextual: the latter points to

the paths in the beam before the update, the former after

the update.

b

t

1

bt;(1:1

K)

All pre xes in the beam seach at time t (current).

logpb

t

log P (bt(1:K))

The log-probabilities of the beam search pre xes up to time

t (current).

c

t

ct

Context vector (for attention) at time t (current).

alpha

t

t;1:S

Attention weights over all source times at target time t (cur-

rent).

e

t

et;1:S

Energy scores (for attention) over all source times at target

time t (current).

11