Is there a way to predict unknown function value based on its previous values

Question

I have values returned by unknown function like for example

# this is an easy case - parabolic function
# but in my case function is realy unknown as it is connected to process execution time
[0, 1, 4, 9]

is there a way to predict next value?

Answer 1

You can apply statistical methods to try and guess the next answer, but that might not work very well if the function is like this one (c):

int evil(void){
  static int e = 0;
  if(50 == e++){
    e = e * 100;
  }
  return e;
}

This function will return nice simple increasing numbers then ... BAM.

Answer 2

Not necessarily. Your "parabolic function" might be implemented like this:

def mindscrew
  @nums ||= [0, 1, 4, 9, "cat", "dog", "cheese"]
  @nums.pop
end

You can take a guess, but to predict with certainty is impossible.

Answer 3

Use the Wolfram Alpha API :)

Answer 4

That's a hard problem.

You should check out the recurrence relation equation for special cases where it could be possible such a task.

Answer 5

If you just want data points

Extrapolation of data outside of known points can be estimated, but you need to accept the potential differences are much larger than with interpolation of data between known points. Strictly, both can be arbitrarily inaccurate, as the function could do anything crazy between the known points, even if it is a well-behaved continuous function. And if it isn't well-behaved, all bets are already off ;-p

There are a number of mathematical approaches to this (that have direct application to computer science) - anything from simple linear algebra to things like cubic splines; and everything in between.

If you want the function

Getting esoteric; another interesting model here is genetic programming; by evolving an expression over the known data points it is possible to find a suitably-close approximation. Sometimes it works; sometimes it doesn't. Not the language you were looking for, but Jason Bock shows some C# code that does this in .NET 3.5, here: Evolving LINQ Expressions.

I happen to have his code "to hand" (I've used it in some presentations); with something like a => a * a it will find it almost instantly, but it should (in theory) be able to find virtually any method - but without any defined maximum run length ;-p It is also possible to get into a dead end (evolutionary speaking) where you simply never recover...

Answer 6

Yes. Maybe.

If you have some input and output values, i.e. in your case [0,1,2,3] and [0,1,4,9], you could use response surfaces (basicly function fitting i believe) to 'guess' the actual function (in your case f(x)=x^2). If you let your guessing function be f(x)=c1*x+c2*x^2+c3 there are algorithms that will determine that c1=0, c2=1 and c3=0 given your input and output and given the resulting function you can predict the next value.

Note that most other answers to this question are valid as well. I am just assuming that you want to fit some function to data. In other words, I find your question quite vague, please try to pose your questions as complete as possible!

Answer 7

You can try using neural networks approach. There are pretty many articles you can find by Google query "neural network function approximation". Many books are also available, e.g. this one.

Answer 8

In general, no... unless you know it's a function of a particular form (e.g. polynomial of some degree N) and there is enough information to constrain the function.

e.g. for a more "ordinary" counterexample (see Chuck's answer) for why you can't necessarily assume n^2 w/o knowing it's a quadratic equation, you could have f(n) = n⁴ - 6n³ + 12n² - 6n, which has for n=0,1,2,3,4,5 f(n) = 0,1,4,9,40,145.

If you do know it's a particular form, there are some options... if the form is a linear addition of basis functions (e.g. f(x) = a + b*cos(x) + c*sqrt(x)) then using least-squares can get you the unknown coefficients for the best fit using those basis functions.

Answer 9

See also this question.