Machine Learning for Programming
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.
- 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
- Gradient Descent
- Neural Networks
- Find a function, f, to minimize error on examples, and generalization (previously unseen) erro.
- Linear regression: calculate exact answers(Gauss)
- For linear functions => minimization function is convex
- Non-linear functions => surface is more complicated
- 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.