What Do You Get When You Cross Beam Search with Nucleus Sampling?

• URL: http://arxiv.org/abs/2107.09729v1
• Date: Tue, 20 Jul 2021 18:59:14 GMT
• Title: What Do You Get When You Cross Beam Search with Nucleus Sampling?
• Authors: Uri Shaham and Omer Levy
• Abstract summary: We create two deterministic nucleus search algorithms for natural language generation. Experiments on machine translation and summarization benchmarks show that both algorithms reach the same performance levels as standard beam search.
• Score: 23.5360917879657
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We combine beam search with the probabilistic pruning technique of nucleus sampling to create two deterministic nucleus search algorithms for natural language generation. The first algorithm, p-exact search, locally prunes the next-token distribution and performs an exact search over the remaining space. The second algorithm, dynamic beam search, shrinks and expands the beam size according to the entropy of the candidate's probability distribution. Despite the probabilistic intuition behind nucleus search, experiments on machine translation and summarization benchmarks show that both algorithms reach the same performance levels as standard beam search.

Related papers

• Bayesian Binary Search [5.292593801475208]
  We present a novel probabilistic variant of the classical binary search/bisection algorithm, BBS. BBS estimates the probability density of the search space and modifies the bisection step to split based on probability density rather than the traditional midpoint. We demonstrate significant efficiency gains of using BBS on both simulated data across a variety of distributions and in a real-world binary search use case of probing channel balances in the Bitcoin Lightning Network.
  arXiv  Detail & Related papers  (2024-10-02T17:28:22Z)
• A Three-Stage Algorithm for the Closest String Problem on Artificial and Real Gene Sequences [39.58317527488534]
  Closest String Problem is an NP-hard problem that aims to find a string that has the minimum distance from all sequences that belong to the given set of strings. In this paper, we introduce a three-stage algorithm that comprises the following process: first, we apply a novel alphabet pruning method to reduce the search space for effectively finding promising search regions. Second, a variant of beam search to find a solution is employed. This method utilizes a newly developed guiding function based on an expected distance score of partial solutions.
  arXiv  Detail & Related papers  (2024-07-17T21:26:27Z)
• Rectangle Search: An Anytime Beam Search (Extended Version) [9.59799149404787]
  Anytime search algorithms try to find a (potentially suboptimal) solution as quickly as possible. We propose a new algorithm, rectangle search, that is instead based on beam search.
  arXiv  Detail & Related papers  (2023-12-19T19:50:45Z)
• Best-$k$ Search Algorithm for Neural Text Generation [118.02691398555781]
  We propose a deterministic search algorithm balancing both quality and diversity. The proposed algorithm is parameter-free, lightweight, efficient, and easy to use.
  arXiv  Detail & Related papers  (2022-11-22T00:26:13Z)
• Exploring Complicated Search Spaces with Interleaving-Free Sampling [127.07551427957362]
  In this paper, we build the search algorithm upon a complicated search space with long-distance connections. We present a simple yet effective algorithm named textbfIF-NAS, where we perform a periodic sampling strategy to construct different sub-networks. In the proposed search space, IF-NAS outperform both random sampling and previous weight-sharing search algorithms by a significant margin.
  arXiv  Detail & Related papers  (2021-12-05T06:42:48Z)
• Determinantal Beam Search [75.84501052642361]
  Beam search is a go-to strategy for decoding neural sequence models. In use-cases that call for multiple solutions, a diverse or representative set is often desired. By posing iterations in beam search as a series of subdeterminant problems, we can turn the algorithm into a diverse subset selection process.
  arXiv  Detail & Related papers  (2021-06-14T13:01:46Z)
• Deterministic spatial search using alternating quantum walks [0.0]
  We prove that for a set of optimal quantum walk times and marked vertex phase shifts, a deterministic algorithm for structured spatial search is established. This improves on the original spatial search algorithm on the same class of graphs, which we show can only amplify to 50% probability. It is expected that this new framework can be readily extended to deterministic spatial search on other families of graph structures.
  arXiv  Detail & Related papers  (2021-04-08T14:32:48Z)
• Best-First Beam Search [78.71330480725668]
  We show that the standard implementation of beam search can be made up to 10x faster in practice. We propose a memory-reduced variant of Best-First Beam Search, which has a similar beneficial search bias in terms of downstream performance.
  arXiv  Detail & Related papers  (2020-07-08T05:56:01Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data. We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem. In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
  arXiv  Detail & Related papers  (2020-06-11T19:40:38Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.