6

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 me if I am wrong

user3880907
  • 271
  • 2
  • 4
  • 10

2 Answers2

6

Stochastic pretty much means randomized in some way. One of the major issues with beam search is that it tends to get stuck into local optima instead of the global optimum. To avoid that stochastic search gives some(most often small) probability of the solution to choose the step that is not optimal at a given moment. You can think of that as "adding randomness". A bit better approach would be simulated annealing where the chance to take suboptimal choice decreases with time.

Local search on the other hand will always choose the best K neighbours, never allowing to deviate from a local optimum if you happen to hit one.

Wyetro
  • 8,439
  • 9
  • 46
  • 64
Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176
  • 1
    +1 for having a way better answer than mine lol. I didn't know that about allocating a small amount of probability to continue the random search. – salad_bar_breath Oct 02 '15 at 15:26
  • now it is clear so Stochastic tries to solve getting stuck in Beam, by choosing K for its probability, right ? – user3880907 Oct 02 '15 at 16:09
0

I think that the only difference is that in the Stochastic beam search, the successors of K are chosen at random versus calling K's successor with K in the local beam search. At least that's what I gathered from this SOURCE

Great question!

Edit: Here is another source that goes into a little more detail about those differences

salad_bar_breath
  • 271
  • 4
  • 18