How to best approach the problem of trying to determine the form of an unknown function

Question

I have a set of variables X, Y, ..., Z. My job is to design a function that takes this set of variables and yields an integer. I have a fitness function to test this against.

My first stab at the problem is to assume that I can model f to be a linear function:

f(X, Y, ..., Z) -> aX + bY ... cZ

My first idea was to use either PSO (Particle Swarm Optimization) or Genetic algorithms to solve f for a, b, .., c and I am sure they'd sure yield good results.

On the other hand, I feel like maybe that kind of evolutionary algorithms aren't really needed. First of all, I can think of a couple of good "starting points" for a,b, .., c. Being f a linear function, shouldn't it be easier to just try out a couple of points and then do something like a linear regression to them? And after the linear regression, trying out a couple more points, this time closer to what looks like a good "spot", making again a linear regression on them?

What are the downsides of it? Anyone with experience in these kind of problems? The biggest one I can think of is that maybe what I consider good starting values for a,b, .., c may be a "local optima", and having some kind of evolutionary algorithm would yield me a global one.

f is supposed to be a approximation function for the Minimax algorithm of a Chess-like game, if that matters.

Thanks

Answer 1

Given that you're working on a game, the first thing that comes to mind is an ancient program for playing checkers, developed by Arthur Samuel in the 1950s and mentioned by Russell and Norvig in their chapter on game playing (among others; it's still a classic in unsupervised/semi-supervised machine learning).

This program assumed that the value of a checkers board was a linear function of the board position. I don't know the details, but I assume each of the player's pieces was worth +1, the opponent's pieces -1, and empty fields 0. Each square had a weight associated with it, which was learned by letting the program play against itself some (large) number of times, evaluating play after every match.

This strategy is called self-training and was also applied in the classic backgammon software TD-Gammon, which is based on neural networks (multi-layer/non-linear ones). The Wikipedia page about that program has some potentially interesting references.

This answer is turning into an essay about something at which I'm not an expert. Please see the relevant literature.

Answer 2

If I understand your question, you have a function which takes input, then serves up some output, which is supposed to be related to an approximation function for a chess-like game and you are supposed to guess how it calculates the output.

You didn't state what the input variables are so I have no way of telling what the domains are for each of them, but the general strategy is to keep all of the inputs the same, and iterate for all values in the domain of exactly one variable. Repeat for all inputs and use the resulting data set to guide your next set of tests. Its very possible that actual method used by the function is something absolutely asinine which could not reasonably be reproduced without mapping every input to a to every output.

Answer 3

You are describing a regression problem, this is a classic machine learning problem. There are thousands of scientific papers and entire textbooks written about only this topic. I would suggest taking a look at some machine learning classes online or check out a standard machine learning text.

The general approach is similar to what you have mentioned, solving for linear coefficients on the variables to minimize some loss usually sum of squared errors (L2 Loss). This is desirable because it is a convex function and therefore contains a single minimum and the weights can be solved for in polynomial time. However, like you mentioned the true function may not lie in this function class and you will have a poor estimate. The approach in this case is not to try some sort of non-convex optimization with some obscure particle swarm methods or genetic algorithms or whatever other global optimization technique. Your statement "... may be a "local optima", and having some kind of evolutionary algorithm would yield me a global one." is a naive one. Global optimization is NP-Hard, these techniques are only approximations and carry absolutely no guarantees regarding run time or optimality, and they almost never work.

A much more accepted approach is to use "feature expansion" which takes your variables X, Y, ..., Z and applies a nonlinear transformation to some new set phi(X), phi(Y), ..., phi(Z). At this point you can find an optimal linear weighting for each feature with least squares (if you use L2) or whatever. How to find good features is an open problem in machine learning but there are boatloads of ideas and freely available algorithms to do this.