4 ms·
quite a lot of structure amongst these algorithms that the list misses out: - dynamic programming comes from solving Bellman's equation and Q-learning is an ap
by dododo 16y ago
quite a lot of structure amongst these algorithms that the list misses out:
- dynamic programming comes from solving Bellman's equation and Q-learning is an approximate means of doing dynamic programming.
- It's possible to do beam a* search, where beam search, a* search, and best-first (greedy) search are special cases.
- in the continuous domain, greedy search is essentially gradient ascent.
- you can use discrete differentiation to find the gradients for gradient ascent (actually, i would replace the first order method suggestion of this list with newton-raphson or some quasi-newton raphson method like BFGS).
- EM ties some bits together.
- if you replace the max of the viterbi algorithm with a summation, then you get the sum-product algorithm which is essential in the E step of EM. if you use viterbi instead of sum-product, you get something known as zero-temperature EM, which is an approximate form of EM
- the M step of EM is typically just gradient ascent!
- you can use max flow to do a similar thing to viterbi on certain graphs
and so on...
- jules 16y agoI think the dynamic programming meant here is more general. They mean saving results of a recursively formulated algorithm in a table so that you don't have to recompute them. This can be used for example for finding longest common subsequences, but it is much more general. Can you elaborate on the general search procedure? Is there a good resource that ties algorithms together like you've done here, but less concise?
- dododo 16y agothey do mean dynamic programming in a more general sense: but dynamic programming was invented originally to solve Bellman's equation. it turns out many other problems have a similar structure which is quite surprising! before bellman's seminal work in 1940s, it wasn't known how to efficiently these problems. indeed, you can often do something like Q-learning for finding approximate solutions to dynamic programming problems even faster. the general search procedure is just A* search but with the beam search pruning each time you expand the fringe of exploration. i don't know a good source, i picked this up from a bunch of courses/research.
- jules 16y agoThanks! You should consider writing an article about this :)
- iskander 16y ago1) Just do EM with parameters in an arbitrary semiring and you generalize nicely to all the special cases you mentioned (and more) 2) I see how all of EM is coordinate ascent, but I don't see how the M step is gradient ascent. Where the gradients at? 3) Second-order optimization methods can be pretty tricky and fall apart for large problems. Stochastic gradient descent ftw.
- jefffoster 16y agoThe search chapter in PAIP has an excellent description of A* search, beam search and best first search that shows the relationship between the algorithms. The code is available on-line (http://norvig.com/paip/search.lisp http://norvig.com/paip/search.lisp).