**Name**

Beam Search

**Intent**

Improve training selecting only the best alternatives to explore.

**Motivation**

How can we reduce the solution search space?

**Structure**

<Diagram>

**Discussion**

**Known Uses**

**Related Patterns**

<Diagram>

**References**

**Known Uses**

http://googleresearch.blogspot.ca/2016/05/chat-smarter-with-allo.html
*
Another interesting challenge we had to solve when generating predictions is controlling for message length. Sometimes none of the most probable responses are appropriate - if the model predicts too short a message, it might not be useful to the user, and if we predict something too long, it might not fit on the phone screen. We solved this by biasing the beam search to follow paths that lead to higher utility responses instead of favoring just the responses that are most probable. That way, we can efficiently generate appropriate length response predictions that are useful to our users.*

** References **
https://en.wikipedia.org/wiki/Beam_search

https://arxiv.org/abs/1606.02960 Sequence-to-Sequence Learning as Beam-Search Optimization

Sequence-to-sequence models have become extremely popular recently. This paper proposes a training approach that overcomes some of the limitations of the standard sequence-to-sequence formulation (the label bias problem) in a computationally tractable way.

http://arxiv.org/abs/1603.06042v2 Globally Normalized Transition-Based Neural Networks

In this work we demonstrate that simple feed-forward networks without any recurrence can achieve comparable or better accuracies than LSTMs, as long as they are globally normalized.

https://arxiv.org/abs/1609.08144v1 Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation

https://research.googleblog.com/2016/10/graph-powered-machine-learning-at-google.html Graph Powered Machine Learning at Google

https://arxiv.org/abs/1512.01752 Large Scale Distributed Semi-Supervised Learning Using Streaming Approximation

http://web.eecs.umich.edu/~baveja/Papers/UCTtoCNNsAtariGames-FinalVersion.pdf Deep Learning for Real-Time Atari Game Play Using Offline Monte-Carlo Tree Search Planning

http://openreview.net/pdf?id=HJV1zP5xg DIVERSE BEAM SEARCH: DECODING DIVERSE SOLUTIONS FROM NEURAL SEQUENCE MODELS

. To overcome this problem, we propose Diverse Beam Search (DBS), an alternative to BS that decodes a list of diverse outputs by optimizing a diversity-augmented objective

https://arxiv.org/abs/1612.04774v1 Beam Search for Learning a Deep Convolutional Neural Network of 3D Shapes

This paper addresses 3D shape recognition. Recent work typically represents a 3D shape as a set of binary variables corresponding to 3D voxels of a uniform 3D grid centered on the shape, and resorts to deep convolutional neural networks(CNNs) for modeling these binary variables. Robust learning of such CNNs is currently limited by the small datasets of 3D shapes available, an order of magnitude smaller than other common datasets in computer vision. Related work typically deals with the small training datasets using a number of ad hoc, hand-tuning strategies. To address this issue, we formulate CNN learning as a beam search aimed at identifying an optimal CNN architecture, namely, the number of layers, nodes, and their connectivity in the network, as well as estimating parameters of such an optimal CNN. Each state of the beam search corresponds to a candidate CNN. Two types of actions are defined to add new convolutional filters or new convolutional layers to a parent CNN, and thus transition to children states. The utility function of each action is efficiently computed by transferring parameter values of the parent CNN to its children, thereby enabling an efficient beam search. Our experimental evaluation on the 3D ModelNet dataset demonstrates that our model pursuit using the beam search yields a CNN with superior performance on 3D shape classification than the state of the art.

https://arxiv.org/abs/1612.00576v1 Guided Open Vocabulary Image Captioning with Constrained Beam Search

Our method uses constrained beam search to force the inclusion of selected tag words in the output, and fixed, pretrained word embeddings to facilitate vocabulary expansion to previously unseen tag words. Using this approach we achieve state of the art results for out-of-domain captioning on MS COCO (and improved results for in-domain captioning).

https://arxiv.org/abs/1610.02424v1 Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Models

Neural sequence models are widely used to model time-series data in many fields. Equally ubiquitous is the usage of beam search (BS) as an approximate inference algorithm to decode output sequences from these models. BS explores the search space in a greedy left-right fashion retaining only the top-B candidates – resulting in sequences that differ only slightly from each other.

https://arxiv.org/abs/1701.01724v2 DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker

https://arxiv.org/pdf/1704.07138v1.pdf Lexically Constrained Decoding for Sequence Generation Using Grid Beam Search

http://julian.togelius.com/Bravi2017Evolving.pdf Evolving game-specific UCB alternatives for General Video Game Playing

https://arxiv.org/pdf/1708.00111.pdf A Continuous Relaxation of Beam Search for End-to-end Training of Neural Sequence Models

https://arxiv.org/abs/1811.00512v1 Learning Beam Search Policies via Imitation Learning

Beam search is widely used for approximate decoding in structured prediction problems. Models often use a beam at test time but ignore its existence at train time, and therefore do not explicitly learn how to use the beam. We develop an unifying meta-algorithm for learning beam search policies using imitation learning. In our setting, the beam is part of the model, and not just an artifact of approximate decoding. Our meta-algorithm captures existing learning algorithms and suggests new ones. It also lets us show novel no-regret guarantees for learning beam search policies.