<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Translation of Numeric Phrases with Seq2Seq
In the following we will try to build a translation model from french phrases describing numbers to the corresponding numeric representation (base 10).
This is a toy machine translation task with a restricted vocabulary and a single valid translation for each source phrase which makes it more tractable to train on a laptop computer and easier to evaluate. Despite those limitations we expect that this task will highlight interesting properties of Seq2Seq models including
Step1:  Generating a Training Set
The following will generate phrases 20000 example phrases for numbers between 1 and 1,000,000 (excluded). We chose to over-represent small numbers by generating all the possible short sequences between 1 and exhaustive=5000.
We then split the generated set into non-overlapping train, validation and test splits.
Step2:  Vocabularies
Build the vocabularies from the training set only to get a chance to have some out-of-vocabulary words in the validation and test sets.
First we need to introduce specific symbols that will be used to
Step3:  To build the vocabulary we need to tokenize the sequences of symbols. For the digital number representation we use character level tokenization while whitespace-based word level tokenization will do for the French phrases
Step4:  Let's now use this tokenization strategy to assign a unique integer token id to each possible token string found the traing set in each language ('French' and 'numeric')
Step5:  The two languages do not have the same vocabulary sizes
Step6:  We also built the reverse mappings from token ids to token string representations
Step7:  Seq2Seq with a single GRU architecture
<img src="images/basic_seq2seq.png" width="80%" />
From
Step8:  Vectorization of the parallel corpus
Let's apply the previous transformation to each pair of (source, target) sequene and use a shared vocabulary to store the results in numpy arrays of integer token ids, with padding on the left so that all input / output sequences have the same length
Step9:  This looks good. In particular we can note
Step10:  A simple homogeneous Seq2Seq architecture
To keep the architecture simple we will use the same RNN model and weights for both the encoder part (before the _GO token) and the decoder part (after the _GO token).
We may GRU recurrent cell instead of LSTM because it is slightly faster to compute and should give comparable results.
Exercise
Step11:  Questions
Step12:  Let's register a callback mechanism to automatically snapshot the best model by measure the performance of the model on the validation set at the end of each epoch during training
Step13:  We need to use np.expand_dims trick on Y
Step14:  Let's load the best model found on the validation set at the end of training
Step15:  If you don't have access to a GPU and cannot wait 10 minutes to for the model to converge to a reasonably good state, feel to use the pretrained model. This model has been obtained by training the above model for ~150 epochs. The validation loss is significantly lower than 1e-5. In practice it should hardly ever make any prediction error on this easy translation problem.
Alternatively we will load this imperfect model (trained only to 50 epochs) with a validation loss of ~7e-4. This model makes funny translation errors so I would suggest to try it first
Step16:  Let's have a look at a raw prediction on the first sample of the test set
Step17:  In numeric array this is provided (along with the expected target sequence) as the following padded input sequence
Step18:  Remember that the _GO (symbol indexed at 1) separates the reversed source from the expected target sequence
Step19:  Interpreting the model prediction
Exercise
Step21:  In the previous exercise we cheated because we gave the complete sequence along with the solution in the input sequence.
To be more realistic we need to use the model in a setting where we do not provide any token of expected translation as part of the input sequence
Step22:  The results are far from perfect but we can see that the network has already picked up some translation skills.
Why does the partially trained network is able to give the correct translation for
Step23:  Model evaluation
Because we expect only one correct translation for a given source sequence, we can use phrase-level accuracy as a metric to quantify our model quality.
Note that this is not the case for real translation models (e.g. from French to English on arbitrary sentences). Evaluation of a machine translation model is tricky in general. Automated evaluation can somehow be done at the corpus level with the BLEU score (bilingual evaluation understudy) given a large enough sample of correct translations provided by certified translators but its only a noisy proxy.
The only good evaluation is to give a large enough sample of the model predictions on some test sentences to certified translators and ask them to give an evaluation (e.g. a score between 0 and 6, 0 for non-sensical and 6 for the hypothetical perfect translation). However in practice this is very costly to do.
Fortunately we can just use phrase-level accuracy on a our very domain specific toy problem
Step26:  Bonus
Step27:  Model Accuracy with Beam Search Decoding
<ASSISTANT_TASK:>
Python Code:
from french_numbers import to_french_phrase
for x in [21, 80, 81, 300, 213, 1100, 1201, 301000, 80080]:
    print(str(x).rjust(6), to_french_phrase(x))
