started in a moment uh since it's now uh
12:30 are there any questions before we
get
started okay I don't see I don't see any
so I guess we can uh Jump Right In this
time I'll be talking about sequence
modeling and N first I'm going to be
talking about uh why why we do sequence
modeling what varieties of sequence
modeling exist and then after that I'm
going to talk about kind of three basic
techniques for sequence modeling namely
recurrent neural networks convolutional
networks and
attention so when we talk about sequence
modeling in NLP I've kind of already
made the motivation for doing this but
basically NLP is full of sequential data
and this can be everything from words
and sentences or tokens and sentences to
uh characters and words to sentences in
a discourse or a paragraph or a
document um it can also be multiple
documents in time multiple social media
posts whatever else you want there's
just you know sequences all over
NLP and I mentioned this uh last time
also but there's also long-distance
dependencies in language so uh just to
give an example there's agreement in
number uh gender Etc so in order to
create a fluent language model you'll
have to handle this agreement so if we
you say he does not have very much
confidence in uh it would have to be
himself but if you say she does not have
very much confidence in it would have to
be herself and this is this gender
agreement is not super frequent in
English but it's very frequent in other
languages like French or uh you know
most languages in the world in some uh
way or
another then separately from that you
also have things like selectional
preferences um like the Reign has lasted
as long as the life of the queen and the
rain has lasted as long as the life of
the clouds uh in American English the
only way you could know uh which word
came beforehand if you were doing speech
recognition is if you uh like had that
kind of semantic uh idea of uh that
these agree with each other in some way
and there's also factual knowledge
there's all kinds of other things uh
that you need to carry over long
contexts um these can be comp
complicated so this is a a nice example
so if we try to figure out what it
refers to here uh the trophy would not
fit in the brown suitcase because it was
too big what is it
here the trophy yeah and then what about
uh the trophy would not fit in the brown
suitcase because it was too
small suit suitcase right um does anyone
know what the name of something like
this is
has anyone heard of this challenge uh
before no one okay um this this is
called the winegrad schema challenge or
these are called winegrad schemas and
basically winterr schemas are a type
of they're type of kind of linguistic
challenge where you create two paired uh
examples
that you vary in very minimal ways where
the answer differs between the two um
and so uh there's lots of other examples
about how you can create these things
and they're good for testing uh whether
language models are able to do things
because they're able to uh kind of
control for the fact that you know like
the answer might be
um the answer might be very uh like
more frequent or less frequent and so
the language model could just pick that
so another example is we uh we came up
with a benchmark of figurative language
where we tried to figure out whether
language models would be able
to interpret figur figurative language
and I actually have the multilingual uh
version on the suggested projects uh on
the Piaza oh yeah that's one
announcement I posted a big list of
suggested projects on pza I think a lot
of people saw it you don't have to
follow these but if you're interested in
them feel free to talk to the contacts
and we can give you more information
about them um but anyway uh so in this
data set what we did is we came up with
some figurative language like this movie
had the depth of of a waiting pool and
this movie had the depth of a diving
pool and so then after that you would
have two choices this movie was uh this
movie was very deep and interesting this
movie was not very deep and interesting
and so you have these like like two
pairs of questions and answers and you
need to decide between them and
depending on what the input is the
output will change and so that's a good
way to control for um and test whether
language models really understand
something so if you're interested in
benchmarking or other things like that
it's a good parad time to think about
anyway that's a little bit of an aside
um so now I'd like to go on to types of
sequential prediction problems
and types of prediction problems in
general uh binary and multiclass we
already talked about that's when we're
doing for example uh classification
between two classes or classification
between multiple
classes but there's also another variety
of prediction called structured
prediction and structured prediction is
when you have a very large number of
labels it's not you know a finite number
of labels and uh so that would be
something like uh if you take in an
input and you want to predict all of the
parts of speech of all the words in the
input and if you had like 50 parts of
speech the number of labels that you
would have for each sentence
is any any
ideas 50 50 parts of speech and like
let's say for
wordss 60 um it it's every combination
of parts of speech for every words so
uh close but maybe the opposite it's uh
50 to the four because you have 50 50
choices here 50 choices here so it's a c
cross product of all of the
choices um and so that becomes very
quickly un untenable um let's say you're
talking about translation from English
to Japanese uh now you don't really even
have a finite number of choices because
the length could be even longer uh the
length of the output could be even
longer than the
C
rules
together makes it
fewer yeah so really good question um so
the question or the the question or
comment was if there are certain rules
about one thing not ever being able to
follow the other you can actually reduce
the number um you could do that with a
hard constraint and make things uh kind
of
and like actually cut off things that
you know have zero probability but in
reality what people do is they just trim
hypotheses that have low probability and
so that has kind of the same effect like
you almost never see a determiner after
a determiner in English um and so yeah
we're going to talk about uh algorithms
to do this in the Generation section so
we could talk more about that
that um but anyway the basic idea behind
structured prediction is that you don't
like language modeling like I said last
time you don't predict all of the the
whole sequence at once you usually
predict each element at once and then
somehow calculate the conditional
probability of the next element given
the the current element or other things
like that so that's how we solve
structured prediction
problems another thing is unconditioned
versus conditioned predictions so
uncondition prediction we don't do this
very often um but basically uh we
predict the probability of a a single
variable or generate a single variable
and condition pro prediction is
predicting the probability of an output
variable given an input like
this so um for unconditioned prediction
um the way we can do this is left to
right autoagressive models and these are
the ones that I talked about last time
when I was talking about how we build
language models um and these could be uh
specifically this kind though is a kind
that doesn't have any context limit so
it's looking all the way back to the
beginning of the the sequence and this
could be like an infinite length endr
model but practically we can't use those
because they would have too many
parameters they would be too sparse for
us to estimate the parameters so um what
we do instead with engram models which I
talked about last time is we limit the
the context length so we have something
like a trigram model where we don't
actually reference all of the previous
outputs uh when we make a prediction oh
and sorry actually I I should explain
how how do we uh how do we read this
graph so this would be we're predicting
number one here we're predicting word
number one and we're conditioning we're
not conditioning on anything after it
we're predicting word number two we're
conditioning on Word number one we're
predicting word number three we're
conditioning on Word number two so here
we would be uh predicting word number
four conditioning on Words number three
and two but not number one so that would
be like a trigram
bottle um so
the what is this is there a robot
walking around somewhere um Howard drill
okay okay' be a lot more fun if it was a
robot um so
uh the things we're going to talk about
today are largely going to be ones that
have unlimited length context um and so
we can uh we'll talk about some examples
here and then um there's also
independent prediction so this uh would
be something like a unigram model where
you would just uh not condition on any
previous
context there's also bidirectional
prediction where basically when you
predict each element you predict based
on all of the other elements not the
element itself uh this could be
something like a masked language model
um but note here that I put a slash
through here uh because this is not a
well-formed probability because as I
mentioned last time um in order to have
a well-formed probability you need to
predict the elements based on all of the
elements that you predicted before and
you can't predict based on future
elements so this is not actually a
probabilistic model but sometimes people
use this to kind of learn
representations that could be used
Downstream for some
reason cool is this clear any questions
comments
yeah so these are all um not
conditioning on any prior context uh so
when you predict each word it's
conditioning on context that you
previously generated or previously
predicted yeah so and if I go to the
conditioned ones these are where you
have like a source x uh where you're
given this and then you want to
calculate the conditional probability of
something else
so um to give some examples of this um
this is autor regressive conditioned
prediction and um this could be like a
SE a standard sequence to sequence model
or it could be a language model where
you're given a prompt and you want to
predict the following output like we
often do with chat GPT or something like
this and so
um yeah I I don't think you
can
yeah I don't know if any way you can do
a chat GPT without any conditioning
context um but there were people who
were sending uh I saw this about a week
or two ago there were people who were
sending things to the chat um to the GPD
3.5 or gp4 API with no input and it
would randomly output random questions
or something like that so that's what's
what happens when you send things to uh
to chat GPT without any prior
conditioning conts but normally what you
do is you put in you know your prompt
and then it follows up with your prompt
and that would be in this uh in this
Paradigm there's also something called
non-auto regressive condition prediction
um and this can be used for something
like sequence labeling or non- autor
regressive machine translation I'll talk
about the first one in this class and
I'll talk about the the second one maybe
later um it's kind of a minor topic now
it used to be popular a few years ago so
I'm not sure whether it'll cover it but
um uh
yeah cool so the basic modeling Paradigm
that we use for things like this is
extracting features and predicting so
this is exactly the same as the bag of
wordss model right I the bag of wordss
model that I talked about the first time
we extracted features uh based on those
features we made predictions so it's no
different when we do sequence modeling
um but the methods that we use for
feature extraction is different so given
in the input text X we extract features
H and predict labels
Y and for something like text
classification what we do is we uh so
for example we have text classification
or or sequence labeling and for text
classification usually what we would do
is we would have a feature extractor
from this feature extractor we take the
sequence and we convert it into a single
vector and then based on this Vector we
make a prediction so that that's what we
do for
classification um for sequence labeling
normally what we do is we extract one
vector for each thing that we would like
to predict about so here that might be
one vector for each
word um and then based on this uh we
would predict something for each word so
this is an example of part of speech
tagging but there's a lot of other
sequence labeling tasks
also and what tasks exist for something
like sequence labeling so sequence lab
in is uh a pretty
big subset of NLP tasks you can express
a lot of things as sequence labeling and
basically given an input text X we
predict an output label sequence y of
equal length so this can be used for
things like part of speech tagging to
get the parts of speech of each word um
it can also be used for something like
lemmatization and litiz basically what
that is is it is predicting the base
form of each word uh and this can be
used for normalization if you want to
find like for example all instances of a
a particular verb being used or all
instances of a particular noun being
used this is a little bit different than
something like stemming so stemming
normally what stemming would do is it
would uh chop off the plural here it
would chop off S but it wouldn't be able
to do things like normalized saw into C
because uh stemming uh just removes
suffixes it doesn't do any sort of
normalization so that's the difference
between lonization and
stemon there's also something called
morphological tagging um in
morphological tagging basically what
this is doing is this is a
more advanced version of part of speech
tagging uh that predicts things like
okay this is a a past tense verb uh this
is a plural um this is a particular verb
form and you have multiple tags here
this is less interesting in English
because English is kind of boring
language morphology morphologically it
doesn't have a lot of conjugation and
other stuff but it's a lot more
interesting in more complex languages
like Japanese or Hindi or other things
like
that Chinese is even more boring than
English so if you're interested in
Chinese then you don't need to worry
about
that cool um but actually what's maybe
more widely used from the sequence
labeling perspective is span labeling
and here you want to predict spans and
labels and this could be uh named entity
recognitions so if you say uh Graham nub
is teaching at Carnegie melan University
you would want to identify each entity
is being like a person organization
Place governmental entity other stuff
like that um there's also
uh things like syntactic chunking where
you want to find all noun phrases and
verb phrases um also semantic role
labeling where semantic role labeling is
uh demonstrating who did what to whom so
it's saying uh this is the actor the
person who did the thing this is the
thing that is being done and this is the
place where it's being done so uh this
can be useful if you want to do any sort
of analysis about who does what to whom
uh other things like
that um there's also a more complicated
thing called an entity linking which
isn't really a span linking task but
it's basically named entity recognition
and you link it to um and you link it to
to like a database like Wiki data or
Wikipedia or something like this and
this doesn't seem very glamorous perhaps
you know a lot of people might not you
might not
sound like immediately excit be
immediately excited by entity linking
but actually it's super super important
for things like news aggregation and
other stuff like that find all the news
articles about the celebrity or
something like this uh find all of the
mentions of our product um our company's
product and uh social media or things so
it's actually a really widely used
technology and then finally span
labeling can also be treated as sequence
labeling um and the way we normally do
this is we use something called bio tags
and uh here you predict the beginning uh
in and out tags for each word or spans
so if we have this example of spans uh
we just convert this into tags uh where
you say uh begin person in person o
means it's not an entity begin
organization in organization and then
you canvert that back into um into these
spans so this makes it relatively easy
to uh kind of do the span
prediction cool um so now you know uh
now you know what to do if you want to
predict entities or other things like
that there's a lot of models on like
hugging face for example that uh allow
you to do these things are there any
questions uh before I move
on okay
cool I'll just go forward then so um now
I'm going to talk about how we actually
model these in machine learning models
and there's three major types of
sequence models uh there are other types
of sequence models but I'd say the great
majority of work uses one of these three
different types and the first one is
recurrence um what recurrence does it is
it conditions on representations on an
encoding of the
history and so the way this works works
is essentially you have your input
vectors like this uh usually word
embeddings or embeddings from the
previous layer of the model and you have
a recurrent neural network and the
recurrent neural network um at the very
beginning might only take the first
Vector but every subsequent step it
takes the input vector and it takes the
hidden Vector from the previous uh
input and the uh then you keep on going
uh like this all the way through the
sequence the convolution is a
conditioning representations on local
context so you have the inputs like this
and here you're conditioning on the word
itself and the surrounding um words on
the right or the left so um you would do
something like this this is a typical
convolution where you have this this
certain one here and the left one and
the right one and this would be a size
three convolution you could also have a
size five convolution 7 n you know
whatever else um that would take in more
surrounding words like
this and then finally we have attention
um and attention is conditioned
representations at a weighted average of
all tokens in the sequence and so here
um we're conditioning on all of the
other tokens in the sequence but um the
amount that we condition on each of the
tokens differs uh between
so we might get more of this token less
of this token and other things like that
and I'll go into the mechanisms of each
of
these one important thing to think about
is uh the computational complexity of
each of these and um the computational
complexity can be
expressed as the sequence length let's
call the sequence length n and
convolution has a convolution window
size so I'll call that
W so does anyone have an idea of the
computational complexity of a recurrent
neural
network so how um how quickly does the
computation of a recurrent neural
network grow and one way you can look at
this is uh figure out the number of
arrows uh that you see
here yeah it's it's linear so it's
basically
n um what about
convolution any other ideas any ideas
about
convolution n yeah NW n
w and what about
attention n squar
yeah so what you can see is um for very
long
sequences um for very long sequences the
asymptotic complexity of running a
recurrent neural network is uh lower so
you can run a recurrent neural network
over a sequence of length uh you know 20
million or something like that and as
long as you had enough memory it would
take a linear time but um if you do
something like attention over a really
long sequence it would be more difficult
there's a lot of caveats here because
attention and convolution are easily
paral
parallelized uh whereas uh recurrence is
not um and I'll talk about that a second
but any anyway it's a good thing to keep
in
mind cool um so the next the first
sequence model I want to introduce is
recurrent neural networks oh um sorry
one other thing I want to mention is all
of these are still used um it might seem
that like if you're very plugged into
NLP it might seem like Well everybody's
using attention um so why do we need to
learn about the other ones uh but
actually all of these are used and
usually recurrence and convolution are
used in combination with attention uh in
some way for particular applications
where uh like uh recurrence or a
convolution are are useful so I'll I'll
go into details of that
l so let's talk about the first sequence
model uh recurrent neural networks so
recurrent neural networks um they're
basically tools to remember information
uh they were invented in uh around
1990 and
the way they work is a feedforward
neural network looks a bit like this we
have some sort of look up over the
context we calculate embeddings we do a
transform we get a hidden State and we
make the
prediction whereas a recurrent neural
network uh feeds in the previous hidden
State and a very simple Elman style
neural network looks um or I'll contrast
the feed forward neural network that we
already know with an Elman style neural
network um
uh recurrent neural network so basically
the feed forward Network that we already
know does a um linear transform over the
input and then it runs it through a
nonlinear function and this could be
like a tan function or a Ru function or
anything like that in a recurrent neural
network we add uh multiplication by the
hidden the previous hidden state so it
looks like
this and so if we look at what
processing a sequence looks like uh
basically what we do is we start out
with an initial State this initial State
could be like all zeros or it could be
randomized or it could be learned or
whatever
else and then based on based on this uh
we run it through an RNN function um and
then you know use calculate the hidden
State use it to make a prediction uh we
have the RNN function uh make a
prediction RNN make a prediction RNN
make a
prediction so one important thing here
is that this RNN is exactly the same
function
no matter which position it appears in
and so because of that we just no matter
how long the sequence becomes we always
have the same number of parameters which
is always like really important for a
sequence model so uh that's what this
looks like
here so how do we train
rnns um
basically if you remember we can trade
neural networks as long as we have a
directed e cyclic graph that calculates
our loss function and then for uh
forward propagation and back propagation
we'll do all the rest to calculate our
parameters and we uh we update the
parameters so the way this works is uh
let's say we're doing sequence labeling
in each of these predictions is a part
of speech uh each of these labels is a
true part of speech label or sorry each
of these predictions is like a
probability over the part parts of
speech for that sequence each of these
labels is a true part of speech label so
basically what we do is from this we
calculate the negative log likelihood of
the true part of speech we get a
loss and so now we have four losses uh
here this is no longer a nice directed
acyclic uh graph that ends in a single
loss function which is kind of what we
needed for back propagation right so
what do we do uh very simple we just add
them together uh we take the sum and now
we have a single loss function uh which
is the sum of all of the loss functions
for each prediction that we
made and that's our total loss and now
we do have a directed asli graph where
this is the terminal node and we can do
backr like
this this is true for all sequence
models I'm going to talk about today I'm
just illustrating it with recurrent
networks um any any questions here
everything
good
okay cool um yeah so now we have the
loss it's a Well form dag uh we can run
backrop so uh basically what we do is we
just run back propop and our loss goes
out uh back into all of the
places now parameters are tied across
time so the derivatives into the
parameters are aggregated over all of
the time
steps um and this has been called back
propagation through time uh since uh
these were originally invented so
basically what it looks like is because
the parameters for this RNN function are
shared uh they'll essentially be updated
they'll only be updated once but they're
updated from like four different
positions in this network
essentially yeah and this is the same
for all sequence uh sequence models that
I'm going to talk about
today um another variety of models that
people use are bidirectional rnns and
these are uh used when you want to you
know do something like sequence labeling
and so you just uh run two rnns you want
run one from the beginning one from the
end and concatenate them together like
this make predictions
cool uh any questions yeah if you run
the does that change your
complexity does this change the
complexity it doesn't change the ASM
totic complexity because you're
multiplying by two uh and like Big O
notation doesn't care if you multiply by
a constant but it it does double the Ty
that it would
do cool any
other
okay let's go forward um another problem
that is particularly Salient in rnns and
part of the reason why attention models
are so useful is Vanishing gradients but
you should be aware of this regardless
of whether like no matter which model
you're using and um thinking about it
very carefully is actually a really good
way to design better architectures if
you're going to be designing uh
designing
architectures so basically the problem
with Vanishing gradients is like let's
say we have a prediction task where
we're calculating a regression we're
inputting a whole bunch of tokens and
then calculating a regression at the
very end using a square air loss
function if we do something like this uh
the problem is if we have a standard RNN
when we do back
propop we'll have a big gradient
probably for the first RNN unit here but
every time because we're running this
through through some sort of
nonlinearity if we for example if our
nonlinearity is a t h function uh the
gradient of the tan H function looks a
little bit like
this and um here I if I am not mistaken
this Peaks at at one and everywhere else
at zero and so because this is peing at
one everywhere else at zero let's say um
we have an input way over here like
minus minus 3 or something like that if
we have that that basically destroys our
gradient our gradient disappears for
that particular unit um and you know
maybe one thing that you might say is oh
well you know if this is getting so
small because this only goes up to one
let's do like 100 time t
h as our uh as our activation function
we'll do 100 time tan H and so now this
goes up to 100 and now our gradients are
not going to disapp here but then you
have the the opposite problem you have
exploding gradients where it goes up by
100 every time uh it gets unmanageable
and destroys your gradient descent
itself so basically we have uh we have
this problem because if you apply a
function over and over again your
gradient gets smaller and smaller every
smaller and smaller bigger and bigger
every time you do that and uh you have
the vanishing gradient or exploding
gradient
problem um it's not just a problem with
nonlinearities so it also happens when
you do do your weight Matrix multiplies
and other stuff like that basically
anytime you modify uh the the input into
a different output it will have a
gradient and so it will either be bigger
than one or less than
one um so I mentioned this is a problem
for rnns it's particularly a problem for
rnns over long sequences but it's also a
problem for any other model you use and
the reason why this is important to know
is if there's important information in
your model finding a way that you can
get a direct path from that important
information to wherever you're making a
prediction often is a way to improve
your model
um improve your model performance and on
the contrary if there's unimportant
information if there's information that
you think is likely to be unimportant
putting it farther away or making it a
more indirect path so the model has to
kind of work harder to use it is a good
way to prevent the model from being
distracted by like tons and tons of
information um uh some of it
which may be irrelevant so it's a good
thing to know about in general for model
design so um how did RNN solve this
problem of uh of the vanishing gradient
there is a method called long short-term
memory
um and the basic idea is to make
additive connections between time
steps
and so addition is the
only addition or kind of like the
identity is the only thing that does not
change the gradient it's guaranteed to
not change the gradient because um the
identity function is like f
ofx equals X and if you take the
derivative of this it's one so you're
guaranteed to always have a gradient of
one according to this function so um
long shortterm memory makes sure that
you have this additive uh input between
time steps and this is what it looks
like it's not super super important to
understand everything that's going on
here but just to explain it very quickly
this uh C here is something called the
memory cell it's passed on linearly like
this and then um you have some gates the
update gate is determining whether uh
whether you update this hidden state or
how much you update given this hidden
State this input gate is deciding how
much of the input you take in um and
then the output gate is deciding how
much of uh the output from the cell you
uh you basically push out after using
the cells so um it has these three gates
that control the information flow and
the model can learn to turn them on or
off uh or something like that so uh
that's the basic uh basic idea of the
LSM and there's lots of other like
variants of this like gated recurrent
units that are a little bit simpler but
the basic idea of an additive connection
plus gating is uh something that appears
a lot in many different types of
architectures um any questions
here another thing I should mention that
I just realized I don't have on my
slides but it's a good thing to know is
that this is also used in uh deep
networks and uh multi-layer
networks and so
basically lstms uh this is
time lstms have this additive connection
between the member eel where you're
always
adding um adding this into to whatever
input you
get and then you you get an input and
you add this in you get an
input and so this this makes sure you
pass your gradients forward in
time there's also uh something called
residual connections which I think a lot
of people have heard of if you've done a
deep learning class or something like
that but if you haven't uh they're a
good thing to know residual connections
are if you run your input through
multiple
layers like let's say you have a block
here
let's let's call this an RNN for now
because we know um we know about RNN
already so
RNN so this this connection here is
called the residual connection and
basically it's adding an additive
connection before and after layers so um
this allows you to pass information from
the very beginning of a network to the
very end of a network um through
multiple layers and it also is there to
help prevent the gradient finishing
problem so like in a way you can view uh
you can view lstms what lstms are doing
is preventing loss of gradient in time
and these are preventing loss of
gradient as you go through like multiple
layers of the network and this is super
standard this is used in all like
Transformer models and llama and GPT and
whatever
else cool um any other questions about
that okay cool um so next I'd like to go
into convolution um one one thing I
should mention is rnns or RNN style
models are used extensively in very long
sequence modeling and we're going to
talk more about like actual
architectures that people use uh to do
this um usually in combination with
attention based models uh but they're
used in very long sequence modeling
convolutions tend to be used in um a lot
in speech and image processing uh and
the reason why they're used a lot in
speech and image processing is
because when we're processing
language uh we have like
um
this is
wonderful like this is wonderful is
three tokens in language but if we look
at it in speech it's going to be
like many many
frames so kind of
the semantics of language is already
kind of like if you look at a single
token you already get something
semantically meaningful um but in
contrast if you're looking at like
speech or you're looking at pixels and
images or something like that you're not
going to get something semantically
meaningful uh so uh convolution is used
a lot in that case and also you could
create a convolutional model over
characters as well
um so what is convolution in the first
place um as I mentioned before basically
you take the local window uh around an
input and you run it through um
basically a model and a a good way to
think about it is it's essentially a
feed forward Network where you can
catenate uh all of the surrounding
vectors together and run them through a
linear transform like this so you can
Cate XT minus XT XT
plus1 convolution can also be used in
Auto regressive models and normally like
we think of it like this so we think
that we're taking the previous one the
current one and the next one and making
a prediction based on this but this
would be good for something like
sequence labeling but it's not good for
for something like language modeling
because in language modeling we can't
look at the future right but there's a
super simple uh solution to this which
is you have a convolution that just
looks at the past basically um and
predicts the next word based on the the
you know current word in the past so
here you would be predicting the word
movie um this is actually essentially
equivalent to the feed forward language
model that I talked about last time uh
so you can also think of that as a
convolution
a convolutional language model um so
when whenever you say feed forward or
convolutional language model they're
basically the same uh modulo some uh
some details about striding and stuff
which I'm going to talk about the class
today cool um I covered convolution very
briefly because it's also the least used
of the three uh sequence modeling things
in NLP nowadays but um are there any
questions there or can I just run into
attention
okay cool I'll go into attention next so
uh the basic idea about
attention um
is that we encode uh each token and the
sequence into a
vector
um or so we we have input an input
sequence that we'd like to encode over
and we perform a linear combination of
the vectors weighted by attention weight
and there's two varieties of attention
uh that are good to know about the first
one is cross
atten where each element in a sequence
attends to elements of another sequence
and this is widely used in encoder
decoder models where you have one
encoder and you have a separate decoder
um these models the popular models that
are like this that people still use a
lot are T5 uh is a example of an encoder
decoder model or embar is another
example of encoder decoder model um but
basically the uh The Way Cross attention
works is we have for example an English
uh sentence here and we want to
translate it into uh into a Japanese
sentence and so when we output the first
word we would mostly uh upweight this or
sorry we have a we have a Japanese
sentence and we would like to translated
into an English sentence for example so
when we generate the first word in
Japanese means this so in order to
Output the first word we would first uh
do a weighted sum of all of the
embeddings of the Japanese sentence and
we would focus probably most on this
word up here C because it corresponds to
the word
this in the next step of generating an
out output uh we would uh attend to
different words because different words
correspond to is so you would attend to
which corresponds to is um when you
output n actually there's no word in the
Japanese sentence that correspon to and
so you might get a very like blob like
uh in attention weight that doesn't look
very uh that looks very smooth not very
peaky and then when you do example you'd
have strong attention on uh on the word
that corresponds to example
there's also self
attention and um self attention
basically what it does is each element
in a sequence attends to elements of the
same sequence and so this is a good way
of doing sequence encoding just like we
used rnns by rnns uh convolutional
neural networks and so um the reason why
you would want to do something like this
just to give an example let's say we
wanted to run this we wanted to encode
the English sentence before doing
something like translation into Japanese
and if we did that um this maybe we
don't need to attend to a whole lot of
other things because it's kind of clear
what this means but um
is the way you would translate it would
be rather heavily dependent on what the
other words in the sentence so you might
want to attend to all the other words in
the sentence say oh this is is co
cooccurring with this and example and so
if that's the case then well we would
need to translate it in this way or we'
need to handle it in this way and that's
exactly the same for you know any other
sort of
disambiguation uh style
task so uh yeah we do something similar
like this so basically cross attention
is attending to a different sequence
self attention is attending to the same
sequence so how do we do this
mechanistically in the first place so
like let's say We're translating from
Japanese to English um we would have uh
and we're doing it with an encoder
decoder model where we have already ENC
coded the
input sequence and now we're generating
the output sequence with a for example a
recurrent neural network um and so if
that's the case we have uh I I hate uh
like this and we want to predict the
next word so what we would do is we
would take the current state
here and uh we use something called a
query vector and the query Vector is
essentially the vector that we want to
use to decide what to attend
to we then have key vectors and the key
vectors are the vectors that we would
like to use to decide which ones we
should be attending
to and then for each query key pair we
calculate a
weight and we do it like this um this
gear here is some function that takes in
the uh query vector and the key vector
and outputs a weight and notably we use
the same function every single time this
is really important again because like
RNN that allows us to extrapolate
unlimited length sequences because uh we
only have one set of you know we only
have one function no matter how long the
sequence gets so we can just apply it
over and over and over
again uh once we calculate these values
we normalize so that they add up to one
using the softmax function and um
basically in this case that would be
like 0.76 uh etc etc oops
so step number two is once we have this
uh these
attention uh values here notably these
values aren't really probabilities uh
despite the fact that they're between
zero and one and they add up to one
because all we're doing is we're using
them to uh to combine together uh
multiple vectors so I we don't really
normally call them attention
probabilities or anything like that I
just call them attention values or
normalized attention values
is um but once we have these uh
attention uh attention weights we have
value vectors and these value vectors
are the vectors that we would actually
like to combine together to get the uh
encoding here and so we take these
vectors we do a weighted some of the
vectors and get a final final sum
here and we can take this uh some and
use it in any part of the model that we
would like um and so is very broad it
can be used in any way now the most
common way to use it is just have lots
of self attention layers like in
something in a Transformer but um you
can also use it in decoder or other
things like that as
well this is an actual graphical example
from the original attention paper um I'm
going to give some other examples from
Transformers in the next class but
basically you can see that the attention
weights uh for this English to French I
think it's English French translation
task basically um overlap with what you
would expect uh if you can read English
and French it's kind of the words that
are semantically similar to each other
um it even learns to do this reordering
uh in an appropriate way here and all of
this is completely unsupervised so you
never actually give the model
information about what it should be
attending to it's all learned through
gradient descent and the model learns to
do this by making the embeddings of the
key and query vectors closer together
cool
um any
questions okay so um next I'd like to go
a little bit into how we actually
calculate the attention score function
so that's the little gear that I had on
my
uh my slide before so here Q is a query
and K is the key um the original
attention paper used a multi-layer layer
uh a multi-layer neural network to
calculate this so basically what it did
is it concatenated the query and key
Vector together multiplied it by a
weight Matrix calculated a tan H and
then ran it through uh a weight
Vector so this
is essentially very expressive
um uh it's flexible it's often good with
large data but it adds extra parameters
and uh computation time uh to your
calculations here so it's not as widely
used
anymore the uh other thing which was
proposed by long ad all is a bilinear
function um and a bilinear function
basically what it does is it has your
key Vector it has your query vector and
it has a matrix in between them like
this and uh then you calculate uh you
calculate the
alut
so
this is uh nice because it basically um
Can Transform uh the key and
query uh together
here
um people have also experimented with
DOT product and the dot product is
basically query times
key uh query transpose times key or
query. key this is okay but the problem
with this is then the query vector and
the key vectors have to be in exactly
the same space and that's kind of too
hard of a constraint so it doesn't scale
very well if you're um if you're working
hard uh if you're uh like training on
lots of data um then the scaled dot
product um the scale dot product here uh
one problem is that the scale of the dot
product increases as the dimensions get
larger and so there's a fix to scale by
the square root of the length of one of
the vectors um and so basically you're
multiplying uh you're taking the dot
product but you're dividing by the uh
the square root of the length of one of
the vectors uh does anyone have an idea
why you might take the square root here
if you've taken a machine
learning uh or maybe statistics class
you might have a an
idea any any ideas yeah it normalization
to make sure
because otherwise it will impact the
result because we want normalize one yes
so we do we do want to normalize it um
and so that's the reason why we divide
by the length um and that prevents it
from getting too large
specifically does anyone have an idea
why you take the square root here as
opposed to dividing just by the length
overall so um this is this is pretty
tough and actually uh we I didn't know
one of the last times I did this class
uh and had to actually go look for it
but basically the reason why is because
if you um if you have a whole bunch of
random variables so let's say you have a
whole bunch of random variables no
matter what kind they are as long as
they're from the same distribution
they're IID and you add them all
together um then the variance I believe
yeah the variance of this variant
standard deviation maybe standard
deviation of this goes uh goes up uh
square root uh yeah I think standard
deviation goes
up dividing by something that would
divide by this the standard deviation
here so it's made like normalizing by
that so um it's a it's that's actually I
don't think explicitly explained and the
uh attention is all you need paper uh
the vasani paper where they introduce
this but that's basic idea um in terms
of what people use most widely nowadays
um they
are basically doing
this
so they're taking the the hidden state
from the keys and multiplying it by a
matrix the hidden state by the queries
and multiplying it by a matrix um this
is what is done in uh in
Transformers and the uh and then they're
using this to um they're normalizing it
by this uh square root here
and
so this is essentially a bilinear
model um it's a bilinear model that is
normalized uh they call it uh scale do
product detention but actually because
they have these weight matrices uh it's
a bilinear model so um that's the the
most standard thing to be used
nowadays cool any any questions about
this
part
okay so um finally when you actually
train the model um as I mentioned
before right at the very
beginning
we when we're training an autor
regressive model we don't want to be
referring to the Future to things in the
future um because then you know
basically we'd be cheating and we'd have
a nonprobabilistic model it wouldn't be
good when we actually have to generate
left to right um and
so we essentially want to prevent
ourselves from using information from
the
future
and in an unconditioned model we want to
prevent ourselves from using any
information in the feature here um in a
conditioned model we're okay with doing
kind of bir
directional conditioning here to
calculate the representations but we're
not okay with doing it on the target
side so basically what we
do basically what we do is we create a
mask that prevents us from attending to
any of the information in the future
when we're uh predicting when we're
calculating the representations of the
the current thing uh word and
technically how we do this is we have
the attention
values uh like
2.1
attention
0.3 and
attention uh
0.5 or something like
that these are eventually going to be
fed through the soft Max to calculate
the attention values that we use to do
the waiting so what we do is any ones we
don't want to attend to we just add
negative infinity or add a very large
negative number so we uh cross that out
and set this the negative infinity and
so then when we take the softb basically
the value goes to zero and we don't
attend to it so um this is called the
attention mask and you'll see it when
you have to implement
attention cool
any any questions about
this okay great um so next I'd like to
go to Applications of sequence models um
there's a bunch of ways that you can use
sequence models of any variety I wrote
RNN here arbitrarily but it could be
convolution or Transformer or anything
else so the first one is encoding
sequences
um and essentially if you do it with an
RNN this is one way you can encode a
sequence basically you take the
last uh value here and you use it to uh
encode the
output this can be used for any sort of
uh like binary or multiclass prediction
problem it's also right now used very
widely in sentence representations for
retrieval uh so for example you build a
big retrieval index uh with these
vectors
and then you do a vector near you also
in quote a query and you do a vector
nearest neighbor search to look up uh
the most similar sentence here so this
is uh these are two applications where
you use something like this right on
this slide I wrote that you use the last
Vector here but actually a lot of the
time it's also a good idea to just take
the mean of the vectors or take the max
of all of the vectors
uh in fact I would almost I would almost
say that that's usually a better choice
if you're doing any sort of thing where
you need a single Vector unless your
model has been specifically trained to
have good like output vectors uh from
the final Vector here so um you could
also just take the the mean of all of
the purple
ones um another thing you can do is
encode tokens for sequence labeling Um
this can also be used for language
modeling and what do I mean it can be
used for language
modeling
basically you can view this as first
running along sequence encoding and then
after that making all of the predictions
um it's also a good thing to know
computationally because um often you can
do sequence encoding uh kind of all in
parallel and yeah actually I said I was
going to mention I said I was going to
mention that but I don't think I
actually have a slide about it but um
one important thing about rnn's compared
to convolution or Transformers uh sorry
convolution or attention is rnns in
order to calculate this RNN you need to
wait for this RNN to finish so it's
sequential and you need to go like here
and then here and then here and then
here and then here and that's a pretty
big bottleneck because uh things like
gpus or tpus they're actually really
good at doing a bunch of things at once
and so attention even though its ASM
totic complexity is worse o of n squ uh
just because you don't have that
bottleneck of doing things sequentially
it can be way way faster on a GPU
because you're not wasting your time
waiting for the previous thing to be
calculated so that's actually why uh
Transformers are so fast
um uh Transformers and attention models
are so
fast
um another thing to note so that's one
of the big reasons why attention models
are so popular nowadays because fast to
calculate on Modern Hardware another
reason why attention models are popular
nowadays does anyone have a um does
anyone have an
idea uh about another reason it's based
on how easy they are to learn and
there's a reason why and that reason why
has to do with
um that reason why has to do with uh
something I introduced in this lecture
uh
earlier I'll give a
hint gradients yeah more more
specifically what what's nice about
attention with respect to gradients or
Vanishing
gradients any
ideas let's say we have a really long
sentence it's like X1 X2 X3
X4 um
X200 over here and in order to predict
X200 you need to pay attention to X3
any
ideas another another hint how many
nonlinearities do you have to pass
through in order to pass that
information from X3 to
X200 in a recurrent Network um in a
recurrent Network or
attention netw should be
197 yeah in a recurrent Network it's
basically 197 or may maybe 196 I haven't
paid attention but every time every time
you pass it to the hidden
state it has to go through a
nonlinearity so it goes through like
1907 nonlinearities and even if you're
using an lstm um it's still the lstm
hidden cell is getting information added
to it and subtracted to it and other
things like that so it's still a bit
tricky
um what about
attention yeah basically one time so
attention um in the next layer here
you're passing it all the way you're
passing all of the information directly
in and the only qualifying thing is that
your weight has to be good it has to
find a good attention weight so that
it's actually paying attention to that
information so this is actually
discussed in the vaswani at all
attention is all you need paper that
introduced Transformers um convolutions
are kind of in the middle so like let's
say you have a convolution of length 10
um and then you have two layers of it um
if you have a convolution of length
10 or yeah let's say you have a
convolution of length 10 you would need
basically you would pass from 10
previous
ones and then you would pass again from
10 previous ones and then you would have
to go through like 16 or like I guess
almost 20 layers of convolution in order
to pass that information along so it's
kind of in the middle of RNs in uh in
lsms uh sorry RNN in attention
Ms Yeah question so regarding how you
have to wait for one r& the next one can
you inflence on one RNN once it's done
even though the next one's competing off
that one
yes yeah you can you can do
inference you could is well so as long
as
the as long as the output doesn't affect
the next input so in this
case in this case because of language
modeling or generation is because the
output doesn't affect the ne uh because
the output affects the next input if
you're predicting the output you have to
weigh if you know the output already um
if you know the output already you could
make the prediction at the same time
miscalculating this next hidden State um
so if you're just calculating the
probability you could do that and that's
actually where Transformers or attention
models shine attention models actually
aren't great for Generation Um and the
reason why they're not great for
generation is because they're
um
like when you're you're generating the
next token you still need to wait you
can't calculate in parallel because you
need to generate the next token before
you can encode the next uh the previous
sorry need to generate the next token
before you can encode it so you can't do
everything in parallel so Transformers
for generation are actually
slow and um there are models uh I don't
know if people are using them super
widely now but there were actually
transform uh language model sorry
machine translation model set we in
production they had a really big strong
Transformer encoder and then they had a
tiny fast RNN decoder um
and and if you want a actual
reference there's there's
this deep encoder shellow
decoder um and then there's also the the
Maran machine translation toolkit that
supports uh supports those types of
things as well so um it's also the
reason why uh if you're using if you're
using uh like the GPT models through the
API that decoding is more expensive
right like
encoding I forget exactly is it 0.03
cents for 1,000 tokens for encoding and
0.06 cents for 1,000 tokens for decoding
in like gp4 or something like this the
reason why is precisely that just
because it's so much more expensive to
to run the
decoder um cool I have a few final
things also about efficiency so um these
go back to the efficiency things that I
talked about last time um handling mini
batching so what do we have to do when
we're handling mini batching if we were
handling mini batching in feed forward
networks it's actually relatively easy
um because we all of our computations
are the same shape so we just
concatenate them all together into a big
tensor and run uh run over it uh we saw
mini batching makes things much faster
but mini batching and sequence modeling
is harder than in feed forward networks
um one reason is in rnns each word
depends on the previous word um also
because sequences are of various
lengths so so what we do to handle this
is uh we do padding and masking uh
so we can do padding like this uh so we
just add an extra token at the end to
make all of the sequences at the same
length um if we are doing an encoder
decoder style model uh where we have an
input and then we want to generate all
the outputs based on the input one of
the easy things is to add pads to the
beginning um and then so yeah it doesn't
really matter but you can add pads to
the beginning so they're all starting at
the same place especially if you're
using RNN style models um then we
calculate the loss over the output for
example we multiply the loss by a mask
to remove the loss over the tokens that
we don't care about and we take the sum
of these and so luckily most of this is
implemented in for example ptch or
huging face Transformers already so you
don't need to worry about it but it is a
good idea to know what's going on under
the hood if you want to implement
anything unusual and also um it's good
to know for the following reason also
which is bucketing and
sorting so if we use sentences of vastly
different lengths and we put them in the
same mini batch this can uh waste a
really large amount of computation so
like let's say we're processing
documents or movie reviews or something
like that and you have a most movie
reviews are like
10 words long but you have one movie
review in your mini batch of uh a
thousand words so basically what that
means is you're padding most of your
sequences 990 times to process 10
sequences which is like a lot of waste
right because you're running them all
through your GPU and other things like
that so one way to remedy this is to
sort sentences so similarly length
sentences are in the same batch so you
uh you first sort before building all of
your batches and then uh that makes it
so that similarly sized ones are the
same
batch this goes into the problem that I
mentioned before but only in passing
which is uh let's say you're calculating
your batch based on the number of
sequences that you're
processing if you say Okay I want 64
sequences in my mini batch um if most of
the time those 64 sequences are are 10
tokens that's fine but then when you get
the One Mini batch that has a thousand
tokens in each sentence or each sequence
um suddenly you're going to run out of
GPU memory and you're like training is
going to crash right which is you really
don't want that to happen when you
started running your homework assignment
and then went to bed and then wake up
and it crashed you know uh 15 minutes
into Computing or something so uh this
is an important thing to be aware of
practically uh again this can be solved
by a lot of toolkits like I know fer uh
does it and hugging face does it if you
set the appropriate settings but it's
something you should be aware of um
another note is that if you do this it's
reducing the randomness in your
distribution of data so um stochastic
gradient descent is really heavily
reliant on the fact that your ordering
of data is randomized or at least it's a
distributed appropriately so it's
something to definitely be aware of um
so uh this is a good thing to to think
about another really useful thing to
think about is strided
architectures um strided architectures
appear in rnns they appear in
convolution they appear in trans
Transformers or attention based models
um they're called different things in
each of them so in rnns they're called
pyramidal rnns in convolution they're
called strided architectures and in
attention they're called sparse
attention usually they all actually kind
of mean the same thing um and basically
what they mean is you don't you have a
multi-layer model and when you have a
multi-layer model you don't process
every input uh from the uh from the
previous layer so here's an example um
like let's say you have a whole bunch of
inputs um each of the inputs is
processed in the first layer in some way
but in the second layer you actually
input for example uh two inputs to the
RNN but you you skip so you have one
state that corresponds to state number
one and two another state that
corresponds to state number two and
three another state that corresponds to
state number three and four so what that
means is you can gradually decrease the
number like the length of the sequence
every time you process so uh this is a
really useful thing that to do if you're
processing very long sequences so you
should be aware of it
cool um everything
okay okay the final thing is truncated
back propagation through time and uh
truncated back propagation Through Time
what this is doing is basically you do
back propop over shorter segments but
you initialize with the state from the
previous
segment and the way this works is uh
like for example if you're running an
RNN uh you would run the RNN over the
previous segment maybe it's length four
maybe it's length 400 it doesn't really
matter but it's uh coherently length
segment and then when you do the next
segment what you do is you only pass the
hidden state but you throw away the rest
of the previous computation graph and
then walk through uh like this uh so you
won't actually be updating the
parameters of this based on the result
the lost from this but you're still
passing the information so this can use
the information for the previous state
so this is an example from RNN this is
used pretty widely in RNN but there's
also a lot of Transformer architectures
that do things like this um the original
one is something called Transformer
Excel that was actually created here at
CMU but this is also um used in the new
mistol models and other things like this
as well so um it's something that's
still very much alive and well nowadays
as well
cool um that's all I have for today are
there any questions people want to ask
before we wrap
up
yeah doesent yeah so for condition
prediction what is Source X and Target y
um I think I kind of maybe carried over
uh some terminology from machine
translation uh by accident maybe it
should be input X and output y uh that
would be a better way to put it and so
uh it could be anything for translation
it's like something in the source
language and something in the target
language so like English and Japanese um
if it's just a regular language model it
could be something like a prompt and the
output so for
UNC y example that
yeah so for unconditioned prediction
that could just be straight up language
modeling for example so um language
modeling with no not necessarily any
problems okay thanks and anything
else okay great thanks a lot I'm happy
to take questions
to