4 ms·

That’s not entirely correct, as I know of at least one approach to neural program synthesis that employs self supervised learning. https://arxiv.org/abs/2006.0

That’s not entirely correct, as I know of at least one approach to neural program synthesis that employs self supervised learning. https://arxiv.org/abs/2006.08381 https://arxiv.org/abs/2006.08381 It’s a slightly different, easier problem: generating programs based on example outputs, rather than natural language specifications.

YeGoblynQueenne 5y ago
The difference is that DreamCoder has a hand-crafted PCFG [1] that is used to generate programs, rather than a large language model. So the difference is in how programs are generated. ________ [1] The structure of the PCFG is hand-crafted, but the weights are trained during learning in a cycle alternating with neural net training. It's pretty cool actually, thought a bit over-engineered if you ask me.
- bglazer 5y ago
  Right, I think it’s a bit crazy not to use a grammar as part of the generation process when you have one. My guess is that constraining LLM generation with a grammar would make it way more efficient. But that’s more complicated than just throwing GPT3 at all of Github. Also, my understanding is that Dreamcoder does some fancy PL theory stuff to factorize blocks of code with identical behavior into functions. Honestly I think that’s the key advance in the paper, more than the wake-sleep algorithm they focus on. Anyways the point was more that self supervised learning is quite applicable to learning to program. I think the downside is that the model learns its own weird, non-idiomatic conventions, rather than copying github.
  - YeGoblynQueenne 5y ago
    I guess you're right. The sleep-wake cycle is like a kind of roundabout and overcomplicated EM process. I've read the paper carefully but theirs is a complicated approach and I'm not sure what its contributions are exactly. I guess I should read it again. Yes, it's possible to apply self-supervised learning to program synthesis, because it's possible to generate programs. It's possible to generate _infinite_ sets of programs. The problem is that if you make a generator with Universal Turing Machine expressivity, you're left with an intractable search over an infinite search space. And if you don't generate an infinite set of programs, then you 're left with an incomplete search over a space that may not include your target program. In the latter case you need to make sure that your generator can generate the programs you're looking for, which is possible, but it limits the approach to only generating certain kinds of programs. In the end, it's the easiest thing to create a generator for progams that you already know how to write- and no others. How useful is that is an open question. So far no artificial system has ever made an algorithmic contribution, to my knowledge, in the sense of coming up with a new algorithm for a problem for which we don't have good algorithms, or coming up with an algorithm for a problem we can't solve at all. My perception is influenced by my studies, of course, but for me, a more promising approach than the generate-and-test approach exemplified by DreamCoder and AlphaCode etc. is Inductive Programming, which is to say, program synthesis from input-output examples only, without examples of _programs_ (the AlphaCode paper says that is an easier setting but I very disagree). Instead of generating a set of candidate programs and trying to find a program that agrees with the I/O examples, you have an inference procedure that generates _only_ the programs that agree with the I/O examples. In that case you don't need to hand-craft or learn a generator. But you do need to impose an inductive bias on the inference procedure that restricts the hypothesis language, i.e. the form of the programs that can be learned. And then you're back to worrying about infinite vs. incomplete search spaces. But there may be ways around that, ways not available to purely search-based systems. Anyway program synthesis is a tough nut to crack and I don't think that language models can do the job, just like that. The work described in the article above, despite all the fanfare about "reasoning" and "critical thinking" is only preliminary and its results are not all that impressive. At least not yet. We shall see. After all, DeepMind has deep resources and they may yet surprise me.
    - ahgamut 5y ago
      Could you provide some papers/link related to Inductive Logic Programming? I'd like to look at other techniques in this space.
      - YeGoblynQueenne 5y ago
        My pleasure! - First, some more recent work, mostly overviews. 1. The following is the most recent overview of the field I'm aware of: Inductive logic programming at 30 (Cropper et al, 2020) https://www.doc.ic.ac.uk/~shm/Papers/ilp30.pdf https://www.doc.ic.ac.uk/~shm/Papers/ilp30.pdf 2. And a slightly shorter version of the same paper that summarises new trends: Turning 30: New Ideas in Inductive Logic Programming (Cropper et al, 2020) https://www.ijcai.org/Proceedings/2020/0673.pdf https://www.ijcai.org/Proceedings/2020/0673.pdf 3. Here's a short introduction to the relatively new ILP direction of learning Answer Set Programming: Inductive Logic Programming in Answer Set Programming (Corapi et al, 2011) https://link.springer.com/chapter/10.1007/978-3-642-31951-8_12 https://link.springer.com/chapter/10.1007/978-3-642-31951-8_... 4. This is an overview of Meta-Interpretive Learning (MIL), a new approach to ILP that overcomes many difficulties of earlier approaches (Full disclosure: my own work is on MIL, though not the article linked): Meta-Interpretive Learning: achievements and challenges (Stephen Muggleton, 2017) https://www.doc.ic.ac.uk/~shm/Papers/rulemlabs.pdf https://www.doc.ic.ac.uk/~shm/Papers/rulemlabs.pdf 5. And this is a (short vesion) of a paper on δILP, a neural-net based ILP system: Learning Explanatory Rules from Noisy Data (Evans and Grefenstette, 2018) https://www.ijcai.org/Proceedings/2018/0792.pdf https://www.ijcai.org/Proceedings/2018/0792.pdf - Next, some earlier work that is still relevant: 6. This is the inaugural paper of the field, that first named it (a little heavy reading though): Inductive Logic Programming (Stephen Muggleton, 1990) https://www.doc.ic.ac.uk/~shm/Papers/ilp.pdf https://www.doc.ic.ac.uk/~shm/Papers/ilp.pdf 7. Here's an early paper on predicate invention, an important technique in ILP (only recently fully realised via MIL): Predicate Invention in ILP - an Overview (Irene Stahl, 1993) https://link.springer.com/chapter/10.1007%2F3-540-56602-3_144 https://link.springer.com/chapter/10.1007%2F3-540-56602-3_14... 8. And an early overview of learning recursion (and performing predicate invention) that also lists several early ILP systems: Inductive synthesis of recursive logic programs:achievements and prospects (Flener and Yilmaz, 1999) https://core.ac.uk/download/pdf/82810434.pdf https://core.ac.uk/download/pdf/82810434.pdf That should be enough to get you started. I recommend reading in the order I linked to the various articles. I tried to give links to documents that I know can be read for free. Unfortunately most of the material on ILP is either in scholarly articles, or, where there are textbooks, they tend to be older. That sounds bad, but there has been much new work recently with several new approaches. Let me know if you're looking for more specific information. See my signature for contact details- I'm happy to answer emails about ILP :)

