# 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.

### 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.