Incremental Beam Manipulation for Natural Language Generation (2021)

Abstract: The performance of natural language generation systems has improved substantially with modern neural networks. At test time they typically employ beam search to avoid locally optimal but globally suboptimal predictions. However, due to model errors, a larger beam size can lead to deteriorating performance according to the evaluation metric. For this reason, it is common to rerank the output of beam search, but this relies on beam search to produce a good set of hypotheses, which limits the potential gains. Other alternatives to beam search require changes to the training of the model, which restricts their applicability compared to beam search. This paper proposes incremental beam manipulation, i.e. reranking the hypotheses in the beam during decoding instead of only at the end. This way, hypotheses that are unlikely to lead to a good final output are discarded, and in their place hypotheses that would have been ignored will be considered instead. Applying incremental beam manipulation leads to an improvement of 1.93 and 5.82 BLEU points over vanilla beam search for the test sets of the E2E and WebNLG challenges respectively. The proposed method also outperformed a strong reranker by 1.04 BLEU points on the E2E challenge, while being on par with it on the WebNLG dataset.

## introduction in natural language generation (nlg), the goal is to generate text representing structured information (e.g. a database record or a meaning representation) that is both fluent and contains the right information. sequence-to-sequence models (seq2seq) have been effective on many tasks in nlg (for example: @xcite . these systems first create an embedding for the input information. this embedding is used incrementally during decoding, generating one token at a time. seq2seq models are generally decoded using beam search, to mitigate the effect of locally optimal but globally suboptimal decisions made by greedy search. the performance of nlg systems can plateau or even decrease when beam sizes larger than 10 are used, which is counter-intuitive since larger beams produce more likely sequences according to the model. for example, @xcite used a beam size of 10, and @xcite found a size of 5 to be optimal. decreasing performance has been found across a range of tasks including @xcite . moreover, it and was given by @xcite as one of the six main challenges facing neural machine translation. to investigate this, @xcite presented an exact search algorithm to find the most likely output according to a seq2seq model. however, this performed poorly compared to beam search, demonstrating that search errors (from beam search) can mask model errors (from the seq2seq model). to mitigate the limitations of beam search, it is common practice to apply a reranker to the final set of hypotheses. this can be done by defining a reranking criterion (for example: @xcite @xcite or by training a reranker to predict the best hypothesis in a beam (for example: @xcite . training a reranker allows us to take into account information from outside the model and mitigate model errors. however, rerankers can only choose a hypothesis from the final beam, which limits their potential. to quantify this, we trained the seq2seq model proposed by @xcite , and applied it to the e2e validation set @xcite . for each instance, we recorded the point at which all gold-standard references fell out of the beam, meaning that none of the partial hypotheses in the beam could be extended to a gold reference. a final beam containing at least one of the references would score optimally with an oracle reranker (providing an upper bound on performance). figure 1 shows the results for beam size 3. 1 the final beam contained a reference in only 60 out of 547 cases (11%). for the remaining 89% of the cases, even an oracle reranker would be unable to give optimal results. the figure also shows that in over half of the cases, all references fell out in the first 6 steps. in contrast, references that were still in the beam at step 15 were almost certain to stay in the beam until the end. these observations suggest that an early manipulation of the beam has a strong potential to improve performance. in this paper, we propose a method for manipulating which items are pruned from the beam at each stage of decoding. we then present evidence that this is a successful approach: it led to an improvement of 1.93, and 5.82 bleu points over vanilla beam search on the e2e and webnlg challenges, respectively. when comparing to a strong reranker, the performance of incremental beam manipulation was similar on the webnlg dataset, whilst increasing the performance on the e2e challenge by 1.04 points. we also applied beam manipulation on top of length normalisation @xcite , and incremental beam manipulation was able to improve its performance. this paper is far from the first to try to improve beam search for natural language generation. one modification is to use a variable beam size instead of a fixed one @xcite . however, this can only improve decoding speed, as the ranking of the hypotheses in the beam remains unchanged, and thus model errors are exposed by the reduction of search errors. length normalisation @xcite is widely used strategy that often improves the performance of a beam search decoder, by mitigating the fact that seq2seq models are biased towards generating shorter sequences. rather than directly using model probabilities to order the hypotheses in the beam, each probability is normalised according to the length of the hypothesis, so that shorter hypotheses are penalised. however, this only has an impact once the hypotheses within the beam have different lengths. this only occurs towards the end of the decoding process, and we showed in the previous section that the reference hypotheses often fall out of the beam relatively early. furthermore, @xcite showed that the biases causing the deteriorating model performance are more complex than a simple length bias. wiseman and rush (2016) modified the training procedure for seq2seq models. they ran beam search and introduced a loss each time the gold standard sequence fell out of the beam. @xcite and @xcite also modified the training procedure. they added a term to the loss function that approximated the loss that the model would receive when generating using a beam search method for each example in the training set. however, one of the reasons that beam search has been so widely used is that it can be applied on top of a language model without changing the training procedure, and this is lost with these approaches. @xcite manipulated the hidden state of the language model at each step of the decoding. this was achieved via a multi-output regressor that produced a vector that is added to the hidden state used in decoding. the regressor was trained via reinforcement learning, and the training signal was gathered by injecting unstructured noise to the hidden state. @xcite also manipulate the hidden state. for each training instance, they apply beam search and take the hypothesis with the highest bleu score. the manipulator network is trained to encourage a greedy decoder to produce this output. both of these approaches rely on inferring a better hidden state to be used in the decoding, which is not straightforward to define. we instead manipulate the hypotheses in the beam directly. finally, @xcite presented a framework for learning a beam search framework via imitation learning. this resulted in a beam aware algorithm which was proved to have no regret guarantees. while this paper makes a compelling argument for this method in theory, putting it into practice requires a number of further engineering decisions. our work can be seen as a way of applying this general framework using a simple and computationally efficient roll-out strategy. ## incremental beam manipulation in order to describe our method for incremental beam search, we first introduce terminology to describe a standard beam search decoder. the decoder produces a sequence iteratively, token by token. at each iteration it performs 3 actions: expand, rank and prune. the expand step generates all possible next step hypotheses. the rank step orders these hypotheses from most likely to least likely. the pruning step then removes the hypotheses that are near the end of this order. this formulation of the beam search algorithm enables us to view beam manipulation as a ranking problem since expand is determined by the (fixed) decoder and the size of the beam chosen determines the pruning. the rank step determines which hypotheses will not be kept in the next iteration and hence discarded. by modifying the ranking method used, we can choose the partial hypotheses expanded during beam search, taking into account the current state of the beam as well as signals beyond model scores. it is worth noting that while this paper applies beam manipulation on top of a seq2seq model, the techniques used could be applied without change to any conditional or unconditional neural language model that can be decoded using beam search. ## experiments in this section we will present results on the e2e @xcite and webnlg challenges @xcite . we evaluate the systems using the bleu implementation used in the original e2e challenge. 4 for all the experiments reported we use the seq2seq architecture from @xcite for the underlying model that we are trying to manipulate. foot_4 it is well-known that bleu is not a completely reliable method for predicting human perceptions to support the idea behind our approach, i.e. manipulating the beam during decoding instead of only at the end, we compare against existing rerankers applied to the beam at the end of decoding. these include the tgen reranker, proposed by @xcite , that has achieved state-of-theart bleu scores on nlg tasks, as well as the same reranker architecture defined in section 3.2. both architectures are trained to perform reranking of the final beam only. when comparing between these two methods of reranking the final beam, no significant difference in performance was found. in this section, we report results for the architecture defined in section 3.2. for completeness, results for both rerankers are included in appendix c. by using the same architecture both for the finalbeam reranker and for beam manipulation, we can be more confident that any difference in results is due to the beam manipulation strategy (reranking during decoding, not just at the end). in our experiments, we also consider length normalisation @xcite , which is a well-known technique that often increases the bleu score of the resulting sequences since it addresses the bias of language models to favour short sequences, as discussed in section 2. although the values assigned to a sequence when using length normalisation are no longer probabilities, it still performs the expand, rank and prune steps at each iteration of the decoding. hence, we can apply beam manipulation in tandem with length normalisation. finally, we also considered nucleus sampling @xcite ) as a baseline. however, it was found to decrease performance even when compared to vanilla beam search. in what follows, we will not only comment on test results when the beam size is tuned on the validation sets, but we will also comment on test results across all beam sizes. the reason for doing this is that considering all beam sizes assesses whether the technique is robust to changes in beam size. in our opinion, this makes for a more convincing result then just indicating a difference in performance at a single beam size. this is especially pertinent since a well-documented issue of beam search is that larger beam sizes can lead to deteriorating performance. the results table in appendix c indicates the validation set's optimal beam size for each of the systems. ## conclusions rerankers are commonly used to increase the performance of nlg systems decoded by beam search, by modifying which hypothesis from the final beam is chosen. this means that rerankers are dependent on good hypotheses reaching the final beam. however, this is often not the case; on the validation set of e2e challenge, only 11% of references were present in the final beam when the seq2seq model from @xcite was decoded with a beam size of 3. to address this limitation, we proposed incremental beam manipulation, which modifies the ranking of partial hypotheses within the beam at intermediate steps of the decoding, and hence chooses which are pruned. we evaluated this method on both the e2e and webnlg challenges. the results showed that applying beam manipulation, instead of a reranker, was able to increase the bleu score by 1.04 on the e2e challenge. we further showed that incremental beam manipulation was able to increase performance when applied on top of length normalisation. the optimal reranker for incremental beam manipulation may differ at each step of generation (for example, token 5 vs. token 20). in future work, we intend to refine our method further by conditioning the reranker on how far through the beam search we are. empirical methods in natural language processing (emnlp), pages 1296-1306. ning zhang, shui-long shen, annan zhou, and ye-shuang xu. 2019. investigation on performance of neural networks using quadratic relative error cost function. ieee access, 7:106642-106652.