Algoritmo de mínimos cuadrados regularizado recursivo (en línea)

12

¿Alguien puede señalarme en la dirección de un algoritmo en línea (recursivo) para la regularización de Tikhonov (mínimos cuadrados regularizados)?

En una configuración fuera de línea, calcularía usando mi conjunto de datos original donde se encuentra usando la validación cruzada n-fold. Se puede predecir un nuevo valor de para una dada usando . $\hat\beta=(X^TX+λI)^{−1}X^TY$ $λ$ $y$ $x$ $y=x^T\hat\beta$

En un entorno en línea, dibujo continuamente nuevos puntos de datos. ¿Cómo puedo actualizar $\hat\beta$ cuando extraigo nuevas muestras de datos adicionales sin hacer un recálculo completo de todo el conjunto de datos (original + nuevo)?

regression machine-learning least-squares regularization online rnoodle
fuente

1

Sus mínimos cuadrados regularizados por Tikhonov se llaman más comúnmente Levenberg-Marquardt en círculos estadísticos, incluso cuando se aplican a problemas lineales puros (como aquí). Hay un artículo sobre Levenberg Marquardt en línea aquí . No sé si eso es de alguna ayuda.

Glen_b -Reinstala a Mónica el

11

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

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

$\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 con la fórmula de Woodbury , 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})$

El promedio de Polyak indica que puede usar para aproximar con rangos de a . En su caso, puede intentar seleccionar el mejor para su recursión. $\eta_n = n^{-\alpha}$ $\frac{M_{n}^{−1}}{1 + x_n^TM_n^{-1}x_n}$ $\alpha$ $0.5$ $1$ $\alpha$

Creo que también funciona si aplica un algoritmo de gradiente por lotes:

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

lennon310
fuente

¿Qué sucede si actualizo mi regresor cada vez con muestras de lotes de datos nuevos, donde cada lote sucesivo se extrae de una distribución ligeramente diferente? es decir, no IID. En este caso, me gustaría que el regresor tenga en cuenta los nuevos datos, pero que no afecte sus predicciones en la localidad de los datos antiguos (lotes anteriores). ¿Me puede indicar alguna literatura que pueda sentir útil?

rnoodle

Buena pregunta, pero lo siento, actualmente no puedo decir cuánto afectaría a su modelo si todavía está usando la fórmula de gradiente por lotes en la respuesta, o aproximando aplicando la forma de matriz directamente: eta ^ (- alpha) * X (Y-X 'beta_n) donde X, Y son sus nuevas muestras de lote

lennon310

hola, parece que el coeficiente de regularización no está involucrado en la fórmula de actualización recursiva? ¿O solo importa en la inicialización de la inversa de la matriz M?

Peng Zhao

4

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

Brian Borchers
fuente

Ese es un punto interesante. Pero, ¿por qué "no tiene sentido" exactamente? Mantener constante seguramente es matemáticamente válido, por lo que "no tiene sentido" debe entenderse en algún tipo de contexto estadístico. ¿Pero qué contexto? Que sale mal ¿Habría algún tipo de solución fácil, como reemplazar las sumas de cuadrados por cuadrados medios?

λ

$\lambda$

whuber

Reemplazar la suma de cuadrados con una versión escalada (por ejemplo, el error cuadrático medio) tendría sentido, pero el simple uso de mínimos cuadrados recursivos no logrará eso.

Brian Borchers

En cuanto a lo que saldría mal, dependiendo de su elección de , obtendría una solución muy poco regularizada con una gran cantidad de puntos de datos o una solución muy sobrerregulada con una pequeña cantidad de puntos de datos.

λ

$\lambda$

Brian Borchers

Uno sospecharía eso, pero si se sintoniza inicialmente después de recibir puntos de datos y luego se agregan más puntos de datos, si las soluciones resultantes con más puntos de datos y la misma están sobre o poco regularizadas dependerían de esos nuevos puntos de datos. Esto puede ser analizado por suponiendo que los puntos de datos actúan como una muestra iid de una distribución multivariada, en cuyo caso aparece se debe establecer en en la etapa . Esto cambiaría las fórmulas de actualización, pero de una manera tan regular y simple que aún podría ser posible un cálculo eficiente. (+1)

λ

$\lambda$

n

$n$

λ

$\lambda$

λ

$\lambda$

N / n

$N/n$

N

$N$

whuber

3

Quizás algo como el descenso de gradiente estocástico podría funcionar aquí. Calcule usando su ecuación anterior en el conjunto de datos inicial, esa será su estimación inicial. Para cada nuevo punto de datos, puede realizar un paso de descenso de gradiente para actualizar su estimación de parámetros. $\hat{\beta}$

Max S.
fuente

Desde entonces me di cuenta de que SGD (quizás minibatch) es el camino a seguir para problemas en línea como este, es decir, actualizar las aproximaciones de funciones.

rnoodle

1

En la regresión lineal, una posibilidad es actualizar la descomposición QR de directamente, como se explica aquí . Supongo que, a menos que desee volver a estimar después de agregar cada nuevo punto de datos, se puede hacer algo muy similar con la regresión de cresta. $X$ $\lambda$

Matteo Fasiolo
fuente

0

Aquí hay un enfoque alternativo (y menos complejo) en comparación con el uso de la fórmula de Woodbury. Tenga en cuenta que y se pueden escribir como sumas . Dado que estamos calculando cosas en línea y no queremos la suma para hacer estallar, podemos utilizar alternativamente medios ( y ). $X^TX$ $X^Ty$ $X^TX/n$ $X^Ty/n$

Si escribe e como: $X$ $y$

X = (\begin{matrix} x_{1}^{T} \\ ⋮ \\ x_{n}^{T} \end{matrix}), y = (\begin{matrix} y_{1} \\ ⋮ \\ y_{n} \end{matrix}),

$X = \begin{pmatrix} x_1^T \\ \vdots \\ x_n^T \end{pmatrix}, \quad y = \begin{pmatrix} y_1 \\ \vdots \\ y_n \end{pmatrix},$

podemos escribir las actualizaciones en línea a y (calculada hasta el fila -ésimo) como: $X^TX/n$ $X^Ty/n$ $t$

A_{t} = (1 - \frac{1}{t}) A_{t - 1} + \frac{1}{t} x_{t} x_{t}^{T},

$A_t = \left(1 - \frac{1}{t}\right) A_{t-1} + \frac{1}{t}x_t x_t^T,$

b_{t} = (1 - \frac{1}{t}) b_{t - 1} + \frac{1}{t} x_{t} y_{t} .

$b_t = \left(1 - \frac{1}{t}\right) b_{t-1} + \frac{1}{t}x_t y_t.$

Su estimación en línea de se convierte en $\beta$

{\hat{β}}_{t} = (A_{t} + λ I)^{- 1} b_{t} .

$\hat\beta_t = (A_t + \lambda I)^{-1}b_t.$

Tenga en cuenta que esto también ayuda a que la interpretación de permanezca constante a medida que agrega observaciones. $\lambda$

Este procedimiento es cómo https://github.com/joshday/OnlineStats.jl calcula estimaciones en línea de regresión lineal / cresta.

joshday
fuente

Algoritmo de mínimos cuadrados regularizado recursivo (en línea)

Respuestas: