# Find how the data has been processed

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)`

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".

• I'd add that this is in general what "regression" is about - finding numerical relationship between two columns of data. Apr 28, 2013 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. Apr 28, 2013 at 17:29

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 ?

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.

• There is no reason to "guess around". This problem is mathematically well-known. Apr 27, 2013 at 9:41

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.