Explanation: Translation of Numeric Phrases with Seq2Seq
In the following we will try to build a translation model from french phrases describing numbers to the corresponding numeric representation (base 10).
This is a toy machine translation task with a restricted vocabulary and a single valid translation for each source phrase which makes it more tractable to train on a laptop computer and easier to evaluate. Despite those limitations we expect that this task will highlight interesting properties of Seq2Seq models including:
the ability to deal with different length of the source and target sequences,
handling token with a meaning that changes depending on the context (e.g "quatre" vs "quatre vingts" in "quatre cents"),
basic counting and "reasoning" capabilities of LSTM and GRU models.
The parallel text data is generated from a "ground-truth" Python function named to_french_phrase that captures common rules. Hyphenation was intentionally omitted to make the phrases more ambiguous and therefore make the translation problem slightly harder to solve (and also because Olivier had no particular interest hyphenation in properly implementing rules :).
End of explanation
from french_numbers import generate_translations
from sklearn.model_selection import train_test_split
numbers, french_numbers = generate_translations(
    low=1, high=int(1e6) - 1, exhaustive=5000, random_seed=0)
num_train, num_dev, fr_train, fr_dev = train_test_split(
    numbers, french_numbers, test_size=0.5, random_state=0)
num_val, num_test, fr_val, fr_test = train_test_split(
    num_dev, fr_dev, test_size=0.5, random_state=0)
len(fr_train), len(fr_val), len(fr_test)
for i, fr_phrase, num_phrase in zip(range(5), fr_train, num_train):
    print(num_phrase.rjust(6), fr_phrase)
for i, fr_phrase, num_phrase in zip(range(5), fr_val, num_val):
    print(num_phrase.rjust(6), fr_phrase)
Explanation: Generating a Training Set
The following will generate phrases 20000 example phrases for numbers between 1 and 1,000,000 (excluded). We chose to over-represent small numbers by generating all the possible short sequences between 1 and exhaustive=5000.
We then split the generated set into non-overlapping train, validation and test splits.
End of explanation
PAD, GO, EOS, UNK = START_VOCAB = ['_PAD', '_GO', '_EOS', '_UNK']
Explanation: Vocabularies
Build the vocabularies from the training set only to get a chance to have some out-of-vocabulary words in the validation and test sets.
First we need to introduce specific symbols that will be used to:
- pad sequences
- mark the beginning of translation
- mark the end of translation
- be used as a placehold for out-of-vocabulary symbols (not seen in the training set).
Here we use the same convention as the tensorflow seq2seq tutorial:
End of explanation
def tokenize(sentence, word_level=True):
    if word_level:
        return sentence.split()
    else:
        return [sentence[i:i + 1] for i in range(len(sentence))]
tokenize('1234', word_level=False)
tokenize('mille deux cent trente quatre', word_level=True)
Explanation: To build the vocabulary we need to tokenize the sequences of symbols. For the digital number representation we use character level tokenization while whitespace-based word level tokenization will do for the French phrases:
End of explanation
def build_vocabulary(tokenized_sequences):
    rev_vocabulary = START_VOCAB[:]
    unique_tokens = set()
    for tokens in tokenized_sequences:
        unique_tokens.update(tokens)
    rev_vocabulary += sorted(unique_tokens)
    vocabulary = {}
    for i, token in enumerate(rev_vocabulary):
        vocabulary[token] = i
    return vocabulary, rev_vocabulary
