:label:sec_seq2seq
As we have seen in :numref:sec_machine_translation
,
in machine translation
both the input and output are a variable-length sequence.
To address this type of problem,
we have designed a general encoder-decoder architecture
in :numref:sec_encoder-decoder
.
In this section,
we will
use two RNNs to design
the encoder and the decoder of
this architecture
and apply it to sequence to sequence learning
for machine translation
:cite:Sutskever.Vinyals.Le.2014,Cho.Van-Merrienboer.Gulcehre.ea.2014
.
Following the design principle
of the encoder-decoder architecture,
the RNN encoder can
take a variable-length sequence as the input and transforms it into a fixed-shape hidden state.
In other words,
information of the input (source) sequence
is encoded in the hidden state of the RNN encoder.
To generate the output sequence token by token,
a separate RNN decoder
can predict the next token based on
what tokens have been seen (such as in language modeling) or generated,
together with the encoded information of the input sequence.
:numref:fig_seq2seq
illustrates
how to use two RNNs
for sequence to sequence learning
in machine translation.
:label:fig_seq2seq
In :numref:fig_seq2seq
,
the special "<eos>" token
marks the end of the sequence.
The model can stop making predictions
once this token is generated.
At the initial time step of the RNN decoder,
there are two special design decisions.
First, the special beginning-of-sequence "<bos>" token is an input.
Second,
the final hidden state of the RNN encoder is used
to initiate the hidden state of the decoder.
In designs such as :cite:Sutskever.Vinyals.Le.2014
,
this is exactly
how the encoded input sequence information
is fed into the decoder for generating the output (target) sequence.
In some other designs such as :cite:Cho.Van-Merrienboer.Gulcehre.ea.2014
,
the final hidden state of the encoder
is also fed into the decoder as
part of the inputs
at every time step as shown in :numref:fig_seq2seq
.
Similar to the training of language models in
:numref:sec_language_model
,
we can allow the labels to be the original output sequence,
shifted by one token:
"<bos>", "Ils", "regardent", "." $\rightarrow$
"Ils", "regardent", ".", "<eos>".
In the following,
we will explain the design of :numref:fig_seq2seq
in greater detail.
We will train this model for machine translation
on the English-French dataset as introduced in
:numref:sec_machine_translation
.
%load ../utils/djl-imports
%load ../utils/plot-utils
%load ../utils/Functions.java
%load ../utils/PlotUtils.java
%load ../utils/StopWatch.java
%load ../utils/Accumulator.java
%load ../utils/Animator.java
%load ../utils/TrainingChapter9.java
%load ../utils/timemachine/Vocab.java
%load ../utils/timemachine/RNNModel.java
%load ../utils/timemachine/RNNModelScratch.java
%load ../utils/timemachine/TimeMachine.java
%load ../utils/timemachine/TimeMachineDataset.java
%load ../utils/NMT.java
%load ../utils/lstm/Encoder.java
%load ../utils/lstm/Decoder.java
%load ../utils/lstm/EncoderDecoder.java
import java.util.stream.*;
import ai.djl.modality.nlp.*;
import ai.djl.modality.nlp.embedding.*;
NDManager manager = NDManager.newBaseManager();
ParameterStore ps = new ParameterStore(manager, false);
Technically speaking,
the encoder transforms an input sequence of variable length into a fixed-shape context variable $\mathbf{c}$, and encodes the input sequence information in this context variable.
As depicted in :numref:fig_seq2seq
,
we can use an RNN to design the encoder.
Let us consider a sequence example (batch size: 1). Suppose that the input sequence is $x_1, \ldots, x_T$, such that $x_t$ is the $t^{\mathrm{th}}$ token in the input text sequence. At time step $t$, the RNN transforms the input feature vector $\mathbf{x}_t$ for $x_t$ and the hidden state $\mathbf{h} _{t-1}$ from the previous time step into the current hidden state $\mathbf{h}_t$. We can use a function $f$ to express the transformation of the RNN's recurrent layer:
$$\mathbf{h}_t = f(\mathbf{x}_t, \mathbf{h}_{t-1}). $$In general, the encoder transforms the hidden states at all the time steps into the context variable through a customized function $q$:
$$\mathbf{c} = q(\mathbf{h}_1, \ldots, \mathbf{h}_T).$$For example, when choosing $q(\mathbf{h}_1, \ldots, \mathbf{h}_T) = \mathbf{h}_T$ such as in :numref:fig_seq2seq
,
the context variable is just the hidden state $\mathbf{h}_T$
of the input sequence at the final time step.
So far we have used a unidirectional RNN to design the encoder, where a hidden state only depends on the input subsequence at and before the time step of the hidden state. We can also construct encoders using bidirectional RNNs. In this case, a hidden state depends on the subsequence before and after the time step (including the input at the current time step), which encodes the information of the entire sequence.
Now let us implement the RNN encoder.
Note that we use an embedding layer
to obtain the feature vector for each token in the input sequence.
The weight
of an embedding layer
is a matrix
whose number of rows equals to the size of the input vocabulary (vocabSize
)
and number of columns equals to the feature vector's dimension (embedSize
).
For any input token index $i$,
the embedding layer
fetches the $i^{\mathrm{th}}$ row (starting from 0) of the weight matrix
to return its feature vector.
Besides,
here we choose a multilayer GRU to
implement the encoder.
public static class Seq2SeqEncoder extends Encoder {
private TrainableWordEmbedding embedding;
private GRU rnn;
/* The RNN encoder for sequence to sequence learning. */
public Seq2SeqEncoder(
int vocabSize, int embedSize, int numHiddens, int numLayers, float dropout) {
List<String> list =
IntStream.range(0, vocabSize)
.mapToObj(String::valueOf)
.collect(Collectors.toList());
Vocabulary vocab = new DefaultVocabulary(list);
// Embedding layer
embedding =
TrainableWordEmbedding.builder()
.optNumEmbeddings(vocabSize)
.setEmbeddingSize(embedSize)
.setVocabulary(vocab)
.build();
addChildBlock("embedding", embedding);
rnn =
GRU.builder()
.setNumLayers(numLayers)
.setStateSize(numHiddens)
.optReturnState(true)
.optBatchFirst(false)
.optDropRate(dropout)
.build();
addChildBlock("rnn", rnn);
}
/** {@inheritDoc} */
@Override
public void initializeChildBlocks(
NDManager manager, DataType dataType, Shape... inputShapes) {
embedding.initialize(manager, dataType, inputShapes[0]);
Shape[] shapes = embedding.getOutputShapes(new Shape[] {inputShapes[0]});
try (NDManager sub = manager.newSubManager()) {
NDArray nd = sub.zeros(shapes[0], dataType);
nd = nd.swapAxes(0, 1);
rnn.initialize(manager, dataType, nd.getShape());
}
}
@Override
protected NDList forwardInternal(
ParameterStore ps,
NDList inputs,
boolean training,
PairList<String, Object> params) {
NDArray X = inputs.head();
// The output `X` shape: (`batchSize`, `numSteps`, `embedSize`)
X = embedding.forward(ps, new NDList(X), training, params).head();
// In RNN models, the first axis corresponds to time steps
X = X.swapAxes(0, 1);
return rnn.forward(ps, new NDList(X), training);
}
}
The returned variables of recurrent layers
have been explained in :numref:sec_rnn-concise
.
Let us still use a concrete example
to illustrate the above encoder implementation.
Below
we instantiate a two-layer GRU encoder
whose number of hidden units is 16.
Given
a minibatch of sequence inputs X
(batch size: 4, number of time steps: 7),
the hidden states of the last layer
at all the time steps
(output
return by the encoder's recurrent layers)
are a tensor
of shape
(number of time steps, batch size, number of hidden units).
Seq2SeqEncoder encoder = new Seq2SeqEncoder(10, 8, 16, 2, 0);
NDArray X = manager.zeros(new Shape(4, 7));
encoder.initialize(manager, DataType.FLOAT32, X.getShape());
NDList outputState = encoder.forward(ps, new NDList(X), false);
NDArray output = outputState.head();
output.getShape()
Since a GRU is employed here,
the shape of the multilayer hidden states
at the final time step
is
(number of hidden layers, batch size, number of hidden units).
If an LSTM is used,
memory cell information will also be contained in state
.
NDList state = outputState.subNDList(1);
System.out.println(state.size());
System.out.println(state.head().getShape());
:label:sec_seq2seq_decoder
As we just mentioned, the context variable $\mathbf{c}$ of the encoder's output encodes the entire input sequence $x_1, \ldots, x_T$. Given the output sequence $y_1, y_2, \ldots, y_{T'}$ from the training dataset, for each time step $t'$ (the symbol differs from the time step $t$ of input sequences or encoders), the probability of the decoder output $y_{t'}$ is conditional on the previous output subsequence $y_1, \ldots, y_{t'-1}$ and the context variable $\mathbf{c}$, i.e., $P(y_{t'} \mid y_1, \ldots, y_{t'-1}, \mathbf{c})$.
To model this conditional probability on sequences, we can use another RNN as the decoder. At any time step $t^\prime$ on the output sequence, the RNN takes the output $y_{t^\prime-1}$ from the previous time step and the context variable $\mathbf{c}$ as its input, then transforms them and the previous hidden state $\mathbf{s}_{t^\prime-1}$ into the hidden state $\mathbf{s}_{t^\prime}$ at the current time step. As a result, we can use a function $g$ to express the transformation of the decoder's hidden layer:
$$\mathbf{s}_{t^\prime} = g(y_{t^\prime-1}, \mathbf{c}, \mathbf{s}_{t^\prime-1}).$$:eqlabel:eq_seq2seq_s_t
After obtaining the hidden state of the decoder, we can use an output layer and the softmax operation to compute the conditional probability distribution $P(y_{t^\prime} \mid y_1, \ldots, y_{t^\prime-1}, \mathbf{c})$ for the output at time step $t^\prime$.
Following :numref:fig_seq2seq
,
when implementing the decoder as follows,
we directly use the hidden state at the final time step
of the encoder
to initialize the hidden state of the decoder.
This requires that the RNN encoder and the RNN decoder have the same number of layers and hidden units.
To further incorporate the encoded input sequence information,
the context variable is concatenated
with the decoder input at all the time steps.
To predict the probability distribution of the output token,
a fully-connected layer is used to transform
the hidden state at the final layer of the RNN decoder.
public static class Seq2SeqDecoder extends Decoder {
private TrainableWordEmbedding embedding;
private GRU rnn;
private Linear dense;
/* The RNN decoder for sequence to sequence learning. */
public Seq2SeqDecoder(
int vocabSize, int embedSize, int numHiddens, int numLayers, float dropout) {
List<String> list =
IntStream.range(0, vocabSize)
.mapToObj(String::valueOf)
.collect(Collectors.toList());
Vocabulary vocab = new DefaultVocabulary(list);
embedding =
TrainableWordEmbedding.builder()
.optNumEmbeddings(vocabSize)
.setEmbeddingSize(embedSize)
.setVocabulary(vocab)
.build();
addChildBlock("embedding", embedding);
rnn =
GRU.builder()
.setNumLayers(numLayers)
.setStateSize(numHiddens)
.optReturnState(true)
.optBatchFirst(false)
.optDropRate(dropout)
.build();
addChildBlock("rnn", rnn);
dense = Linear.builder().setUnits(vocabSize).build();
addChildBlock("dense", dense);
}
/** {@inheritDoc} */
@Override
public void initializeChildBlocks(
NDManager manager, DataType dataType, Shape... inputShapes) {
embedding.initialize(manager, dataType, inputShapes[0]);
try (NDManager sub = manager.newSubManager()) {
Shape shape = embedding.getOutputShapes(new Shape[] {inputShapes[0]})[0];
NDArray nd = sub.zeros(shape, dataType).swapAxes(0, 1);
NDArray state = sub.zeros(inputShapes[1], dataType);
NDArray context = state.get(new NDIndex(-1));
context =
context.broadcast(
new Shape(
nd.getShape().head(),
context.getShape().head(),
context.getShape().get(1)));
// Broadcast `context` so it has the same `numSteps` as `X`
NDArray xAndContext = NDArrays.concat(new NDList(nd, context), 2);
rnn.initialize(manager, dataType, xAndContext.getShape());
shape = rnn.getOutputShapes(new Shape[] {xAndContext.getShape()})[0];
dense.initialize(manager, dataType, shape);
}
}
public NDList initState(NDList encOutputs) {
return new NDList(encOutputs.get(1));
}
@Override
protected NDList forwardInternal(
ParameterStore parameterStore,
NDList inputs,
boolean training,
PairList<String, Object> params) {
NDArray X = inputs.head();
NDArray state = inputs.get(1);
X =
embedding
.forward(parameterStore, new NDList(X), training, params)
.head()
.swapAxes(0, 1);
NDArray context = state.get(new NDIndex(-1));
// Broadcast `context` so it has the same `numSteps` as `X`
context =
context.broadcast(
new Shape(
X.getShape().head(),
context.getShape().head(),
context.getShape().get(1)));
NDArray xAndContext = NDArrays.concat(new NDList(X, context), 2);
NDList rnnOutput =
rnn.forward(parameterStore, new NDList(xAndContext, state), training);
NDArray output = rnnOutput.head();
state = rnnOutput.get(1);
output =
dense.forward(parameterStore, new NDList(output), training)
.head()
.swapAxes(0, 1);
return new NDList(output, state);
}
}
To illustrate the implemented decoder, below we instantiate it with the same hyperparameters from the aforementioned encoder. As we can see, the output shape of the decoder becomes (batch size, number of time steps, vocabulary size), where the last dimension of the tensor stores the predicted token distribution.
Seq2SeqDecoder decoder = new Seq2SeqDecoder(10, 8, 16, 2, 0);
state = decoder.initState(outputState);
NDList input = new NDList(X).addAll(state);
decoder.initialize(manager, DataType.FLOAT32, input.getShapes());
outputState = decoder.forward(ps, input, false);
output = outputState.head();
System.out.println(output.getShape());
state = outputState.subNDList(1);
System.out.println(state.size());
System.out.println(state.head().getShape());
To summarize,
the layers in the above RNN encoder-decoder model are illustrated in :numref:fig_seq2seq_details
.
:label:fig_seq2seq_details
At each time step, the decoder
predicts a probability distribution for the output tokens.
Similar to language modeling,
we can apply softmax to obtain the distribution
and calculate the cross-entropy loss for optimization.
Recall :numref:sec_machine_translation
that the special padding tokens
are appended to the end of sequences
so sequences of varying lengths
can be efficiently loaded
in minibatches of the same shape.
However,
prediction of padding tokens
should be excluded from loss calculations.
To this end,
we can use the following
sequenceMask
function
to mask irrelevant entries with zero values
so later
multiplication of any irrelevant prediction
with zero equals to zero.
For example,
if the valid length of two sequences
excluding padding tokens
are one and two, respectively,
the remaining entries after
the first one
and the first two entries are cleared to zeros.
X = manager.create(new int[][] {{1, 2, 3}, {4, 5, 6}});
System.out.println(X.sequenceMask(manager.create(new int[] {1, 2})));
We can also mask all the entries across the last few axes. If you like, you may even specify to replace such entries with a non-zero value.
X = manager.ones(new Shape(2, 3, 4));
System.out.println(X.sequenceMask(manager.create(new int[] {1, 2}), -1));
Now we can extend the softmax cross-entropy loss to allow the masking of irrelevant predictions. Initially, masks for all the predicted tokens are set to one. Once the valid length is given, the mask corresponding to any padding token will be cleared to zero. In the end, the loss for all the tokens will be multipled by the mask to filter out irrelevant predictions of padding tokens in the loss.
public static class MaskedSoftmaxCELoss extends SoftmaxCrossEntropyLoss {
/* The softmax cross-entropy loss with masks. */
@Override
public NDArray evaluate(NDList labels, NDList predictions) {
NDArray weights = labels.head().onesLike().expandDims(-1).sequenceMask(labels.get(1));
// Remove the states from the labels NDList because otherwise, it will throw an error as SoftmaxCrossEntropyLoss
// expects only one NDArray for label and one NDArray for prediction
labels.remove(1);
return super.evaluate(labels, predictions).mul(weights).mean(new int[] {1});
}
}
For a sanity check, we can create three identical sequences. Then we can specify that the valid lengths of these sequences are 4, 2, and 0, respectively. As a result, the loss of the first sequence should be twice as large as that of the second sequence, while the third sequence should have a zero loss.
Loss loss = new MaskedSoftmaxCELoss();
NDList labels = new NDList(manager.ones(new Shape(3, 4)));
labels.add(manager.create(new int[] {4, 2, 0}));
NDList predictions = new NDList(manager.ones(new Shape(3, 4, 10)));
System.out.println(loss.evaluate(labels, predictions));
:label:sec_seq2seq_training
In the following training loop,
we concatenate the special beginning-of-sequence token
and the original output sequence excluding the final token as
the input to the decoder, as shown in :numref:fig_seq2seq
.
This is called teacher forcing because
the original output sequence (token labels) is fed into the decoder.
Alternatively,
we could also feed the predicted token
from the previous time step
as the current input to the decoder.
public static void trainSeq2Seq(
EncoderDecoder net,
ArrayDataset dataset,
float lr,
int numEpochs,
Vocab tgtVocab,
Device device)
throws IOException, TranslateException {
Loss loss = new MaskedSoftmaxCELoss();
Tracker lrt = Tracker.fixed(lr);
Optimizer adam = Optimizer.adam().optLearningRateTracker(lrt).build();
DefaultTrainingConfig config =
new DefaultTrainingConfig(loss)
.optOptimizer(adam) // Optimizer (loss function)
.optInitializer(new XavierInitializer(), "");
Model model = Model.newInstance("");
model.setBlock(net);
Trainer trainer = model.newTrainer(config);
Animator animator = new Animator();
StopWatch watch;
Accumulator metric;
double lossValue = 0, speed = 0;
for (int epoch = 1; epoch <= numEpochs; epoch++) {
watch = new StopWatch();
metric = new Accumulator(2); // Sum of training loss, no. of tokens
try (NDManager childManager = manager.newSubManager(device)) {
// Iterate over dataset
for (Batch batch : dataset.getData(childManager)) {
NDArray X = batch.getData().get(0);
NDArray lenX = batch.getData().get(1);
NDArray Y = batch.getLabels().get(0);
NDArray lenY = batch.getLabels().get(1);
NDArray bos =
childManager
.full(new Shape(Y.getShape().get(0)), tgtVocab.getIdx("<bos>"))
.reshape(-1, 1);
NDArray decInput =
NDArrays.concat(
new NDList(bos, Y.get(new NDIndex(":, :-1"))),
1); // Teacher forcing
try (GradientCollector gc = Engine.getInstance().newGradientCollector()) {
NDArray yHat =
net.forward(
new ParameterStore(manager, false),
new NDList(X, decInput, lenX),
true)
.get(0);
NDArray l = loss.evaluate(new NDList(Y, lenY), new NDList(yHat));
gc.backward(l);
metric.add(new float[] {l.sum().getFloat(), lenY.sum().getLong()});
}
TrainingChapter9.gradClipping(net, 1, childManager);
// Update parameters
trainer.step();
}
}
lossValue = metric.get(0) / metric.get(1);
speed = metric.get(1) / watch.stop();
if ((epoch + 1) % 10 == 0) {
animator.add(epoch + 1, (float) lossValue, "loss");
animator.show();
}
}
System.out.format(
"loss: %.3f, %.1f tokens/sec on %s%n", lossValue, speed, device.toString());
}
Now we can create and train an RNN encoder-decoder model for sequence to sequence learning on the machine translation dataset.
int embedSize = 32;
int numHiddens = 32;
int numLayers = 2;
int batchSize = 64;
int numSteps = 10;
int numEpochs = Integer.getInteger("MAX_EPOCH", 300);
float dropout = 0.1f, lr = 0.005f;
Device device = manager.getDevice();
Pair<ArrayDataset, Pair<Vocab, Vocab>> dataNMT =
NMT.loadDataNMT(batchSize, numSteps, 600, manager);
ArrayDataset dataset = dataNMT.getKey();
Vocab srcVocab = dataNMT.getValue().getKey();
Vocab tgtVocab = dataNMT.getValue().getValue();
encoder = new Seq2SeqEncoder(srcVocab.length(), embedSize, numHiddens, numLayers, dropout);
decoder = new Seq2SeqDecoder(tgtVocab.length(), embedSize, numHiddens, numLayers, dropout);
EncoderDecoder net = new EncoderDecoder(encoder, decoder);
trainSeq2Seq(net, dataset, lr, numEpochs, tgtVocab, device);
To predict the output sequence
token by token,
at each decoder time step
the predicted token from the previous
time step is fed into the decoder as an input.
Similar to training,
at the initial time step
the beginning-of-sequence ("<bos>") token
is fed into the decoder.
This prediction process
is illustrated in :numref:fig_seq2seq_predict
.
When the end-of-sequence ("<eos>") token is predicted,
the prediction of the output sequence is complete.
:label:fig_seq2seq_predict
We will introduce different
strategies for sequence generation in
:numref:sec_beam-search
.
/* Predict for sequence to sequence. */
public static Pair<String, ArrayList<NDArray>> predictSeq2Seq(
EncoderDecoder net,
String srcSentence,
Vocab srcVocab,
Vocab tgtVocab,
int numSteps,
Device device,
boolean saveAttentionWeights)
throws IOException, TranslateException {
Integer[] srcTokens =
Stream.concat(
Arrays.stream(
srcVocab.getIdxs(srcSentence.toLowerCase().split(" "))),
Arrays.stream(new Integer[] {srcVocab.getIdx("<eos>")}))
.toArray(Integer[]::new);
NDArray encValidLen = manager.create(srcTokens.length);
int[] truncateSrcTokens = NMT.truncatePad(srcTokens, numSteps, srcVocab.getIdx("<pad>"));
// Add the batch axis
NDArray encX = manager.create(truncateSrcTokens).expandDims(0);
NDList encOutputs =
net.encoder.forward(
new ParameterStore(manager, false), new NDList(encX, encValidLen), false);
NDList decState = net.decoder.initState(encOutputs.addAll(new NDList(encValidLen)));
// Add the batch axis
NDArray decX = manager.create(new float[] {tgtVocab.getIdx("<bos>")}).expandDims(0);
ArrayList<Integer> outputSeq = new ArrayList<>();
ArrayList<NDArray> attentionWeightSeq = new ArrayList<>();
for (int i = 0; i < numSteps; i++) {
NDList output =
net.decoder.forward(
new ParameterStore(manager, false),
new NDList(decX).addAll(decState),
false);
NDArray Y = output.get(0);
decState = output.subNDList(1);
// We use the token with the highest prediction likelihood as the input
// of the decoder at the next time step
decX = Y.argMax(2);
int pred = (int) decX.squeeze(0).getLong();
// Save attention weights (to be covered later)
if (saveAttentionWeights) {
attentionWeightSeq.add(net.decoder.attentionWeights);
}
// Once the end-of-sequence token is predicted, the generation of the
// output sequence is complete
if (pred == tgtVocab.getIdx("<eos>")) {
break;
}
outputSeq.add(pred);
}
String outputString =
String.join(" ", tgtVocab.toTokens(outputSeq).toArray(new String[] {}));
return new Pair<>(outputString, attentionWeightSeq);
}
We can evaluate a predicted sequence
by comparing it with the
label sequence (the ground-truth).
BLEU (Bilingual Evaluation Understudy),
though originally proposed for evaluating
machine translation results :cite:Papineni.Roukos.Ward.ea.2002
,
has been extensively used in measuring
the quality of output sequences for different applications.
In principle, for any $n$-grams in the predicted sequence,
BLEU evaluates whether this $n$-grams appears
in the label sequence.
Denote by $p_n$ the precision of $n$-grams, which is the ratio of the number of matched $n$-grams in the predicted and label sequences to the number of $n$-grams in the predicted sequence. To explain, given a label sequence $A$, $B$, $C$, $D$, $E$, $F$, and a predicted sequence $A$, $B$, $B$, $C$, $D$, we have $p_1 = 4/5$, $p_2 = 3/4$, $p_3 = 1/3$, and $p_4 = 0$. Besides, let $\mathrm{len}_{\text{label}}$ and $\mathrm{len}_{\text{pred}}$ be the numbers of tokens in the label sequence and the predicted sequence, respectively. Then, BLEU is defined as
$$ \exp\left(\min\left(0, 1 - \frac{\mathrm{len}_{\text{label}}}{\mathrm{len}_{\text{pred}}}\right)\right) \prod_{n=1}^k p_n^{1/2^n},$$:eqlabel:eq_bleu
where $k$ is the longest $n$-grams for matching.
Based on the definition of BLEU in :eqref:eq_bleu
,
whenever the predicted sequence is the same as the label sequence, BLEU is 1.
Moreover,
since matching longer $n$-grams is more difficult,
BLEU assigns a greater weight
to a longer $n$-gram precision.
Specifically, when $p_n$ is fixed,
$p_n^{1/2^n}$ increases as $n$ grows (the original paper uses $p_n^{1/n}$).
Furthermore,
since
predicting shorter sequences
tends to obtain a higher $p_n$ value,
the coefficient before the multiplication term in :eqref:eq_bleu
penalizes shorter predicted sequences.
For example, when $k=2$,
given the label sequence $A$, $B$, $C$, $D$, $E$, $F$ and the predicted sequence $A$, $B$,
although $p_1 = p_2 = 1$, the penalty factor $\exp(1-6/2) \approx 0.14$ lowers the BLEU.
We implement the BLEU measure as follows.
/* Compute the BLEU. */
public static double bleu(String predSeq, String labelSeq, int k) {
String[] predTokens = predSeq.split(" ");
String[] labelTokens = labelSeq.split(" ");
int lenPred = predTokens.length;
int lenLabel = labelTokens.length;
double score = Math.exp(Math.min(0, 1 - lenLabel / lenPred));
for (int n = 1; n < k + 1; n++) {
float numMatches = 0f;
HashMap<String, Integer> labelSubs = new HashMap<>();
for (int i = 0; i < lenLabel - n + 1; i++) {
String key =
String.join(" ", Arrays.copyOfRange(labelTokens, i, i + n, String[].class));
labelSubs.put(key, labelSubs.getOrDefault(key, 0) + 1);
}
for (int i = 0; i < lenPred - n + 1; i++) {
String key =
String.join(" ", Arrays.copyOfRange(predTokens, i, i + n, String[].class));
if (labelSubs.getOrDefault(key, 0) > 0) {
numMatches += 1;
labelSubs.put(key, labelSubs.getOrDefault(key, 0) - 1);
}
}
score *= Math.pow(numMatches / (lenPred - n + 1), Math.pow(0.5, n));
}
return score;
}
In the end, we use the trained RNN encoder-decoder to translate a few English sentences into French and compute the BLEU of the results.
String[] engs = {"go .", "i lost .", "he\'s calm .", "i\'m home ."};
String[] fras = {"va !", "j\'ai perdu .", "il est calme .", "je suis chez moi ."};
for (int i = 0; i < engs.length; i++) {
Pair<String, ArrayList<NDArray>> pair = predictSeq2Seq(net, engs[i], srcVocab, tgtVocab, numSteps, device, false);
String translation = pair.getKey();
ArrayList<NDArray> attentionWeightSeq = pair.getValue();
System.out.format("%s => %s, bleu %.3f\n", engs[i], translation, bleu(translation, fras[i], 2));
}