fit to data

Can you clairify what you mean by "integer data" and "equation generator"?

Curve fitting typically involves a set of known or measured data points (x, y) and the desire to find a relationship of the form y = f(x) or y = g(t), x = h(t) where t is some other variable.

Usually one has some initial knowledge about the shape of the curve to be fit. For example, right now I'm working on extracting rate contants that appear in a set of differential equations from a series of measured data points.

Or are you trying to randomly generate the relationships themselves, rather than fit to a set of known data points? A simple example of this would be to start with a general equation, and generate some constants to determine its exact form, and then generate y values for a set of fixed or known x values.

For example, I could assume the relationship is y = Ax^2 + Bx + C, then randomly generate A, B and C, and then generate values of y for x = 1, 2, 3, 4, 5.

What exactly are you trying to do?

The equation generator takes a list of possible inputs and outputs and finds an equation that satisfies those outputs with those inputs and/or additional constants. What i meant by integers is that i'm using 32 bit integers and the operators AND, OR, XOR, +, -, left shift, and right shift. No floating point math or multiplication/division is used.

I realize that "fit to data" usually refers to fitting a curve to a list of points, but it was the closest term i could use to describe what i'm trying to do. The data i'm using may or may not fit a curve.

You're probably going to have to give an example problem and solution. The description is still too vague or incomplete to understand what you're trying to describe without a lot of guessing to fill in the blanks...

However, you might be describing a more general case of the Subset Sum Problem.

edit: Yes, the subset sum problem does look to be related, i'll look into it to see if i can relate it to my problem.

An example:

"input" is a 2 dimensional array of variables that the resulting equation will receive as arguments. "output" is an array of the desired outputs for the equation, given the inputs.

The array index for input corresponds with the array index for output, so if the equation was given arguments input[5][0] and input[5][1], it should ouput output[5]. The input array can have any number of sub elements, in this case it has 2. The ouput array only has 1 sub element, since there should only be 1 answer for given inputs.



The "generate_equation()" function should output the equation, "input[0]+input[1]+1=output", in some form or another. Using fibonacci numbers was just an example in this case, any numbers may be used. The input array could have any number of sub elements, and the resulting equation may have any number of operands, constants, and uses of the input array, though bounds can be placed on any them if need be.

Basically, i have inputs and outputs, but no equation that can relate the inputs to the outputs. The job of the equation generator is to find the equation that relates them.

Genetic Programming all the way.

Funny pattern recognition problem.
There might be an infinite number of solutions, too.

If you limit yourself to a certain model, like a polynome, you can use different regression methods. Like using the a linear model:

ax+by+c = z;

you can use regression to find a, b, and c that solve the equation for all your (x,y,z) triplets.

If you dont want to limit you to a certain model, some kind of search is your best chance, but I dont see any good heuristic for that.

I remember I did something similar, thought yours looks simpler.

I had fa(a,b,c,d,e,f) -> some module -> (a?, b?, c?)
and group (a?,b?,c?) could be validated only through one way hash function.

Of course simple solution with breath first actually worked because I was interested by computationally least intensive solution. (Actually it worked after infusion of dot product, forcing your weak AI to reinvent dot product because you were lazy is bad idea.)

Your problem would be probably simplier, if you know the order of numbers beforehand. Try to test subchains for validity, it might save some computing power.

5 & 5 & 5 = 5
5 - 5 + 5 = 5

So be prepared for multiple correct solutions, that would break in real live situation. BTW if you plan to get some "real" world data, be prepared for soft tests, because quite a lot of real world data is malformed.

And one more thing, do you mean SAR by bitshift to the right? All CPUs are able to do SHR as well. ((int)-1 SAR 1 = -1, (int)-1 SHR 1 = INT32.MAX_NUMBER)

Rockoon1, genetic programming seems like the best option so far, though it's going to be more involving than "just" an equation generator.

Steadtler, there would be constraints placed on the number of possible operators, constants, etc so there wouldn't be infinite possibilities.

Raghar, my current brute force methods precomputes sections of the equation being tested, though it's still very slow. I meant SHR (unsigned shift).

Quote:

Original post by flounder Steadtler, there would be constraints placed on the number of possible operators, constants, etc so there wouldn't be infinite possibilities.

Thats no guaranty of a single solution, tho.

Quote:

Original post by flounder Rockoon1, genetic programming seems like the best option so far, though it's going to be more involving than "just" an equation generator.

Well thats the nice thing about genetic programming, its more than just an equation generator. It is probably not the "best" way to attack this sort of problem, but its right up there in good company.

Quote:

Original post by flounder Raghar, my current brute force methods precomputes sections of the equation being tested, though it's still very slow. I meant SHR (unsigned shift).

I can imagine that. brute force searching the space of even short equation lengths can be computationally irretractable.