Recursiva (en línea) regularizado menos algoritmo de cuadrados

Question

Puede alguien me apunte en la dirección de una línea (recursivo) algoritmo para la Regularización de Tikhonov (regularización de los mínimos cuadrados)?

En una configuración sin conexión, me gustaría calcular el $\hat\beta=(X^TX+λI)^{−1}X^TY$ usando mi conjunto de datos original donde $λ$ se encuentra utilizando n-fold cross validation. Un nuevo $y$ valor puede ser predicho para un determinado$x$$y=x^T\hat\beta$.

En un entorno en línea puedo llamar continuamente nuevos puntos de datos. ¿Cómo puedo actualizar a $\hat\beta$ cuando me dibujar nuevas muestras de datos sin tener que hacer una actualización completa en el conjunto de datos completo (original + nuevo)?

Answer 1

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

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

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

$M_{n+1} - M_n = x_nx_n^T$, podemos obtener

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

De acuerdo a Woodbury fórmula, tenemos

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

Como resultado,

$\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 promedio indica que puede usar $\eta_n = n^{-\alpha}$ para aproximar $\frac{M_{n}^{−1}}{1 + x_n^TM_n^{-1}x_n}$ $\alpha$ rangos de$0.5$$1$. Usted puede intentar en su caso, para seleccionar la mejor $\alpha$ por su recursividad.

---

Creo que también funciona si se aplica un lote algoritmo de gradiente:

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

Answer 2

Un punto que nadie ha abordado hasta ahora es que generalmente no tiene sentido mantener la regularización parámetro $\lambda$ constante como datos se agregan puntos. La razón de esto es que el $\| X \beta -y \|^{2}$ típicamente crecerá linealmente con el número de puntos de datos, mientras que el término regularización del $\| \lambda\beta \|^{2}$ no.

Answer 3

Quizás algo así como descenso de gradiente estocástico podría trabajar aquí. Calcular el $\hat{\beta}$ usando la ecuación arriba sobre el conjunto de datos inicial, que será su estimación inicial. Para cada nuevo punto de datos se puede realizar a un paso de gradiente pendiente para actualizar su estimación del parámetro.

Answer 4

En regresión lineal, una posibilidad es la actualización de la descomposición de QR de $X$ directamente, como explicado aquí. Supongo que, a menos que desee volver a calcular $\lambda$ después de añadir cada nuevo punto de datos, algo muy similar puede hacerse con regresión ridge.