Stack Overflow
Stack Overflow

Questions tagged [beam-search]

This tag is for questions related to the heuristic search algorithm beam search.

From https://en.wikipedia.org/wiki/Beam_search:

Beam search is a heuristic search algorithm that explores a graph by expanding the most promising node in a limited set. Beam search is an optimization of best-first search that reduces its memory requirements. Best-first search is a graph search which orders all partial solutions (states) according to some heuristic which attempts to predict how close a partial solution is to a complete solution (goal state). But in beam search, only a predetermined number of best partial solutions are kept as candidates.

41 questions
29
votes
1 answer

Tensorflow: Can't understand ctc_beam_search_decoder() output sequence

I am using Tensorflow's tf.nn.ctc_beam_search_decoder() to decode the output of a RNN doing some many-to-many mapping (i.e., multiple softmax outputs for each network cell). A simplified version of the network's output and the Beam search decoder…
Nur L
  • 791
  • 7
  • 15
11
votes
0 answers

how to get top-k best candidate sequences when using CRF for decoding in tensorflow

CRF++ allows us to get marginal probabilities for each tag (a kind of confidece measure for each output tag) and a conditional probably for the output (confidence measure for the entire output). % crf_test -v2 -m model test.data # 0.478113 Rockwell…
longbowking
  • 285
  • 2
  • 7
10
votes
2 answers

What does the beam size represent in the beam search algorithm?

I have a question about the beam search algorithm. Let's say that n = 2 (the number of nodes we are going to expand from every node). So, at the beginning, we only have the root, with 2 nodes that we expand from it. Now, from those two nodes, we…
Dimitar Spasovski
  • 2,023
  • 9
  • 29
  • 45
9
votes
2 answers

How does Beam Search operate on the output of The Transformer?

According to my understanding (please correct me if I'm wrong), Beam Search is BFS where it only explores the "graph" of possibilities down b the most likely options, where b is the beam size. To calculate/score each option, especially for the work…
Tony
  • 183
  • 2
  • 6
6
votes
3 answers

Batch-wise beam search in pytorch

I'm trying to implement a beam search decoding strategy in a text generation model. This is the function that I am using to decode the output probabilities. def beam_search_decoder(data, k): sequences = [[list(), 0.0]] # walk over each step…
Hari Krishnan
  • 2,049
  • 2
  • 18
  • 29
6
votes
2 answers

What is the difference between Local beam search and Stochastic beam search?

I know that both of them select K randomly, and then choose the best K, as I understand the best K call the others to find the goal, so what is the exact difference between Local beam search and Stochastic beam search ? Please help me and correct to…
user3880907
  • 271
  • 2
  • 4
  • 10
5
votes
1 answer

What's the difference between a greedy decoder RNN and a beam decoder with k=1?

Given a state vector we can recursively decode a sequence in a greedy manner by generating each output successively, where each prediction is conditioned on the previous output. I read a paper recently that described using beam search during…
jstaker7
  • 1,226
  • 4
  • 15
  • 29
4
votes
2 answers

Beam Search in Python

I am implementing a Seq2Seq model in Keras. However, they have not provided the beam search option in the decoder. Hence, I considered pynlpl's BeamSearch but their documentation on search found here doesn't have any information about how to…
Karthik
  • 71
  • 1
  • 8
3
votes
2 answers

Beam-search Algorithm for Decoding RNN output

I have been trying to understand the logic used by the beam-search algorithm in automatic speech recognition for the decoding part. The papers I've tried to follow are First-Pass Large Vocabulary Continuous Speech Recognition using Bi-Directional…
Giovanni Rescia
  • 605
  • 5
  • 15
2
votes
0 answers

Why word-level language model should help in beam search decoding in ASR?

I was experimenting with beam search decoding of an acoustic model trained with CTC loss trained on an automatic speech recognition task. The version I was using was based on this paper. However, even though many sources describe integration of…
JAV
  • 279
  • 2
  • 9
2
votes
1 answer

Does NOT `tf.nn.ctc_beam_search_decoder()` support GPU in TensorFlow2?

Now, I try to use tf.nn.ctc_beam_search_decoder() on GPU. But I have a problem that it does not use GPU. I was able to check that other tensorflow functions(e.g. Reshape and SigmoidGrad etc.) run on GPU. But some ones including…
YK_
  • 23
  • 3
2
votes
3 answers

Prolog Programming

I have made two programs in Prolog for the nqueens puzzle using hill climbing and beam search algorithms. Unfortunately I do not have the experience to check whether the programs are correct and I am in dead end. I would appreciate if someone could…
user596970
  • 21
  • 1
  • 2
2
votes
1 answer

How to use the schedule sampling in beam search decoder in tensorflow.

The basic decoder contains a parameter to add helper method that can be a schedule sampling helper. But the beam search decoding does not contain any helper parameter. While in the code it looks like there is some sampling used, but it is not clear…
pratsbhatt
  • 1,498
  • 10
  • 20
2
votes
0 answers

Why the variable of sequence_length is useless in the ctc_beam_search_decoder of tensorflow-r1.0?

I'd like to generate a batch of sequence with a fixed shape [batch_size, seq_lenth]. Thus my code: output, _ = tf.nn.ctc_beam_search_decoder( logits, tf.ones([batch_size])*seq_length, merge_repeated=False ) output =…
user5779223
  • 1,460
  • 3
  • 21
  • 42
2
votes
0 answers

How to implement a custom beam search in TensorFlow?

In the original Google's SmartReply paper: Our search is conducted as follows. First, the elements of R (the set of all possible responses) are organized into a trie. Then, we conduct a left-to-right beam search, but only retain hypotheses that…
AmirHJ
  • 827
  • 1
  • 11
  • 21
1
2 3