6 ms·

This is one of the most exciting things I've seen come out of AI research for my own interests. The way that they distributed the mathematical equations is call

This is one of the most exciting things I've seen come out of AI research for my own interests. The way that they distributed the mathematical equations is called an abstract syntax tree (maybe they mentioned this, but I was excited-skimming), and is also how computer code is represented. It also happens that there is _a lot_ more computer code laying around in computer-readable format than high school and college math problems. With this, you get: metamorphic code, better optimizers, more abstract programming languages (maybe), and probably lots of other steps forward. If anyone is working on AI+programming languages, please send me a message. I'd love to work with others on this problem.

keenmaster 6y ago
"With this, you get: ... more abstract programming languages (maybe)." That would be great. If you could guess, how would you go about using symbolic math and neural nets to create a more abstract programming language?
- MaxBarraclough 6y ago
  If you'll entertain my clueless guesswork: If it could be used to greatly accelerate SMT solving/constraint solving, perhaps it would be possible to run a formal model as if it were code, i.e. fast and scalable constraint-based programming. That's about as high-level as you can get, short of a requirements document. I'm not sure if that's the kind of symbolic mathematics that's being studied here, as they seem to be looking at mathematically interesting expressions, rather than boring-but-enormous constraints. Or, somewhat related, perhaps it could be used to help scale formal verification with languages like SPARK and ZZ.
  - orange3xchicken 6y ago
    In general, I think neural networks really struggle with np hard problems. Current state of the art is bottlenecked wrt to even subtle generalization. The strong baselines have been variations on the pointer-network architecture for some time now. Even though they can do reasonably well on restricted problems (e.g. instances of sat/traveling salesman with fixed # of nodes), they struggle to generalize to instances of the problem with variable # of nodes - not to mention varying the problem itself. Some popular approaches also incl. applications of Graph CNNs & reinforcement learning. Don't really have much more than a cursory idea of the current directions though. To me, more exciting is some kind of joint collaboration between modern ml systems & formal solvers.
    - bglazer 6y ago
      You might be interested in the line of work around differentiable relaxations of formal solvers that was kicked off by Zico Kolter et al. They add a Max=SAT solver as a differentiable layer. This allows the neat trick of solving handwritten Sudoku puzzles by composing a ConvNet with the differentiable Max-SAT layer. [1] https://arxiv.org/abs/1905.12149 https://arxiv.org/abs/1905.12149
      - orange3xchicken 6y ago
        Thanks - that's great! I'm familiar with Kolter's work on adversarial robustness.
Jugglerofworlds 6y ago
I'm planning on applying for PhD programs this fall to work in this area. There are only a few places in the world right now that I know of working on these types of problems. They are: * Martin Vechev, ETH Zurich * Dawn Song, University of California Berkeley * Eran Yahav, Technion * Miltiadis Allamanis, Microsoft Research Cambridge If anyone knows other advisors looking for graduate students in this area, please let me know. Due to personal circumstances I can most likely not apply to ETH Zurich or Technion (I don't speak Hebrew anyway), which leaves me with only one potential advisor in a program that I really want. There is also the Python writing model that Open AI showed recently at the Microsoft Build conference, so maybe there is some interest growing at other places as well. I was also recently working on a deep learning decompiler but was unable to get my transformer model to learn well enough to actually decompile x64 assembly. I have the source code for the entire Linux kernel as training data, so it's not an issue with quantity. If anyone is interested in helping out with this project, please let me know in a comment.
- Mehdi2277 6y ago
  UCL is another good choice for this area. I did some research in this area back in undergrad. There was a workshop called NAMPI (neural abstract machine program intelligence) on this subfield so I'd recommend going through the accepted papers for it and seeing where all the faculty come from. Also general advice, after finding a few papers you like go through the papers they cite that are relevant to the subfield and also papers that cite them. That's one of the best ways of finding other related research that interests you.
- lmeyerov 6y ago
  As part of the short list: * Swarat: https://blog.sigplan.org/2020/04/15/synthesizing-neurosymbolic-programs/ https://blog.sigplan.org/2020/04/15/synthesizing-neurosymbol... <- probably heaviest on the math side wrt PL people * Ras Bodik (Berkeley -> UW): esp. w/ Pedro Domingos and all the MSR collaborators (Sumit Gulwani, ...) <- a bit biased b/c I was in the group while at Berkeley; Ras + Dawn are crazy creative * Percy Liang (Stanford): Coming from the ML side and w/ a long-running interest here
