5 ms·

IMHO, stochastic optimal (SOC) control is a framework that is much more powerful than anything like current artificial intelligence, machine learning, deep lear

IMHO, stochastic optimal (SOC) control is a framework that is much more powerful than anything like current artificial intelligence, machine learning, deep learning, etc. and, in particular, a much better version of something like actual learning. The difference is like going from gnats to elephants, like a bicycle to the star ship Enterprise. A good application of SOC looks not just "intelligent" but wise, prudent, brilliant, and prescient. There have been claims that necessarily SOC is the most powerful version of learning there can be -- a bit much but ... maybe. For computing architectures, the computing that SOC can soak up makes the computing needs of current deep learning look like counting on fingers in kindergarten. The subject is no joke and goes back to E. Dynkin (student of Kolmogorov and Gel'fand), D. Bertsekas (used neural nets for approximations for some of the huge tables of data), R. Rockafellar (e.g., scenario aggregation), and, sure, R. Bellman. Some of the pure math is tricky, e.g., measurable selection. I did my Ph.D. dissertation in SOC and there actually made the computing reasonable, e.g., wrote and ran the software -- ran in a few minutes, with my progress in algorithms down from an estimate of 64 years. For larger problems, can be back to taking over all of Amazon for 64 years. More algorithmic progress is possible, and, then, some specialized hardware should also help, sure, by factors of 10; right, we want lots of factors of 10. If want to think ambitious computing, past Moore's law, past anything like current AI, with special purpose hardware, go for SOC. SOC Applications 101. For your company, do financial planning for the next 50 years, 60 months. So, set up a spreadsheet with one column for each month, one column for the current state of the company and then 60 more columns. Goal is, say, to maximize the expected value of something, maybe the value of the company, in the last column, right, with control over the probability of going broke, if a bank always be able to meet reserve requirements and pass stress tests; if a property-casuality insurance company, stay in business after hurricane Florence, etc. For each variable of interest, have a row. In the cells, put in the usual expressions in terms of the values of cells in earlier columns. Also have some cells with random numbers -- the stochastic part. Also have some cells empty for the business decisions, the control part. This is the 101 version; the 201 version has more detail! Can't get the solution with just the usual spreadsheet recalc because the best solution is optimal and varies through the 60 months as more information is gathered -- and that is the core of the need for more in algorithms and taking over all of Amazon for the computing. Really, the work comes too close to looking at all possible business state scenarios over the 60 months yet still is astronomically faster than direct or naive ways to do this. Or, a little like football, don't call the play on 2nd down until see the results of the play on 1st down, BUT the play called on 1st down was optimal considering the options for the later downs and plays. The optimality achieved is strict, the best possible, not merely heuristic: No means of making the decisions using only information available when the decisions are made can do better (proved in my dissertation). Intel, AMD, Qualcomm, DARPA, NSF, Microsoft, etc., think SOC!!! You just heard it here -- I might not bother to tell you again.

ssvss 8y ago
What book would you recommend to know more about SOC?
- graycat 8y ago
  Start with books on dynamic programming, discrete time, discrete space space, no uncertainty. There's a nice one by Dreyfus and Law, The Art and Theory of Dynamic Programming that also gets into the stochastic case. It's called dynamic programming because the program, that is, the planning, changes dynamically over time as learn more and more as time passes. D&L show a nice result that could be used for some first cut approximations: If are minimizing a quadratic cost, if the algebraic expressions in that spreadsheet I mentioned are all linear, and if the randomness is all just Gaussian, then get "certainty equivalence" -- that is, get to f'get about the Gaussian, random, stochastic part and use just the expectations themselves. Huge speedup. For more, there is Dynkin and Yushkevich, Controlled Markov Processes -- one of the key assumptions that permits treating the spreadsheet columns one at a time is that the stochastic part obeys a Markov assumption (the past and future are conditionally independent given the present). There is, from MIT and CMU, Dimitri P. Bertsekas and Steven E. Shreve, Stochastic Optimal Control: The Discrete Time Case. And there is Wendell H. Fleming and Raymond W. Rishel, Deterministic and Stochastic Optimal Control. There are papers by R. Rockafellar, long at U. Washington. There is now an ambitious program at Princeton in the department of Operations Research and Financial Engineering. I tried to get IBM's Watson lab interested; by now they would have been nicely ahead. The guys I was working for wanted me to do software architecture for the OSI/ISO CMIS/P data standards. Garbage direction. A really big mistake for Big Blue, not so big now. One of the reasons for IBM to have done SOC was that they had some vector hardware instructions, that is, that would do an inner product, that is, for positive integer n, given arrays A and B, each of length n, find the sum, i = 1, 2, ..., n of A(i)*B(i). Well inevitably work in probability does a LOT of this. So, if thinking about hardware instructions for SOC, such a vector instruction would be one of the first features. Then maybe more for neural net approximations to some big tables of several dimensions, e.g., computer language arrays A(m, n, p, q) for 4 dimensions but in practice several more. And multivariate splines can play a role. Commonly can get some nice gains by finding non-inferior points -- so will want some fast ways to work with those. The software for my dissertation did that; got a speedup of maybe 100:1; on large problems, commonly could get much more. There is some compiling that can get some big gains -- some of the big gains I got were from just my doing the compiling by hand, but what I did could be a feature in a compiler -- there's likely still a stream of publications there if anyone is interested in publications (my interests are in business, the money making kind, now my startup). There is a cute trick if, say, all the spreadsheet column logic is the same -- can "double up on number of stages". There are lots of speedup techniques known. A big theme will be various approximations. If there's an opportunity to exploit sufficient statistics, then that could yield big speedups and shouldn't be missed. Having the compiling, sufficient statistics, and non-inferior exploitation all work together could yield big gains -- that should all be compiled. Get some papers out of that! No doubt similarly for other speedups. There's lots to be done.

ssvss 8y ago

What book would you recommend to know more about SOC?

graycat 8y ago
Start with books on dynamic programming, discrete time, discrete space space, no uncertainty. There's a nice one by Dreyfus and Law, The Art and Theory of Dynamic Programming that also gets into the stochastic case. It's called dynamic programming because the program, that is, the planning, changes dynamically over time as learn more and more as time passes. D&L show a nice result that could be used for some first cut approximations: If are minimizing a quadratic cost, if the algebraic expressions in that spreadsheet I mentioned are all linear, and if the randomness is all just Gaussian, then get "certainty equivalence" -- that is, get to f'get about the Gaussian, random, stochastic part and use just the expectations themselves. Huge speedup. For more, there is Dynkin and Yushkevich, Controlled Markov Processes -- one of the key assumptions that permits treating the spreadsheet columns one at a time is that the stochastic part obeys a Markov assumption (the past and future are conditionally independent given the present). There is, from MIT and CMU, Dimitri P. Bertsekas and Steven E. Shreve, Stochastic Optimal Control: The Discrete Time Case. And there is Wendell H. Fleming and Raymond W. Rishel, Deterministic and Stochastic Optimal Control. There are papers by R. Rockafellar, long at U. Washington. There is now an ambitious program at Princeton in the department of Operations Research and Financial Engineering. I tried to get IBM's Watson lab interested; by now they would have been nicely ahead. The guys I was working for wanted me to do software architecture for the OSI/ISO CMIS/P data standards. Garbage direction. A really big mistake for Big Blue, not so big now. One of the reasons for IBM to have done SOC was that they had some vector hardware instructions, that is, that would do an inner product, that is, for positive integer n, given arrays A and B, each of length n, find the sum, i = 1, 2, ..., n of A(i)*B(i). Well inevitably work in probability does a LOT of this. So, if thinking about hardware instructions for SOC, such a vector instruction would be one of the first features. Then maybe more for neural net approximations to some big tables of several dimensions, e.g., computer language arrays A(m, n, p, q) for 4 dimensions but in practice several more. And multivariate splines can play a role. Commonly can get some nice gains by finding non-inferior points -- so will want some fast ways to work with those. The software for my dissertation did that; got a speedup of maybe 100:1; on large problems, commonly could get much more. There is some compiling that can get some big gains -- some of the big gains I got were from just my doing the compiling by hand, but what I did could be a feature in a compiler -- there's likely still a stream of publications there if anyone is interested in publications (my interests are in business, the money making kind, now my startup). There is a cute trick if, say, all the spreadsheet column logic is the same -- can "double up on number of stages". There are lots of speedup techniques known. A big theme will be various approximations. If there's an opportunity to exploit sufficient statistics, then that could yield big speedups and shouldn't be missed. Having the compiling, sufficient statistics, and non-inferior exploitation all work together could yield big gains -- that should all be compiled. Get some papers out of that! No doubt similarly for other speedups. There's lots to be done.