Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Beam search fails if empty sequence is predicted #2486

Closed
leonweber opened this Issue Feb 7, 2019 · 3 comments

Comments

Projects
None yet
3 participants
@leonweber
Copy link

leonweber commented Feb 7, 2019

Describe the bug
Beam search fails if empty sequence is predicted

To Reproduce
At prediction time, if the first prediction of the model is self._end_index beam search is aborted due to

# If every predicted token from the last step is `self._end_index`,
# then we can stop early.
if (last_predictions == self._end_index).all():
    break

which leads to backpointers being empty and triggering

cur_backpointers = backpointers[-1]
IndexError: list index out of range

Expected behavior
Evaluation should not crash if this is the case.

System (please complete the following information):

  • OS: Linux
  • Python version: 3.6.8
  • AllenNLP version: 0.8.1
  • PyTorch version: 1.0.1

Additional context
I fixed it locally by changing the line to if (last_predictions == self._end_index).all() and timestep > 0:. Is this correct, or does it lead to other problems?

@matt-gardner

This comment has been minimized.

Copy link
Member

matt-gardner commented Feb 26, 2019

Hey, sorry this issue slipped by us, we've been having a hard time keeping up with issues recently. My gut reaction to this is that you should handle the error after search instead of modifying the search directly, but I'd have to play around with it myself to really be sure of that.

@epwalsh

This comment has been minimized.

Copy link
Contributor

epwalsh commented Mar 1, 2019

@matt-gardner FWIW I agree this edge case is probably something that the user should catch and avoid, but maybe it's worth throwing in a check for this in BeamSearch.search and throwing a RuntimeError in that case? At least then a helpful error message is spit out.

@matt-gardner

This comment has been minimized.

Copy link
Member

matt-gardner commented Mar 1, 2019

That sounds like a good solution to me. PR welcome!

brendan-ai2 added a commit that referenced this issue Mar 14, 2019

Handle edge cases in beam search (#2557)
Addresses the edge case brought up in #2486 (fixes #2486) as well as another. This actually turned out to be a little more nuanced...

I first thought the issue brought up was caused by `start_predictions` being the `end_index`, but it actually occurs in general with a beam size of 1 when the first predictions that the step function produces are the `end_index`, regardless of what `start_predictions` are, i.e. at this line: 

`start_class_log_probabilities, state = step(start_predictions, start_state)`

The other edge case is similar, and occurs when the beam size is smaller than the number of valid (non-zero probability) transitions that the step function produces. For example, this could happen in a semantic parsing task where a masked log softmax is used to create predicted log probs for valid next actions. Though this doesn't cause the beam search to crash per se, I thought it would still be good to warn the user in these cases since some of the predicted sequences may be improbable.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.