4 ms·

Neurosymbolic Programming (2021) [pdf]

exdsq 5y ago
Anyone here working on program synthesis? I did a little research project as part of an MSc in CS and found it really interesting, but when I looked at industry applications I only found one YC startup working on it in the smart contract space.
- yldedly 5y ago
  I dabble in it. FlashFill in Excel uses program synthesis, but yeah, not many applications exist yet. Have you seen DreamCoder?
  - exdsq 5y ago
    I’ll check it out, thanks!
- YeGoblynQueenne 5y ago
  I study Inductive Logic Programming (ILP) which is a kind of inductive program synthesis. Inductive program synthesis is learning from partial specifications, where deductive program synthesis is learning from complete specifications (compilation can be seen as a form of deductive program synthesis, for example). ILP studies algorithms that learn logic programs from examples. "Logic programs" as in programs in a language of the Logic Programming paradigm, such as Prolog or Answer Set Programming (ASP). If you're interested in program synthesis, this is the staple modern reference: Program Synthesis https://www.microsoft.com/en-us/research/wp-content/uploads/2017/10/program_synthesis_now.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... For ILP, see this recent review: Inductive logic programming at 30 https://arxiv.org/abs/2102.10556 https://arxiv.org/abs/2102.10556 Or this longer version, here: Inductive logic programming at 30: a new introduction https://arxiv.org/abs/2008.07912 https://arxiv.org/abs/2008.07912 (Both of which ignore my own contributions. Oh well :)
  - exdsq 5y ago
    Thank you!! :)
  - yldedly 5y ago
    I got a lot out of this course https://people.csail.mit.edu/asolar/SynthesisCourse/ https://people.csail.mit.edu/asolar/SynthesisCourse/ from one of the authors of OP.
    - YeGoblynQueenne 5y ago
      Oh, yes! I should have added that to my links. Thanks!
      - exdsq 5y ago
        So my little project was essentially a research survey on neural program synthesis - do you have any good sources on building program synthesis projects? I noted a lot of the literature talks about outcomes but rarely how I can go about building something small that takes some Input, Output tuples and returns some code. Ended up dropping the MSc because of Covid and moving to the Bay Area but I'd love to eventually do a research-focused masters in the future. Which may be difficult, because I don't have a Bachelors to begin with and took a lot of effort to get onto a Masters in the first place lol!
        YeGoblynQueenne 5y ago
        You mean resources on creating your own program synthesis system? Hm, I don't know of anything like a program synthesis toolbox, like OpenCV for machine vision, etc. There are many freely available program synthesis systems, but most are research prototypes and they only use a particular approach anyway, while I think you 'd prefer to be able to experiment with different approaches, no? I fear the best option is to try to roll-your-own, based on the descriptions in many different program synthesis papers. Btw, I wouldn't choose neural program synthesis for a first Project! First because neural program synthesis requires as training examples both programming tasks (usually in the form of I/O examples) _and_ programs solving the tasks, and many many of them to boot. Second because it's an uncommon enough approach, or combination of approaches, that I doubt you'll find much support for it in the standard neural net frameworks. I think the CSAIL program synthesis course suggested above by yldedly is a good starting place though. It's graded by a program synthesis project and you might find some tools meant to help students carry out their assignment on the course pages. Or you may try asking the tutors by email even. Other than that, the simples thing to get you started is to define a DSL, generate programs from it and test them against I/O examples of the target programs. That's the simplest, most primitive kind of thing you can do. It's not a very efficient thing to do, but it's a start. The trick is in figuring out how to define the DSL and how to search it efficiently. Good luck, I guess! Feel free to email me if you think I can help. See profile for email. Edit: Here's a blog post about creating a DSL in Python: https://dbader.org/blog/writing-a-dsl-with-python https://dbader.org/blog/writing-a-dsl-with-python
sidpatil 5y ago
If I understand this correctly, this is saying that instead of representing the approximated function as a purely numerical operation (e.g. just a bunch of linear algebra), it can be represented as a program which contains a mixture of typical symbolic syntax and numerical operations. One of the benefits mentioned is better accessibility for existing analysis tools. If I understand the concept correctly, could this also make it easier to implement the approximated functions in environments that lack efficient numerical algorithms and data structures? These two are usually only found in technical computing languages (e.g. FORTRAN, Julia, etc.), or as libraries for a handful of general-purpose languages (e.g. Numpy, Numba, etc.)
blurbleblurble 5y ago
Julia is the perfect language for something like this.
- mark_l_watson 5y ago
  I agree that something like Julia vs. Python + libraries written in C++ seems like a better fit. However, there is such a vast wealth of tooling around Python, and high level development services like Huggingface, that for the foreseeable future, Python dominates.
  - blurbleblurble 5y ago
    Sure, makes sense. The way I see it that Julia's differentiable programming features seem like a really good match for building stuff in this framework.