tokenized_fr_train = [tokenize(s, word_level=True) for s in fr_train]
tokenized_num_train = [tokenize(s, word_level=False) for s in num_train]
fr_vocab, rev_fr_vocab = build_vocabulary(tokenized_fr_train)
num_vocab, rev_num_vocab = build_vocabulary(tokenized_num_train)
Explanation: Let's now use this tokenization strategy to assign a unique integer token id to each possible token string found the traing set in each language ('French' and 'numeric'):
End of explanation
len(fr_vocab)
len(num_vocab)
for k, v in sorted(fr_vocab.items())[:10]:
    print(k.rjust(10), v)
print('...')
for k, v in sorted(num_vocab.items()):
    print(k.rjust(10), v)
Explanation: The two languages do not have the same vocabulary sizes:
End of explanation
print(rev_fr_vocab)
print(rev_num_vocab)
Explanation: We also built the reverse mappings from token ids to token string representations:
End of explanation
def make_input_output(source_tokens, target_tokens, reverse_source=True):
    # TOTO
    return input_tokens, output_tokens
# %load solutions/make_input_output.py
input_tokens, output_tokens = make_input_output(
    ['cent', 'vingt', 'et', 'un'],
    ['1', '2', '1'],
)
# Expected outputs:
# ['un', 'et', 'vingt', 'cent', '_GO', '1', '2', '1']
# ['1', '2', '1', '_EOS']
input_tokens
output_tokens
Explanation: Seq2Seq with a single GRU architecture
<img src="images/basic_seq2seq.png" width="80%" />
From: Sutskever, Ilya, Oriol Vinyals, and Quoc V. Le. "Sequence to sequence learning with neural networks." NIPS 2014
For a given source sequence - target sequence pair, we will:
- tokenize the source and target sequences;
- reverse the order of the source sequence;
- build the input sequence by concatenating the reversed source sequence and the target sequence in original order using the _GO token as a delimiter, 
- build the output sequence by appending the _EOS token to the source sequence.
Let's do this as a function using the original string representations for the tokens so as to make it easier to debug:
Exercise
- Write a function that turns a pair of tokenized (source, target) sequences into a pair of (input, output) sequences as described above.
- The function should have a reverse_source=True as an option.
Notes: 
- The function should output two sequences of string tokens: one to be fed as the input and the other as expected output for the seq2seq network.
- Do not pad the sequences: we will handle the padding later.
- Don't forget to insert the _GO and _EOS special symbols at the right locations.
End of explanation
all_tokenized_sequences = tokenized_fr_train + tokenized_num_train
shared_vocab, rev_shared_vocab = build_vocabulary(all_tokenized_sequences)
max(len(s) for s in tokenized_fr_train)
max(len(s) for s in tokenized_num_train)
import numpy as np
max_length = 20  # found by introspection of our training set
def vectorize_corpus(source_sequences, target_sequences, shared_vocab,
                     word_level_source=True, word_level_target=True,
                     max_length=max_length):
    assert len(source_sequences) == len(target_sequences)
    n_sequences = len(source_sequences)
    source_ids = np.empty(shape=(n_sequences, max_length), dtype=np.int32)
    source_ids.fill(shared_vocab[PAD])
    target_ids = np.empty(shape=(n_sequences, max_length), dtype=np.int32)
    target_ids.fill(shared_vocab[PAD])
    numbered_pairs = zip(range(n_sequences), source_sequences, target_sequences)
    for i, source_seq, target_seq in numbered_pairs:
        source_tokens = tokenize(source_seq, word_level=word_level_source)
        target_tokens = tokenize(target_seq, word_level=word_level_target)
        
        in_tokens, out_tokens = make_input_output(source_tokens, target_tokens)
        
        in_token_ids = [shared_vocab.get(t, UNK) for t in in_tokens]
        source_ids[i, -len(in_token_ids):] = in_token_ids
    
        out_token_ids = [shared_vocab.get(t, UNK) for t in out_tokens]
        target_ids[i, -len(out_token_ids):] = out_token_ids
    return source_ids, target_ids
