Dynamic Progamming: First Principles
flawlessrhetoric.com
flawlessrhetoric.com
One important takeaway is that dynamic programming in the Bellman formulation is a discrete analogue of Hamilton-Jacobi theory in how it writes down an equation for the optimal value as a function of a given endpoint rather than writing down an equation for the path as with the Euler-Lagrange equations. (You can reconstruct the path from the value function after the fact by gradient descent.) The relationship between Hamilton-Jacobi and Euler-Lagrange is the classical version of wave-particle duality. A concrete example in geometrical optics is the eikonal equation, a Hamilton-Jacobi type PDE, versus the geodesic equation, an Euler-Lagrange type ODE. Not coincidentally, one common numerical method for the eikonal equation called the fast marching method is a dynamic programming algorithm, very similar to Dijkstra's algorithm for shortest paths.
It should be mentioned that any "local" equation like a PDE or ODE cannot describe a globally optimal solution without strong assumptions such as convexity. In fact, satisfying the Euler-Lagrange equation isn't even sufficient for local optimality without further qualifications (Weierstrass conditions). But the Bellman dynamic programming equation, being recursive, can describe globally optimal solutions.
>The relationship between Hamilton-Jacobi and Euler-Lagrange is the classical version of wave-particle duality.
in what sense are two formalisms (hamiltonian and lagrange) related to the relationship between time and freq space for fourier solutions to pdes?
also holy shit i would pay pretty good money for a service that typeset these old monographs using latex.
In any case, I'm happy with a computer science course that doesn't involve actual computer implementations, and it's not just because it drives home the point that they are different things, but also because you don't have to get bogged down in the practicalities of wrestling with a particular language or a particular toolchain.
- Its a lot quicker to sketch an algorithm on paper ( you can ignore some details which are either trivial, or irrelevant to the problem )
- At a certain level you are expected to be able to convert pseudo code into actual code
- The most important part of an algorithm is knowing about it and what problems it solves (and variations). As well as the "trick" that makes it solve something particularly well - dynamic programming for solving sub problems etc... Even if I implement an algorithm or just write the pseudo code, I will forget the details fairly quickly, but the takeaway is that I know that for problems of type X I can use algorithms of type Y, (and sometimes i'll remember I can use Y because of fact C related to that particular problem or algorithm)
The most important insight of the old saw that teaching someone builds your understanding, but being able to code it ensures you have actual, deep understanding is this: the details you ignore as "trivial" or "irrelevant to the problem" are quite likely the crucial details to understand it and make it work. You can't safely handwave away parts of the problem until you have a good understanding of the entire problem.
I can't even count the cases in which I though I understand some algorithm (either in uni, or more recently, through reading a paper), then I sat down to implement it and realized I don't really understand shit about it.
I mean, I ended up implementing most of the problem sets in Python anyway - then had to transpile them into the bizarre undocumented form of pseudocode that was apparently the only thing the instructor and TAs could understand.
Combined with the complete lack of value added by the in-class lectures, compared to just reading the textbook, and the draconian attendance policy, it was far and away the worst class I endured in college. Particularly galling for a subject so central to the course of study and one that had material that could be so interesting if handled differently.
It was also the class that introduced us to unit tests, by having the code delivered as C library, that the teacher would link against to run her tests.
Back when I was there, we used Caml Light.
Miss the campus. :)
However I would definitely struggle with it today. My best simplistic explanation is that it is a method in which you cache values in order to not duplicate work.
I then tell about the only example which I could still bang out on a white board, which is fibonacci with a cache.
Oh yeah and another important detail is something something solving subproblems :p
I ended up using it as the basis for another extra-credit project that demonstrated the algorithm with a GUI: Select inputs, choose speed, hit Play, watch the numbers and lines, etc.
Anyway, it's stayed with me as my go-to DP example.
IIRC, his complaints were about the speed of formulation, difficulty to understand and communicate the model to others, and the processing required to regenerate answers when the model changed.
I believe Optiant used Dynamic Programming for supply chain optimization.. So people do or did use it for practical problem solving. ..I think.
Generally, shortest path algorithms rely on dynamic programming for a reasonable solution. Examples of include the Traveling Salesman.
Yes, the least cost path problem is not just a classic DP problem but is an example in this article.
I agree reformulating the problem can be confusing. It wouldn't be worth it, but for the incredible efficiency gains (not always needed).
All of this is explained very intuitively in speech.zone
In the wikipedia entry there is a fun (really) explanation of why its creator called it like this.
I don't understand this part, can anybody explain?
e.g., consider the following recursive solution for calculating the sum of all positive integers up to a given `n`:
fn sum(n):
if n == 0:
return 0
else:
return n + sum(n - 1) // A
That's where tail-recursion or tail-call optimization comes in:
fn sum_tail(n, pre_sum):
if n == 0:
return pre_sum
return sum_tail(n - 1, pre_sum + n) // B
fn sum(n):
return sum_tail(n, 0)
It's useful to know that whether any stack space can actually be saved, depends on whether your language of choice implements tail-call optimization. e.g., JavaScript recently started supporting tail-call optimization after ES6 [1], and Python does not support it [2].
[1] http://2ality.com/2015/06/tail-call-optimization.html [2] https://stackoverflow.com/questions/13591970/does-python-opt...
But I still don't see how tail recursion implements memoisation? One might even argue that tail recursion is the opposite of memoisation; while tail recursion saves memory because it eliminates the need to remember previous results of function calls, memoisation on the other hand uses extra memory to save results of earlier function calls.
The crux of the misunderstanding is here: [tail recursion] eliminates the need to remember previous results of function calls.
Emphasis: results. The thing is: tail call recursion essentially means "finish all intermediate computations and pass the results of these to the next function call".
In the non-tail call version, the sum function has no results until you hit the deepest level of recursion; it is the equivalent of writing the sum out in full, which causes all that extra overhead:
sum = n + (n-1) + (n-2) + ... + 0
The `pre_sum + n` bit in the second example is what fixes this. All intermediate calculations are finished and then "stored" by passing them as arguments to recursive calls. This gives the functional equivalent of a for loop:
sum = 0
for i in n..0:
sum += i
Ok, but isn't this then also the case for non-tail recursive calls? And ordinary recursive call builds just as well on the finished result of the previous call and no result is really "stored" in either case.
> You have to recurse until you reach n == 0, and only then does the whole sum "collapse".
It is memoization, not memorisation! Although for two weeks in algorithms class I did in fact think our prof was just pronouncing memorize in a cutesy manner.
So if you see the word, you instantly know that this is the context. You wouldn't know that if you see "memorization".
Seeing the word memorize implies a process that an actor is undergoing and says nothing about the data being memorized. Seeing the word memoize implies the existence of an expensive function and implies a process of repeated calls to the function. It also implies the function is pure, i.e. you can't memoize calls to fread().
Memoization is close enough to "memorization" that you pretty much know what it is without having heard of it before and easily rememberable, while being specific enough to the actual concept as to be easily searchable and imply specific concerns of its own. That's a win-win in my book.
But that's part of it, you generally don't really associate that with memory until you get older...
Memorization makes me think of a repetitive process of committing something permanently to memory.