Body: <p>Backprop is used to train deep neural networks to remarkable success. Deep neural networks, on the other hands, can be seen as as a specific kind of computer function that receives inputs and produces outputs. Suppose, though, that one wanted to train functions in a programming language like Python or Haskell, that solve a specific problem. Due to the discrete nature of these objects, there is obviously no way to apply backprop to generate these. My question is: is there any algorithm that has satisfactory success in the task of training or generating these functions?</p>
  <p>The last time I had this question, I learned about program synthesis, but the field seems to be way behind machine learning, in special due to the lack of satisfactory training procedures. What is the state of the art and where can I find the relevant literature?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-10-27T07:44:15.810Z
Comments.Text: As far as I know, what you call "backtracking" is more commonly termed "back propagation"
Comments.UserDisplayName: David Hoelzer
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-10-27T20:36:38.450Z
Comments.Text: @DavidHoelzer oops, yes! No idea what happened with my brain. Fixed it. Thanks.
Comments.UserDisplayName: MaiaVictor
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-10-27T23:15:56.593Z
Comments.Text: Can you clarify what you mean by "Due to the discrete nature of these objects, there is obviously no way to apply backprop to generate these."  You have a lot of pronouns and it is not clear what they refer to.  Maybe edit your post and give an example of what you mean.  You will get more responses with better posed questions.
Comments.UserDisplayName: Snehal Patel
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-10-28T03:12:52.260Z
Comments.Text: @SnehalPatel since I'm not from the field (as it shows), it is hard to come up with a well-written question; sorry about that. What I mean is that neural networks are basically described as matrices of floating point numbers, so one can adjust the weights to minimize error, perform gradient descent and so on. That's doesn't apply (nor makes sense) when you're trying to optimize something like a λ-term, or a programming language's AST. The lack of such technique to "incrementally improve" is what, I believe, is making me unsure about how I could "train" programs like we train neural nets.
Comments.UserDisplayName: MaiaVictor
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-10-28T09:37:46.350Z
Comments.Text: Like https://arxiv.org/pdf/2206.08896.pdf or https://arxiv.org/pdf/2206.08896.pdf ?
Comments.UserDisplayName: maxy
Tags: <machine-learning><genetic-algorithms><genetic-programming><program-synthesis>
Title: Is there anything remotely as successful as backprop, but for training programs, not neural networks?
UserDisplayName: MaiaVictor
ThreadText: # Is there anything remotely as successful as backprop, but for training programs, not neural networks?
  
  (Asked by: username_0 on 2022-10-27)
  
  Backprop is used to train deep neural networks to remarkable success. Deep neural networks, on the other hands, can be seen as as a specific kind of computer function that receives inputs and produces outputs. Suppose, though, that one wanted to train functions in a programming language like Python or Haskell, that solve a specific problem. Due to the discrete nature of these objects, there is obviously no way to apply backprop to generate these. My question is: is there any algorithm that has satisfactory success in the task of training or generating these functions?
  
  The last time I had this question, I learned about program synthesis, but the field seems to be way behind machine learning, in special due to the lack of satisfactory training procedures. What is the state of the art and where can I find the relevant literature?
  
  **Tags:** machine-learning, genetic-algorithms, genetic-programming, program-synthesis
  > **Comments:**
  > **username_1**: As far as I know, what you call "backtracking" is more commonly termed "back propagation"  
  > **username_0**: @DavidHoelzer oops, yes! No idea what happened with my brain. Fixed it. Thanks.  
  > **username_2**: Can you clarify what you mean by "Due to the discrete nature of these objects, there is obviously no way to apply backprop to generate these."  You have a lot of pronouns and it is not clear what they refer to.  Maybe edit your post and give an example of what you mean.  You will get more responses with better posed questions.  
  > **username_0**: @SnehalPatel since I'm not from the field (as it shows), it is hard to come up with a well-written question; sorry about that. What I mean is that neural networks are basically described as matrices of floating point numbers, so one can adjust the weights to minimize error, perform gradient descent and so on. That's doesn't apply (nor makes sense) when you're trying to optimize something like a λ-term, or a programming language's AST. The lack of such technique to "incrementally improve" is what, I believe, is making me unsure about how I could "train" programs like we train neural nets.  
  > **username_3**: Like https://arxiv.org/pdf/2206.08896.pdf or https://arxiv.org/pdf/2206.08896.pdf ?  
  
  ---
  
  ## 0 answers
  
  