X_train, Y_train = vectorize_corpus(fr_train, num_train, shared_vocab,
                                    word_level_target=False)
X_train.shape
X_train[0]
Y_train.shape
fr_train[0]
num_train[0]
X_train[0]
Y_train[0]
Explanation: Vectorization of the parallel corpus
Let's apply the previous transformation to each pair of (source, target) sequene and use a shared vocabulary to store the results in numpy arrays of integer token ids, with padding on the left so that all input / output sequences have the same length:
End of explanation
X_val, Y_val = vectorize_corpus(fr_val, num_val, shared_vocab,
                                word_level_target=False)
X_test, Y_test = vectorize_corpus(fr_test, num_test, shared_vocab,
                                  word_level_target=False)
X_val.shape, Y_val.shape
X_test.shape, Y_test.shape
Explanation: This looks good. In particular we can note:
the PAD=0 symbol at the beginning of the two sequences,
the input sequence has the GO=1 symbol to separate the source from the target,
the output sequence is a shifted version of the target and ends with EOS=2.
Let's vectorize the validation and test set to be able to evaluate our models:
End of explanation
from tensorflow.keras.models import Sequential
from tensorflow.keras.layers import Embedding, Dropout, GRU, Dense
vocab_size = len(shared_vocab)
simple_seq2seq = Sequential()
# TODO
# Here we use the sparse_categorical_crossentropy loss to be able to pass
# integer-coded output for the token ids without having to convert to one-hot
# codes
simple_seq2seq.compile(optimizer='adam', loss='sparse_categorical_crossentropy')
# %load solutions/simple_seq2seq.py
Explanation: A simple homogeneous Seq2Seq architecture
To keep the architecture simple we will use the same RNN model and weights for both the encoder part (before the _GO token) and the decoder part (after the _GO token).
We may GRU recurrent cell instead of LSTM because it is slightly faster to compute and should give comparable results.
Exercise:
- Build a Seq2Seq model:
  - Start with an Embedding layer;
  - Add a single GRU layer: the GRU layer should yield a sequence of output vectors, one at each timestep;
  - Add a Dense layer to adapt the ouput dimension of the GRU layer to the dimension of the output vocabulary;
  - Don't forget to insert some Dropout layer(s), especially after the Embedding layer.
Note:
- The output dimension of the Embedding layer should be smaller than usual be cause we have small vocabulary size;
- The dimension of the GRU should be larger to give the Seq2Seq model enough "working memory" to memorize the full input sequence before decoding it;
- Your model should output a shape [batch, sequence_length, vocab_size].
End of explanation
# simple_seq2seq.predict(X_train[0:1]).shape
# simple_seq2seq.summary()
Explanation: Questions:
What is the expected shape of the output of the model when fed with input of length 20 tokens? What is the meaning of the values in the output of the model?
What is the shape of the output of each layer in the model?
End of explanation
from tensorflow.keras.callbacks import ModelCheckpoint
from tensorflow.keras.models import load_model
best_model_fname = "simple_seq2seq_checkpoint.h5"
best_model_cb = ModelCheckpoint(best_model_fname, monitor='val_loss',
                                save_best_only=True, verbose=1)
Explanation: Let's register a callback mechanism to automatically snapshot the best model by measure the performance of the model on the validation set at the end of each epoch during training:
End of explanation
%matplotlib inline
import matplotlib.pyplot as plt
history = simple_seq2seq.fit(X_train, np.expand_dims(Y_train, -1),
                             validation_data=(X_val, np.expand_dims(Y_val, -1)),
                             epochs=15, verbose=2, batch_size=32,
                             callbacks=[best_model_cb])
