Machine Learning Newsletter

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


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

comments powered by Disqus