YeGoblynQueenne 5y ago

The difference is that DreamCoder has a hand-crafted PCFG [1] that is used to generate programs, rather than a large language model. So the difference is in how programs are generated. ________ [1] The structure of the PCFG is hand-crafted, but the weights are trained during learning in a cycle alternating with neural net training. It's pretty cool actually, thought a bit over-engineered if you ask me.

bglazer 5y ago
Right, I think it’s a bit crazy not to use a grammar as part of the generation process when you have one. My guess is that constraining LLM generation with a grammar would make it way more efficient. But that’s more complicated than just throwing GPT3 at all of Github. Also, my understanding is that Dreamcoder does some fancy PL theory stuff to factorize blocks of code with identical behavior into functions. Honestly I think that’s the key advance in the paper, more than the wake-sleep algorithm they focus on. Anyways the point was more that self supervised learning is quite applicable to learning to program. I think the downside is that the model learns its own weird, non-idiomatic conventions, rather than copying github.
- YeGoblynQueenne 5y ago
  I guess you're right. The sleep-wake cycle is like a kind of roundabout and overcomplicated EM process. I've read the paper carefully but theirs is a complicated approach and I'm not sure what its contributions are exactly. I guess I should read it again. Yes, it's possible to apply self-supervised learning to program synthesis, because it's possible to generate programs. It's possible to generate _infinite_ sets of programs. The problem is that if you make a generator with Universal Turing Machine expressivity, you're left with an intractable search over an infinite search space. And if you don't generate an infinite set of programs, then you 're left with an incomplete search over a space that may not include your target program. In the latter case you need to make sure that your generator can generate the programs you're looking for, which is possible, but it limits the approach to only generating certain kinds of programs. In the end, it's the easiest thing to create a generator for progams that you already know how to write- and no others. How useful is that is an open question. So far no artificial system has ever made an algorithmic contribution, to my knowledge, in the sense of coming up with a new algorithm for a problem for which we don't have good algorithms, or coming up with an algorithm for a problem we can't solve at all. My perception is influenced by my studies, of course, but for me, a more promising approach than the generate-and-test approach exemplified by DreamCoder and AlphaCode etc. is Inductive Programming, which is to say, program synthesis from input-output examples only, without examples of _programs_ (the AlphaCode paper says that is an easier setting but I very disagree). Instead of generating a set of candidate programs and trying to find a program that agrees with the I/O examples, you have an inference procedure that generates _only_ the programs that agree with the I/O examples. In that case you don't need to hand-craft or learn a generator. But you do need to impose an inductive bias on the inference procedure that restricts the hypothesis language, i.e. the form of the programs that can be learned. And then you're back to worrying about infinite vs. incomplete search spaces. But there may be ways around that, ways not available to purely search-based systems. Anyway program synthesis is a tough nut to crack and I don't think that language models can do the job, just like that. The work described in the article above, despite all the fanfare about "reasoning" and "critical thinking" is only preliminary and its results are not all that impressive. At least not yet. We shall see. After all, DeepMind has deep resources and they may yet surprise me.
  - ahgamut 5y ago
    Could you provide some papers/link related to Inductive Logic Programming? I'd like to look at other techniques in this space.
    - YeGoblynQueenne 5y ago
      My pleasure! - First, some more recent work, mostly overviews. 1. The following is the most recent overview of the field I'm aware of: Inductive logic programming at 30 (Cropper et al, 2020) https://www.doc.ic.ac.uk/~shm/Papers/ilp30.pdf https://www.doc.ic.ac.uk/~shm/Papers/ilp30.pdf 2. And a slightly shorter version of the same paper that summarises new trends: Turning 30: New Ideas in Inductive Logic Programming (Cropper et al, 2020) https://www.ijcai.org/Proceedings/2020/0673.pdf https://www.ijcai.org/Proceedings/2020/0673.pdf 3. Here's a short introduction to the relatively new ILP direction of learning Answer Set Programming: Inductive Logic Programming in Answer Set Programming (Corapi et al, 2011) https://link.springer.com/chapter/10.1007/978-3-642-31951-8_12 https://link.springer.com/chapter/10.1007/978-3-642-31951-8_... 4. This is an overview of Meta-Interpretive Learning (MIL), a new approach to ILP that overcomes many difficulties of earlier approaches (Full disclosure: my own work is on MIL, though not the article linked): Meta-Interpretive Learning: achievements and challenges (Stephen Muggleton, 2017) https://www.doc.ic.ac.uk/~shm/Papers/rulemlabs.pdf https://www.doc.ic.ac.uk/~shm/Papers/rulemlabs.pdf 5. And this is a (short vesion) of a paper on δILP, a neural-net based ILP system: Learning Explanatory Rules from Noisy Data (Evans and Grefenstette, 2018) https://www.ijcai.org/Proceedings/2018/0792.pdf https://www.ijcai.org/Proceedings/2018/0792.pdf - Next, some earlier work that is still relevant: 6. This is the inaugural paper of the field, that first named it (a little heavy reading though): Inductive Logic Programming (Stephen Muggleton, 1990) https://www.doc.ic.ac.uk/~shm/Papers/ilp.pdf https://www.doc.ic.ac.uk/~shm/Papers/ilp.pdf 7. Here's an early paper on predicate invention, an important technique in ILP (only recently fully realised via MIL): Predicate Invention in ILP - an Overview (Irene Stahl, 1993) https://link.springer.com/chapter/10.1007%2F3-540-56602-3_144 https://link.springer.com/chapter/10.1007%2F3-540-56602-3_14... 8. And an early overview of learning recursion (and performing predicate invention) that also lists several early ILP systems: Inductive synthesis of recursive logic programs:achievements and prospects (Flener and Yilmaz, 1999) https://core.ac.uk/download/pdf/82810434.pdf https://core.ac.uk/download/pdf/82810434.pdf That should be enough to get you started. I recommend reading in the order I linked to the various articles. I tried to give links to documents that I know can be read for free. Unfortunately most of the material on ILP is either in scholarly articles, or, where there are textbooks, they tend to be older. That sounds bad, but there has been much new work recently with several new approaches. Let me know if you're looking for more specific information. See my signature for contact details- I'm happy to answer emails about ILP :)