RNN & LSTM

Lecture 5

Language Models Recap

Jurafsky & Martin chapter 3

Ngram Language Models

Naive first attempt:

​

​

w_a^b = sequence w_a, w_a+1, w_a+2, …, w_b-1, w_b

We measure P(w_i | w₁^i-1) by counting the number of times the sequence w₁^i-1 happens in the training set, and measuring the percent of times it was followed by w_i

What is wrong with this?

Naive example

P(“Please turn your homework in”)

= P(sequence starts with “Please”)*P(second word is “turn” | first word is “Please”)

* P(third word is “your” | first two words are “Please turn”)�* P(fourth word is “homework” | first three words are “Please turn your”)�* P(fifth word is “in” | first four words are “Please turn your homework”)

​

By the end of the document, the P will be conditioned on the entire document, which only happens once. So it will just memorize that one document

Ngram Language Models

Rather than using the entire previous sequence, we use only the last n terms

​

The probability of the sequence is:

​

​

We calculate these conditional probabilities from the training set:

Ngram Language Model Example

In this example, N=2

• If N is bigger, the leftmost column will be sequences of words

We use the Berkeley Restaurant Project dataset, which looks like this:

Ngram Language Model Example

P(<s> i want english food </s>)

= P(i|<s>) P(want|i) P(english|want) P(food|english) P(</s>|food)

= .25 × .33 × .0011 × 0.5 × 0.68

= .000031

​

P(<s> i want chinese food </s>)

= P(i|<s>) P(want|i) P(chinese|want) P(food|chinese) P(</s>|food)

= .25 × .33 × .0065 × 0.5 × 0.52

= 0.000139

Ngram Language Models: Practical Considerations

• When N > 2, the first few probabilities have “dummy” words
• E.g. For N = 3 and a sentence starting with “I” we use P(I | <s><s>)
• We often combine N = 2, 3, … up to the real N
• Use a weighted sum of the probabilities
• In the code, we usually use log-probabilities
• We often use Laplace add-k smoothing (like with Naive Bayes) to deal with unknown words (out-of-vocabulary or OOV) and ngram sequences
• Another way to deal with OOV is in the training set, label all words that appear less than n times as <UNK>. Test set OOV words are also <UNK>

Ngram Language Models: Generating Sentences

• Start with <s>.
• Since we have a probability distribution for P(w | <s>), we randomly pick the next word using those probabilities.
• Continue randomly picking the next word according to the probability distributions until you reach </s>.

Perplexity

• Extrinsic evaluation = see how using the language model helps with a downstream task
• Intrinsic evaluation = check perplexity on a test set of text

​

​

​

​

​

• Lower perplexity → text is more likely. Higher perplexity → text is less likely
• Smaller perplexity on the test set means your language model was better
• LMs tested on WSJ corpus:

Neural Networks & Deep Learning

Jurafsky & Martin chapters 7 & 9

Neural Networks

The network that we saw for Word2Vec is an example of a fully connected neural network with 1 hidden layer

• The elements of the vectors in each layer are the neurons
• “Fully connected” means that each neuron in each layer is used to calculate each neuron in the next layer
• It was also “feedforward” because the computation goes from each layer to the next (no looping back to previous layers)

Input layer

Output layer

Hidden layer

Building Block: Perceptron

• A perceptron is a linear classifier
• A weight for each feature, plus a bias

1

(bias)

> 0?

Neural unit: Perceptron + activation function

• Why? differentiable, has numbers between 0 and 1
• As before, x₁, x₂, … are input and y is output
• w₁, w₂, … and b are the weights we want to learn
• Sigmoid is a popular activation function

Multi-layer Perceptrons (MLP)

U = W[2]

Each g is an activation function

including g[2], which is softmax

Training a Neural Network

• Minimize a loss function
• Common loss function for classification: cross-entropy loss (aka log-loss or negative log-likelihood)
• y_i is the true labels and ŷ_i is the output

https://ml-cheatsheet.readthedocs.io/en/latest/loss_functions.html

Training a neural net: Backpropagation