plt.figure(figsize=(12, 6))
plt.plot(history.history['loss'], label='train')
plt.plot(history.history['val_loss'], '--', label='validation')
plt.ylabel('negative log likelihood')
plt.xlabel('epoch')
plt.legend()
plt.title('Convergence plot for Simple Seq2Seq')
Explanation: We need to use np.expand_dims trick on Y: this is required by Keras because of we use a sparse (integer-based) representation for the output:
End of explanation
simple_seq2seq = load_model(best_model_fname)
Explanation: Let's load the best model found on the validation set at the end of training:
End of explanation
from tensorflow.keras.utils import get_file
filename = get_file(
    "simple_seq2seq_partially_pretrained.h5", 
    "https://github.com/m2dsupsdlclass/lectures-labs/releases/"
    "download/0.4/simple_seq2seq_partially_pretrained.h5"
)
# Uncomment the following to replace for the fully trained network:
# filename= get_file(
#     "simple_seq2seq_pretrained.h5", 
#     "https://github.com/m2dsupsdlclass/lectures-labs/releases/"
#     "download/0.4/simple_seq2seq_pretrained.h5")
simple_seq2seq.load_weights(filename)
Explanation: If you don't have access to a GPU and cannot wait 10 minutes to for the model to converge to a reasonably good state, feel to use the pretrained model. This model has been obtained by training the above model for ~150 epochs. The validation loss is significantly lower than 1e-5. In practice it should hardly ever make any prediction error on this easy translation problem.
Alternatively we will load this imperfect model (trained only to 50 epochs) with a validation loss of ~7e-4. This model makes funny translation errors so I would suggest to try it first:
End of explanation
fr_test[0]
Explanation: Let's have a look at a raw prediction on the first sample of the test set:
End of explanation
first_test_sequence = X_test[0:1]
first_test_sequence
Explanation: In numeric array this is provided (along with the expected target sequence) as the following padded input sequence:
End of explanation
rev_shared_vocab[1]
Explanation: Remember that the _GO (symbol indexed at 1) separates the reversed source from the expected target sequence:
End of explanation
# %load solutions/interpret_output.py
Explanation: Interpreting the model prediction
Exercise:
- Feed this test sequence into the model. What is the shape of the output?
- Get the argmax of each output prediction to get the most likely symbols
- Dismiss the padding / end of sentence
- Convert to readable vocabulary using rev_shared_vocab
Interpretation
- Compare the output with the first example in numerical format num_test[0]
- What do you think of this way of decoding? Is it correct to use it at inference time?
End of explanation
def greedy_translate(model, source_sequence, shared_vocab, rev_shared_vocab,
                     word_level_source=True, word_level_target=True):
    Greedy decoder recursively predicting one token at a time
    # Initialize the list of input token ids with the source sequence
    source_tokens = tokenize(source_sequence, word_level=word_level_source)
    input_ids = [shared_vocab.get(t, UNK) for t in reversed(source_tokens)]
    input_ids += [shared_vocab[GO]]
    # Prepare a fixed size numpy array that matches the expected input
    # shape for the model
    input_array = np.empty(shape=(1, model.input_shape[1]),
                           dtype=np.int32)
    decoded_tokens = []
    while len(input_ids) <= max_length:
        # Vectorize a the list of input tokens as 
        # and use zeros padding.
        input_array.fill(shared_vocab[PAD])
        input_array[0, -len(input_ids):] = input_ids
        
        # Predict the next output: greedy decoding with argmax
        next_token_id = model(input_array)[0, -1].numpy().argmax()
        
        # Stop decoding if the network predicts end of sentence:
        if next_token_id == shared_vocab[EOS]:
            break
            
        # Otherwise use the reverse vocabulary to map the prediction
        # back to the string space
        decoded_tokens.append(rev_shared_vocab[next_token_id])
        
        # Append prediction to input sequence to predict the next
        input_ids.append(next_token_id)
    separator = " " if word_level_target else ""
    return separator.join(decoded_tokens)
