What is the difference between Local beam search and Stochastic beam search?

Question

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

Niela

Answer 1

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.

Huffy

+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. – Cosecant

now it is clear so Stochastic tries to solve getting stuck in Beam, by choosing K for its probability, right ? – Niela

Answer 2

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

Cosecant

Thank you for your resources :) – Niela

Very welcome, glad I could help! Thanks for the great question that made me seek out those resources lol – Cosecant

I hoped to profit from your links... but they are not up to date :( – Straticulate