QUESTION: can solve_least_squares be used to do least squares polynomial fitting?

[pfeatherstone]

Can solve_least_squares be used to do polynomial fitting like : https://numpy.org/doc/stable/reference/generated/numpy.polyfit.html https://numpy.org/doc/stable/reference/generated/numpy.polyval.html#numpy.polyval ?

[pfeatherstone]

There is an analytical solution to polynomial fitting, so the concept of having to provide a stop_strategy_type object doesn't seem right.

[davisking]

Yeah you should just use a linear solver if you want to do ols fits of polynomials.

[pfeatherstone]

This works fine:

dlib::matrix<float> dlib_polyfit(const vector<float>& x, const vector<float>& y, int order)
{
    DLIB_ASSERT(x.size() == y.size(), "bad input sizes. x and y must have matching sizes.");

    /*setup state*/
    dlib::matrix<float> Y = dlib::mat(y);
    dlib::matrix<float> X(x.size(),order+1);
    dlib::matrix<float> x_mat = dlib::mat(x);
    dlib::set_colm(X,0) = 1;
    for (int i = 1 ; i <= order ; i++)
        dlib::set_colm(X,i) = dlib::pointwise_multiply(dlib::colm(X,i-1),x_mat);

    dlib::matrix<float> X_t = dlib::trans(X);
    dlib::matrix<float> B = dlib::inv(X_t*X)*X_t*Y;

    DLIB_ASSERT(B.nr() == (order+1) && B.nc() == 1);
    return B;
}

float dlib_polyval(const dlib::matrix<float>& B, float x_hat)
{
    dlib::matrix<float,1,0> X(B.nr());
    X(0) = 1;
    for (long i = 1 ; i < B.nr() ; i++)
        X(i) = X(i-1)*x_hat;
    dlib::matrix<float> Y = X*B;
    DLIB_ASSERT(Y.size() == 1);
    return Y(0);
}

[pfeatherstone]

These functions, give or take some refactorisation, might be useful additions to dlib. @davisking, what do you think?

[davisking]

There are already a bunch of regression methods in dlib (like http://dlib.net/ml.html#rr_trainer) that do this sort of thing. It's not clear to me that anyone would use this if it was in dlib when there are the other options. And like, if I was going to add something specifically for regressing 1D functions to scalars I would add something that fits a piecewise linear interpolator or some kind of spline. That would be cool. But polynomial regression isn't really very general and often gives bad results. That's not to say I haven't used polynomial regression in real applications, but it was always in a specialized context.

As an aside, you don't and generally shouldn't make named temporaries with dlib::matrix. It's unneeded and might make you lose out on optimization opportunities. Like just do inv(trans(X)*X)*trans(X)*Y. It's definitely going to run faster than what you put there. Dlib's matrix is also not like Eigen. I realize that in Eigen you have to make lots of temporaries because Eigen fails to handle aliasing and will give incorrect results. However, dlib::matrix will always do the right thing.

[pfeatherstone]

Thanks for the comments. Would you say using rr_trainer is useful if you only have 10 samples ? It looks like rr_trainer adds a regularisation term.

[pfeatherstone]

So here is some context for what I'm doing. I'm currently doing some object tracking-by-detection. I have an object detector that spits out fresh, untracked, detections on each frame. I have an object tracker that uses max_cost_assignment with a CIOU cost function that matches tracklet predictions with fresh detections. For each matched tracklet/detection pair, the detection is assigned the tracklet's tracking number and the tracklet is updated with the detection. For unmatched detections, new tracklets are created. When a tracklet reaches a certain number of iterations without having been updated with a detection, it is removed from the buffer of tracklets. This is roughly how SORT and deepSORT work, and how i imagine other trackers work too. I've been experimenting with different types of tracklets. I have tried correlation_tracker from dlib. I have tried a kalman filter based tracklet using both opencv and dlib (they give roughly the same results). I have tried all the trackers from opencv (MIL, KCF, BOOSTING, etc). They all work fine to be honest. But i want to try other things too. Now i'm trying some polynomial regression. So if each tracklet cyclically buffers the last 10 detections say, i can use quadratic regression to predict the next detection. I'm tracking still objects, captured from a moving camera. So still objects move quadratically (roughly) within the camera frame, hence why polynomial regression seemed like a good idea to try. And indeed it all works. BUT, i was using liquid-dsp, a fantastic DSP library, which has polyfit and polyval functions. Since i'm using dlib anyway, i thought i could have 1 less dependency by defining polyfit and polyval in dlib.

Now that you mention rr_trainer, there are many other algorithms in dlib i could try. krls comes to mind to.

[pfeatherstone]

I also saw that you have a "learning to track" tutorial. But that requires training data, which I do not have. Otherwise that would have been oven baked ready to use.

[davisking]

Thanks for the comments. Would you say using rr_trainer is useful if you only have 10 samples ? It looks like rr_trainer adds a regularisation term.

Yes, it's useful when you have less data. The regularization goes a long way. It's also useful even when you have a lot of data.

[davisking]

To predict the next state of a track I would honestly use a Kalman filter (or an extended Kalman filter if you believe your motion dynamics require it). A Kalman filter is an unassailable formalism in a lot of cases.

[pfeatherstone]

OK using rr_trainer works. It's not obviously better than traditional polynomial fitting in my tests.

[pfeatherstone]

krls also works. Not necessarily better than rr_trainer, polyfit or kalman.

[pfeatherstone]

The best so far is correlation_tracker, but much more computationally expensive. Anyway, this is a tangent.