phrases = [
    "un",
    "deux",
    "trois",
    "onze",
    "quinze",
    "cent trente deux",
    "cent mille douze",
    "sept mille huit cent cinquante neuf",
    "vingt et un",
    "vingt quatre",
    "quatre vingts",
    "quatre vingt onze mille",
    "quatre vingt onze mille deux cent deux",
]
for phrase in phrases:
    translation = greedy_translate(simple_seq2seq, phrase,
                                   shared_vocab, rev_shared_vocab,
                                   word_level_target=False)
    print(phrase.ljust(40), translation)
Explanation: In the previous exercise we cheated because we gave the complete sequence along with the solution in the input sequence.
To be more realistic we need to use the model in a setting where we do not provide any token of expected translation as part of the input sequence: the model shall predict one token at a time starting only from the source sequence along with the &lt;GO&gt; special symbol. At each step, we append the new predicted output token in the input sequence to predict the next token:
End of explanation
phrases = [
    "quatre vingt et un",
    "quarante douze",
    "onze mille soixante vingt sept",
    "deux mille soixante vingt quatorze",
]
for phrase in phrases:
    translation = greedy_translate(simple_seq2seq, phrase,
                                   shared_vocab, rev_shared_vocab,
                                   word_level_target=False)
    print(phrase.ljust(40), translation)
Explanation: The results are far from perfect but we can see that the network has already picked up some translation skills.
Why does the partially trained network is able to give the correct translation for:
"sept mille huit cent cinquante neuf"
but not for:
"cent mille douze" ?
The answer is as following:
- it is rather easy for the network to learn a mapping between symbols (first case), by dismissing "cent" and "mille";
- outputing the right amount of symbols, especially 0s for "cent mille douze" requires more reasoning and ability to count.
Let's have a look at generalization out of correct French and see if the network would generalize like a French speaker would do:
End of explanation
def phrase_accuracy(model, num_sequences, fr_sequences, n_samples=300,
                    decoder_func=greedy_translate):
    correct = []
    n_samples = len(num_sequences) if n_samples is None else n_samples
    for i, num_seq, fr_seq in zip(range(n_samples), num_sequences, fr_sequences):
        if i % 100 == 0:
            print("Decoding %d/%d" % (i, n_samples))
        predicted_seq = decoder_func(simple_seq2seq, fr_seq,
                                     shared_vocab, rev_shared_vocab,
                                     word_level_target=False)
        correct.append(num_seq == predicted_seq)
    return np.mean(correct)
print("Phrase-level train accuracy: %0.3f"
      % phrase_accuracy(simple_seq2seq, num_train, fr_train))
print("Phrase-level test accuracy: %0.3f"
      % phrase_accuracy(simple_seq2seq, num_test, fr_test))
Explanation: Model evaluation
Because we expect only one correct translation for a given source sequence, we can use phrase-level accuracy as a metric to quantify our model quality.
Note that this is not the case for real translation models (e.g. from French to English on arbitrary sentences). Evaluation of a machine translation model is tricky in general. Automated evaluation can somehow be done at the corpus level with the BLEU score (bilingual evaluation understudy) given a large enough sample of correct translations provided by certified translators but its only a noisy proxy.
The only good evaluation is to give a large enough sample of the model predictions on some test sentences to certified translators and ask them to give an evaluation (e.g. a score between 0 and 6, 0 for non-sensical and 6 for the hypothetical perfect translation). However in practice this is very costly to do.
Fortunately we can just use phrase-level accuracy on a our very domain specific toy problem:
End of explanation
def beam_translate(model, source_sequence, shared_vocab, rev_shared_vocab,
                   word_level_source=True, word_level_target=True,
                   beam_size=10, return_ll=False):
    Decode candidate translations with a beam search strategy
    
    If return_ll is False, only the best candidate string is returned.
    If return_ll is True, all the candidate strings and their loglikelihoods
    are returned.
    
