×

Best approximations of fitness functions of binary strings. (English) Zbl 1074.68668

Summary: Fitness functions of binary strings (pseudo-boolean functions) can be represented as polynomials over a set of boolean variables. We show that any such function has a unique best approximation in the linear span of any subset of polynomials. For example, there is a unique best linear approximation and a unique best quadratic approximation. The error of an approximation here is root-mean-squared error. If all the details of the function to be approximated are known, then the approximation can be calculated directly. Of more practical importance, we give a method for using sampling to estimate the coefficients of the approximation, and describe its limitations.

MSC:

68W05 Nonnumerical algorithms
68T05 Learning and adaptive systems in artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI