I have an online learning problem where every second (say) I receive a new observation $(x_1,x_2,y)$. I'd like to fit the following models: $$ y = f(x_1) + f(x_2)$$ and maybe $$ y = f(x_1,x_2) $$

In an offline setting I would simply run the data through R npreg package or the gam function. Those methods however are offline methods that compute the model once. Whenever a new datum shows up I need to recompute the whole regression all over again.

This is very wasteful and I was hoping I could compute a simple non-parametric regression the same way I use recursive least squares filters for the parametric case (which predicts very poorly in this case).

  • 1
    $\begingroup$ Kernel smoothing regression techniques don't need to do anything to add a data point; the work is all at prediction time (except in choosing a bandwidth, but you can probably do that much less frequently). Do you need to keep a current set of estimates on some test points, or are you just asking about code to accomplish keeping the predictive model up to date so that test points can be predicted on at any time (which is probably off-topic here)? $\endgroup$ – Danica Apr 2 '16 at 9:07
  • $\begingroup$ Yes, sorry about the terseness, I tried to keep the question short. Yes I have a set of fixed test points I need to update and unfortunately they are a lot (about 2000) $\endgroup$ – CarrKnight Apr 2 '16 at 9:23
  • $\begingroup$ The gam() function in mgcv lets you provide initial estimates for the regression coefficients and for the smoothing parameters (see ?gam and ?gam.fit). Every time you get a new observation you could re-estimate, using the old estimates as starting point. Maybe the resulting speed-up is sufficient for your application. It might even make sense fixing the smoothing parameters entirely, given that it takes several fits to estimate them, and that they are unlikely to change much if few data points are added. $\endgroup$ – Matteo Fasiolo Apr 2 '16 at 9:39
  • $\begingroup$ Do you have a fixed bandwidth as you add points? npreg would change bandwidth as you added points $\endgroup$ – Glen_b Apr 2 '16 at 11:35
  • $\begingroup$ I will try the gam trick of feeding it old parameters, but I want to give it a proper treatment and look through the code. @Glen_b I don't mind having a non-optimal predictor as long as its fast. I made peace with the idea of non optimizing the bandwith as I go. I am fine even with nearest neighbor regression if there was a fast way to compute confidence intervals of the predictor $\endgroup$ – CarrKnight Apr 2 '16 at 17:43

Turns out there is a way to do this with Kernel regressions.
Assuming your fixed test point is $x$, rather than computing every time the prediction at that point through the usual Kernel regression formula we can do the following:

$m_0(x) = g_0(x)=0$
$g_n(x) = g_{n-1}(x) + K_h(x-X_n)$
$m_n(x) = m_{n-1} + \frac{ \left(Y_n - m_{n-1}(x) \right) K_{h}(x-X_n)}{g_n(x)}$

Where $m_n(\cdot)$ is the prediction after $n$ observations, $(Y_n,X_n)$ is the new observation and $g_n(\cdot)$ is just the running denominator.

This comes from:
Krzyzak, Adam. "Global convergence of the recursive kernel regression estimates with applications in classification and nonlinear system estimation." IEEE Transactions on Information Theory 38.4 (1992): 1323-1338.


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.