Approximating Pseudo-Boolean Functions on Non-Uniform Domains

1 Introduction

A pseudo-Boolean function of n variables is a function from {0, 1}n to the real numbers. Such functions are used in 0-1 optimization problems, cooperative game theory, multicriteria decision making, and as fitness functions. It is not hard to see that such a function f(x1, . . . , xn) has a unique expression as a multilinear polynomial

∗Research partially supported by NSF grant ITR-0326387 and AFOSR grants F49620-03-1-0238,F49620-03-1-0239, and F4962003-1-0241

where N = {1, . . . , n} and the aT are real numbers. By the degree of a pseudo-Boolean function, we mean the degree of its multilinear polynomial representation.

Several authors have considered the problem of finding the best pseudo-Boolean function of degree ≤ k approximating a given pseudo-Boolean function f , where "best" means a least squares criterion. Hammer and Holzman [Hammer and Holzman, 1992] derived a system of equations for finding such a best degree ≤ k approximation, and gave explicit solutions when k = 1 and k = 2. They proved that such an approximation is characterized as the unique function of degree ≤ k that agrees with f in all average m-th order derivatives for m = 0, 1, . . . , k, in analogy with the Taylor polynomials from calculus. Grabisch, Marichal, and Roubens [Grabisch et al., 2000] solve the system of equations derived by Hammer and Holzman, and give explicit formulas for the coefficients of the best degree ≤ k function. Zhang and Rowe [Zhang and Rowe, 2004] use linear algebra to find the best approximation that lies in a linear subspace of the space of pseudo-Boolean functions; for example, these methods can be used to find the best approximation of degree ≤ k.

Here, instead of simply viewing the domain of a pseudoBoolean function as the set {0, 1}n, we consider {0, 1}n as a discrete sample space and introduce a probability measure on this space. Thus, a pseudo-Boolean function will be a random variable on this sample space. (Viewing {0, 1} simply as a set corresponds to viewing all of its points as equally likely outcomes.) Given a pseudo-Boolean random variable f, we then use methods from linear algebra to find the best approximation to f that lies in a linear subspace, taking into account the weighting of the elements of {0, 1}n. Such a best approximation will then be close to f at the "most likely" n-tuples, and may not be so close to f at the "least likely" n-tuples.

2 Best Approximation on a Non-Uniform Domain

We will identify the integers 0, 1, . . . , 2n - 1 with the elements in Bn via binary representation. Let p(i), i = 0, 1, . . . , 2n - 1, be a probability measure on Bn. Let F denote the space of all pseudo-Boolean functions in n variables. Then F has the structure of a real vector space. Define an inner product 〈 , 〉p on F by We note that 〈f, g〉p is the expected value of the random vari-

able fg. Put ‖ f ‖p= √〈f, f〉p. Now let L be a vector subspace of F of dimension m. For example, L might be the space of all pseudo-Boolean functions of degree at most k, for some fixed k. We recall how to use an orthonormal basis of L to find the best approximation to a given element of F (cf. [Hoffman and Kunze, 1971]).

Given f ∈ F, the "best approximation" to f by functions in L is that function g ∈ L that minimizes

Let v1, . . . , vm be a basis for L. We can find an orthonormal basis u1, . . . , um for L by applying the Gram-Schmidt algorithm. This orthonormal basis satisfies the property 〈ur, us〉p = δrs for r, s = 1, . . . ,m, where δrs equals 0 if r ̸= s and equals 1 if r = s. The orthonormal basis can be obtained as follows: Take u1 = (1/ ‖ v1 ‖p)v1. If u1, . . . , ur-1 have been obtained, then put wr = vr - ∑r-1 j=1 〈vr , uj 〉puj , and take ur = (1/ ‖ wr ‖p)wr.

3 Example

Notice that if we take the uniform distribution on Bn , so that p(i) = (1/2)n for all i, then the best approximation to f in L is the function g ∈ L that also minimizes ∑2n-1 i=0 (f(i) - g(i))2 . This is the usual "least squares" condition used in [Hammer and Holzman, 1992], [Grabisch et al., 2000], [Zhang and Rowe, 2004], and in this case one may simply use the usual Euclidean inner product in R2n . In our more general setting, it follows from section 8.2 of [Hoffman and Kunze, 1971] that the best approximation to f by functions in L is the unique function g = ∑mj=1 〈f, uj 〉puj .

To illustrate these ideas, we look at an example considered by [Zhang and Rowe, 2004]. Take n = 3 and f(x1, x2, x3) = 5x1 + 13x3 + 9x1x2 - 4x1x3 - 4x2x3 + 4x1x2x3. We wish to approximate f by the best linear function, so we let L be the space spanned by the functions v1 = 1, v2 = x1, v3 = x2, v4 = x3. If we take the uniform distribution on B3 , so that p(i) = 1/8 for i = 0, 1, . . . , 7, then by applying the Gram-Schmidt algorithm we get the following orthonormal basis for L with respect to the inner product 〈 , 〉p:

(More generally, one can show that, for any n, an orthonormal basis for the space of pseudo-Boolean functions of degree at most 1 with respect to the uniform distribution is 1, 2x1 - 1, . . . , 2xn - 1.) Then the best linear approximation to f is

in agreement with Example 4.1 of [Zhang and Rowe, 2004]. Here, ‖ f - g ‖p ≈ 2.88.

Now we take a different probability measure on B3 . Supposing that a "1" is twice as likely as a "0" we define a probability measure ˜ p on B3 by ˜ p(0) = 1/27, ˜ p(1) = 2/27, ˜ p(2) = 2/27, ˜ p(3) = 4/27, ˜ p(4) = 2/27, ˜ p(5) = 4/27, ˜ p(6) = 4/27, ˜ p(7) = 8/27. An orthonormal basis for L with respect to the inner product 〈 , 〉˜ p is then

Then the best linear approximation to f is now ˜ g(x1, x2, x3) = ∑4j=1 〈f, ˜ uj 〉 ˜ p˜uj =

Here, ‖ f - ˜ g ‖˜ p ≈ 2.55. For comparison, the distance now between the linear function g we found above and the function f is ‖ f -g ‖˜ p ≈ 2.79.

4 Conclusion

Instead of considering Bn = {0, 1}n simply as a set, we allow it to be viewed as a sample space wth a probability measure p. Then pseudo-Boolean functions are random variables on this sample space. Given a complicated pseudo-Boolean function, it is natural to want to approximate it by a simpler function, for example a linear or quadratic function. As an example, we found the best linear approximation to a given pseudo-Boolean function in three variables with respect to two different probability measures on B3 . Further research is needed to find an effective method of computing the best approximation on a non-uniform domain when the number of variables is large.