Name
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. |
Year | Venue | Keywords |
|---|---|---|
2005 | IJCAI | linear function,complicated function,target function,fitness function,non-uniform domain,pseudo-boolean function,possible approximating function,function g,quadratic function,instance space,probability distribution,probability measure,random variable,pac learning,linear algebra,machine learning |
Field | DocType | Citations |
Probability mass function,Discrete mathematics,Random element,Random variable,Characteristic function (probability theory),Probability distribution,Artificial intelligence,Probability-generating function,Moment-generating function,Machine learning,Mathematics,Random function | Conference | 2 |
PageRank | References | Authors |
0.54 | 6 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Robert F. Lax | 1 | 2 | 0.54 |
| Guoli Ding | 2 | 444 | 51.58 |
| Peter P. Chen | 3 | 1027 | 1122.69 |
| Jianhua Chen | 4 | 2 | 0.87 |