- NwtnsMthd 6y ago
KhoomeiK 6y ago
I believe Jacob Andreas at MIT is working on compositional neural net architectures for applications in programming language theory at the moment
gavinray 6y ago
Forgive me for being entirely ignorant about the field, but I've thought about this frequently and would be grateful for a decent answer: How theoretically feasible would it be to create Meta-AI. My naive (incredibly over-simplified) notion goes something like this: - You convert open-source code into a generic/universal AST/IR format, and figure out a means to represent function inputs and outputs (behavior) - You use all of the OSS code in the world as data for this, to train a neural network to start making predictions about what kind of AST inputs in a program lead to what kinds of outputs (function synthesis) - You tell the program to look at other deep learning/ML code, and to attempt to optimize it's own code, while running, inside of isolated processes/VM's. Something like Erlang/Elixir or Lisp should be capable of this meta-programming and self-code modification while still running. And the BEAM would theoretically be able to isolate actors in the event that the epoch doesn't pan out very well and just kill that branch/lineage off. Is this insane? I've wondered about this for years.
- dunefox 6y ago
  > You convert open-source code into a generic/universal AST/IR format, and figure out a means to represent function inputs and outputs (behavior) I think this alone is a herculean task.
  - gavinray 6y ago
    Definitely, it's _practically_ impossible, but I am just curious whether the idea/theory of it isn't.
- gnramires 6y ago
  No it isn't, in fact this line of work has already a tradition seen here: https://en.wikipedia.org/wiki/Genetic_programming#Meta-genetic_programming https://en.wikipedia.org/wiki/Genetic_programming#Meta-genet... Although it uses genetic programming instead of neural networks. Those approaches are equivalent in power, the difference is only that neural networks are more amenable to parallelization and we know a very good baseline optimization algorithm (gradient descent and friends). The problem is that coming up with an optimizer/architecturer is hard. So the benefit of running a meta-optimizer to solve a problem is difficult to realize versus a handmade neural network. The problem needs to be so large the network would need to re-engineer itself to solve it -- but think how many resources have already been spent in engineering neural networks (by humans no less, which are quite powerful optimizers!). Unless the problem is truly titanic (w.r.t. other current problems) the yields might be small. What you can do in a similar vein is gather a large set of problems and train a 'Neural architect' or something like that that then can be applied many times to new problems. This allows sharing this cost over many new networks. I think it could make sense for governments and large organizations to get together and create this sort of thing. If you know the costs of training a large neural network, imagine the cost of training hundreds of millions to train some kind of neural architect (NA). There are milder versions of this, where the architecture search itself isn't trained: https://en.wikipedia.org/wiki/Neural_architecture_search https://en.wikipedia.org/wiki/Neural_architecture_search https://en.wikipedia.org/wiki/Automated_machine_learning https://en.wikipedia.org/wiki/Automated_machine_learning Of course even this approach has limitations (even if you theoretically allow it to create essentially arbitrary architectures), because it will still have difficulty "thinking outside the box" like we do using huge amounts of mathematical expertise and intuition (see EfficientNet -- the insight in that paper would be difficult to arise from a NA network) -- it's not the thing that will solve all of our problem forever; but it would be pretty significant (perhaps towards making large AI-based systems with multiple components, say self-driving cars and robots of the future).