• Forward Pass: present training input to network and calculate output
• Backward Pass: calculate error gradient and update weights starting at output layer going backwards

Activation functions

Activation functions

Activation functions

More useful if you don’t just want {0,1} output, and you want numbers between 0 and 1 (for example, if you have a classifier with multiple classes and want to compare numbers for each)

Activation functions

Scaled version of sigmoid. It just has a “stronger” derivative.

Note:

Activation functions

Since the range is [0, inf), it can “blow up” the activation.

​

Not as easy for classification as the functions with range [0,1].

​

Since the derivative in negative section is 0, it can cause neurons to “die” (no update to weights). Solution: make the horizontal line into a very slightly tilted line → “leaky ReLu”

​

Since negative values → 0, ReLu is less costly and overtrains less.

Hyperparameters

• Learning rate: “step size” in direction of gradient (usually: start with ~0.01 and decrease over iteration)
• Usually: try a few different (starting) learning rates, and see what fits best (Hyperparameter Tuning)
• Batch size: number of training examples you see before taking a step in direction of gradient (usually: as big as fits in RAM)
• Epochs: number of times iterate over entire training set (usually: as long as willing to wait, with early stopping so you stop if gradient of loss becomes 0)

Naive Neural Language Model: Sliding Window

• Feedforward neural LMs are no longer SOTA, but the basics still apply
• Predict each next word
• Train using cross entropy loss for the correct next word

​

• Represent inputs using word embeddings (this helps because similar words are similar)

Naive Neural LM: Sliding Window

• Pretraining = learning the word embeddings via another method (like Word2Vec) beforehand
• To learn the embeddings while training for the downstream task, represent the inputs as one-hot vectors and add another layer E

• It is the same matrix E for all steps, but it still works because multiplying by the one-hot makes it select the part that is specific to the given input word
• This helps if your task only cares about certain aspects of words (e.g. sentiment)

Naive Neural Language Model: Sliding Window

• Output of each window has no impact on next window
• Fixed window size → cannot use information from parts of sequence outside of the window
• Has to learn the same pattern in multiple “locations” in the features (ex. “the ground” appears as different features in different iterations, so any patterns have to be learned in multiple locations)

Sequences

• Non-sequential machine learning takes input from a single point in time, and outputs a prediction or classification:

y = f(x(t))

• Now we look at sequential inputs where the output y can depend on more than just the immediate input:

y = f(s(t)) = F(x(t), x(t-1), …, x(1))

Solution: Recurrent Neural Network

• The hidden state can loop back to itself to use again with the next term in the sequence
• No fixed length

Training a Recurrent Neural Network

• Forward pass: process the sequence
• Backward pass: Backpropagation Through Time
• Note: since the input at each step affects multiple outputs (and therefore different parts of loss), we “assign blame” proportionally to weights when updating weights in gradient descent

Structure

• For each epoch (entire training set):
• For each batch:
• Loss = 0
• For each sequence in this batch:
• Loss += this sequence’s loss (includes a loop over the words in this sequence)
• Backwards pass over that batch (direction of loss’s gradient)

Recurrent Neural Language Models

• Avoid the Markov assumption made by Ngram and Sliding Window Language Models:
• At each step, the input to the RNN is the word embedding for the current word
• Softmax on the hidden layer to get the probability distribution for the next word

​

• Train it to predict the next word
• Cross-entropy loss

Generation with Recurrent Neural Language Models

• Called autoregressive generation
• Shannon’s Method: do generation the same way we did with Ngram language models, where we start with <s> and randomly pick the next word using the probabilities until we pick </s> (or reach a fixed length limit)
• Machine translation, summarization, and question answering work by using a variation of this, but with the last hidden state of the “encoder” RNN instead of <s>

Sequence Labeling with RNNs

• Task: label each input word (e.g. POS tags)
• Inputs: word embeddings
• Outputs: tag / label for each word
• Common algorithm: use the probabilities learned via this task in a previously covered algorithm such as Viterbi
• Common way to draw RNN →^

Sequence Classification with RNNs

