Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Well this has been a question I have puzzled about for a long time:

Suppose I have a dictionary of input:output like:

  1. This

    {2: 6,
     5: 15,
     20: 60,
     26: 78,
     ...
     982: 2946,
     997: 2991}
    

    where output = input*3.

  2. or This

    {0: 5,
     3: 8,
     17: 22,
     19: 24,
     ...
     991: 996,
     996: 1001}
    

    where output = input+5

or something else.
In short where there is a definite relation between input and output.
How can a program find the relation between the input and output, such that, given another input, the output can be calculated??

Is it possible to do the same with more complex calculations like output = 5*((input*5)+3)

share|improve this question
add comment

4 Answers

Mathematically, the problem you describe is to find an unknown function f with

  y_i= f(x_i)   (i=1,...n)

for a given set of input values x_1, x_2, ... and corresponding output values y_1, y_2, ...

To answer such questions, you will typically have to make some assumptions about your function f. For example, if you assume f is a linear function of the form

  f(x) =  a * x + b

(which is true for all 3 examples you gave above), then you can find f by using two input values, solve the related linear equation system of degree 2 for a and b (and test if the other input values match the other output).

If you assume f is a polynomial of a certain degree, that means,

  f(x) =  a_n * x^n  + a_(n-1) * x^(n-1) + ... + a_1 * x + a_0

you need to apply the the theory of polynomial interpolation. A polynomial is what you get when you allow arbitrary summation, subtraction, and multiplication, but no division. This problem is well known and if you choose a high-enough degree n, you can always construct a polynomial f matching all of your input and output values.

One can extend this problem to allow division, which leads to rational function modeling. If you want to know more about that, google for "rational interpolation".

share|improve this answer
    
I'd add that this is in general what "regression" is about - finding numerical relationship between two columns of data. –  rwong Apr 28 '13 at 3:37
    
@rwong: IMHO "regression" is a more general problem, because it allows the function f to approximate the output values (within some error range). "Interpolation" is about finding a function which matches the input/output exactly. –  Doc Brown Apr 28 '13 at 17:29
add comment

It seems like the problem is to find the "simplest" function that fits the data. For example, given 1->2, 2->4, 3->8, 4->16 you could fit a cubic polynomial, but the simplest answer is f(x) = 2^x. This problem can be solved by simply trying all possible functions starting with the simplest: f(x) = 0 and moving to more complex functions. At worst you will find a polynomial function of degree n-1. However, such a brute force search could take a while, and the correct answer is not clear. Suppose you have:

f(1) = 2, f(2) = 6, f(3) = 11. Is a quadratic polynomial more or less complex than 2^x + x ?

share|improve this answer
add comment

I think the only way of doing this is taking 2 number pairs, and doing some basic mathematical operations on them and seeing if they give the same expected output.

Check for the difference between the two, divide the two, etc. Then do the same for the next pair and see if it's a match.

For example (3,8) and (10,15). Difference is 5, then add 5 to the 10 and see whether or not it's a match. If it's not, find another relation to check for.

share|improve this answer
1  
There is no reason to "guess around". This problem is mathematically well-known. –  Doc Brown Apr 27 '13 at 9:41
add comment

The obvious strategy would be to use a linear regression apporach like @DocBrown suggested. If you know the functional form, e.g. a simple linear relationship, getting your answer is rather straightforward. A big complication comes when the functional form is also unknown. Here some kind of optimization is needed to also fit the functional form. This optimization can be done using all kinds of optimizers, e.g. gradient descent, genetic algorithms.

I worked together with some people from Lubljana (Slovenia) who's main research interest is Equation Discovery. They do exactly the kind of things you are looking for, find equations for data that you have available. They find the functional form and the fitted coefficients using machine learning techniques. One additional technique they use is not to fit just one potential model, but a ensemble of possible models. See this link for some details.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.