Conditional P oisson Stochastic Beams (2021)

Abstract: Beam search is the default decoding strategy for many sequence generation tasks in NLP. The set of approximate K-best items returned by the algorithm is a useful summary of the distribution for many applications; however, the candidates typically exhibit high overlap and may give a highly biased estimate for expectations under our model. These problems can be addressed by instead using stochastic decoding strategies. In this work, we propose a new method for turning beam search into a stochastic process: Conditional Poisson stochastic beam search. Rather than taking the maximizing set at each iteration, we sample K candidates without replacement according to the conditional Poisson sampling design. We view this as a more natural alternative to Kool et al. (2019)’s stochastic beam search (SBS). Furthermore, we show how samples generated under the CPSBS design can be used to build consistent estimators and sample diverse sets from sequence models. In our experiments, we observe CPSBS produces lower variance and more efficient estimators than SBS, even showing improvements in high entropy settings.

## introduction many nlp tasks require the prediction of structured outputs, such as sentences or parse trees, either during decoding or as part of a training algorithm. for today's neural architectures, beam search @xcite has become the decoding algorithm of choice due to its efficiency and empirical performance @xcite @xcite . beam search is a deterministic method, which invites a natural question: what is the proper stochastic generalization of beam search? several recent papers have investigated this question @xcite @xcite . here we build operator set size ## beam search in this section, we overview the necessary background on neural sequence models and beam search in order to motivate our algorithm in §3. neural sequence models. we consider locally normalized probabilistic models over sequences y: ## conditional poisson stochastic beams our paper capitalizes on a very simple observation: rather than taking its argmax, we may renormalize eq. ( 4 ) into a distribution and sample-withoutreplacement a size k set at each iteration: this recursion corresponds to performing conditional poisson sampling (cps; hájek 1964; see app. a for overview), a common sampling-withoutreplacement design (tillé, 2006), 3 at every time step. thus we term this scheme conditional poisson stochastic beam search. cpsbs gives us a probability distribution over sets of candidates of size k, i.e., the final beam y t . we denote the cpsbs distribution p and we write y t ∼ p to indicate that y t is the stochastic beam at the end of a sampling run. we may write p (y t ) as a marginal probability, summing over all sequences of beams that could have resulted in y t : foot_2 note the structural zeros of q t prevent any incompatible sequence of beams. we provide a theoretical analysis of the scheme in §4 and an empirical analysis in §5. at each time step t, we compute q t (• | y t-1 )-a distribution over subsets of size k of a base set b t -using the cps design. the normalizing constant for this distribution is defined as despite there being exponentially many summands, we can sum over all n k subsets in o(n k) time via the following recurrence relation: 5 we give complete pseudocode in app. c. correctness of this algorithm is shown in @xcite . the normalizing constant can then be efficiently computed as sampling from q t (• | y t-1 ). we can efficiently sample sets from q t (• | y t-1 ) using the algorithm below: this formulation reveals that it is wildly intractable to compute p (yt ). 5 the reader may recognize this recurrence as the weighted generalization of pascal's triangle, n @xmath0, which is why we chose the notation w n k . add the n th element of b t to y t with prob. one strategy is to choose w n at time step t such that π qt y ## experiments we repeat the analyses performed by @xcite , running experiments on neural machine translation (nmt) models; for reproducibility, we use the pretrained transformer model for wmt'14 @xcite english-french made available by fairseq foot_5 @xcite . we evaluate on the en-fr newstest2014 set, containing 3003 sentences. further details can be found in app. d. our implementation of cpsbs modifies the beam search algorithm from the fairseq library. we additionally consider the beam search, stochastic beam search, diverse beam search, and ancestral sampling algorithms available in fairseq. ## conclusion in this work, we present conditional poisson stochastic beam search, a sampling-withoutreplacement strategy for sequence models. through a simple modification to beam search, we turn this mainstay decoding algorithm into a stochastic process. we derive a low-variance, consistent estimator of inclusion probabilities under this scheme; we then present a general framework for using cpsbs to construct statistical estimators for expectations under sequence models. in our experiments, we observe a reduction in mean square error, and an increase in sample efficiency, when using our estimator in comparison to several baselines, showing the benefits of cpsbs.