Imputer: Sequence Modelling via Imputation and Dynamic Programming
deep learning machine learning nlp natural language processing machine translation arxiv google attention mechanism attention transformer seq2seq autoregressive independence decoding
The imputer is a sequence-to-sequence model that strikes a balance between fully autoregressive models with long inference times and fully non-autoregressive models with fast inference. The imputer achieves constant decoding time independent of sequence length by exploiting dynamic programming.

https://arxiv.org/abs/2002.08926

Abstract:
This paper presents the Imputer, a neural sequence model that generates output sequences iteratively via imputations. The Imputer is an iterative generative model, requiring only a constant number of generation steps independent of the number of input or output tokens. The Imputer can be trained to approximately marginalize over all possible alignments between the input and output sequences, and all possible generation orders. We present a tractable dynamic programming training algorithm, which yields a lower bound on the log marginal likelihood. When applied to end-to-end speech recognition, the Imputer outperforms prior non-autoregressive models and achieves competitive results to autoregressive models. On LibriSpeech test-other, the Imputer achieves 11.1 WER, outperforming CTC at 13.0 WER and seq2seq at 12.5 WER.

Authors: William Chan, Chitwan Saharia, Geoffrey Hinton, Mohammad Norouzi, Navdeep Jaitly

Links:
YouTube: https://www.youtube.com/c/yannickilcher
Twitter: https://twitter.com/ykilcher
BitChute: https://www.bitchute.com/channel/yannic-kilcher
Minds: https://www.minds.com/ykilcher
 Hi there! Today we're looking at the imputer sequence modeling via imputation and dynamic programming by William Chan, Chitwan Sariah, Jeffrey Hinton, Mohamed Nourouzi and Navdeep Jaitley. So this is a model to perform sequence-to-sequence tasks. Now sequence-to-sequence tasks are very very common in NLP, but in this case it's kind of a subset of sequence-to-sequence tasks. So a classic sequence-to-sequence task is a machine translation. Here for example the sentence I like you. If you want to translate it to German, sorry you, if you want to translate it to German that would become Ich mag dich. And you see that the input is a sequence right and the output is a sequence. Now the imputer deals with very special kind of sequence-to-sequence tasks. Namely it deals with sequence-to-sequence tasks where there is a monotonic alignment. So you see that this is given here. The first word is corresponding to the first word here, the second to the second and the third to the third. This is not always the case in machine translation. You know different languages have different sentence structures. So for example in French this would be je d'aime. And you can see that the first word is still the first word, however the third word has become the second, the you and the verb goes to the end. So the imputer would not be able to deal with this task very well. A different task where the imputer would be useful for would be something like speech recognition. So if someone were to speak the words I like you and you would measure the waveform of that it would look something like I like you. So if you have this waveform let's actually make some chunk samples out of this. Let's say this is a sample right here and here is a break here and here. So we have five samples on the bottom. You can see pretty easily that this sample here, this is the I and then this is silence, this is the like, this is silence and this is the you. So the imputer deals with these kind of sequence to sequence tasks where first of all there is a monotonic alignment, sorry monotonic alignment and second of all this is an engineering constraint where the length of the input sequence X is larger or equal to the length of the input sequence Y and you'll see why mainly because we rely on being able to compute this alignment here. The alignment of input samples to output samples. You can see that the monotonic alignment is actually given fairly well in speech recognition because if something is later down here it is also later in the sequence up here. That is a monotonic alignment and also usually we have more wave samples then we have words in the output sequence. So that would be a task for the imputer. Now let's think about how we would do something like this. So let's put X at the top here and we said X has five tokens in it and let's put Y at the bottom. Y actually has three tokens. So this here is I like you. This is the waveform and we want the I like you at the bottom. So what could we do? First of all what the imputer does is it represents I like you not as this form right here but as a form where you have the same length as X divided into the same amount of things and then it does the following. So for this this is an example. This is how it would represent Y. It would say I have as many chunks on the top as on the bottom. I know this chunk here corresponds to this token then this here to this and this here to this and then these are these intermediate ones. So you can see these correspond to those. These are silents right here. Now it doesn't always need to be that there is always one token and a silence then a token and a silence. The task of the imputer is actually to see whether this is more likely than for example I like and then silence silence and then you. So the task of the imputer is to distinguish these two from each other and then of course also produce the actual tokens. Now if you think about how would you go about taking X and producing something like Y. So this is Y let's call it tilde. This is the actual Y right but you can see that this here is a deterministic function in one way. It's actually not a deterministic function in the other way and that becomes interesting when you have to compute a loss for this. But how would we go about doing this? What we could do is we could just take a big transformer BERT. That's actually drawn arrow. We could just take BERT and we could simply so in BERT you have in if you if you construct it correctly you have as many input tokens as output tokens. So what we could simply say is for each of the outputs that we get we simply make this as a softmax classifier over our vocabulary with the silence being one special token and we simply classify each of the outputs into this vocabulary. This would be one step right? So we could do one step BERT bang bang input to output and there is more there are more sophisticated approaches to doing this in one step like CTC but ultimately we could just do one step but then you'd have the same problem like for example XL net if you haven't seen my XL net video I recommend it that they exactly take the problem if you do this right then at the moment where you decode the word like you have no idea that there is an I over here all you know is the the vector you have here that you sample the I from right but this could be a distribution where I is pretty high but some other word is also pretty high so this process over here that samples the word like has no idea which of the two here you actually would sample so it cannot condition on it so it is the the assumption here is that the sampling of the word like is independent of the sampling of the word I and of course that's not the case the you need to know what word is there if you want to sample the word like otherwise you can end up with some very confusing sentences so this one step process is pretty quick but it has the drawback that there are these conditional independence assumptions and again I invite you to watch the XL net video if you want to dive more into this problem the second thing we could do is we could just decode one after another right so we could say all right I'll make sorry I'll make my five slots here and I just leave them empty for now and I'm just going to decode the one that I am most sure about and let's say the the speech at the back here is very clear and you say other I'm I know this is a you right so I'm gonna fill in you right here right and make this alignment that this goes here this is the you right I still don't know what the others are but now what I did they do a second step and in the second step I get as an input not only the original input like this this thing here but I also get the fact that I already decoded the word you to here right in this step so now I say given that I already decoded the word you which one am I now most sure about and I might be most sure about to say I'm most sure about this now being an eye because there's a you at the end and this kind of sounds like an eye so an eye here right it goes to the next step and then the next step it already has the information that it decoded I and you and now it's a might say ah okay given these that's so probably this thing so I here probably the thing here the thing right here is silence right makes the most sense I kind of hear some noise but there's already a word after so now I'm pretty sure that this here is a silent token right and you go this until the end until you're actually at this so this here would be n step decoding this here would be n steps of decoding which now no longer has the problem of these conditional independence assumptions but of course now you have the problem that you need n steps right the imputer does something in the middle of this the imputer will as you can see here it will form this into blocks right blocks of size B and this is the empty symbol here right and what it will do is it will make a step where in each block for each block it will conditioned on the previous alignment and conditioned on the input it will decode whatever it feels it is most certain about in each block and then it does this for as long as there are still empty tokens right you can see here the first block and then in the second step it will decode this this this and this so the imputer can trade off between the conditional independence assumption of the one step BERT and the full conditional independence assumption of the n step decoding right so it will compute this alignment and the actual tokens at the same time in this process so how many steps does this take this takes now B steps and this is pretty cool because B is the block size so this is independent of the sequence length so it is able to compute this alignment and output in a constant number of steps right so you're by modulating this B you're now able to trade off speed versus let's say performance in the imputer and this is pretty cool so I think actually I think the the bigger point to understand here is how to actually use the assumption that there is a monotonic alignment right because if there is a monotonic alignment and if this thing is given here then you can do this you can do this representation right here with the silence tokens and that allows you to basically represent the output in a form that is of the same length as the input and do this kind of token by token decoding while still allowing you to have variable lengths output as long as they're smaller in length than the input so that's pretty cool and then the the next pretty cool thing is the fact that they do this in blocks now of course my issue with this so this is how the system works my issue with this is how the system is trained so if you think about how you train this you must train this first of all the loss function right has to revert this and how they do it as they marginalize you see this down here you want to marginalize over all the possible alignments right here so this is how you train you sample an alignment from the alignment policy and this alignment policy is I think they have some heuristics of how they construct the alignments during during training or you have experts actually giving you this alignment I think they use in the speech recognition they use something like CTC to give you the alignments from the alignment policy and then you have a masking policy and I think they also they just do random masking and then they use that for training and then they marginalize over the alignments this I'm pretty sure is not the same distribution as the decoding procedure I just described right so the decoding procedure if you do this in B steps right that means each of the step is dependent on the step before so that means the distribution of whatever you whatever the imputer sees is actually dependent on itself while these people are proposing a training framework where you have here you have a heuristic in order to come up with the training sample alignments and here you have a random I think a random masking policy that comes up with the with where the empty tokens are so this is not the same distribution and then also it marginalizes over all compatible alignments which I'm I'm pretty sure this is not the same distribution this is not the correct loss distribution they have some math to show that in expectation it's the same but yeah this is this is over there over their role in policy and role and expert and and marginalization this I don't want to go too deep into this I've given it some thought but it will make this video too long and boring if I actually go into the details here suffice to say I invite you to look at the loss computation and ask yourself if you think that is the correct way to produce the data set for training given how you do the inference later the architecture of the imputer is actually pretty similar to BERT in that first of all well okay you're dealing with audio in the input so you're going to have some convolutional network here and you also need to take as an input the prior alignment that you've already produced right so this you embed and but then you simply do an attention network a transformer which will which is pretty close to to the bird example we've made and so I mean they stress that that their that their loss is actually a lower bound on the loss so I shouldn't be I shouldn't be too hard when I say it's not the correct distribution they do minimize something some loss that actually makes sense but yeah I mainly wanted to go over the over the how the imputer works and how the it is structured and I think it's pretty cool and it lends itself very well to these tasks and most of all I like the fact that it exploits the these assumptions here so not all tasks fit these assumptions but if a task does fit the assumption then I think it should be you know it it should be fairly obvious that one should exploit that in order to perform better all right that was it for me thanks
 Hi there! Today we're looking at the imputer sequence modeling via imputation
 and dynamic programming by William Chan, Chitwan Sariah, Jeffrey Hinton, Mohamed
 Nourouzi and Navdeep Jaitley. So this is a model to perform sequence-to-sequence
 tasks. Now sequence-to-sequence tasks are very very common in NLP, but in this
 case it's kind of a subset of sequence-to-sequence tasks. So a classic
 sequence-to-sequence task is a machine translation. Here for example the
 sentence I like you. If you want to translate it to German, sorry you, if you
 want to translate it to German that would become Ich mag dich. And you see that the
 input is a sequence right and the output is a sequence. Now the imputer deals with
 very special kind of sequence-to-sequence tasks. Namely it deals with
 sequence-to-sequence tasks where there is a monotonic alignment. So you see
 that this is given here. The first word is corresponding to the first word here,
 the second to the second and the third to the third. This is not always the case
 in machine translation. You know different languages have different sentence
 structures. So for example in French this would be je d'aime. And you can see that
 the first word is still the first word, however the third word has become the
 second, the you and the verb goes to the end. So the imputer would not be able to
 deal with this task very well. A different task where the imputer would be
 useful for would be something like speech recognition. So if someone were to speak
 the words I like you and you would measure the waveform of that it would
 look something like I like you. So if you have this waveform let's actually
 make some chunk samples out of this. Let's say this is a sample right here and
 here is a break here and here. So we have five samples on the bottom.
 You can see pretty easily that this sample here, this is the I and then this
 is silence, this is the like, this is silence and this is the you. So the
 imputer deals with these kind of sequence to sequence tasks where first
 of all there is a monotonic alignment, sorry monotonic alignment and second of
 all this is an engineering constraint where the length of the input sequence X
 is larger or equal to the length of the input sequence Y and you'll see
 why mainly because we rely on being able to compute this alignment here. The
 alignment of input samples to output samples. You can see that the
 monotonic alignment is actually given fairly well in speech recognition
 because if something is later down here it is also later in the sequence up here.
 That is a monotonic alignment and also usually we have more wave samples
 then we have words in the output sequence. So that would be a task for the
 imputer. Now let's think about how we would do something like this. So let's
 put X at the top here and we said X has five tokens in it and let's put Y at the
 bottom. Y actually has three tokens. So this here is I like you.
 This is the waveform and we want the I like you at the bottom. So what could we
 do? First of all what the imputer does is it represents I like you not as this
 form right here but as a form where you have the same length as X divided into
 the same amount of things and then it does the following. So for this this is
 an example.
 This is how it would represent Y. It would say I have as many chunks on
 the top as on the bottom. I know this chunk here corresponds to this token
 then this here to this and this here to this and then these are these
 intermediate ones. So you can see these correspond to those. These are
 silents right here. Now it doesn't always need to be that there is always one
 token and a silence then a token and a silence. The task of the imputer is
 actually to see whether this is more likely than for example I like and then
 silence silence and then you. So the task of the imputer is to distinguish
 these two from each other and then of course also produce the actual tokens.
 Now if you think about how would you go about taking X and producing something
 like Y. So this is Y let's call it tilde. This is the actual Y right but you can
 see that this here is a deterministic function in one way. It's actually not a
 deterministic function in the other way and that becomes interesting when you
 have to compute a loss for this. But how would we go about doing this? What
 we could do is we could just take a big transformer BERT. That's actually
 drawn arrow. We could just take BERT and we could simply so in BERT you have
 in if you if you construct it correctly you have as many input tokens as output
 tokens. So what we could simply say is for each of the outputs that we get we
 simply make this as a softmax classifier over our vocabulary with the silence
 being one special token and we simply classify each of the outputs into this
 vocabulary. This would be one step right? So we could do one step BERT bang bang
 input to output and there is more there are more sophisticated approaches to
 doing this in one step like CTC but ultimately we could just do one step but
 then you'd have the same problem like for example XL net if you haven't seen
 my XL net video I recommend it that they exactly take the problem if you do this
 right then at the moment where you decode the word like you have no idea
 that there is an I over here all you know is the the vector you have here
 that you sample the I from right but this could be a distribution where I is
 pretty high but some other word is also pretty high so this process over here
 that samples the word like has no idea which of the two here you actually would
 sample so it cannot condition on it so it is the the assumption here is that
 the sampling of the word like is independent of the sampling of the word
 I and of course that's not the case the you need to know what word is there if
 you want to sample the word like otherwise you can end up with some very
 confusing sentences so this one step process is pretty quick but it has the
 drawback that there are these conditional independence assumptions and
 again I invite you to watch the XL net video if you want to dive more into this
 problem the second thing we could do is we could just decode one after another
 right so we could say all right I'll make sorry I'll make my five slots here
 and I just leave them empty for now and I'm just going to decode the one that I
 am most sure about and let's say the the speech at the back here is very clear
 and you say other I'm I know this is a you right so I'm gonna fill in you right
 here right and make this alignment that this goes here this is the you right I
 still don't know what the others are but now what I did they do a second step and
 in the second step I get as an input not only the original input like this this
 thing here but I also get the fact that I already decoded the word you to here
 right in this step so now I say given that I already decoded the word you which
 one am I now most sure about and I might be most sure about to say I'm most sure
 about this now being an eye because there's a you at the end and this kind
 of sounds like an eye so an eye here right it goes to the next step and then
 the next step it already has the information that it decoded I and you
 and now it's a might say ah okay given these that's so probably this thing so I
 here probably the thing here the thing right here is silence right makes the
 most sense I kind of hear some noise but there's already a word after so now I'm
 pretty sure that this here is a silent token right and you go this until the
 end until you're actually at this so this here would be n step decoding this
 here would be n steps of decoding which now no longer has the problem of these
 conditional independence assumptions but of course now you have the problem that
 you need n steps right the imputer does something in the middle of this the
 imputer will as you can see here it will form this into blocks right blocks of
 size B and this is the empty symbol here right and what it will do is it will
 make a step where in each block for each block it will conditioned on the
 previous alignment and conditioned on the input it will decode whatever it
 feels it is most certain about in each block and then it does this for as long
 as there are still empty tokens right you can see here the first block and then
 in the second step it will decode this this this and this so the imputer can
 trade off between the conditional independence assumption of the one step
 BERT and the full conditional independence assumption of the n step
 decoding right so it will compute this alignment and the actual tokens at the
 same time in this process so how many steps does this take this takes now B
 steps and this is pretty cool because B is the block size so this is independent
 of the sequence length so it is able to compute this alignment and output in a
 constant number of steps right so you're by modulating this B you're now able to
 trade off speed versus let's say performance in the imputer and this is
 pretty cool so I think actually I think the the bigger point to understand here
 is how to actually use the assumption that there is a monotonic alignment
 right because if there is a monotonic alignment and if this thing is given
 here then you can do this you can do this representation right here with the
 silence tokens and that allows you to basically represent the output in a
 form that is of the same length as the input and do this kind of token by token
 decoding while still allowing you to have variable lengths output as long as
 they're smaller in length than the input so that's pretty cool and then the the
 next pretty cool thing is the fact that they do this in blocks now of course my
 issue with this so this is how the system works my issue with this is how
 the system is trained so if you think about how you train this you must train
 this first of all the loss function right has to revert this and how they
 do it as they marginalize you see this down here you want to marginalize over
 all the possible alignments right here so this is how you train you sample an
 alignment from the alignment policy and this alignment policy is I think they
 have some heuristics of how they construct the alignments during during
 training or you have experts actually giving you this alignment I think they
 use in the speech recognition they use something like CTC to give you the
 alignments from the alignment policy and then you have a masking policy and I
 think they also they just do random masking and then they use that for
 training and then they marginalize over the alignments this I'm pretty sure is
 not the same distribution as the decoding procedure I just described
 right so the decoding procedure if you do this in B steps right that means each
 of the step is dependent on the step before so that means the distribution of
 whatever you whatever the imputer sees is actually dependent on itself while
 these people are proposing a training framework where you have here you have a
 heuristic in order to come up with the training sample alignments and here you
 have a random I think a random masking policy that comes up with the with where
 the empty tokens are so this is not the same distribution and then also it
 marginalizes over all compatible alignments which I'm I'm pretty sure
 this is not the same distribution this is not the correct loss distribution
 they have some math to show that in expectation it's the same but yeah this
 is this is over there over their role in policy and role and expert and and
 marginalization this I don't want to go too deep into this I've given it some
 thought but it will make this video too long and boring if I actually go into
 the details here suffice to say I invite you to look at the loss computation and
 ask yourself if you think that is the correct way to produce the data set for
 training given how you do the inference later the architecture of the imputer is
 actually pretty similar to BERT in that first of all well okay you're dealing
 with audio in the input so you're going to have some convolutional network here
 and you also need to take as an input the prior alignment that you've already
 produced right so this you embed and but then you simply do an attention
 network a transformer which will which is pretty close to to the bird example
 we've made and so I mean they stress that that their that their loss is
 actually a lower bound on the loss so I shouldn't be I shouldn't be too hard when
 I say it's not the correct distribution they do minimize something some loss
 that actually makes sense but yeah I mainly wanted to go over the over the
 how the imputer works and how the it is structured and I think it's pretty cool
 and it lends itself very well to these tasks and most of all I like the fact
 that it exploits the these assumptions here so not all tasks fit these
 assumptions but if a task does fit the assumption then I think it should be you
 know it it should be fairly obvious that one should exploit that in order to
 perform better all right that was it for me thanks