Name
Abstract | ||
|---|---|---|
We consider {0,1}^n as a sample space with a probability measure on it, thus making pseudo-Boolean functions into random variables. We then derive explicit formulas for approximating a pseudo-Boolean random variable by a linear function if the measure is permutation-invariant, and by a function of degree at most k if the measure is a product measure. These formulas generalize results due to Hammer-Holzman and Grabisch-Marichal-Roubens. We also derive a formula for the best faithful linear approximation that extends a result due to Charnes-Golany-Keane-Rousseau concerning generalized Shapley values. We show that a theorem of Hammer-Holzman that states that a pseudo-Boolean function and its best approximation of degree at most k have the same derivatives up to order k does not generalize to this setting for arbitrary probability measures, but does generalize if the probability measure is a product measure. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.dam.2007.08.034 | Discrete Applied Mathematics |
Keywords | Field | DocType |
linear function,faithful linear approximation,generalized shapley value,arbitrary probability measure,pseudo-boolean function,pseudo-boolean random variable,derive explicit formula,probability measure,pseudo inner product,linear approximation,random variable,pseudo-inner product,best approximation,product measure,inner product,shapley value | Probability mass function,Discrete mathematics,σ-finite measure,Random element,Combinatorics,Random variable,Point process,Probability measure,Empirical measure,Mathematics,Random measure | Journal |
Volume | Issue | ISSN |
156 | 10 | Discrete Applied Mathematics |
Citations | PageRank | References |
3 | 0.53 | 4 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guoli Ding | 1 | 444 | 51.58 |
| R. F. Lax | 2 | 45 | 4.05 |
| Jianhua Chen | 3 | 65 | 9.15 |
| Peter P. Chen | 4 | 1027 | 1122.69 |