Determinantal Beam Search (2021)

Abstract: Beam search is a go-to strategy for decoding neural sequence models. The algorithm can naturally be viewed as a subset optimization problem, albeit one where the corresponding set function does not reflect interactions between candidates. Empirically, this leads to sets often exhibiting high overlap, e.g., strings may differ by only a single word. Yet in use-cases that call for multiple solutions, a diverse or representative set is often desired. To address this issue, we propose a reformulation of beam search, which we call determinantal beam search. Determinantal beam search has a natural relationship to determinantal point processes (DPPs), models over sets that inherently encode intra-set interactions. By posing iterations in beam search as a series of subdeterminant maximization problems, we can turn the algorithm into a diverse subset selection process. In a case study, we use the string subsequence kernel to explicitly encourage n-gram coverage in text generated from a sequence model. We observe that our algorithm offers competitive performance against other diverse set generation strategies in the context of language generation, while providing a more general approach to optimizing for diversity.

## introduction the decoding of neural sequence models is a fundamental component of many tasks in nlp. yet, many proposed decoding methods aim to produce only a single solution; further, decoding strategies that provide a set, such as beam search, admit high overlap between solutions. such approaches fail to reflect that for many nlp tasks, foot_0 there can be multiple correct solutions-or that we may desire a diverse set of solutions. as it stands, standard beam search chooses items based purely on individual scores, with no means for encoding interaction between candidates; this is the limitation which we attempt to address in this work. we derive determinantal beam search, a novel generalization of beam search that casts subset selection as the subdeterminant optimization problem. specifically, we formulate each iteration of beam search as a subdeterminant maximization problem parameterized by a positive semi-definite matrix that encodes interactions between the possible candidates; standard beam search is recovered by a specific diagonal matrix. this framing creates a natural paradigm for taking the relationships between candidates during the decoding process, and can thus assign higher scores to diversified sets; we show how this approach relates to k-determinantal point processes (dpps). given the wealth of research on efficient kernel computation @xcite and dpp inference strategies @xcite @xcite , we find the impact on runtime to be quite reasonable in comparison to standard decoding techniques. in a case study on neural machine translation (nmt), we demonstrate how to make use of the string subsequence kernel @xcite to encode the notion of n-gram diversity in the language generation process, allowing us to derive an elegant diverse beam search. under this scheme, we observe that determinantal beam search generates more diverse sets than standard beam search with minimal trade-off in terms of bleu. we see improved performance over stochastic beam search (sbs; @xcite , which is reported to encourage diversity, and a slight improvement over @xcite 's diverse beam search (dbs) while providing a more general approach to optimizing for intra-set diversity. ## neural sequence models neural sequence models are probability distributions p(y | x) over sequences y in an output space y conditioned on an input x. 2 here we define y as the set of all valid sequences derived from a vocabulary v that are bookended by distinguished bos and eos tokens, indicating the beginning and end of the sequence, respectively. typically, the sequence length is upper-bounded by some value n @xmath0, which may depend on x. in this work, we consider locally normalized models, i.e. where p is a probability distribution over v @xmath1. the probability of the full sequence @xmath2, y 2 , . . . is then calculated via the chain rule of probability: we define the decoding problem as the search for the highest-scoring y among all sequences in y according to the model p(y | x), which is also called maximum-a-posteriori (map) inference: similarly to eq. ( 2 ), the set-decoding problem is then defined as: however, as has been noted in the literature, there are a number of issues with both eq. ( 2 ) and (4). first, as y may be an exponentially large (in v) space and p is typically non-markovian, we cannot efficiently search over y, much less over y k . second, specifically for language generation tasks, these might not be useful objectives. 2 x may be, e.g., a source sentence or an image. ## determinantal beam search we are now in a position to ask the fundamental question of this work: what happens if we replace the diagonal matrix d with a non-diagonal matrix? this substitution allows us to account for interactions between the elements in the beam. formally, we consider a timestep-dependent positive semi-definite (psd) matrix d + w • k where the off-diagonal matrix k indicates the strength of the interactions between candidates. the nonnegative weight @xmath3. in this case, the beam search recursion becomes: clearly, we recover beam search when @xmath4; however, we can now select subsets based additionally on candidate interactions. that is, eq. ( 9 ) now has an interpretation as a diversity objective function @xcite when k is chosen wisely. due to the presence of the log, eq. ( 9 ) is only well defined when the matrix ## case study: diverse beam search we now consider the task of language generation, where our vocabulary v is a set of words and y is the set of all valid strings derived from v. when the space of our kernel function @xmath5, one simple way of modeling interactions is through a string subsequence kernel @xcite . ## experiments in our experiments, we explore the use of determinantal beam search as a diverse decoding strategy for language generation. ## related work our work is built upon much of the subset optimization literature in machine learning. we base our algorithm off the subdeterminant maximization problem @xcite , which has been used to find core sets-a concept originating in computational geometry concerning the existence of a small, representative set of core items-in data summarization problems @xcite , nearest neighbor search @xcite and streaming algorithms @xcite inter alia. informally, we can connect our problem to the notion of decoding a core set from sequence models. to the best of our knowledge, our work is the first to use this concept when decoding sequence models. @xcite incorporate dpps into a reinforcement learning objective to optimize for diverse text when training image captioning models. we optimize for diversity during decoding, rather than training, which makes our methods applicable with out-of-the-box models and allows us to avoid highly hyperparametersensitive techniques, like minimum-risk training or reinforcement learning-based algorithms, while achieving the same goal. while the application of our methods at training times is an interesting research direction, we foresee technical challenges corresponding to such approaches that may outweigh their benefits. tam (2020) likewise adapts beam search, proposing a k-means clustering version that clusters solutions by averaged word embeddings. as there lacks an interpretation of distance between averaged word embeddings though, it is unclear if the method can explicitly optimize for any tangible notion of coverage or diversity. ## conclusion we propose determinantal beam search (detbs): a new way of framing beam search that allows us to optimize set generation for diversity and coverage rather than simply individual scores. formally, we redefine beam search as an iterative subdeterminant maximization problems where we select the approximately maximizing set according to the psd matrix parameterizing our score function. this gives us the ability to encode the notion of intra-set diversity into the beam search optimization problem. we discuss and experiment with efficient methods for inference and kernel computation that make detbs an efficient decoding strategy in practice. we use detbs in the context of language generation, where we explicitly encourage n-gram coverage through the string subsequence kernel. in our nmt experiments, we find detbs generates much more diverse sets of strings than standard beam search and stochastic beam search with a small tradeoff in median bleu. we observe competitive performance compared with diverse beam search.