• Task: classify the entire document
• Inputs: word embeddings (for each word in the document)
• Pass the final hidden layer into a feedforward network
• There is no loss at each step, only at the end

Stacked RNNs

• Take the sequence of hidden layers as input to another RNN
• This has been shown to help detect layers of abstraction (the same way our eyes and conv. neural networks use pixels to detect edges and then use edges to detect shapes)
• This is slow

Bidirectional RNNs

• One RNN goes forward as usual
• Another RNN starts from the last word and goes backwards
• Hidden layer at each step = combination of the hidden state from the forward and backward RNNs
• Combine using concatenation, addition, multiplication, or averaging

Bidirectional RNN

Bidirectional RNN for classification

Further reading

• https://www.geeksforgeeks.org/introduction-to-recurrent-neural-network/
• https://stanford.edu/~shervine/teaching/cs-230/cheatsheet-recurrent-neural-networks
• https://colah.github.io/posts/2015-08-Understanding-LSTMs/

​

​

Long Short-Term Memory (LSTM)

• Vanishing Gradients problem: with a regular RNN, due to the multiplications in the chain rule, words at the beginning of a sequence have less of an impact on the output than words at the end of the sequence
• This is why in NLP, we usually use an LSTM
• We address this by adding a context layer and three “gates”
• Each gate has a feedforward layer, a sigmoid activation, and then pointwise multiplication with the layer being gated
• The sigmoid almost turns the output of the feedforward layer into a binary mask (sigmoid pushes numbers close to 0 and 1)
• This helps tell the network which elements of the layer being gated are important to remember
• The gates are the forget gate, add gate, and output gate

Long Short-Term Memory

Forget gate

Previous context

Previous hidden state

Current input

Current hidden state

Current context

Add gate

Output gate

sigmoid

sigmoid

g is the part that came from RNN (with a tanh activation function)

​

f, i, and o are sigmoided and used as the masks for the forget, add, and output gates, respectively

​

Output gate decides what is important for current output as opposed to later

sigmoid

Gated Recurrent Unit (GRU)

• LSTMs are expensive because for each of the three gates and also the original RNN layer g, you have to learn a matrix to multiply for the hidden state and a matrix to multiply for the current input - this is 8 sets of weights
• This is usually worth it
• RNNs have only 2 sets of

weights

• GRUs have just 2 gates:
• reset and update
• (in addition to the original

RNN layer)

• GRU has no context layer

Subwords

Downsides to representing entire words as embeddings:

• Some lexicons have too many words
• Unknown words (rare words and misspellings)
• Morphological information is useful

​

Approaches to addressing this:

• Character ngrams
• Subwords based on phonetic analysis
• Morphological analysis to get linguistically motivated word pieces (usually overkill)

RNNs with Subwords

The lower Bi-RNN processes sequences of characters, and the upper RNN processes sequences of words.

This way you can still get output per word.

The backprop goes from the output task all the way back to the character level.

RNNs can be any variation (LSTM, Bi-RNN, …)

Encoder-Decoder Models

• Also called Sequence to Sequence Models
• Two RNNs: one that “encodes” by taking input from the first sequence, and the other that “decodes” by taking the last hidden state from the encoder as input and generating a sequence
• Used for any task where the input and output are sequences
• Machine translation
• Summarization
• Question answering
• Dialogue

https://d2l.ai/chapter_recurrent-modern/seq2seq.html

Attention in Encoder-Decoder Models

• Another revelation in NLP in 2018
• Pass all the hidden states from the encoder RNN to the decoder RNN (not just the last hidden state)
• The decoder uses attention to figure out which encoder hidden states are relevant at each step
• Attention is just another learned parameter, a number for each encoder hidden layer for each decoding step, softmaxed to be between 0 and 1
• At each decoding step, concatenate the current hidden layer with a combination of the attention-multiplied encoder hidden states, and pass this vector into a feedforward layer to get the output word at this step

https://jalammar.github.io/visualizing-neural-machine-translation-mechanics-of-seq2seq-models-with-attention/

BERT

https://jalammar.github.io/illustrated-transformer/