Is beam search always better than greedy search?
How to generate textstates:Beam search will always find an output sequence with higher probability than greedy searchIt’s not clear to me why that is the case. Consider this example, comparing greedy search with beam search with beam width 2:image551×665 24.1 KBBy the 3rd step, beam search with beam width 2 has found two sequences BFI and BGK, each with probability .49*.5*.51 = 0.12495, but greedy search found ADH, with probability .51*.4*.99 = 0.20196Exploring more of the tree may cause beam search to get stuck on paths that seem more promising at first, but end up with lower probability than the greedy path. Is this right, or have I misunderstood how beam search works?Thanks!Robby
2020-12-23T22:37:39Z
I think this is an interesting adversarial case for beam-searchSo I agree with you that in this case Greedy found the more probable path.
2020-12-27T19:09:42Z
Thanks for your response Jung. This is not quite an adversarial example – I discovered a very similar one “in the wild” while analyzing my own implementation of beam search.Since I’ve heard that increasing the beam width increases the probability of the best path, I attempted to test my implementation with that idea. If my implementation was correct, then it should show path probability monotonically increasing with beam width when searching through any random tree.But instead I found that there is often dips in the path probabilities as beam width increases, especially for longer paths.Screen Shot 2020-12-27 at 1.08.32 PM1352×1058 83.7 KBHere’s my full implementation, tested with different lengths and a few different trees:Google Colab
2022-05-24T11:59:14Z
Hey robz. I went through your code and your observations sounds interesting. Can we have some discussion offline?