Magenta's melody_rnn_generate method includes a parameter beam_size. What is it and how does affect the melody?

Beam size, or beam width, is a parameter in the beam search algorithm which determines how many of the best partial solutions to evaluate. In an LSTM model of melody generation, for example, beam size limits the number of candidates to take as input for the decoder. A beam size of 1 is a best-first search - only the most probable candidate is chosen as input for the decoder. A beam size of $k$ will decode and evaluate the top $k$ candidates. A large beam size means a more extensive search - not only the single best candidate is evaluated.

Beam search is a heuristic search algorithm that uses breadth-first search to build its search tree and reduces the search space by eliminating candidates to reduce the memory and time requirements.1 Without the beam search, the worst time and space complexity for the best-search would be $\mathcal{O}(b^m)$ where $b$ is the branching factor and $m$ is the maximum depth. With beam search, the worst time complexity is $\mathcal{O}(kb)$ and the worst case space complexity is $\mathcal{O}(k)$2.

In the case of melody creation with Magenta, a beam size larger than the default of 1 will build a search tree for each candidate evaluation, as visible in this incomplete sketch of the graph ('h' represents an arbitrary heuristic cost): Beam search graph sketch for melody generation

A larger beam generally means a more accurate prediction at the expense of memory and time. In one trial using attention_rnn, for example, modifying the beam width from 1 to 4 decreased the average negative log-likelihood of sequence (melody) generation from 84.2 to 38.6.

1 - Beam search (Wikipedia)

2 - Notes on the Complexity of Search (MIT)

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.