# %load solutions/beam_search.py
def beam_translate(model, source_sequence, shared_vocab, rev_shared_vocab,
                   word_level_source=True, word_level_target=True,
                   beam_size=10, return_ll=False):
    Decode candidate translations with a beam search strategy
    If return_ll is False, only the best candidate string is returned.
    If return_ll is True, all the candidate strings and their loglikelihoods
    are returned.
    
    # Initialize the list of input token ids with the source sequence
    source_tokens = tokenize(source_sequence, word_level=word_level_source)
    input_ids = [shared_vocab.get(t, UNK) for t in source_tokens[::-1]]
    input_ids += [shared_vocab[GO]]
    # initialize loglikelihood, input token ids, decoded tokens for
    # each candidate in the beam
    candidates = [(0, input_ids[:], [], False)]
    # Prepare a fixed size numpy array that matches the expected input
    # shape for the model
    input_array = np.empty(shape=(beam_size, model.input_shape[1]),
                           dtype=np.int32)
    while any([not done and (len(input_ids) < max_length)
               for _, input_ids, _, done in candidates]):
        # Vectorize a the list of input tokens and use zeros padding.
        input_array.fill(shared_vocab[PAD])
        for i, (_, input_ids, _, done) in enumerate(candidates):
            if not done:
                input_array[i, -len(input_ids):] = input_ids
        # Predict the next output in a single call to the model to amortize
        # the overhead and benefit from vector data parallelism on GPU.
        next_likelihood_batch = model(input_array).numpy()
        # Build the new candidates list by summing the loglikelood of the
        # next token with their parents for each new possible expansion.
        new_candidates = []
        for i, (ll, input_ids, decoded, done) in enumerate(candidates):
            if done:
                new_candidates.append((ll, input_ids, decoded, done))
            else:
                next_loglikelihoods = np.log(next_likelihood_batch[i, -1])
                for next_token_id, next_ll in enumerate(next_loglikelihoods):
                    new_ll = ll + next_ll
                    new_input_ids = input_ids[:]
                    new_input_ids.append(next_token_id)
                    new_decoded = decoded[:]
                    new_done = done
                    if next_token_id == shared_vocab[EOS]:
                        new_done = True
                    if not new_done:
                        new_decoded.append(rev_shared_vocab[next_token_id])
                    new_candidates.append(
                        (new_ll, new_input_ids, new_decoded, new_done))
        # Only keep a beam of the most promising candidates
        new_candidates.sort(reverse=True)
        candidates = new_candidates[:beam_size]
    separator = " " if word_level_target else ""
    if return_ll:
        return [(separator.join(decoded), ll) for ll, _, decoded, _ in candidates]
    else:
        _, _, decoded, done = candidates[0]
        return separator.join(decoded)
candidates = beam_translate(simple_seq2seq, "cent mille un",
                            shared_vocab, rev_shared_vocab,
                            word_level_target=False,
                            return_ll=True, beam_size=10)
candidates
candidates = beam_translate(simple_seq2seq, "quatre vingts",
                            shared_vocab, rev_shared_vocab,
                            word_level_target=False,
                            return_ll=True, beam_size=10)
candidates
Explanation: Bonus: Decoding with a Beam Search
Instead of decoding with greedy strategy that only considers the most-likely next token at each prediction, we can hold a priority queue of the most promising top-n sequences ordered by loglikelihoods.
This could potentially improve the final accuracy of an imperfect model: indeed it can be the case that the most likely sequence (based on the conditional proability estimated by the model) starts with a character that is not the most likely alone.
Bonus Exercise:
- build a beam_translate function which decodes candidate translations with a beam search strategy
- use a list of candidates, tracking beam_size candidates and their corresponding likelihood
- compute predictions for the next outputs by using predict with a batch of the size of the beam
- be careful to stop appending results if EOS symbols have been found for each candidate!
End of explanation
print("Phrase-level test accuracy: %0.3f"
      % phrase_accuracy(simple_seq2seq, num_test, fr_test,
                        decoder_func=beam_translate))
print("Phrase-level train accuracy: %0.3f"
      % phrase_accuracy(simple_seq2seq, num_train, fr_train,
                        decoder_func=beam_translate))
Explanation: Model Accuracy with Beam Search Decoding
End of explanation
<END_TASK>