Machine Learning for Programming

home · about · subscribe

Peter Norvig presented a great overview how programming could use more machine learning. He presented quite nice overview of what has been done in research and what could be possible. Generally, the presentation followed a question-answer style where he first presented the question and then try to give answer by providing additional context. I liked this format a lot. It is both easy to follow and also easy to build the solution step by step.

What is programming?

• Given a specification of a function f
• Implement f that meets the specification

What is Machine Learning?

• Given some example (x, y) pairs
• Induce f such that y=f(x) for given pairs, and generalizes well for unseen x.

Questions & Answers

Q: Can we learn functions from examples?
A: Yes, for many kinds of functions.

Q: Can we learn parts of programs from examples?
A: Yes, machine learning is the ultimate agile programming.

Program Induction

• 1980s: Logical Functional Languages
• 2000s: Probabilistic search rather than logical
• 2010s: Deep, LSTM: intermediate representations
• TOOWTDI languages
• Only one of “a+1” or “1+a” is allowed
• Stranger type systems
• Total functional programming: only allow recursion that probably terminates
• DSLs, such as regular expressions

Q: Can we learn entire programs from examples?
A: Yes, for short programs; no, for complex programs

Mini Lesson in ML

• Regression
• Gradient Descent
• Neural Networks

Regression

• Find a function, f, to minimize error on examples, and generalization (previously unseen) erro.
• $f =min_f Loss(f)$
• $Loss(f) = EmpiricalLoss(f) + GeneralizeLoss(f)$
• $Empiricalloss(f) = \sum_i (y_i - f(x_i))^2$
• Linear regression: calculate exact answers(Gauss)

Gradient Descent

• For linear functions => minimization function is convex
• Non-linear functions => surface is more complicated

Neural Network

• Has nothing to do with Neural
• Sums + Products + Squashing Function (complicated function to optimize)

Q: Can we learn complex non-traditional programs from examples?
A: Not yet, maybe someday.

Q: Can we learn to optimize programs?
A: Yes, short parts.

Q: Can we learn to efficiently execute declarative programs?
A: Maybe. So far, not done via learning. Need help with languages.

Declarative Languages for AI/ML Applications

• DYNA(Jason Eisner)
  • Probabilistic Context Free Parser
  • A single word is a phrase(given an appropriate grammar rule)
  • phrase(X, I, J) += rewrite(X, W) * word(W, I, J)
• Probabilistic(Relational Languages: any variables can be input or output)

Q: Can we learn an interpreter?
A: Partly, that is not the point.

Q: Can we learn a user’s language?
A: Interesting idea, but so far done by hand.

Q: Can we learn tutoring feedback from examples?
A: Yes! Works better as a human/machine partnership.