9wzYQbTYsAIc 5y ago
> In contrast, a neural component is a (typically over-)parameterized, differentiable blackbox function that does not have an a priori specification. > The holy grail for research on neurosym- bolic programming would be a general learning algorithm that could efficiently generate arbitrary combinations of neural components and symbolic code. This is one area where the authors may be missing the point of the parallel distributed processing approach. The authors treat ANN’s as blind guesses from massive training data, but they forget that in most cases the choice of training data is the a priori specification. Additionally, an ANN can be comprised of multitudes of types of artificial neurons. While some learning models are designed to discover relationships between complex data, other learning models are designed for simple data. The simpler the training data, the easier to assign a meaning to the output. Simple back-propagation was followed by the development of deep learning and complex network architectures. The explosion in interest in deep learning is, in part, due to the realization that complex neural architectures can be comprised of a variety of neural components in a variety of ways and that the resulting neural architectures would almost certainly avail us with solutions that span the entirety of possible problems to solve. That is to say, deterministic behavior (“symbolic program synthesis”) could be implemented by an ANN, if the ANN had the required minimum complexity. Since the minimum complexity of such an ANN is currently incomprehensibly high, due to deep learning being in its infancy, there has been a heavy focus on striking results with low complexity. In my view, instead of trying to bring back the zombie of symbolic programming for AI, the authors’ time would be better spent on contributing novel, highly complex neural architectures. For example, some biological neurons in the visual cortex have been shown to be responsive to single individuals faces. If there is one neuron per face, then there could be thousands or more of face neurons in the visual cortex. Where normal deep learning would focus on parameterized feature recognition for face detection, a highly complex neural architecture would focus on multitudes of small models that are trained with minute data sets of individuals per model. A standard deep learning “face detection” model could then feed the training of the “face neurons” Layering other types of neural architecture around and within that multitude of models, along with some other neural architecture that generates new “face neurons” to be included in the multitude, would provide both the robustness of deep learning and the determinism of symbolic programming. Each “face neuron” would have an a priori specification of which particular face data was used in its training. One could even imagine further granularity such as “smile neurons”, “chin neurons”, “pimple neurons”, and so on. That is neuro-glial programming, a subset of Parallel Distributed Processing, not neuro-symbolic programming. https://www.igi-global.com/chapter/artificial-neuroglial-networks/10243 https://www.igi-global.com/chapter/artificial-neuroglial-net...
mark_l_watson 5y ago
This seems a little similar to Genetic Programming, from John Koza. In my very old McGraw-Hill book (“C++ Power Paradigms”, McGraw-Hill 1994. Genetic Algorithms, Neural Networks, and Constraint Programming), I had an example using a genetic algorithm for synthesizing a recurrent network. I had lunch with John Koza, he said that it was an interesting idea but that it wouldn’t scale - and he was correct about that.

Anyone here working on program synthesis? I did a little research project as part of an MSc in CS and found it really interesting, but when I looked at industry applications I only found one YC startup working on it in the smart contract space.

yldedly 5y ago
I dabble in it. FlashFill in Excel uses program synthesis, but yeah, not many applications exist yet. Have you seen DreamCoder?
- exdsq 5y ago
  I’ll check it out, thanks!
YeGoblynQueenne 5y ago
I study Inductive Logic Programming (ILP) which is a kind of inductive program synthesis. Inductive program synthesis is learning from partial specifications, where deductive program synthesis is learning from complete specifications (compilation can be seen as a form of deductive program synthesis, for example). ILP studies algorithms that learn logic programs from examples. "Logic programs" as in programs in a language of the Logic Programming paradigm, such as Prolog or Answer Set Programming (ASP). If you're interested in program synthesis, this is the staple modern reference: Program Synthesis https://www.microsoft.com/en-us/research/wp-content/uploads/2017/10/program_synthesis_now.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... For ILP, see this recent review: Inductive logic programming at 30 https://arxiv.org/abs/2102.10556 https://arxiv.org/abs/2102.10556 Or this longer version, here: Inductive logic programming at 30: a new introduction https://arxiv.org/abs/2008.07912 https://arxiv.org/abs/2008.07912 (Both of which ignore my own contributions. Oh well :)
- exdsq 5y ago
  Thank you!! :)
