---
title: "Approximating Pseudo-Boolean Functions on Non-Uniform Domains"
authors:
  - "Robert F. Lax"
  - "Guoli Ding"
  - "Peter P. Chen"
  - "Jianhua Chen"
doi: ""
url: "https://ijcai.org/proceedings/2005/256"
pdf: "https://ijcai.org/proceedings/2005/0256.pdf"
venue: "Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence"
year: 2005
pages: "1754-1754"
track: ""
keywords:
---

# Approximating Pseudo-Boolean Functions on Non-Uniform Domains

Robert F. Lax, Guoli Ding, Peter P. Chen, Jianhua Chen

*Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence*, pages 1754-1754.

## Abstract

In Machine Learning (ML) and Evolutionary Computation (EC), it is often beneficial to approximate a complicated function by a simpler one, such as a linear or quadratic function, for computational efficiency or feasibility reasons (cf. [Jin, 2005]). A complicated function (the target function in ML or the fitness function in EC) may require an exponential amount of computation to learn/evaluate, and thus approximations by simpler functions are needed. We consider the problem of approximating pseudo-Boolean functions by simpler (e.g., linear) functions when the instance space is associated with a probability distribution. We consider {0, 1}n as a sample space with a (possibly nonuniform) probability measure on it, thus making pseudo-Boolean functions into random variables. This is also in the spirit of the PAC learning framework of Valiant [Valiant, 1984] where the instance space has a probability distribution on it. The best approximation to a target function f is then defined as the function g (from all possible approximating functions of the simpler form) that minimizes the expected distance to f . In an example, we use methods from linear algebra to find, in this more general setting, the best approximation to a given pseudo-Boolean function by a linear function.