Well this has been a question I have puzzled about for a long time:
Suppose I have a dictionary of input:output like:
-
This
{2: 6, 5: 15, 20: 60, 26: 78, ... 982: 2946, 997: 2991}where
output = input*3. -
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”.
2
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.
1
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.