A Systematic Characterization of Sampling Algorithms for Open-ended Language Generation

Proceedings of the 1st Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics and the 10th International Joint Conference on Natural Language Processing, pages 334–346 December 4 - 7, 2020. c⃝2020 Association for Computational Linguistics 334 A Systematic Characterization of Sampling Algorithms for Open-ended Language Generation Moin Nadeem∗ Massachusetts Institute of Technology mnadeem@mit.edu Tianxing He∗ Massachusetts Institute of Technology cloudygoose@csail.mit.edu Kyunghyun Cho New York University kyunghyun.cho@nyu.edu James Glass Massachusetts Institute of Technology glass@mit.edu Abstract This work studies the widely adopted ancestral sampling algorithms for auto-regressive lan- guage models, which is not widely studied in the literature. We use the quality-diversity (Q- D) trade-off to investigate three popular sam- pling algorithms (top-k, nucleus and tempered sampling). We focus on the task of open-ended language generation. We first show that the existing sampling algorithms have similar per- formance. After carefully inspecting the trans- formations defined by different sampling algo- rithms, we identify three key properties that are shared among them: entropy reduction, or- der preservation, and slope preservation. To validate the importance of the identified prop- erties, we design two sets of new sampling al- gorithms: one set in which each algorithm sat- isfies all three properties, and one set in which each algorithm violates at least one of the prop- erties. We compare their performance with ex- isting sampling algorithms, and find that vio- lating the identified properties could lead to drastic performance degradation, as measured by the Q-D trade-off. On the other hand, we find that the set of sampling algorithms that sat- isfies these properties performs on par with the existing sampling algorithms.1 1 Introduction A language model (LM) is a central module for nat- ural language generation (NLG) tasks (Young et al., 2018) such as machine translation (Wu et al., 2018), dialogue response generation (Li et al., 2017), im- age captioning (Lin et al.), and related tasks. Given a trained LM, finding the best way to generate a sample from it has been an important challenge for NLG applications. ∗Equal contribution. 1Our data and code are available at https://github.com/moinnadeem/ characterizing-sampling-algorithms. Figure 1: Human evaluation (y-axis: quality, x-axis: diversity, both are the bigger the better) shows that the generation performance of existing sampling algo- rithms are on par with each other. Decoding, i.e., finding the most probable output sequence from a trained model, is a natural prin- ciple for generation. The beam-search decoding algorithm approximately finds the most likely se- quence by performing breadth-first search over a restricted search space. It has achieved success in machine translation, summarization, image cap- tioning, and other subfields. However, in the task of open-ended language generation (which is the focus of this work), a sig- nificant degree of diversity is required. For ex- ample, conditioned on the prompt “The news says that ...”, the LM is expected to be able to generate a wide range of interesting continua- tions. While the deterministic behavior of decoding algorithms could give high-quality samples, they suffer from a serious lack of diversity. This need for …

Content truncated to 500 words