Super interesting! I love how you combined your extensive past experience with competitive programming and are now trying to fuse these 2 approaches together! I've got a bunch of questions if you could answer any one of these I'd be grateful: 1. Do you have an example of an application where it is potentially better to deploy a system like this vs the classical algorithm? (I guess the answer is some type of an NP-hard problem) 2. Can we make some theoretical guarantees that the neural algorithm won't fail on edge cases? 3. Are you considering combining these with RL as RL is notoriously famous for solving that NP-type of problems especially at DeepMind (AlphaStar, AlphaGo/Zero/MuZero, etc.)? 4. What about interpretability?
Thanks for the thoughtful comment! To answer point (1): I think the key application is in the point that most natural (raw/noisy) inputs cannot be easily mapped to satisfy the preconditions of abstract algorithms. Typically a lot of effort is needed to turn them into abstract inputs, and this not only involves a lot of feature engineering, it also represents an "art" of sorts*. If history taught us anything -- whenever there's lots of feature engineering, there's potential for deep learning to thrive. :) A pre-trained algo executor (w/frozen weights) can be 'stitched' into a pipeline that takes raw inputs straight to outputs, removing the need for feature engineering but still retaining computational structure of the original algorithm. When backpropping in this regime, we are effectively learning good 'encoder' functions for the latent-space algorithm, _replacing_ or augmenting the role of the human feature engineer. This leads into my answer of (3). We have follow-up work (XLVIN) which leverages these ideas in reinforcement learning: arxiv.org/abs/2010.13146. We observe that there are many useful traditional planning algorithms (such as Value Iteration) that require knowledge of the full MDP model to be applicable. We pre-train one of these GNN executors to run Value Iteration on a bunch of synthetic fully-specified MDPs, then stitch its frozen weights inside a standard RL pipeline---yielding a useful implicit planner that generalises some prior art such as Value Iteration Nets, and TreeQN. For more info, check out some of my talks at this year's NeurIPS, esp my invited talk at the LMCA workshop. :) As for (2/4), I think a promising direction is to make the executer decode outputs at every step, and try to extract meaningful pseudocode out of it. Such pseudocode can then be analysed by more formal methods, if max correctness is what is sought after, and also provide interpretability for what's going on. But I haven't really validated this idea yet in any way. *Check out the paper that introduces the max-flow problem, in the context of finding a bottleneck capacity of the Soviet railway system: apps.dtic.mil/dtic/tr/fulltext/u2/093458.pdf It summarises this issue succinctly and beautifully: “The evaluation of both railway system and individual track capacities is, to a considerable extent, an art. The authors know of no tested mathematical model or formula that includes all of the variations and imponderables that must be weighed.* Even when the individual has been closely associated with the particular territory he is evaluating, the final answer, however accurate, is largely one of judgment and experience.”
@@petarvelickovic6033 Beautiful! I'll need some time to parse this! 🧠 I'll probably come back in a couple of months once I've read the resources you mentioned hahah. 😅
This approach to algorithm discovery that you described is very exciting!
Very interesting talk - thank you for posting this to UA-cam.
very nice and thought-provoking talk
A beautiful presentation. Great work.
Nice presentation of a novelty use of GNN in graph networks.
Great video, hope you’ll do more!
Exciting and thought provoking.
Super interesting! I love how you combined your extensive past experience with competitive programming and are now trying to fuse these 2 approaches together!
I've got a bunch of questions if you could answer any one of these I'd be grateful:
1. Do you have an example of an application where it is potentially better to deploy a system like this vs the classical algorithm? (I guess the answer is some type of an NP-hard problem)
2. Can we make some theoretical guarantees that the neural algorithm won't fail on edge cases?
3. Are you considering combining these with RL as RL is notoriously famous for solving that NP-type of problems especially at DeepMind (AlphaStar, AlphaGo/Zero/MuZero, etc.)?
4. What about interpretability?
Thanks for the thoughtful comment!
To answer point (1): I think the key application is in the point that most natural (raw/noisy) inputs cannot be easily mapped to satisfy the preconditions of abstract algorithms. Typically a lot of effort is needed to turn them into abstract inputs, and this not only involves a lot of feature engineering, it also represents an "art" of sorts*.
If history taught us anything -- whenever there's lots of feature engineering, there's potential for deep learning to thrive. :) A pre-trained algo executor (w/frozen weights) can be 'stitched' into a pipeline that takes raw inputs straight to outputs, removing the need for feature engineering but still retaining computational structure of the original algorithm. When backpropping in this regime, we are effectively learning good 'encoder' functions for the latent-space algorithm, _replacing_ or augmenting the role of the human feature engineer.
This leads into my answer of (3). We have follow-up work (XLVIN) which leverages these ideas in reinforcement learning: arxiv.org/abs/2010.13146. We observe that there are many useful traditional planning algorithms (such as Value Iteration) that require knowledge of the full MDP model to be applicable. We pre-train one of these GNN executors to run Value Iteration on a bunch of synthetic fully-specified MDPs, then stitch its frozen weights inside a standard RL pipeline---yielding a useful implicit planner that generalises some prior art such as Value Iteration Nets, and TreeQN. For more info, check out some of my talks at this year's NeurIPS, esp my invited talk at the LMCA workshop. :)
As for (2/4), I think a promising direction is to make the executer decode outputs at every step, and try to extract meaningful pseudocode out of it. Such pseudocode can then be analysed by more formal methods, if max correctness is what is sought after, and also provide interpretability for what's going on. But I haven't really validated this idea yet in any way.
*Check out the paper that introduces the max-flow problem, in the context of finding a bottleneck capacity of the Soviet railway system: apps.dtic.mil/dtic/tr/fulltext/u2/093458.pdf
It summarises this issue succinctly and beautifully:
“The evaluation of both railway system and individual track capacities is, to a considerable extent, an art. The authors know of no tested mathematical model or formula that includes all of the variations and imponderables that must be weighed.* Even when the individual has been closely associated with the particular territory he is evaluating, the final answer, however accurate, is largely one of judgment and experience.”
@@petarvelickovic6033 Beautiful! I'll need some time to parse this! 🧠
I'll probably come back in a couple of months once I've read the resources you mentioned hahah. 😅
Fascinating work!
a great innovation