2
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Fwiw I'm not trying to make a prng. I'm trying to figure out if there are any good methods for making a stateful/recurrent type of function that gives something closeish to a specific sequence. Yes, it might need a lot of internal storage. Think more like I'm trying to make an IIR filter that gives some specific output sequence when given an impulse. $\endgroup$ – Alan Wolfe Mar 1 '17 at 2:46
  • $\begingroup$ @AlanWolfe, I understand that you're not trying to make a PRNG. It sounds like you are trying to use a PRNG for curve-fitting. That's what my answer is addressing. I think it's relevant to what you are asking, especially the no-free-lunch theorem. If you're trying to construct an IIR filter with certain properties, doing this by trying to match it to the output of a PRNG is not likely to be the best approach -- sounds like an XY problem. Also, have you read about time series analysis, recurrent neural networks, etc.? $\endgroup$ – D.W. Mar 1 '17 at 3:13
  • $\begingroup$ I'm trying to fit data points by having a stateful function, not a polynomial type setup. Do you know of any techniques for doing so? I thank you for the advice that you think it's an xy problem and that it's a bad way to do what you think I'm doing, but I'm really just trying to get info about any known techniques for doing this, what I asked about. Know any? $\endgroup$ – Alan Wolfe Mar 1 '17 at 3:19
  • $\begingroup$ @AlanWolfe, I still don't understand what you're actually trying to accomplish, so I don't know how to answer that. I suspect the PRNG part is irrelevant and you just want to fit a stateful function, but I can't tell. And, again, I suggest reading about recurrent neural networks. $\endgroup$ – D.W. Mar 1 '17 at 7:12
  • $\begingroup$ Thanks DW. RNNs are actually the reason I'm asking hehe. The RNN's I've seen all work more like FIRs, where you have N layers for N previous data points. It made me wonder how a stateful RNN that worked more like an IIR might work, but I'm trying to find out how fitting an IIR to a data set can work first. I know you can design IIR's to have poles and zeros and such to control frequency response, but I haven't yet found information on how you would eg make an IIR that generated a sequence, even if it did so imperfectly with a lot of internal state. $\endgroup$ – Alan Wolfe Mar 1 '17 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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