Genetic programming with guaranteed quality

When using genetic programming (GP) or other techniques that try to approximate unknown functions, the principle of Occam's razor is of-ten applied: nd the simplest func-tion that explains the given data, as it is assumed to be the best ap-proximation for the unknown func-tion. Using a well-known result from learning theory, it is shown in this paper, how Occam's razor can help GP in nding functions, so that the number of functions that dier from the unknown func-tion by more than a certain degree can be bounded theoretically. Ex-periments show how these bounds can be used to get guaranteed qual-ity assurances for practical applica-tions, even though they are much too conservative.