Fitting a feedback loop to data points

Question

If you want to fit a polynomial to a set of data points, there are many options available including least squares fitting, gradient descent, and lagrange interpolation.

However, thinking in more programmer / computer science terms, let's say that I had something more like a pseudo random number generator where it had some internal state, and when you ran a function, it would do an operation, update the internal state and spit out a new value. (Note, I'm not trying to make a prng, just using it as an example of the type of function I'd like to fit to my data)

Are there any methods other than brute force for creating (or iteratively training, ala gradient descent) a system like that to give something close to a specific sequence of desired output values?

For example, a simple feedback function may look something like this in C++:

float SequenceGenerator()
{
    // internal storage
    static float internalState = 16.371f;

    // adjust the internal storage
    internalState += internalState * 83.12f;

    // keep the internal storage <= 100
    while(internalState > 100.0f)
        internalState -= 100.0f;

    // return the next value in the sequence
    return internalState;
}

I definitely see how i could choose some random value for the initial values for the starting state, and the multiplication amount. I can also see how I could compare the values that come out to my sequence and come up with something like a mean squared error.

I'm not sure however, how I might be able to do something like calculate a gradient to adjust those values to iteratively minimize the mean squared error.

Is there a way to do something like this?

(I can't seem to find appropriate tags other than PRNG, please let me know if there are better tags or feel free to edit)

Answer 1

This is probably an awful approach to fitting points and prediction.

There's no reason to expect that a PRNG will do a good job at fitting points. Interpolation is effective because we think that not all curves are equally likely. Some kind of Occam's razor applies: all else being equal, the "simpler" the curve, the more likely that it is as a plausible model.

Thus, linear regression is useful precisely because not all curve shapes are possible; only straight lines. Empirically, straight lines occur more often than crazy-wiggly shapes. Similarly, polynomial regression is useful because a low-order polynomial is more likely than a high-order polynomial.

Now consider the following approach: try to fit the data you already have to an arbitrary function (with no restrictions on the function or the shape of the curve; all functions are valid/legal models). Well, that'll be an absolutely terrible approach at prediction. You'll be able to find a function that exactly fits all of the data you already have, but (most likely) it will be absolutely useless at predicting values you haven't seen -- it'll be absolutely useless at generalization / prediction. Essentially, you'll have massively overfitted the data set.

Now a PRNG is designed to behave like a true-random generator. In other words, all sequences of outputs are supposed to be equally likely (or, at least, you can't tell the difference). Fitting your data to a true-random generator will be useless at prediction/generalization. For the same reason, fitting your data to a PRNG is likely to be useless at prediction/generalization.

You should probably read about the "no free lunch" theorems for machine learning and prediction: https://en.wikipedia.org/wiki/No_free_lunch_theorem, http://www.aihorizon.com/essays/generalai/no_free_lunch_machine_learning.htm, http://no-free-lunch.org/. To be effective at prediction, the learning technique must embed some bias about what hypotheses/models are more likely. A true-random generator has no bias and thus is useless. A PRNG behaves like a true-random generator and thus will probably be useless (or, to the extent it has bias, its bias is towards distributions that are very unlikely to appear in nature).