title: Python beam search for Keras LSTM model generating the same sequence
body: <p>I am working on an image captioning system in python using Keras and when using argmax search I get reasonable results (~0.58 Bleu_1 score and the sentences are quite diverse). </p>
  
  <p>When I try beam search, however, I get almost the same sentence for every image. </p>
  
  <p>I have the following code for generating the captions:</p>
  
  <pre class="lang-python prettyprint-override"><code># create an array of captions for a chunk of images; first token
  # of each caption is the start token
  test_x = np.zeros((chunk_size, self.max_len - 1), dtype=np.int)
  test_x[:, 0] = self.start_idx + 1
  
  # probability of each caption is 1
  captions_probs = np.ones(chunk_size)
  
  # for every image, maintain a heap with the best captions 
  self.best_captions = [FixedCapacityMaxHeap(20) for i in range(chunk_size)]
  
  # call beam search using the current cnn features
  self.beam_search(cnn_feats, test_x, captions_probs, 0, beam_size)
  </code></pre>
  
  <p>The beam search method is the following:</p>
  
  <pre class="lang-python prettyprint-override"><code>def beam_search(self, cnn_feats, generated_captions, captions_probs, t, beam_size):
      # base case: the generated captions have max_len length, so
      # we can remove the (zero) pad at the end and for each image
      # we can insert the generated caption and its probablity into
      # the heap with the best captions
      if t == self.max_len - 1:
          for i in range(len(generated_captions)):
              caption = self.remove_zero_pad(list(generated_captions[i]))
              self.best_captions[i].push(list(caption), captions_probs[i])
      else:
          # otherwise, make a prediction (we only keep the element at time 
          # step t + 1, as the LSTM has a many-to-many architecture, but we
          # are only interested in the next token (for each image).
          pred = self.model.predict(x=[cnn_feats, generated_captions], 
                                batch_size=128,
                                verbose=1)[:, t + 1, :]
  
          # efficiently get the indices of the tokens with the greatest probability 
          # for each image (they are not necessarily sorted)
          top_idx = np.argpartition(-pred, range(beam_size), axis=1)[:, :beam_size]
  
          # store the probability of those tokens
          top_probs = pred[np.arange(top_idx.shape[0])[:, None], top_idx]
  
          # for every 'neighbour' (set of newly generated tokens for every image)
          # get the indices of these tokens, add them to the current captions and 
          # update the captions probabilities by multiplying them with the probabilities
          # of the current tokens, then recursively call beam_search
          for i in range(beam_size):
              curr_idx = top_idx[:, i]
              generated_captions[:, t + 1] = curr_idx
              curr_captions_probs = top_probs[:, i] * captions_probs
              self.beam_search(cnn_feats, generated_captions, curr_captions_probs, t+1, beam_size)
  </code></pre>
  
  <p>The FixedCapacityHeap I am using is:</p>
  
  <pre class="lang-python prettyprint-override"><code>class FixedCapacityMaxHeap(object):
  
      def __init__(self, capacity):
          self.capacity = capacity
          self.h = []
  
      def push(self, value, priority):
          if len(self.h) &lt; self.capacity:
              heapq.heappush(self.h, (priority, value))
          else:
              heapq.heappushpop(self.h, (priority, value))
  
      def pop(self):
          if len(self.h) &gt;= 0:
              return heapq.nlargest(1, self.h)[0]
          else:
              return None
  </code></pre>
  
  <p>The problem is that the captions generated using beam search are almost the same for every image (eg: 'scaling a in on', 'scaling a are in in of'', 'scaling a are in'), while the argmax version (just taking the token with the highest probability at each time step) is capable of actually producing good captions. I have been stuck on this for quite a long time now. I have tried a different implementation (computing the caption for each image with a beam_seach call instead of computing all of them at once) and I have also experimented with the softmax temperature parameter (which is responsible for how confident the LSTM is in its predictions), but none of these seems to solve the problem, so any idea is appreciated.</p>