tasdfqwer0897 6y ago
We have been working on this recently on the Google Brain team. We are working both on synthesizing programs from scratch (see https://arxiv.org/abs/2002.09030 https://arxiv.org/abs/2002.09030 for example) and on understanding computer programs using machine learning (see e.g. https://arxiv.org/abs/1911.01205 https://arxiv.org/abs/1911.01205). I'm always happy to correspond with people about these topics.
- yazr 6y ago
  Love to chat. Sent u an email (former HFT and kernel guy). One topic which is feel is neglected is a good GCN (or any GNN) to operate on existing code trees. Most approaches seem to prefer seq or at most tree inputs. Is this simply not finding yet a good network architecture, or is it a performance issue ?
  - siv_ran7611 6y ago
    I dont see any email listed on your profile. Would like to have a chat to work/learn on this stuff
- logicchains 6y ago
  Have you considered attempting to develop a "differentiable programming language" so that it's possible to do gradient descent directly on the space of programs? There was some work on building a "differentiable lambda calculus", https://core.ac.uk/download/pdf/82396223.pdf https://core.ac.uk/download/pdf/82396223.pdf, but I haven't heard of anyone trying to use something like that in modern program synthesis.
  - m3at 6y ago
    Late on the thread but you might be interested in this: https://www.tensorflow.org/swift https://www.tensorflow.org/swift
    - logicchains 6y ago
      That's something different: it allows doing gradient descent on the space of paramaters for programs, not on the space of programs.
throw_away 6y ago
This vid from the MS Build conf is pretty amazing (skip to around the 30m mark for the mindblowing stuff): https://twitter.com/i/broadcasts/1OyKAYWPRrWKb https://twitter.com/i/broadcasts/1OyKAYWPRrWKb
thomasahle 6y ago
They don't actually use trees in the paper though. https://arxiv.org/abs/1912.01412 https://arxiv.org/abs/1912.01412 They express everything in reverse polish notation, exactly so the transformer network can work on streams and not care about the nesting levels. It's a bit odd that this article doesn't talk about that.
sharemywin 6y ago
I found this video interesting. It takes comments and generates code. https://www.youtube.com/watch?v=fZSFNUT6iY8 https://www.youtube.com/watch?v=fZSFNUT6iY8

keenmaster 6y ago

"With this, you get: ... more abstract programming languages (maybe)." That would be great. If you could guess, how would you go about using symbolic math and neural nets to create a more abstract programming language?

MaxBarraclough 6y ago
If you'll entertain my clueless guesswork: If it could be used to greatly accelerate SMT solving/constraint solving, perhaps it would be possible to run a formal model as if it were code, i.e. fast and scalable constraint-based programming. That's about as high-level as you can get, short of a requirements document. I'm not sure if that's the kind of symbolic mathematics that's being studied here, as they seem to be looking at mathematically interesting expressions, rather than boring-but-enormous constraints. Or, somewhat related, perhaps it could be used to help scale formal verification with languages like SPARK and ZZ.
- orange3xchicken 6y ago
  In general, I think neural networks really struggle with np hard problems. Current state of the art is bottlenecked wrt to even subtle generalization. The strong baselines have been variations on the pointer-network architecture for some time now. Even though they can do reasonably well on restricted problems (e.g. instances of sat/traveling salesman with fixed # of nodes), they struggle to generalize to instances of the problem with variable # of nodes - not to mention varying the problem itself. Some popular approaches also incl. applications of Graph CNNs & reinforcement learning. Don't really have much more than a cursory idea of the current directions though. To me, more exciting is some kind of joint collaboration between modern ml systems & formal solvers.
  - bglazer 6y ago
    You might be interested in the line of work around differentiable relaxations of formal solvers that was kicked off by Zico Kolter et al. They add a Max=SAT solver as a differentiable layer. This allows the neat trick of solving handwritten Sudoku puzzles by composing a ConvNet with the differentiable Max-SAT layer. [1] https://arxiv.org/abs/1905.12149 https://arxiv.org/abs/1905.12149
    - orange3xchicken 6y ago
      Thanks - that's great! I'm familiar with Kolter's work on adversarial robustness.

Jugglerofworlds 6y ago

I'm planning on applying for PhD programs this fall to work in this area. There are only a few places in the world right now that I know of working on these types of problems. They are: * Martin Vechev, ETH Zurich * Dawn Song, University of California Berkeley * Eran Yahav, Technion * Miltiadis Allamanis, Microsoft Research Cambridge If anyone knows other advisors looking for graduate students in this area, please let me know. Due to personal circumstances I can most likely not apply to ETH Zurich or Technion (I don't speak Hebrew anyway), which leaves me with only one potential advisor in a program that I really want. There is also the Python writing model that Open AI showed recently at the Microsoft Build conference, so maybe there is some interest growing at other places as well. I was also recently working on a deep learning decompiler but was unable to get my transformer model to learn well enough to actually decompile x64 assembly. I have the source code for the entire Linux kernel as training data, so it's not an issue with quantity. If anyone is interested in helping out with this project, please let me know in a comment.

Mehdi2277 6y ago
UCL is another good choice for this area. I did some research in this area back in undergrad. There was a workshop called NAMPI (neural abstract machine program intelligence) on this subfield so I'd recommend going through the accepted papers for it and seeing where all the faculty come from. Also general advice, after finding a few papers you like go through the papers they cite that are relevant to the subfield and also papers that cite them. That's one of the best ways of finding other related research that interests you.
lmeyerov 6y ago
As part of the short list: * Swarat: https://blog.sigplan.org/2020/04/15/synthesizing-neurosymbolic-programs/ https://blog.sigplan.org/2020/04/15/synthesizing-neurosymbol... <- probably heaviest on the math side wrt PL people * Ras Bodik (Berkeley -> UW): esp. w/ Pedro Domingos and all the MSR collaborators (Sumit Gulwani, ...) <- a bit biased b/c I was in the group while at Berkeley; Ras + Dawn are crazy creative * Percy Liang (Stanford): Coming from the ML side and w/ a long-running interest here
NwtnsMthd 6y ago

KhoomeiK 6y ago

I believe Jacob Andreas at MIT is working on compositional neural net architectures for applications in programming language theory at the moment

gavinray 6y ago

Forgive me for being entirely ignorant about the field, but I've thought about this frequently and would be grateful for a decent answer: How theoretically feasible would it be to create Meta-AI. My naive (incredibly over-simplified) notion goes something like this: - You convert open-source code into a generic/universal AST/IR format, and figure out a means to represent function inputs and outputs (behavior) - You use all of the OSS code in the world as data for this, to train a neural network to start making predictions about what kind of AST inputs in a program lead to what kinds of outputs (function synthesis) - You tell the program to look at other deep learning/ML code, and to attempt to optimize it's own code, while running, inside of isolated processes/VM's. Something like Erlang/Elixir or Lisp should be capable of this meta-programming and self-code modification while still running. And the BEAM would theoretically be able to isolate actors in the event that the epoch doesn't pan out very well and just kill that branch/lineage off. Is this insane? I've wondered about this for years.

dunefox 6y ago
> You convert open-source code into a generic/universal AST/IR format, and figure out a means to represent function inputs and outputs (behavior) I think this alone is a herculean task.
- gavinray 6y ago
  Definitely, it's _practically_ impossible, but I am just curious whether the idea/theory of it isn't.
gnramires 6y ago
No it isn't, in fact this line of work has already a tradition seen here: https://en.wikipedia.org/wiki/Genetic_programming#Meta-genetic_programming https://en.wikipedia.org/wiki/Genetic_programming#Meta-genet... Although it uses genetic programming instead of neural networks. Those approaches are equivalent in power, the difference is only that neural networks are more amenable to parallelization and we know a very good baseline optimization algorithm (gradient descent and friends). The problem is that coming up with an optimizer/architecturer is hard. So the benefit of running a meta-optimizer to solve a problem is difficult to realize versus a handmade neural network. The problem needs to be so large the network would need to re-engineer itself to solve it -- but think how many resources have already been spent in engineering neural networks (by humans no less, which are quite powerful optimizers!). Unless the problem is truly titanic (w.r.t. other current problems) the yields might be small. What you can do in a similar vein is gather a large set of problems and train a 'Neural architect' or something like that that then can be applied many times to new problems. This allows sharing this cost over many new networks. I think it could make sense for governments and large organizations to get together and create this sort of thing. If you know the costs of training a large neural network, imagine the cost of training hundreds of millions to train some kind of neural architect (NA). There are milder versions of this, where the architecture search itself isn't trained: https://en.wikipedia.org/wiki/Neural_architecture_search https://en.wikipedia.org/wiki/Neural_architecture_search https://en.wikipedia.org/wiki/Automated_machine_learning https://en.wikipedia.org/wiki/Automated_machine_learning Of course even this approach has limitations (even if you theoretically allow it to create essentially arbitrary architectures), because it will still have difficulty "thinking outside the box" like we do using huge amounts of mathematical expertise and intuition (see EfficientNet -- the insight in that paper would be difficult to arise from a NA network) -- it's not the thing that will solve all of our problem forever; but it would be pretty significant (perhaps towards making large AI-based systems with multiple components, say self-driving cars and robots of the future).

tasdfqwer0897 6y ago

We have been working on this recently on the Google Brain team. We are working both on synthesizing programs from scratch (see https://arxiv.org/abs/2002.09030 https://arxiv.org/abs/2002.09030 for example) and on understanding computer programs using machine learning (see e.g. https://arxiv.org/abs/1911.01205 https://arxiv.org/abs/1911.01205). I'm always happy to correspond with people about these topics.

yazr 6y ago
Love to chat. Sent u an email (former HFT and kernel guy). One topic which is feel is neglected is a good GCN (or any GNN) to operate on existing code trees. Most approaches seem to prefer seq or at most tree inputs. Is this simply not finding yet a good network architecture, or is it a performance issue ?
- siv_ran7611 6y ago
  I dont see any email listed on your profile. Would like to have a chat to work/learn on this stuff
logicchains 6y ago
Have you considered attempting to develop a "differentiable programming language" so that it's possible to do gradient descent directly on the space of programs? There was some work on building a "differentiable lambda calculus", https://core.ac.uk/download/pdf/82396223.pdf https://core.ac.uk/download/pdf/82396223.pdf, but I haven't heard of anyone trying to use something like that in modern program synthesis.
- m3at 6y ago
  Late on the thread but you might be interested in this: https://www.tensorflow.org/swift https://www.tensorflow.org/swift
  - logicchains 6y ago
    That's something different: it allows doing gradient descent on the space of paramaters for programs, not on the space of programs.

throw_away 6y ago

This vid from the MS Build conf is pretty amazing (skip to around the 30m mark for the mindblowing stuff): https://twitter.com/i/broadcasts/1OyKAYWPRrWKb https://twitter.com/i/broadcasts/1OyKAYWPRrWKb

thomasahle 6y ago

They don't actually use trees in the paper though. https://arxiv.org/abs/1912.01412 https://arxiv.org/abs/1912.01412 They express everything in reverse polish notation, exactly so the transformer network can work on streams and not care about the nesting levels. It's a bit odd that this article doesn't talk about that.

sharemywin 6y ago

I found this video interesting. It takes comments and generates code. https://www.youtube.com/watch?v=fZSFNUT6iY8 https://www.youtube.com/watch?v=fZSFNUT6iY8