Rekursiver (online) regularisierter Algorithmus der kleinsten Quadrate

Kann mich jemand auf einen (rekursiven) Online-Algorithmus für die Tikhonov-Regularisierung (regularisierte kleinste Quadrate) hinweisen?

In einer Offline-Einstellung würde ich Verwendung meines ursprünglichen Datensatzes berechnen, wobei unter Verwendung der n-fachen Kreuzvalidierung gefunden wird. Ein neuer Wert kann für ein gegebenes x mit y = x ^ T \ hat \ beta vorhergesagt werden .λyxy=xT$\hat\beta=(X^TX+λI)^{−1}X^TY$$λ$$y$$x$$y=x^T\hat\beta$

In einer Online-Umgebung zeichne ich ständig neue Datenpunkte. Wie kann ich updaten?$\hat\beta$ wenn ich neue zusätzliche Datenmuster zeichne, ohne eine vollständige Neuberechnung des gesamten Datensatzes durchzuführen (Original + Neu)?

$\hat\beta_n=(XX^T+λI)^{−1} \sum\limits_{i=0}^{n-1} x_iy_i$

Sei$M_n^{-1} = (XX^T+λI)^{−1}$ , dann

$\hat\beta_{n+1}=M_{n+1}^{−1} (\sum\limits_{i=0}^{n-1} x_iy_i + x_ny_n)$ und

$M_{n+1} - M_n = x_nx_n^T$ , wir können bekommen

$\hat\beta_{n+1}=\hat\beta_{n}+M_{n+1}^{−1} x_n(y_n - x_n^T\hat\beta_{n})$

Nach der Woodbury-Formel haben wir

$M_{n+1}^{-1} = M_{n}^{-1} - \frac{M_{n}^{-1}x_nx_n^TM_{n}^{-1}}{(1+x_n^TM_n^{-1}x_n)}$

As a result,

$\hat\beta_{n+1}=\hat\beta_{n}+\frac{M_{n}^{−1}}{1 + x_n^TM_n^{-1}x_n} x_n(y_n - x_n^T\hat\beta_{n})$

Polyak averaging indicates you can use $\eta_n = n^{-\alpha}$ to approximate $\frac{M_{n}^{−1}}{1 + x_n^TM_n^{-1}x_n}$ with $\alpha$ ranges from $0.5$ to $1$. You may try in your case to select the best $\alpha$ for your recursion.

I think it also works if you apply a batch gradient algorithm:

$\hat\beta_{n+1}=\hat\beta_{n}+\frac{\eta_n}{n} \sum\limits_{i=0}^{n-1}x_i(y_i - x_i^T\hat\beta_{n})$

A point that no one has addressed so far is that it generally doesn't make sense to keep the regularization parameter $\lambda$ constant as data points are added. The reason for this is that $\| X \beta -y \|^{2}$ will typically grow linearly with the number of data points, while the regularization term $\| \lambda\beta \|^{2}$ won't.

Perhaps something like Stochastic gradient descent could work here. Compute $\hat{\beta}$ using your equation above on the initial dataset, that will be your starting estimate. For each new data point you can perform one step of gradient descent to update your parameter estimate.

In linear regression, one possibility is updating the QR decomposition of $X$ directly, as explained here. I guess that, unless you want to re-estimate $\lambda$ after each new datapoint has been added, something very similar can be done with ridge regression.

Here is an alternative (and less complex) approach compared to using the Woodbury formula. Note that $X^TX$ and $X^Ty$ can be written as sums. Since we are calculating things online and don't want the sum to blow up, we can alternatively use means ($X^TX/n$ and $X^Ty/n$).

If you write $X$ and $y$ as :

we can write the online updates to $X^TX/n$ and $X^Ty/n$ (calculated up to the $t$-th row) as:

Your online estimate of $\beta$ then becomes

Note that this also helps with the interpretation of $\lambda$ remaining constant as you add observations!

This procedure is how https://github.com/joshday/OnlineStats.jl computes online estimates of linear/ridge regression.