The concept of measure functions for generalization performance
is suggested. This concept provides an alternative way of selecting
and evaluating learned models (classifiers). In addition, it makes
it possible to state a learning problem as a computational problem.
The the known prior (meta-)knowledge about the problem domain is
captured in a measure function that, to each possible combination
of a training set and a classifier, assigns a value describing how
good the classifier is. The computational problem is then to find
a classifier maximizing the measure function.
We argue that measure functions are of
great value for practical applications. Besides of being a tool
for model selection, they: (i) force us to make explicit the relevant
prior knowledge about the learning problem at hand, (ii) provide a
deeper understanding of existing algorithms, and (iii)
help us in the construction of problem-specific algorithms.
We illustrate the last point by suggesting a novel algorithm
based on incremental search for a classifier that optimizes
a given measure function.
Preprint (postscript)
Preprint (pdf)
Journal version