Determinantal Beam Search

Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, pages 6551–6562 August 1–6, 2021. ©2021 Association for Computational Linguistics 6551 Determinantal Beam Search Clara Meister Martina Forster Ryan Cotterell , ETH Zürich University of Cambridge meistecl@inf.ethz.ch martfors@ethz.ch ryan.cotterell@inf.ethz.ch 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 di- verse 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 pro- cesses (DPPs), models over sets that inherently encode intra-set interactions. By posing itera- tions in beam search as a series of subdetermi- nant maximization problems, we can turn the algorithm into a diverse subset selection pro- cess. In a case study, we use the string subse- quence 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. 1 Introduction The decoding of neural sequence models is a fun- damental 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,1 there can be mul- tiple correct solutions—or that we may desire a di- verse set of solutions. As it stands, standard beam search chooses items based purely on individual 1As concrete examples, in machine translation there almost always exist multiple ways to translate a sentence; in story generation, we often seek creative language or multiple options to choose from. scores, with no means for encoding interaction be- tween 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 pos- sible candidates; standard beam search is recov- ered by a specific diagonal matrix. This framing creates a natural paradigm for taking the rela- tionships between candidates during the decoding process, and can thus assign higher scores to di- versified sets; we show how this approach relates to k-determinantal point processes (DPPs). Given the wealth of research on efficient kernel com- putation (Rousu and Shawe-Taylor, 2005; Farhan et al., 2017) and DPP inference strategies (Li et al., 2016; Han …

Content truncated to 500 words