Algorithme récursif (en ligne) des moindres carrés régularisés

Quelqu'un peut-il m'orienter vers un algorithme en ligne (récursif) pour la régularisation de Tikhonov (moindres carrés régularisés)?

Dans un cadre hors ligne, je calculerais $\hat\beta=(X^TX+λI)^{−1}X^TY$ utilisant mon ensemble de données d'origine où $λ$ est trouvé en utilisant la validation croisée n fois. Une nouvelle valeur $y$ peut être prédite pour un x donné en $x$utilisant $y=x^T\hat\beta$ .

Dans un environnement en ligne, je dessine continuellement de nouveaux points de données. Comment puis-je mettre à jour $\hat\beta$ lorsque je dessine de nouveaux échantillons de données supplémentaires sans faire un recalcul complet sur l'ensemble des données (original + nouveau)?

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

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

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

$M_{n+1} - M_n = x_nx_n^T$ , nous pouvons obtenir

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

Selon la formule de Woodbury , nous avons

$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)}$

Par conséquent,

$\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})$

La moyenne de Polyak indique que vous pouvez utiliser pour approximer avec plages de au . Vous pouvez essayer dans votre cas de sélectionner le meilleur pour votre récursivité.M - 1 $\eta_n = n^{-\alpha}$α0,51$\frac{M_{n}^{−1}}{1 + x_n^TM_n^{-1}x_n}$$\alpha$$0.5$$1$$\alpha$

Je pense que cela fonctionne aussi si vous appliquez un algorithme de gradient par lots:

$\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})$

Un point que personne n'a abordé jusqu'à présent est qu'il n'est généralement pas logique de maintenir le paramètre de régularisation constant lorsque des points de données sont ajoutés. La raison en est que augmentera généralement linéairement avec le nombre de points de données, tandis que le terme de régularisation ne le fera pas. ‖ X β - y ‖ 2 ‖ λ $\lambda$$\| X \beta -y \|^{2}$$\| \lambda\beta \|^{2}$

Peut-être que quelque chose comme la descente du gradient stochastique pourrait fonctionner ici. Calculez utilisant votre équation ci-dessus sur le jeu de données initial, qui sera votre estimation de départ. Pour chaque nouveau point de données, vous pouvez effectuer une étape de descente de gradient pour mettre à jour votre estimation de paramètre.$\hat{\beta}$

En régression linéaire, une possibilité consiste à mettre à jour directement la décomposition QR de , comme expliqué ici . Je suppose que, sauf si vous souhaitez réestimer après chaque nouveau point de données a été ajouté, quelque chose de très similaire peut être fait avec la régression de crête.$X$$\lambda$

Voici une approche alternative (et moins complexe) par rapport à l'utilisation de la formule de Woodbury. Notez que et peuvent être écrits comme des sommes . Puisque nous calculons des choses en ligne et que nous ne voulons pas que la somme explose, nous pouvons également utiliser des moyens ( et ).$X^TX$$X^Ty$$X^TX/n$$X^Ty/n$

Si vous écrivez et comme:$X$$y$

nous pouvons écrire les mises à jour en ligne à et (à la valeur calculée en de -ième rangée) comme:$X^TX/n$$X^Ty/n$$t$

Votre estimation en ligne de devient alors$\beta$

Notez que cela aide également à l'interprétation de restant constant lorsque vous ajoutez des observations!$\lambda$

Cette procédure est la façon dont https://github.com/joshday/OnlineStats.jl calcule les estimations en ligne de la régression linéaire / crête.