Paper:

# Asymptotic Behavior of Linear Approximations of Pseudo-Boolean Functions

## Guoli Ding^{*}, Robert F. Lax^{*}, Peter Chen^{**},

and Jianhua Chen^{**}

^{*}Department of Mathematics, Louisiana State University, Baton Rouge, LA 70803, USA

^{**}Department of Computer Science, Louisiana State University, Baton Rouge, LA 70803, USA

*k*>1 where

*k*is independent of the number of Boolean variables, the best linear approximating function works better than simply using the linear part of the target function. We also study the behavior of the expected best linear approximating function when the target pseudo-Boolean function to be approximated is random.

*J. Adv. Comput. Intell. Intell. Inform.*, Vol.11 No.4, pp. 403-409, 2007.

- [1] A. T. Bharucha-Reid and M. Sambandham, “Random Polynomials,” Academic Press, 1986.
- [2] E. Boros and P. L. Hammer, “Pseudo-Boolean Optimization,” Discrete Appl. Math., 123 (1-3), pp. 155-225, 2002.
- [3] G. Ding, J. Chen, R. Lax, and P. Chen, “Efficient learning of pseudo-boolean functions from limited training data,” Foundations of Intelligent Systems: 15th International Symposium, ISMIS 2005, Lect. Notes in Comp. Sci. 3488 (Springer, 2005), pp. 323-331.
- [4] H. E. Dixon and M. L. Ginsberg, “Inference methods for a pseudo-Boolean satisfiability solver,” Proc. of American Association of AI Conference, 2002.
- [5] P. H. Giang and P. P. Shenoy, “A Qualitative Linear Utility Theory for Spohn’s Theory of Epistemic Beliefs,” Proceedings of Int. Conference on Uncertainty in AI, San Francisco, CA, pp. 220-229, 2000.
- [6] P. L. Hammer and R. Holzman, “Approximations of Pseudo-Boolean Functions; Applications to Game Theory,” ZOR – Methods and Models of Operations Research, 36, pp. 3-21, 1992.
- [7] R. Herbrich and T. Graepel, “Bayes Point Machines,” Journal of Machine Learning Research, 1, pp. 245-279, 2001.
- [8] Y. Jin, “A Comprehensive Survey of Fitness Approximation in Evolutionary Computation,” Soft Computing, 9, pp. 3-12, 2005.
- [9] R. Khardon, D. Roth, and L. G. Valiant, “Relational Learning for NLP using Linear Threshold Elements,” Proceedings of Int. Joint Conference on AI (IJCAI’99), Aug., 1999.
- [10] R. Lax, G. Ding, P. Chen, and J. Chen, “Approximating Pseudo-Boolean Functions on Non-uniform Domains,” Proceedings of IJCAI-05, pp. 1754-1755, 2005.
- [11] L. Liu, C. Shenoy, and P. P. Shenoy, “A Linear Belief Function Approach to Portfolio Evaluation,” Proceedings of Int. Conference on Uncertainty in AI, San Francisco, CA, pp. 370-377, 2003.
- [12] V. M. Manquinho and J. Marques-Silva, “Integration of Lower Bound Estimates in Pseudo-Boolean Optimization,” Proc. of IEEE Int. Conference on Tools with AI, 2004.
- [13] S. Prestwich and C. Quirke, “Boolean and Pseudo-Boolean Models for Scheduling,” Proc. of Second International Workshop on Modeling and Reformulating Constraint Satisfaction Problems, 2003.
- [14] L. A. Zadeh and J. Kacprzyk (Eds.), “Fuzzy Logic for the Management of Uncertainty,” John Wiley & Sons, 1992.
- [15] H. Zhang and J. E. Rowe, “Best Approximations of Fitness Functions of Binary Strings,” Natural Computing, 3, pp. 113-124, 2004.

This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.