A Syntactic Approach to Prediction

Citation

Woodward J & Swan J (2011) A Syntactic Approach to Prediction. In: Solomonoff 85th Memorial Conference. Solomonoff 85th Memorial Conference, Melbourne, Australia, 30.11.2011-02.12.2011. tzerland: Springer. http://www.cs.nott.ac.uk/~jrw/publications/prediction.pdf

Abstract
A central question in the empirical sciences is; given a body of data how do we best attempt to make predictions? There are subtle differences between current approaches which include Minimum Message Length (MML) and Solomonoff's theory of induction [24]. The nature of hypothesis spaces is explored and we observe a correlation between the complexity of a function and the frequency with which it is represented. There is not a single best hypothesis, as suggested by Occam's razor (which says prefer the simplest), but a set of functionally equivalent hypotheses. One set of hypotheses is preferred over another set because it is larger, thus giving the impression simpler functions generalize better. The probabilistic weighting of one set of hypotheses is given by the relative size of its equivalence class. We justify Occam's razor by a counting argument over the hypothesis space. Occam's razor contrasts with the No Free Lunch theorems which state that it impossible for one machine learning algorithm to generalize better than any other. No Free Lunch theorems assume a distribution over functions, whereas Occam's razor assumes a distribution over programs.

Keywords
Bias; Conservation of Generalization; Induction; No Free Lunch (NFL);Occam’s Razor; Complexity; Machine Learning; Genetic Programming