Monday 13 Oct 2014: Theories Destroy Facts (as Programs Execute)
Dr Colin Johnson -
Harrison 170 16:00-16:00
The execution of a program can be seen as the gradual replacement of input data with new,
computed data that is more relevant to the problem at hand. At the conclusion of each step
of a successful program's execution, the current state of the program contains more
information about the final, target state of the program (otherwise, why bother calculating it?).
This talk considers the implications of this for machine learning of programs. Genetic programming
and related methods evaluate complete programs on the basis of how good those complete
programs are on a set of training data. I would like to argue that this is not what we should be
doing. Instead, we should be measuring how much problem-specific structure a given program
computes, and that learning should favour those programs that improve the structure of the
I will show how this can be formalised using the idea of Kolmogorov complexity and practically
calculated using information distance metrics based on compression and on information gain.
In particular, this provides a way to assign a fitness measure to program fragments without needing
to embed them in complete programs.
The talk will end with the practical application of these techniques for program synthesis,
fault localisation and bug fixing.