- yldedly 5y ago
  I got a lot out of this course https://people.csail.mit.edu/asolar/SynthesisCourse/ https://people.csail.mit.edu/asolar/SynthesisCourse/ from one of the authors of OP.
  - YeGoblynQueenne 5y ago
    Oh, yes! I should have added that to my links. Thanks!
    - exdsq 5y ago
      So my little project was essentially a research survey on neural program synthesis - do you have any good sources on building program synthesis projects? I noted a lot of the literature talks about outcomes but rarely how I can go about building something small that takes some Input, Output tuples and returns some code. Ended up dropping the MSc because of Covid and moving to the Bay Area but I'd love to eventually do a research-focused masters in the future. Which may be difficult, because I don't have a Bachelors to begin with and took a lot of effort to get onto a Masters in the first place lol!
      - YeGoblynQueenne 5y ago
        You mean resources on creating your own program synthesis system? Hm, I don't know of anything like a program synthesis toolbox, like OpenCV for machine vision, etc. There are many freely available program synthesis systems, but most are research prototypes and they only use a particular approach anyway, while I think you 'd prefer to be able to experiment with different approaches, no? I fear the best option is to try to roll-your-own, based on the descriptions in many different program synthesis papers. Btw, I wouldn't choose neural program synthesis for a first Project! First because neural program synthesis requires as training examples both programming tasks (usually in the form of I/O examples) _and_ programs solving the tasks, and many many of them to boot. Second because it's an uncommon enough approach, or combination of approaches, that I doubt you'll find much support for it in the standard neural net frameworks. I think the CSAIL program synthesis course suggested above by yldedly is a good starting place though. It's graded by a program synthesis project and you might find some tools meant to help students carry out their assignment on the course pages. Or you may try asking the tutors by email even. Other than that, the simples thing to get you started is to define a DSL, generate programs from it and test them against I/O examples of the target programs. That's the simplest, most primitive kind of thing you can do. It's not a very efficient thing to do, but it's a start. The trick is in figuring out how to define the DSL and how to search it efficiently. Good luck, I guess! Feel free to email me if you think I can help. See profile for email. Edit: Here's a blog post about creating a DSL in Python: https://dbader.org/blog/writing-a-dsl-with-python https://dbader.org/blog/writing-a-dsl-with-python

sidpatil 5y ago

If I understand this correctly, this is saying that instead of representing the approximated function as a purely numerical operation (e.g. just a bunch of linear algebra), it can be represented as a program which contains a mixture of typical symbolic syntax and numerical operations. One of the benefits mentioned is better accessibility for existing analysis tools. If I understand the concept correctly, could this also make it easier to implement the approximated functions in environments that lack efficient numerical algorithms and data structures? These two are usually only found in technical computing languages (e.g. FORTRAN, Julia, etc.), or as libraries for a handful of general-purpose languages (e.g. Numpy, Numba, etc.)

blurbleblurble 5y ago

Julia is the perfect language for something like this.

mark_l_watson 5y ago
I agree that something like Julia vs. Python + libraries written in C++ seems like a better fit. However, there is such a vast wealth of tooling around Python, and high level development services like Huggingface, that for the foreseeable future, Python dominates.
- blurbleblurble 5y ago
  Sure, makes sense. The way I see it that Julia's differentiable programming features seem like a really good match for building stuff in this framework.

9wzYQbTYsAIc 5y ago

> In contrast, a neural component is a (typically over-)parameterized, differentiable blackbox function that does not have an a priori specification. > The holy grail for research on neurosym- bolic programming would be a general learning algorithm that could efficiently generate arbitrary combinations of neural components and symbolic code. This is one area where the authors may be missing the point of the parallel distributed processing approach. The authors treat ANN’s as blind guesses from massive training data, but they forget that in most cases the choice of training data is the a priori specification. Additionally, an ANN can be comprised of multitudes of types of artificial neurons. While some learning models are designed to discover relationships between complex data, other learning models are designed for simple data. The simpler the training data, the easier to assign a meaning to the output. Simple back-propagation was followed by the development of deep learning and complex network architectures. The explosion in interest in deep learning is, in part, due to the realization that complex neural architectures can be comprised of a variety of neural components in a variety of ways and that the resulting neural architectures would almost certainly avail us with solutions that span the entirety of possible problems to solve. That is to say, deterministic behavior (“symbolic program synthesis”) could be implemented by an ANN, if the ANN had the required minimum complexity. Since the minimum complexity of such an ANN is currently incomprehensibly high, due to deep learning being in its infancy, there has been a heavy focus on striking results with low complexity. In my view, instead of trying to bring back the zombie of symbolic programming for AI, the authors’ time would be better spent on contributing novel, highly complex neural architectures. For example, some biological neurons in the visual cortex have been shown to be responsive to single individuals faces. If there is one neuron per face, then there could be thousands or more of face neurons in the visual cortex. Where normal deep learning would focus on parameterized feature recognition for face detection, a highly complex neural architecture would focus on multitudes of small models that are trained with minute data sets of individuals per model. A standard deep learning “face detection” model could then feed the training of the “face neurons” Layering other types of neural architecture around and within that multitude of models, along with some other neural architecture that generates new “face neurons” to be included in the multitude, would provide both the robustness of deep learning and the determinism of symbolic programming. Each “face neuron” would have an a priori specification of which particular face data was used in its training. One could even imagine further granularity such as “smile neurons”, “chin neurons”, “pimple neurons”, and so on. That is neuro-glial programming, a subset of Parallel Distributed Processing, not neuro-symbolic programming. https://www.igi-global.com/chapter/artificial-neuroglial-networks/10243 https://www.igi-global.com/chapter/artificial-neuroglial-net...

mark_l_watson 5y ago

This seems a little similar to Genetic Programming, from John Koza. In my very old McGraw-Hill book (“C++ Power Paradigms”, McGraw-Hill 1994. Genetic Algorithms, Neural Networks, and Constraint Programming), I had an example using a genetic algorithm for synthesizing a recurrent network. I had lunch with John Koza, he said that it was an interesting idea but that it wouldn’t scale - and he was correct about that.